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

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

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

高速鐵路列車運(yùn)行安全和非正常情況下列車運(yùn)行實(shí)時(shí)調(diào)整(下文簡(jiǎn)稱“調(diào)整”)是鐵路調(diào)度指揮關(guān)注的重點(diǎn)問(wè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種類型的干擾沒(méi)有明確的界定，大部分學(xué)者認(rèn)為：小干擾往往來(lái)源于列車在站時(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)行；大干擾往往來(lái)源于鐵路基礎(chǔ)設(shè)施由于故障在相對(duì)較長(zhǎng)的時(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)整問(wèn)題，區(qū)間能力全失效指由于故障干擾導(dǎo)致某區(qū)間上下行2條正線同時(shí)中斷，該問(wèn)題屬于大干擾條件下的調(diào)整問(wèn)題。當(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è)問(wèn)題變得非常復(fù)雜。比較可行的解決方案是將整個(gè)問(wèn)題分解為運(yùn)行圖調(diào)整、動(dòng)車組調(diào)整和乘務(wù)組調(diào)整3個(gè)子問(wèn)題，進(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)前，國(guó)外學(xué)者對(duì)調(diào)整問(wèn)題開展較系統(tǒng)地研究，較為全面的綜述見文獻(xiàn)[1]；文獻(xiàn)[2-6]研究小干擾條件下的調(diào)整，將該問(wèn)題視為無(wú)等待的作業(yè)車間調(diào)度問(wèn)題，提出基于比選圖的優(yōu)化模型和算法；文獻(xiàn)[7-10]探討另一類小干擾條件下的調(diào)整，稱為晚點(diǎn)管理問(wèn)題，判斷在接續(xù)車站前行列車是否等待后續(xù)晚點(diǎn)列車，對(duì)不同約束下的問(wèn)題建模，設(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)整模型。國(guó)內(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]提出基于場(chǎng)景的滾動(dòng)時(shí)域算法，進(jìn)一步采用多層分支求解策略對(duì)問(wèn)題求解；基于文獻(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)整問(wèn)題，研究對(duì)象為荷蘭鐵路，采用1 h或0.5 h周期運(yùn)行圖，且列車速度等級(jí)較為單一。然而，我國(guó)已經(jīng)投入運(yùn)營(yíng)的高速鐵路(例如京滬、京廣高鐵)采用非周期運(yùn)行圖(或可視為以24 h為周期的運(yùn)行圖)，并存在2種速度等級(jí)列車共線運(yùn)行。相比國(guó)外，我國(guó)高速鐵路運(yùn)行圖規(guī)模更大、運(yùn)營(yíng)模式更為復(fù)雜，但至今鮮見文獻(xiàn)探討符合國(guó)情的嚴(yán)重干擾時(shí)列車運(yùn)行實(shí)時(shí)調(diào)整問(wèn)題。鑒于此，作者在文獻(xiàn)[11-12]基礎(chǔ)上，根據(jù)我國(guó)實(shí)際情況，研究區(qū)間能力全失效條件下的調(diào)整問(wèn)題。首先，借助于事件-活動(dòng)網(wǎng)絡(luò)概念，構(gòu)建大規(guī)?；旌险麛?shù)線性規(guī)劃模型;其次，根據(jù)問(wèn)題特點(diǎn)，開發(fā)有效的兩階段求解算法;最后，結(jié)合中國(guó)高速鐵路實(shí)際，構(gòu)造算例驗(yàn)證所提方法的效果和效率。

1 問(wèn)題描述與界定

1.1 問(wèn)題描述

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

1.2 問(wèn)題界定

區(qū)間能力全失效情況下調(diào)整是非常復(fù)雜的決策問(wèn)題，調(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)化的問(wèn)題；

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

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

2 模型構(gòu)建

2.1 問(wèn)題抽象

為建模方便，從宏觀層面上把高速鐵路列車運(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)。

