国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

高速鐵路區(qū)間能力全失效條件下列車運(yùn)行實(shí)時(shí)調(diào)整研究

2015-05-10 10:29占曙光彭其淵徐培娟張馨竹
鐵道學(xué)報(bào) 2015年11期
關(guān)鍵詞:運(yùn)行圖列車運(yùn)行高速鐵路

占曙光, 趙 軍, 彭其淵, 徐培娟, 張馨竹

(西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院,四川 成都 610031)

高速鐵路列車運(yùn)行安全和非正常情況下列車運(yùn)行實(shí)時(shí)調(diào)整(下文簡稱“調(diào)整”)是鐵路調(diào)度指揮關(guān)注的重點(diǎn)問題。由于高速鐵路速度高、密度大,任何干擾因素都有可能擾亂列車正常運(yùn)行,導(dǎo)致運(yùn)行秩序紊亂,甚至出現(xiàn)運(yùn)行事故。對(duì)高速鐵路列車運(yùn)行產(chǎn)生干擾的因素有很多,主要包括不良天氣、人為失誤以及線路、通信信號(hào)、動(dòng)車組故障等。高速鐵路對(duì)這些干擾具有很強(qiáng)的脆弱性,極易造成列車偏離原定的運(yùn)行計(jì)劃。因此,對(duì)干擾條件下的調(diào)整進(jìn)行研究具有非常重要的現(xiàn)實(shí)意義。

根據(jù)對(duì)列車運(yùn)行的影響程度,高速鐵路干擾因素主要可分為影響程度相對(duì)較小的干擾和影響程度相對(duì)較大的干擾。目前,在學(xué)術(shù)界,2種類型的干擾沒有明確的界定,大部分學(xué)者認(rèn)為:小干擾往往來源于列車在站時(shí)的到發(fā)晚點(diǎn),此時(shí)不需要對(duì)列車運(yùn)行進(jìn)行較大調(diào)整,也不需對(duì)動(dòng)車組、乘務(wù)組等資源的任務(wù)重新進(jìn)行調(diào)整,僅需利用運(yùn)行圖的冗余時(shí)間對(duì)列車到發(fā)時(shí)刻進(jìn)行微調(diào)便可使列車恢復(fù)正常運(yùn)行;大干擾往往來源于鐵路基礎(chǔ)設(shè)施由于故障在相對(duì)較長的時(shí)間內(nèi)不能正常使用,從而導(dǎo)致列車大面積晚點(diǎn),此時(shí)為恢復(fù)列車正常運(yùn)行,不僅需要大規(guī)模調(diào)整運(yùn)行圖,也需要同時(shí)調(diào)整動(dòng)車組和乘務(wù)組等資源的任務(wù)。

本文研究高速鐵路區(qū)間能力全失效時(shí)的調(diào)整問題,區(qū)間能力全失效指由于故障干擾導(dǎo)致某區(qū)間上下行2條正線同時(shí)中斷,該問題屬于大干擾條件下的調(diào)整問題。當(dāng)區(qū)間能力全失效時(shí),調(diào)度員需分別對(duì)運(yùn)行圖、動(dòng)車組和乘務(wù)組進(jìn)行調(diào)整。3項(xiàng)調(diào)整任務(wù)彼此相互影響,理想化的解決方案為將3項(xiàng)調(diào)整任務(wù)集成優(yōu)化,但將使整個(gè)問題變得非常復(fù)雜。比較可行的解決方案是將整個(gè)問題分解為運(yùn)行圖調(diào)整、動(dòng)車組調(diào)整和乘務(wù)組調(diào)整3個(gè)子問題,進(jìn)而依次求解,盡管該方案只能獲得近似解,但更適用于實(shí)時(shí)調(diào)整環(huán)境。本研究側(cè)重于運(yùn)行圖實(shí)時(shí)調(diào)整,當(dāng)干擾導(dǎo)致區(qū)間能力全失效時(shí),調(diào)度員優(yōu)先安排接近中斷區(qū)間的列車在適當(dāng)車站停車等待干擾結(jié)束。若干擾造成的列車晚點(diǎn)情況非常嚴(yán)重,調(diào)度員可選擇取消部分列車運(yùn)行。當(dāng)干擾結(jié)束后,調(diào)度員需慎重安排停站列車的出發(fā)順序和時(shí)刻,以最大程度地減小干擾對(duì)列車運(yùn)行的影響。

當(dāng)前,國外學(xué)者對(duì)調(diào)整問題開展較系統(tǒng)地研究,較為全面的綜述見文獻(xiàn)[1];文獻(xiàn)[2-6]研究小干擾條件下的調(diào)整,將該問題視為無等待的作業(yè)車間調(diào)度問題,提出基于比選圖的優(yōu)化模型和算法;文獻(xiàn)[7-10]探討另一類小干擾條件下的調(diào)整,稱為晚點(diǎn)管理問題,判斷在接續(xù)車站前行列車是否等待后續(xù)晚點(diǎn)列車,對(duì)不同約束下的問題建模,設(shè)計(jì)有效的求解算法。最近,文獻(xiàn)[11-12]研究大干擾條件下的調(diào)整,文獻(xiàn)[11]對(duì)區(qū)間在全部封鎖和部分封鎖情況下的干擾時(shí)段的調(diào)整,分別構(gòu)建整數(shù)規(guī)劃模型,模型由商業(yè)優(yōu)化軟件CPLEX直接求解;在文獻(xiàn)[11]的基礎(chǔ)上,文獻(xiàn)[12]提出更一般化的區(qū)間能力失效情況下的調(diào)整模型。國內(nèi)對(duì)此研究相對(duì)較少,文獻(xiàn)[13-14]研究單線鐵路在區(qū)間能力失效條件下的調(diào)整,針對(duì)線路失效持續(xù)時(shí)間的不確定性,文獻(xiàn)[13]構(gòu)建兩階段帶補(bǔ)償隨機(jī)期望模型,基于多階段遞歸決策概念模型,提出不完全連續(xù)多階段決策模型,并開發(fā)分支定界算法對(duì)所提出的模型進(jìn)行求解;文獻(xiàn)[14]提出基于場景的滾動(dòng)時(shí)域算法,進(jìn)一步采用多層分支求解策略對(duì)問題求解;基于文獻(xiàn)[13-14]的研究,考慮干擾持續(xù)時(shí)間的不確定性,文獻(xiàn)[15-16]分別對(duì)雙線鐵路和雙線鐵路網(wǎng)絡(luò)在干擾條件下的調(diào)整進(jìn)行研究,提出基于模糊數(shù)學(xué)的優(yōu)化模型和求解算法。