目前，我國(guó)高速鐵路普遍采用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)化問(wèn)題。為最大程度地減小干擾對(duì)列車運(yùn)行的影響，以總加權(quán)求和列車取消懲罰值和列車晚點(diǎn)懲罰值最小為目標(biāo)函數(shù)。不考慮運(yùn)營(yíng)安全和設(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)營(yíng)時(shí)間最大不超過(guò)M1，意味著將被取消的列車移動(dòng)到運(yùn)營(yíng)時(shí)間結(jié)束之后。通過(guò)把取消列車移動(dòng)到最后，可有效避免該類列車相互間及與其他未被取消列車之間的影響；約束(4)和約束(5)表示變量的取值范圍。

2.3 約束條件

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

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

正常情況下，列車按照原定運(yùn)行圖運(yùn)行。發(fā)生干擾后，雖受到干擾的影響，但各列車從始發(fā)站到終到站經(jīng)過(guò)的所有事件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)

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

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

(11)

(3) 車站能力約束

列車到達(dá)或者通過(guò)車站必須占用車站線路，相同線路在同一時(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)場(chǎng)情況、干擾信息、以及客票發(fā)售情況等，綜合決策是否停運(yùn)，以盡量減小干擾對(duì)整條線路造成的影響。鑒于此，取消列車約束為

(15)

(16)

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

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

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