綜上,只有文獻(xiàn)[11-12]探討大干擾條件下的調(diào)整問題,研究對(duì)象為荷蘭鐵路,采用1 h或0.5 h周期運(yùn)行圖,且列車速度等級(jí)較為單一。然而,我國已經(jīng)投入運(yùn)營的高速鐵路(例如京滬、京廣高鐵)采用非周期運(yùn)行圖(或可視為以24 h為周期的運(yùn)行圖),并存在2種速度等級(jí)列車共線運(yùn)行。相比國外,我國高速鐵路運(yùn)行圖規(guī)模更大、運(yùn)營模式更為復(fù)雜,但至今鮮見文獻(xiàn)探討符合國情的嚴(yán)重干擾時(shí)列車運(yùn)行實(shí)時(shí)調(diào)整問題。鑒于此,作者在文獻(xiàn)[11-12]基礎(chǔ)上,根據(jù)我國實(shí)際情況,研究區(qū)間能力全失效條件下的調(diào)整問題。首先,借助于事件-活動(dòng)網(wǎng)絡(luò)概念,構(gòu)建大規(guī)?;旌险麛?shù)線性規(guī)劃模型;其次,根據(jù)問題特點(diǎn),開發(fā)有效的兩階段求解算法;最后,結(jié)合中國高速鐵路實(shí)際,構(gòu)造算例驗(yàn)證所提方法的效果和效率。

1 問題描述與界定

1.1 問題描述

以由4個(gè)車站、3個(gè)區(qū)間、4列列車運(yùn)行的高速鐵路為例,對(duì)問題的描述見圖1。已知上行方向有4列高速列車運(yùn)行。其中G1、G3時(shí)速為300 km,D2、D4時(shí)速為250 km。(圖1僅為示意圖,省略部分列車在中間站的停車過程)在時(shí)刻t1,因某種故障干擾,導(dǎo)致區(qū)間3的2條正線完全中斷,4列列車不能按圖定要求繼續(xù)運(yùn)行。為保證干擾情況下列車運(yùn)行的安全,4列列車均應(yīng)在進(jìn)入中斷區(qū)間之前停車。由于車站能力限制,每個(gè)車站容納的停車待避列車數(shù)量不能超過其能力。假設(shè)車站2和車站3分別只有2條可使用的股道,調(diào)度員需決策如何安排G1、D2、G3、D4列車在車站2和車站3的停站方案,既保證安全又使列車晚點(diǎn)最少。假設(shè)在時(shí)刻t2干擾結(jié)束,調(diào)度員還需決策4列列車的出發(fā)順序和時(shí)刻,將干擾的影響降至最小。此外,由于列車G3和D4在干擾發(fā)生時(shí)還沒有從始發(fā)站出發(fā),調(diào)度員可根據(jù)現(xiàn)場情況并結(jié)合實(shí)時(shí)信息,綜合判斷是否需要采取停運(yùn)措施。研究重點(diǎn)在于通過構(gòu)建優(yōu)化模型,在保證各類列車運(yùn)行約束的前提下,對(duì)上文提出的問題進(jìn)行優(yōu)化,提供實(shí)時(shí)的列車運(yùn)行調(diào)整策略,以協(xié)助調(diào)度員的調(diào)度決策。

1.2 問題界定

區(qū)間能力全失效情況下調(diào)整是非常復(fù)雜的決策問題,調(diào)度員進(jìn)行調(diào)整工作時(shí)需考慮許多因素,包括干擾影響范圍、持續(xù)時(shí)間、干擾類型、當(dāng)前列車運(yùn)行狀態(tài)、干擾處理方式以及動(dòng)車組周轉(zhuǎn)情況等。為研究方便,作以下假設(shè):

假設(shè)1 各車站到發(fā)線分上下行分別使用,各到發(fā)線與同方向正線相連,且配有供旅客乘降的站臺(tái);

假設(shè)2 動(dòng)車組數(shù)量足夠,不考慮動(dòng)車組數(shù)量限制和運(yùn)用優(yōu)化的問題;

假設(shè)3 進(jìn)入中斷區(qū)間的列車已經(jīng)通過故障地點(diǎn),可繼續(xù)向前運(yùn)行;

假設(shè)4 干擾發(fā)生前列車按運(yùn)行圖正常行駛,干擾發(fā)生后受影響的列車停留在有剩余能力的車站,不安排在區(qū)間停留。

2 模型構(gòu)建

2.1 問題抽象

為建模方便,從宏觀層面上把高速鐵路列車運(yùn)行描述為由事件和活動(dòng)構(gòu)成的網(wǎng)絡(luò)。事件表示列車發(fā)出或到達(dá)車站;活動(dòng)連接2個(gè)相鄰事件,可進(jìn)一步分為列車活動(dòng)和間隔活動(dòng)。

(1) 列車活動(dòng)

既可視為區(qū)間運(yùn)行活動(dòng),表示列車在相同區(qū)間2個(gè)關(guān)聯(lián)車站的出發(fā)事件與到達(dá)事件之間的活動(dòng);也可視為車站停站活動(dòng),表示列車在相同車站到達(dá)事件與出發(fā)事件之間的活動(dòng)。

(2) 間隔活動(dòng)

既可視為2列車在相同區(qū)間的運(yùn)行間隔活動(dòng),包括在某區(qū)間一端車站的出發(fā)間隔活動(dòng)和在另一端車站的到達(dá)間隔活動(dòng);也可視為2列車在相同車站的發(fā)到間隔活動(dòng)。

目前,我國高速鐵路普遍采用2種速度等級(jí)列車共線運(yùn)行模式,即同線路上運(yùn)行著時(shí)速300 km的高速列車(定義為Ⅰ類列車)和時(shí)速200 km ~ 250 km的中速列車(定義為Ⅱ類列車)。下面結(jié)合該運(yùn)輸組織模式進(jìn)行研究。

2.2 目標(biāo)函數(shù)及基本模型

由既有文獻(xiàn)可看出,高速鐵路區(qū)間能力全失效條件下的調(diào)整為復(fù)雜的組合優(yōu)化問題。為最大程度地減小干擾對(duì)列車運(yùn)行的影響,以總加權(quán)求和列車取消懲罰值和列車晚點(diǎn)懲罰值最小為目標(biāo)函數(shù)。不考慮運(yùn)營安全和設(shè)備能力約束的基本模型為

( 1 )

s. t.M1yte≤xe-qe≤M1?e∈E1

( 2 )

M1yte≤xe-qe≤M1?e∈E2

( 3 )

yt∈{0,1} ?t∈T

( 4 )

xe∈N?e∈E

( 5 )

( 6 )

式中:T1、T2分別為Ⅰ、Ⅱ類列車集合;T為所有列車集合;t為列車索引;λt為列車t取消的懲罰系數(shù);E1、E2分別為Ⅰ、Ⅱ類列車相關(guān)事件集合;E為所有事件集合;e為事件索引;μe為事件e單位晚點(diǎn)懲罰系數(shù);yt為0-1變量,定義見式( 6 );xe、qe分別為事件e在調(diào)整后的運(yùn)行圖以及原始運(yùn)行圖中的發(fā)生時(shí)刻;te為事件e對(duì)應(yīng)的列車;M1為充分大正數(shù),取M1=1 440;N為自然數(shù)。約束(2)和約束(3)表示列車在車站實(shí)際的到發(fā)時(shí)刻不能早于圖定的到發(fā)時(shí)刻。此外,該組約束將取消的列車移動(dòng)到研究的時(shí)間范圍之后,即被取消列車對(duì)應(yīng)事件e的實(shí)際發(fā)生時(shí)刻xe=qe+M1,若取M1=1 440。因?yàn)楦咚勹F路的運(yùn)營時(shí)間最大不超過M1,意味著將被取消的列車移動(dòng)到運(yùn)營時(shí)間結(jié)束之后。通過把取消列車移動(dòng)到最后,可有效避免該類列車相互間及與其他未被取消列車之間的影響;約束(4)和約束(5)表示變量的取值范圍。

2.3 約束條件

為確保高速鐵路行車安全,列車在高速鐵路上運(yùn)行還需滿足多種運(yùn)營安全和設(shè)備能力約束,包括單列列車運(yùn)行約束、相鄰列車間隔約束、車站能力約束、取消列車約束、列車區(qū)間最長運(yùn)行時(shí)間約束及列車發(fā)車時(shí)刻約束等。

(1) 單列列車運(yùn)行約束

正常情況下,列車按照原定運(yùn)行圖運(yùn)行。發(fā)生干擾后,雖受到干擾的影響,但各列車從始發(fā)站到終到站經(jīng)過的所有事件e和活動(dòng)a的順序固定不變,需滿足區(qū)間的運(yùn)行時(shí)間約束和在站停站時(shí)間約束,即

xf-xe≥La?a=(e,f)∈Atrain

( 7 )

式中:e、f分別為某列車先后占用相同資源(區(qū)間或車站資源)的2個(gè)相鄰事件;Atrain為列車活動(dòng)集合;a為活動(dòng)索引,a=(e,f)∈Atrain既可為列車在區(qū)間的運(yùn)行活動(dòng),也可為列車在車站的停站活動(dòng);La為活動(dòng)a的最短持續(xù)時(shí)間,當(dāng)a為區(qū)間運(yùn)行活動(dòng)時(shí),La為列車在區(qū)間的最小運(yùn)行時(shí)間;當(dāng)a為車站停站活動(dòng)時(shí),La為列車在車站的最小停站時(shí)間。

(2) 相鄰列車間隔約束

為避免列車發(fā)生沖突,相鄰列車在區(qū)間運(yùn)行或在站發(fā)到均需滿足間隔約束。本節(jié)僅建立區(qū)間運(yùn)行間隔約束模型,在站到發(fā)間隔約束放在車站能力約束部分。另外,發(fā)生干擾時(shí),不論同等級(jí)或不同等級(jí)列車均可能在車站發(fā)生越行。因此,2列車在站的到發(fā)順序可能產(chǎn)生變化,定義表示事件發(fā)生先后順序的0-1變量λef,即

( 8 )

列車區(qū)間運(yùn)行間隔約束為

xf-xe+M2(1-λef)≥La

( 9 )

(10)

我國高速鐵路為雙線單向鐵路,同方向運(yùn)行的列車只能在車站而不能在區(qū)間越行。為避免同方向的2列車在區(qū)間越行,約束條件為

te=te′tf=tf′(si,si+1)∈Seg

(11)

(3) 車站能力約束

列車到達(dá)或者通過車站必須占用車站線路,相同線路在同一時(shí)間僅允許1列車占用,而各站線路數(shù)量有限,所以列車運(yùn)行必須滿足車站線路能力的限制。鑒于始發(fā)站s1和終到站sn為較大車站,能力充足,在此僅考慮中間站能力約束。定義Sm為中間站集合,si∈Sm,si≠s1,si≠sn。為滿足車站能力約束,每個(gè)中間站需為每列車分配1條站線,即當(dāng)列車到達(dá)時(shí)至少應(yīng)有1條空閑線路供其使用。因此,當(dāng)某列車到達(dá)某車站時(shí),可先統(tǒng)計(jì)已經(jīng)到達(dá)和發(fā)出的列車總數(shù),兩者之差獲取此時(shí)停留在該站的列車數(shù),進(jìn)而用車站線路數(shù)減去停留的列車數(shù)便可獲得空閑的線路數(shù)。