由假設(shè)4，干擾發(fā)生后還未進(jìn)入中斷區(qū)間的列車需依次停在合適的車站，而目前創(chuàng)建的約束可能導(dǎo)致調(diào)整方案中部分列車在區(qū)間過(guò)度緩行甚至停車。為避免這種情況，提出列車區(qū)間最長(zhǎng)運(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 模型合理性說(shuō)明

約定干擾發(fā)生后，未進(jìn)入中斷區(qū)間的列車只能依次停留在適當(dāng)?shù)能囌?。由于我?guó)高速鐵路在相同線路上同時(shí)開行2種速度等級(jí)的列車，Ⅰ類列車的優(yōu)先級(jí)高于Ⅱ類列車，當(dāng)干擾發(fā)生后，應(yīng)如何制定列車停站方案，以便既能充分體現(xiàn)不同等級(jí)列車的優(yōu)先級(jí)，又能有效避免獲得不合理的列車運(yùn)行調(diào)整方案。本節(jié)通過(guò)對(duì)Ⅰ、Ⅱ類列車賦予不同的取消懲罰系數(shù)λt和晚點(diǎn)懲罰系數(shù)μe，再基于車站能力約束3、干擾發(fā)生后列車區(qū)間最長(zhǎng)運(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，誰(shuí)在s3站等待，誰(shuí)繼續(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ā)，然后通過(guò)區(qū)間(s3,s4)緩慢運(yùn)行進(jìn)入車站s4。但是，鑒于干擾持續(xù)時(shí)間的不確定性，此種調(diào)整策略不具有運(yùn)營(yíng)可行性。由于列車G4在區(qū)間(s3,s4)需滿足最長(zhǎng)運(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)場(chǎng)調(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問(wèn)題，針對(duì)大規(guī)模問(wèn)題很難求得最優(yōu)解。實(shí)際工作中，高速鐵路的列車運(yùn)行調(diào)整過(guò)程分階段進(jìn)行，此外，由于干擾持續(xù)時(shí)間的不確定性，調(diào)度員需根據(jù)現(xiàn)場(chǎng)反饋的最新信息動(dòng)態(tài)地對(duì)列車運(yùn)行進(jìn)行調(diào)整。因此，提出兩階段算法，對(duì)整個(gè)問(wèn)題進(jìn)行分解，可快速求解大規(guī)模實(shí)際問(wèn)題，實(shí)時(shí)給出列車運(yùn)行調(diào)整方案。

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

Step1僅對(duì)干擾結(jié)束時(shí)刻之前時(shí)段施加車站能力約束，在干擾結(jié)束之后時(shí)段，假設(shè)車站能力不受限制(即去掉車站能力約束(13)、約束(14))，對(duì)原問(wèn)題求解，獲得調(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ì)原問(wèn)題進(jìn)行求解，獲得全時(shí)段可行的調(diào)整圖φ2，最終獲得全天可行的調(diào)整圖。

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

與整體優(yōu)化相比，兩階段算法屬于啟發(fā)式算法范疇，并不能保證獲得問(wèn)題的全局最優(yōu)解。但當(dāng)高速鐵路受到嚴(yán)重干擾時(shí)，快速提供近似最優(yōu)調(diào)整圖比漫長(zhǎng)等待最優(yōu)調(diào)整圖更重要。因此，對(duì)于大規(guī)模調(diào)整問(wèn)題，兩階段算法具有較好的可行性和實(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)整問(wèn)題大致相同。因此，僅對(duì)上行列車進(jìn)行算例分析，選擇從上海虹橋站至北京南站的42列列車(包括從杭州等地經(jīng)過(guò)上海虹橋到達(dá)北京南站的跨線列車)。其中，時(shí)速300 km的Ⅰ類列車共40列，時(shí)速250 km的Ⅱ類列車共2列，對(duì)模型進(jìn)行驗(yàn)證。

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

場(chǎng)景1

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

場(chǎng)景2

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

場(chǎng)景3

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

為便于表示不同場(chǎng)景下的干擾情景，定義三元組(a,b,c)。其中，a為干擾發(fā)生時(shí)刻，b為干擾所在區(qū)間，c為干擾持續(xù)時(shí)間。3種測(cè)試場(chǎng)景下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列長(zhǎng)途列車，該部分列車的數(shù)量?jī)H占實(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)場(chǎng)經(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ì)南西站雖為大站，但由于沒(méi)有列車在此越行，假設(shè)只有1條股道可供長(zhǎng)途列車使用。

表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)值，通過(guò)內(nèi)置的將分支定界法和割平面法相結(jié)合的分支切割算法對(duì)混合整數(shù)線性規(guī)劃模型進(jìn)行求解。鑒于列車運(yùn)行調(diào)整的實(shí)時(shí)性要求，限制最長(zhǎng)運(yùn)行時(shí)間為120 s，依據(jù)4.1節(jié)設(shè)置的算例及相關(guān)參數(shù)，對(duì)3種測(cè)試場(chǎng)景下的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)無(wú)解)，第8行為該情景在兩階段算法下第1階段求解的結(jié)果，第9行為該情景在兩階段算法下第2階段求解的結(jié)果。為評(píng)估兩階段算法的效果，在不限計(jì)算時(shí)間的前提下，采用整體優(yōu)化模型對(duì)干擾情景(12,12,60)重新進(jìn)行求解，結(jié)果經(jīng)過(guò)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)重，如場(chǎng)景2大于場(chǎng)景1和3。同一場(chǎng)景下，干擾持續(xù)時(shí)間越長(zhǎng)，對(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)場(chǎng)區(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)整問(wèn)題的重要約束，4.1節(jié)構(gòu)造測(cè)試算例時(shí)，為更好地測(cè)試所提方法的效果，將各站的能力設(shè)置為實(shí)際能力的0.5倍。為評(píng)估車站能力對(duì)高速鐵路抗干擾的影響，在保證原始運(yùn)行圖可行的前提下，構(gòu)造5組中間站能力值，詳見表6。對(duì)于測(cè)試場(chǎng)景(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) 通過(guò)引入事件和活動(dòng)的概念，將高速鐵路從宏觀層面抽象為由事件和活動(dòng)構(gòu)成的網(wǎng)絡(luò)，在此基礎(chǔ)上，對(duì)高速鐵路區(qū)間能力全失效條件下調(diào)整問(wèn)題進(jìn)行闡述；

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

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

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

(5) 干擾條件下的調(diào)整是極其復(fù)雜的決策問(wèn)題，涉及到鐵路運(yùn)輸系統(tǒng)的各環(huán)節(jié)。目前本文主要針對(duì)宏觀層面的運(yùn)行圖進(jìn)行調(diào)整，沒(méi)有考慮動(dòng)車組和乘務(wù)組方面的約束，也沒(méi)有從微觀層面上對(duì)干擾的類型進(jìn)行分析。另外，測(cè)試算例僅對(duì)京滬高鐵單方向的部分列車進(jìn)行分析，今后將進(jìn)一步對(duì)整條線路上開行的所有列車以及從整個(gè)路網(wǎng)層面上進(jìn)行優(yōu)化。最后，隨著問(wèn)題的規(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]. 中國(guó)鐵道科學(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.