φa=

(12)

(13)

xf-xe+M2(1-φa)≥La

(14)

(4) 干擾發(fā)生后列車取消約束

當(dāng)干擾導(dǎo)致某區(qū)間能力全失效時(shí),該區(qū)間完全中斷,通行能力為0,導(dǎo)致整條線路列車運(yùn)行受到嚴(yán)重影響。如前所述,若干擾造成列車大面積晚點(diǎn),調(diào)度員針對(duì)不同列車將采用不同的停運(yùn)調(diào)整策略。對(duì)發(fā)生干擾時(shí)已經(jīng)在線路上載客運(yùn)行的列車,由于取消該部分列車存在諸多困難,例如清客、退票、賠償?shù)?,通常采取的措施為合理調(diào)度列車在適當(dāng)?shù)能囌就\嚨却蓴_恢復(fù)。然而,對(duì)于干擾發(fā)生時(shí)還未從始發(fā)站出發(fā)的列車,調(diào)度員可根據(jù)現(xiàn)場情況、干擾信息、以及客票發(fā)售情況等,綜合決策是否停運(yùn),以盡量減小干擾對(duì)整條線路造成的影響。鑒于此,取消列車約束為

(15)

(16)

式中:tdep為列車t在始發(fā)站的出發(fā)時(shí)刻。

式(15)和式(16)表示只有始發(fā)時(shí)刻晚于干擾發(fā)生時(shí)刻的列車才能考慮取消運(yùn)行。

(5) 干擾發(fā)生后列車區(qū)間最長運(yùn)行時(shí)間約束

由假設(shè)4,干擾發(fā)生后還未進(jìn)入中斷區(qū)間的列車需依次停在合適的車站,而目前創(chuàng)建的約束可能導(dǎo)致調(diào)整方案中部分列車在區(qū)間過度緩行甚至停車。為避免這種情況,提出列車區(qū)間最長運(yùn)行時(shí)間約束,即

?a=(e,f)∈ArunArun?Atrain

(17)

(6) 干擾發(fā)生后列車發(fā)車時(shí)刻約束

(18)

(7) 有效不等式約束

顯然,若某列車從某站出發(fā),另一列車尚未到達(dá)該站,同樣該列車到達(dá)該站時(shí)也必定在另一列車到達(dá)該站之前。雖然此約束已隱含在前文的約束中,但是加上該約束后更有利于加快模型的求解速度。有效不等式為

(19)

式中:e′為列車te在車站s的出發(fā)事件;a′為活動(dòng)索引。式(19)表示若列車te在列車tf到達(dá)s站之前從s站出發(fā),則列車te也一定在列車tf之前到達(dá)s站。

2.4 模型合理性說明

約定干擾發(fā)生后,未進(jìn)入中斷區(qū)間的列車只能依次停留在適當(dāng)?shù)能囌?。由于我國高速鐵路在相同線路上同時(shí)開行2種速度等級(jí)的列車,Ⅰ類列車的優(yōu)先級(jí)高于Ⅱ類列車,當(dāng)干擾發(fā)生后,應(yīng)如何制定列車停站方案,以便既能充分體現(xiàn)不同等級(jí)列車的優(yōu)先級(jí),又能有效避免獲得不合理的列車運(yùn)行調(diào)整方案。本節(jié)通過對(duì)Ⅰ、Ⅱ類列車賦予不同的取消懲罰系數(shù)λt和晚點(diǎn)懲罰系數(shù)μe,再基于車站能力約束3、干擾發(fā)生后列車區(qū)間最長運(yùn)行時(shí)間約束5、以及干擾發(fā)生后列車發(fā)車時(shí)刻約束6建立模型,可完全自動(dòng)確定干擾發(fā)生后基于優(yōu)先級(jí)的列車停站方案,且避免產(chǎn)生不合理的列車運(yùn)行調(diào)整方案,案例見圖2。

圖2中,已知車站s3和s4上行方向各有2條股道可使用,干擾發(fā)生在s4與s5之間的區(qū)間,此時(shí)有4列Ⅰ類列車和1列Ⅱ類列車正在運(yùn)行,車次分別為G1、G3、G4、G5和D2。干擾發(fā)生時(shí),對(duì)于列車D2和G3,盡管列車D2早于列車G3進(jìn)入?yún)^(qū)間(s2,s3),但由于Ⅰ類列車優(yōu)先級(jí)高于Ⅱ類列車,列車D2可能將提前在s3站停車等待,讓G3先行。當(dāng)然,對(duì)于列車D2和G3,誰在s3站等待,誰繼續(xù)向前運(yùn)行,模型根據(jù)列車懲罰系數(shù)自動(dòng)確定。對(duì)于列車G1、G3和G4,由于車站s4只有2條股道可使用,受車站能力約束限制,列車G4只能等待列車G1或者G3從車站s4出發(fā)之后才能進(jìn)入該站。從理論上看,列車G4可提前在時(shí)刻t1從車站s3出發(fā),然后通過區(qū)間(s3,s4)緩慢運(yùn)行進(jìn)入車站s4。但是,鑒于干擾持續(xù)時(shí)間的不確定性,此種調(diào)整策略不具有運(yùn)營可行性。由于列車G4在區(qū)間(s3,s4)需滿足最長運(yùn)行時(shí)間約束,因而只能在車站s3停車等待,直到時(shí)刻t2才能出發(fā)。同理,列車G5也只能在車站s2等待,直到車站s3有列車出發(fā)釋放線路能力之后,才能在時(shí)刻t3從車站s2出發(fā)。

當(dāng)調(diào)度員在實(shí)際工作中面臨區(qū)間能力全失效時(shí),通常的做法為:干擾發(fā)生時(shí),已始發(fā)的列車根據(jù)當(dāng)時(shí)所處的位置依次就近在有能力的車站停車等待,未始發(fā)的列車推遲出發(fā);干擾結(jié)束時(shí),各站的列車按照?qǐng)D定順序依次發(fā)出。為便于比較,將現(xiàn)場調(diào)度員采用的策略稱為基于順序的調(diào)整方案,而將本文提出的調(diào)整策略稱為基于優(yōu)先級(jí)的調(diào)整策略。

3 算法設(shè)計(jì)

2.2和2.3小節(jié)建立的模型屬于混合整數(shù)線性規(guī)劃模型(MILP)的范疇,計(jì)算復(fù)雜度屬于NP-hard問題,針對(duì)大規(guī)模問題很難求得最優(yōu)解。實(shí)際工作中,高速鐵路的列車運(yùn)行調(diào)整過程分階段進(jìn)行,此外,由于干擾持續(xù)時(shí)間的不確定性,調(diào)度員需根據(jù)現(xiàn)場反饋的最新信息動(dòng)態(tài)地對(duì)列車運(yùn)行進(jìn)行調(diào)整。因此,提出兩階段算法,對(duì)整個(gè)問題進(jìn)行分解,可快速求解大規(guī)模實(shí)際問題,實(shí)時(shí)給出列車運(yùn)行調(diào)整方案。

車站能力約束是調(diào)整問題求解的難點(diǎn)所在,而且該問題在干擾結(jié)束前后的時(shí)間段內(nèi)表現(xiàn)尤為突出。因此,將原問題分解為2個(gè)階段:第1階段忽略干擾結(jié)束后時(shí)段車站能力約束,對(duì)原問題優(yōu)化,雖然獲得的解從整體上看可能不可行(干擾結(jié)束之后時(shí)段的調(diào)整方案不一定可行),但是可獲得整個(gè)干擾結(jié)束之前時(shí)段可行的調(diào)整方案;第2階段固定第1階段獲得的干擾結(jié)束之前時(shí)段的調(diào)整方案,并完整考慮干擾結(jié)束之后時(shí)段的車站能力約束,對(duì)原問題重新進(jìn)行優(yōu)化,進(jìn)而得到整個(gè)問題可行的調(diào)整方案,具體求解步驟為

Step1僅對(duì)干擾結(jié)束時(shí)刻之前時(shí)段施加車站能力約束,在干擾結(jié)束之后時(shí)段,假設(shè)車站能力不受限制(即去掉車站能力約束(13)、約束(14)),對(duì)原問題求解,獲得調(diào)整后的運(yùn)行圖φ1。在干擾結(jié)束之前時(shí)段,列車按照φ1運(yùn)行;

Step2在第1階段獲得的調(diào)整圖φ1基礎(chǔ)上,考慮干擾結(jié)束之后時(shí)段的車站能力約束(即加上車站能力約束(13)、約束(14)),固定第1階段獲得的調(diào)整圖φ1中干擾結(jié)束之前的部分,重新對(duì)原問題進(jìn)行求解,獲得全時(shí)段可行的調(diào)整圖φ2,最終獲得全天可行的調(diào)整圖。

分析兩階段算法的性質(zhì)可看出:第1階段省略干擾結(jié)束之后時(shí)段車站能力約束,可有效降低問題的規(guī)模和求解難度;第2階段固定第1階段獲得的結(jié)果,即干擾結(jié)束之前部分,相比于原問題,該階段的求解難度也得到明顯緩解。由于車站能力緊張主要集中在干擾結(jié)束前后較小的時(shí)段,兩階段法對(duì)調(diào)整結(jié)果的影響主要也集中在該時(shí)段。具體而言,因?yàn)樵诘?階段固定第1階段在該時(shí)段的調(diào)整結(jié)果,有可能導(dǎo)致整體調(diào)整結(jié)果質(zhì)量下降。由于影響時(shí)段不會(huì)太長,可預(yù)計(jì)兩階段法能在一定程度上保證整個(gè)問題的求解質(zhì)量。

與整體優(yōu)化相比,兩階段算法屬于啟發(fā)式算法范疇,并不能保證獲得問題的全局最優(yōu)解。但當(dāng)高速鐵路受到嚴(yán)重干擾時(shí),快速提供近似最優(yōu)調(diào)整圖比漫長等待最優(yōu)調(diào)整圖更重要。因此,對(duì)于大規(guī)模調(diào)整問題,兩階段算法具有較好的可行性和實(shí)用性。

4 算例分析

4.1 算例描述及參數(shù)設(shè)置

以京滬高速鐵路為例,利用2013年調(diào)整后的列車運(yùn)行圖相關(guān)數(shù)據(jù)進(jìn)行算例分析。京滬高速鐵路由北京南站至上海虹橋站,途經(jīng)23個(gè)車站(不包括天津西站),全線分為22個(gè)區(qū)間。當(dāng)區(qū)間能力全失效時(shí),上下行的列車運(yùn)行調(diào)整問題大致相同。因此,僅對(duì)上行列車進(jìn)行算例分析,選擇從上海虹橋站至北京南站的42列列車(包括從杭州等地經(jīng)過上海虹橋到達(dá)北京南站的跨線列車)。其中,時(shí)速300 km的Ⅰ類列車共40列,時(shí)速250 km的Ⅱ類列車共2列,對(duì)模型進(jìn)行驗(yàn)證。

本文基于已知干擾持續(xù)時(shí)間,通過調(diào)整干擾發(fā)生時(shí)刻和地點(diǎn),設(shè)計(jì)3種測試場景,每種場景通過變化干擾持續(xù)時(shí)間分別設(shè)置3種干擾情景,算例具體設(shè)置為

場景1

09:00蘇州北站-無錫東站之間出現(xiàn)列車運(yùn)行干擾,導(dǎo)致區(qū)間通行能力全部喪失,通過調(diào)整干擾持續(xù)時(shí)間,設(shè)置3種干擾情景,干擾持續(xù)時(shí)間分別為30 min、45 min及60 min;

場景2

12:00宿州東站-徐州東站之間出現(xiàn)列車運(yùn)行干擾,導(dǎo)致區(qū)間通行能力全部喪失30 min、45 min及60 min;

場景3

16:00濟(jì)南西站-德州東站之間出現(xiàn)列車運(yùn)行干擾,導(dǎo)致區(qū)間通行能力全部喪失30 min、45 min及60 min。

為便于表示不同場景下的干擾情景,定義三元組(a,b,c)。其中,a為干擾發(fā)生時(shí)刻,b為干擾所在區(qū)間,c為干擾持續(xù)時(shí)間。3種測試場景下9種干擾情景見表1。

表1 干擾情景的三元組表示

算例中,列車區(qū)間運(yùn)行時(shí)間和停站時(shí)間由原始列車運(yùn)行圖給出,列車區(qū)間運(yùn)行時(shí)間取“京滬高鐵區(qū)間運(yùn)行時(shí)間標(biāo)準(zhǔn)”相應(yīng)數(shù)值。其中,區(qū)間最小運(yùn)行時(shí)間取區(qū)間純運(yùn)行時(shí)間,區(qū)間最大運(yùn)行時(shí)間取區(qū)間純運(yùn)行時(shí)間加上Ⅰ類列車起停附加時(shí)間5 min,列車在站最小停站時(shí)間取為原始運(yùn)行圖上的停站時(shí)間。中間站可使用的到發(fā)線數(shù)量參照“京滬高速鐵路動(dòng)車組停車站到發(fā)線安排”取值,見表2。由于算例僅考慮42列長途列車,該部分列車的數(shù)量僅占實(shí)際全部開行列車的一半。因此,中間站能力僅取實(shí)際能力的0.5。減小車站能力時(shí),充分保證原始運(yùn)行圖的可行性,即如果根據(jù)原始運(yùn)行圖在某站存在列車越行,那么該站必須保證最少有2條線路可使用。表2中,股道數(shù)所在列括號(hào)內(nèi)的第1個(gè)數(shù)值表示上行方向列車實(shí)際可使用的股道數(shù)量,第2個(gè)值表示上行方向列車在算例中可使用的股道數(shù)量。根據(jù)參考文獻(xiàn)[17]以及京滬高速鐵路的實(shí)際資料,相鄰列車之間的最小發(fā)車間隔取2 min、最小到達(dá)間隔取3 min,列車在相同到發(fā)線的發(fā)到間隔取3 min。目標(biāo)函數(shù)中,Ⅰ、Ⅱ類列車取消運(yùn)行的懲罰值按票價(jià)比分別取1 000和600,同時(shí),2類列車到站晚點(diǎn)1 min的懲罰值也根據(jù)票價(jià)比分別取5和3??紤]取消列車對(duì)旅客產(chǎn)生的影響很大,列車取消懲罰值相對(duì)比較大,具體取值根據(jù)現(xiàn)場經(jīng)驗(yàn)靈活調(diào)整,在此不作重點(diǎn)研究,如果有需要,可對(duì)多組取值進(jìn)行計(jì)算。M1取1 440,M2取2 880。2類列車區(qū)間運(yùn)行時(shí)間見表3。

表2 中間站股道數(shù)量

注:昆山南站為京滬高鐵和滬寧城際共用;南京南、濟(jì)南西站雖為大站,但由于沒有列車在此越行,假設(shè)只有1條股道可供長途列車使用。

表3 區(qū)間運(yùn)行時(shí)間(不包括起、停附加時(shí)分)

注:起停附加時(shí)分 Ⅰ類列車起2 min、停3 min;Ⅱ類列車起停均為2 min。

4.2 算例結(jié)果

使用CPU為Inter(R)Core(TM)i5-4570 3.2 GHZ、內(nèi)存為4 GB的電腦,采用IBM ILOG OPL (Optimization Programming Language)編程,調(diào)用CPLEX 12.6實(shí)現(xiàn)提出的方法。CPLEX的相關(guān)參數(shù)設(shè)置為默認(rèn)值,通過內(nèi)置的將分支定界法和割平面法相結(jié)合的分支切割算法對(duì)混合整數(shù)線性規(guī)劃模型進(jìn)行求解。鑒于列車運(yùn)行調(diào)整的實(shí)時(shí)性要求,限制最長運(yùn)行時(shí)間為120 s,依據(jù)4.1節(jié)設(shè)置的算例及相關(guān)參數(shù),對(duì)3種測試場景下的9種干擾情景分別進(jìn)行計(jì)算,得到基于優(yōu)先級(jí)調(diào)整策略的計(jì)算結(jié)果見表4。

表4 基于優(yōu)先級(jí)調(diào)整策略的計(jì)算結(jié)果

借助提出的整體優(yōu)化模型,在設(shè)定的限制時(shí)間內(nèi),干擾情景(12,12,60)不能求得整數(shù)解。因此,使用第3節(jié)描述的兩階段算法對(duì)該干擾情景下列車運(yùn)行調(diào)整方案進(jìn)行分階段求解。表4中,第7行為干擾情景(12,12,60)利用整體優(yōu)化模型求解的結(jié)果(在120 s內(nèi)無解),第8行為該情景在兩階段算法下第1階段求解的結(jié)果,第9行為該情景在兩階段算法下第2階段求解的結(jié)果。為評(píng)估兩階段算法的效果,在不限計(jì)算時(shí)間的前提下,采用整體優(yōu)化模型對(duì)干擾情景(12,12,60)重新進(jìn)行求解,結(jié)果經(jīng)過3 383 s求得最優(yōu)解為9 120。從2種方法的求解結(jié)果可看出,與整體優(yōu)化模型相比,兩階段算法在目標(biāo)函數(shù)值上的誤差為2.68%,可見兩階段算法具有較高的求解質(zhì)量。

從表4可看出,不同的干擾情景對(duì)列車運(yùn)行的影響各不相同。中午時(shí)刻發(fā)生在線路中部的干擾對(duì)列車運(yùn)行影響最為嚴(yán)重,如場景2大于場景1和3。同一場景下,干擾持續(xù)時(shí)間越長,對(duì)列車運(yùn)行的影響越大?;趦?yōu)先級(jí)的調(diào)整策略能夠快速有效地獲得不同干擾情景下的列車運(yùn)行實(shí)時(shí)調(diào)整方案,且絕大多數(shù)調(diào)整方案可在100 s以內(nèi)獲得。針對(duì)較復(fù)雜的干擾情景,如干擾情景(12,12,60),采用兩階段算法后只需不到150 s便可獲得可行的列車運(yùn)行調(diào)整方案,且獲得的解與最優(yōu)解的誤差僅為2.68%。由此可見,本文提出的方法計(jì)算效果和效率可滿足實(shí)時(shí)列車運(yùn)行調(diào)整的需要。

4.3 調(diào)整策略的比較

如前所述,現(xiàn)場區(qū)間能力全失效時(shí),高鐵調(diào)度員通常采用基于順序的調(diào)整策略開展列車運(yùn)行調(diào)整工作。該策略下,4.1節(jié)算例計(jì)算結(jié)果見表5。

表5 基于順序調(diào)整策略的計(jì)算結(jié)果

注:計(jì)算時(shí)間指該干擾情境下列車運(yùn)行調(diào)整方案的計(jì)算機(jī)求解時(shí)間。

比較表4和表5可發(fā)現(xiàn),在相同干擾情景下,采用優(yōu)先級(jí)調(diào)整策略獲得的結(jié)果明顯優(yōu)于順序調(diào)整策略。與順序調(diào)整策略相比,基于優(yōu)先級(jí)調(diào)整策略使目標(biāo)函數(shù)值(總加權(quán)求和列車取消懲罰值和列車晚點(diǎn)懲罰值)減小近50%,同時(shí),取消的列車數(shù)量也大為減小(事實(shí)上,對(duì)于9種干擾情景,只在2種干擾情景下各取消1列列車),見圖3和圖4。由此可見,優(yōu)先級(jí)調(diào)整策略可在保證列車安全運(yùn)行的前提下,較大地減小干擾對(duì)列車運(yùn)行的影響。

4.4 車站能力的影響分析

車站能力是列車運(yùn)行實(shí)時(shí)調(diào)整問題的重要約束,4.1節(jié)構(gòu)造測試算例時(shí),為更好地測試所提方法的效果,將各站的能力設(shè)置為實(shí)際能力的0.5倍。為評(píng)估車站能力對(duì)高速鐵路抗干擾的影響,在保證原始運(yùn)行圖可行的前提下,構(gòu)造5組中間站能力值,詳見表6。對(duì)于測試場景(09,03,-)的3種干擾情景,在不同的中間站能力組合下,基于優(yōu)先級(jí)調(diào)整策略的計(jì)算結(jié)果見圖5。從圖5可知,在一定的范圍內(nèi),隨著中間站能力的增加,高速鐵路抗干擾能力也隨之增加,當(dāng)中間站能力增加到一定程度時(shí),高速鐵路抗干擾能力保持不變,意味著對(duì)于抗干擾能力較差的高速鐵路,若條件允許,可考慮在干擾多發(fā)地段附近的中間站上增設(shè)1~2條到發(fā)線,以提高列車運(yùn)行調(diào)整的質(zhì)量。

表6 中間站能力值

5 結(jié)論

(1) 通過引入事件和活動(dòng)的概念,將高速鐵路從宏觀層面抽象為由事件和活動(dòng)構(gòu)成的網(wǎng)絡(luò),在此基礎(chǔ)上,對(duì)高速鐵路區(qū)間能力全失效條件下調(diào)整問題進(jìn)行闡述;

(2) 考慮運(yùn)營安全和設(shè)備能力等約束,對(duì)高速鐵路區(qū)間能力全失效條件下的調(diào)整問題,建立基于優(yōu)先級(jí)調(diào)整策略的MILP模型;

(3) 結(jié)合高速鐵路調(diào)度指揮分階段逐步進(jìn)行的實(shí)際情況,提出兩階段求解算法,保證求解質(zhì)量的同時(shí),提高求解速度;

(4) 以京滬高速鐵路上行方向全天42列長途列車實(shí)際數(shù)據(jù)為背景,構(gòu)造產(chǎn)生于3種測試場景下的9種干擾情景,對(duì)提出的整體優(yōu)化模型和兩階段求解算法進(jìn)行測試。通過與現(xiàn)場實(shí)際采用的順序調(diào)整策略相比,突出基于優(yōu)先級(jí)的調(diào)整策略在保證行車安全的基礎(chǔ)上,可減小干擾對(duì)列車運(yùn)行的影響;

(5) 干擾條件下的調(diào)整是極其復(fù)雜的決策問題,涉及到鐵路運(yùn)輸系統(tǒng)的各環(huán)節(jié)。目前本文主要針對(duì)宏觀層面的運(yùn)行圖進(jìn)行調(diào)整,沒有考慮動(dòng)車組和乘務(wù)組方面的約束,也沒有從微觀層面上對(duì)干擾的類型進(jìn)行分析。另外,測試算例僅對(duì)京滬高鐵單方向的部分列車進(jìn)行分析,今后將進(jìn)一步對(duì)整條線路上開行的所有列車以及從整個(gè)路網(wǎng)層面上進(jìn)行優(yōu)化。最后,隨著問題的規(guī)模進(jìn)一步擴(kuò)大,如何選擇更為有效的啟發(fā)式算法提高運(yùn)算效率,如滾動(dòng)時(shí)域算法等將是研究的重點(diǎn)。

參考文獻(xiàn):

[1] CACCHIANI V, HUISMAN D, KIDD M P, et al. An Overview of Recovery Models and Algorithms for Real-time Railway Rescheduling[J]. Transportation Research Part B: Methodological, 2014, 63:15-37.

[2] D’ARIANO A, PRANZO M, HANSEN I A. Conflict Resolution and Train Speed Coordination for Solving Real-time Timetable Perturbations[J]. IEEE Transactions on Intelligent Transportation Systems, 2007, 8(2):208-222.

[3] CORMAN F, D’ ARIANO A, PACCIARELLI D, et al. Bi-objective Conflict Detection and Resolution in Railway Traffic Management[J]. Transportation Research Part C: Emerging Technologies, 2012, 20(1): 79-94.

[4] CORMAN F, D’ ARIANO A, PACCIARELLI D, et al. Centralized Versus Distributed Systems to Reschedule Trains in Two Dispatching Areas[J]. Public Transport, 2010, 2(3): 219-247.

[5] CORMAN F, D’ ARIANO A, PACCIARELLI D, et al. A Tabu Search Algorithm for Rerouting Trains During Rail Operations[J]. Transportation Research Part B: Methodological, 2010, 44(1): 175-192.

[6] CORMAN F, D’ ARIANO A, HANSEN I A, et al. Optimal Multi-class Rescheduling of Railway Traffic[J]. Journal of Rail Transport Planning & Management, 2011, 1(1): 14-24.

[7] GINKEL A, SCHOBEL A. To Wait or not to Wait? The Bicriteria Delay Management Problem in Public Transportation[J]. Transportation Science, 2007, 41(4): 527-538.

[8] SCHACHTEBECK M, SCHOBEL A. To Wait or not to Wait-and Who Goes First? Delay Management with Priority Decisions[J]. Transportation Science, 2010, 44(3): 307-321.

[9] DOLLEVOET T, HUISMAN D, SCHMIDT M., et al. Delay Management with Rerouting of Passengers[J]. Transportation Science, 2012, 46(1): 74-89.

[10] DOLLEVOET T, HUISMAN D, KROON L G, et al. Delay Management Including Capacities of Stations[J]. Transportation Science, 2014,49(2):185-203.

[11] LOUWERSE I, HUISMAN D. Adjusting a Railway Timetable in Case of Partial or Complete Blockades[J]. European Journal of Operational Research, 2013, 235(3):583-593.

[12] VEELENTURF L P, KIDD M P, CACCHIANI V, et al. A Macroscopic Railway Timetable Rescheduling Approach for Handling Large Scale Disruptions[C]//Technical report ERS-2014-010-LIS, Erasmus Research Institute in Management (RRIM), 2014. URL http://hdl.handle.net/1765/51678.

[13] 孟令云,楊肇夏,李海鷹. 單線鐵路區(qū)間能力失效條件下列車運(yùn)行調(diào)整模型[J]. 系統(tǒng)工程理論與實(shí)踐,2012,32(4):885-894.

MENG Ling-yun, YANG Zhao-xia, LI Hai-ying. Train Dispatching Models under Field Capacity Breakdowns on Single-track Railway Lines[J]. Systems Engineering Theory & Practice, 2012,32(4):885-894.

[14] MENG L,ZHOU X. Robust Single-track Train Dispatching Model under a Dynamic and Stochastic Environment: A Scenario-based Rolling Horizon Solution Approach[J]. Transportation Research Part B: Methodological, 2011, 45(7): 1080-1102.

[15] YANG L, ZHOU X, GAO Z. Rescheduling Trains with Scenario-based Fuzzy Recovery Time Representation on Two-way Double-track Railways[J]. Soft Computing, 2013, 17(4):605-616.

[16] YANG L, ZHOU X, GAO Z. Credibility-based Rescheduling Model in a Double-track Railway Network: a Fuzzy Reliable Optimization Approach[J]. Omega, 2014, 48:75-93.

[17] 史峰,魏堂建,周文梁,等. 考慮動(dòng)車組周轉(zhuǎn)和到發(fā)線運(yùn)用的高速鐵路列車運(yùn)行圖優(yōu)化方法[J]. 中國鐵道科學(xué),2012,33(2): 107-114.

SHI Feng, WEI Tang-jian, ZHOU Wen-liang, et al. Optimization Method for Train Diagram of High-speed Railway Consider the Turnover of Multiple Units and the Utilization of Arrival-departure Tracks[J]. China Railway Science, 2012, 33(2):107-114.

猜你喜歡
運(yùn)行圖列車運(yùn)行高速鐵路
《高速鐵路技術(shù)》征稿啟事
《高速鐵路技術(shù)》征稿啟事
(六年級(jí))怎么做能在學(xué)習(xí)運(yùn)行圖時(shí)更好地進(jìn)行數(shù)據(jù)分析
預(yù)制膠拼架橋法在高速鐵路工程中的實(shí)踐
改善地鐵列車運(yùn)行舒適度方案探討
CBTC系統(tǒng)列車運(yùn)行間隔控制仿真研究
車輛段收發(fā)車運(yùn)行圖編輯器的設(shè)計(jì)與實(shí)現(xiàn)
現(xiàn)代有軌電車運(yùn)行圖編制策略探討
列車運(yùn)行控制系統(tǒng)技術(shù)發(fā)展趨勢分析
基于TD-LTE的高速鐵路WiFi通信系統(tǒng)
民丰县| 河南省| 琼结县| 民勤县| 正阳县| 礼泉县| 兴城市| 顺义区| 会同县| 新晃| 万宁市| 涿州市| 南丰县| 饶平县| 炉霍县| 元阳县| 崇信县| 麻栗坡县| 普洱| 河东区| 油尖旺区| 长治市| 鸡西市| 合肥市| 保定市| 库车县| 鹤峰县| 濉溪县| 深泽县| 周至县| 宜春市| 黄大仙区| 东明县| 刚察县| 石台县| 冕宁县| 甘谷县| 迁西县| 陇西县| 盐边县| 渝中区|