占曙光，趙 軍，彭其淵

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

在正常情況下，高速列車都能夠按照原定的列車運行計劃自動運行，不需要調(diào)度員對列車的運行進行干預。然而，由于高速鐵路系統(tǒng)不可避免地會受到系統(tǒng)內(nèi)部以及外部各種干擾因素的影響，從而導致列車的運行偏離原來的運行計劃，需要調(diào)度員及時地對列車運行進行調(diào)整。目前我國高速鐵路在非正常情況下的列車運行調(diào)整主要是以調(diào)度員的人為調(diào)整為主，系統(tǒng)調(diào)整為輔，在有限的時間內(nèi)對高速度、高密度運行的列車進行調(diào)整對調(diào)度員而言是一項艱巨的任務。因此，為了緩解調(diào)度員的工作壓力，并確保列車運行安全，研究非正常情況下的列車運行實時調(diào)整具有重要的現(xiàn)實意義。

近年來，干擾情況下的列車運行調(diào)整是鐵路運輸組織研究的熱點問題之一[1]，吸引了許多國內(nèi)外學者的研究興趣。國外方面，學者們主要集中在輕微干擾情況下的列車運行調(diào)整研究，而對嚴重干擾情況下的列車運行調(diào)整研究尚比較缺乏。文獻[2-6]對輕微干擾情況下的列車運行調(diào)整從微觀層面上進行了一系列的研究，采用替代圖的方法構建了列車運行調(diào)整模型，基于這一系列的研究，他們開發(fā)了ROMA系統(tǒng)，該系統(tǒng)目前主要用于實驗研究，尚沒有用于解決大規(guī)模的實際問題。文獻[7-10]從宏觀層面上對列車運行晚點管理問題進行了一系列的研究，主要是對在換乘站前行列車晚點的情況下，后行接續(xù)列車是否等待前行晚點列車問題進行研究。關于嚴重干擾情況下的列車運行調(diào)整，文獻[11，12]從宏觀層面上，基于事件-活動網(wǎng)絡對線路區(qū)間能力全部以及部分失效情況下的列車運行調(diào)整問題分別進行了研究。

與國外相比，國內(nèi)針對干擾情況下的列車運行實時調(diào)整的研究相對比較少。文獻[13]對列車運行沖突進行了預測和判定，提出了基于沖突消解代價最小的列車運行調(diào)整模型。文獻[14-16]對列車由于干擾偏離原運行計劃情況下的列車運行調(diào)整問題進行了研究，在列車運行調(diào)整過程中主要考慮調(diào)整列車到發(fā)順序和時刻，沒有考慮是否取消列車運行。文獻[17]對單線鐵路在線路區(qū)間能力失效條件下的列車運行調(diào)整模型進行了研究，針對線路失效持續(xù)時間的不確定性，提出了兩階段帶補償隨機期望模型，并進一步在多階段遞歸決策概念模型的基礎上提出了不完全連續(xù)多階段決策模型，采用分支定界法對模型進行了求解。文獻[18，19]基于事件-活動網(wǎng)絡從宏觀層面上對區(qū)間能力全部失效情況下的列車運行實時調(diào)整問題進行了研究，建立了該問題的混合整數(shù)線性規(guī)劃模型，并且用中國高速鐵路實際線路作為算例對模型進行了測試。

從國內(nèi)外既有研究可知，高速鐵路區(qū)間能力部分失效情況下的列車運行調(diào)整問題還未被廣泛探討過。國外方法探討的高速鐵路往往采用以1 h或者0.5 h為周期的運行圖，且列車種類較為單一，但我國高速鐵路采用非周期運行圖(或者大體上可視為以天為周期的運行圖)，并且一般開行多種類別的列車，因此，國外方法不適用于我國高速鐵路運營的實際情況。國內(nèi)未見文獻針對我國高速鐵路運營的特點，提出區(qū)間能力部分失效情況下的列車運行調(diào)整方法。高速鐵路由于列車運行速度高，行車密度大，在雙線鐵路某區(qū)間一條線路出現(xiàn)故障導致線路通行能力失效的情況下，列車的運行調(diào)整工作比較復雜，通常需要組織雙向列車在故障區(qū)間共線運行。本文在文獻[11，12]的基礎上，考慮到我國高速鐵路調(diào)度指揮的實際需要，對區(qū)間能力部分失效情況下的列車運行調(diào)整進行研究。通過引入事件-活動網(wǎng)絡的概念，將整個問題構建為混合整數(shù)線性規(guī)劃模型，詳細介紹問題目標函數(shù)和各關鍵約束的建模方法；設計切實案例測試所提出模型的求解能力，并與現(xiàn)場采用的調(diào)度策略進行比較。

1 問題描述

高速鐵路在干擾情況下的列車運行調(diào)整屬于復雜的組合優(yōu)化問題，隨著線路長度以及列車數(shù)量的增加，該問題的求解難度呈指數(shù)級增加，即該問題屬于NP-Complete問題，不存在多項式算法。隨著問題規(guī)模的擴大，時間或空間上無法窮舉所有的可行解，需要現(xiàn)代優(yōu)化算法探尋最優(yōu)解或較優(yōu)解。因此，通常都是將列車運行調(diào)整的三個階段：運行圖調(diào)整、動車組調(diào)整以及乘務調(diào)整分別進行優(yōu)化，從而降低問題的求解難度。本文主要是對列車運行圖進行調(diào)整，同時也通過考慮列車的均衡性兼顧考慮動車組周轉(zhuǎn)。

1.1 問題定義

高速鐵路一般為雙線單向鐵路，在正常情況下，上下行列車分別在各自的線路上按照既定的運行圖運行，互不干擾，同時也不需要調(diào)度員對列車的運行進行人為調(diào)整。但是在高速鐵路線路某區(qū)間能力部分失效的情況下，列車將不能按照既定的運行圖運行，列車運行秩序發(fā)生紊亂。結(jié)合高速鐵路的調(diào)度實際，在線路能力部分失效的情況下，調(diào)度員將組織雙向列車在故障區(qū)間共線運行。在這種情況下，調(diào)度員需要充分考慮列車運行安全約束以及設備能力約束，合理安排從故障開始時刻至運營時段末雙向列車通過每個區(qū)間的順序和時刻，特別是合理安排在故障時段雙向列車通過故障區(qū)間的順序，并確定是否有列車由于線路能力下降而需要取消運行，從而減小干擾對整體列車運行的影響，提高高速鐵路的服務質(zhì)量。

為了更清楚地描述本文所要研究的問題，以圖1所示為例進行說明。一條鐵路線上有6個車站，按照下行方向分別為S1～S6，上下行各有4列車在該線路上運行，下行列車分別為G1、G3、D5和G7，上行列車分別為G2、G4、G6和D8，其中“G”表示速度相對較高的高速列車，在圖1中用粗線表示；“D”表示速度相對較低的高速列車，在圖1中用細線表示。假設在h1時刻，車站S3和S4之間的區(qū)間發(fā)生故障，導致該區(qū)間一條線路(如上行線路)通行能力失效，初步估計故障將持續(xù)到h2。設定在故障時段內(nèi)故障區(qū)間運行的雙向列車均可以追蹤運行，鐵路現(xiàn)場的列車具體組織模式將在后文進行說明。列車G1、G2、G3和G44列車從其始發(fā)站的出發(fā)時刻早于故障發(fā)生時刻h1，因此，根據(jù)規(guī)定這4列車不能取消運行，我們用實線表示這4列車的運行線；列車D5、G6、G7和D8在h1之后始發(fā)，因此，這些列車可以考慮取消運行，在圖中用虛線表示它們的運行線。

圖1 區(qū)間能力部分失效情況下列車運行調(diào)整圖

在車站S3和S4之間的區(qū)間發(fā)生故障的情況下，調(diào)度員首先需要合理安排故障持續(xù)時間內(nèi)上下行列車通過區(qū)間(尤其是故障區(qū)間)的順序和時刻，并確定是否有上下行列車由于線路通行能力下降而需要在靠近故障區(qū)間的車站停車等待，注意，在安排列車停站等待故障時要滿足車站的能力約束。列車G1和G2由于在故障發(fā)生之前已經(jīng)通過了故障區(qū)間，因此可以按計劃運行圖運行；G4到達故障區(qū)間時故障已經(jīng)發(fā)生，且列車G3已經(jīng)進入了故障區(qū)間，因此G4需要在S4站等待G3通過故障區(qū)間后才能出發(fā)；D5到達故障區(qū)間時，G4已經(jīng)進入故障區(qū)間，因此D5需要在車站S3等待G4，此外，由于G6是速度相對較高的高速列車，D5可能要等到G6通過S3站后才能從S3站出發(fā)；列車D8也需要在S4站等待D5，由于G7的等級更高，D8可能還要等G7先通過故障區(qū)間。除了需決策列車的運行順序和時刻以外，列車D5、G6、G7和D8在故障發(fā)生時還沒有始發(fā)，調(diào)度員還可以根據(jù)現(xiàn)場列車運行情況，結(jié)合故障信息確定是否有列車需要取消運行。此外，故障時段內(nèi)可能有大量的下行列車停在S3站，上行列車停在S4站，因此，故障結(jié)束后，調(diào)度員還需決策列車在其所停車站的出發(fā)順序和時刻以及其前方途經(jīng)各車站的到發(fā)順序和時刻。本文將結(jié)合我國高速鐵路的實際情況，通過建立優(yōu)化模型對以上這些問題進行優(yōu)化，從而為調(diào)度員的實時調(diào)度決策提供依據(jù)。

1.2 問題假設

在區(qū)間能力部分失效條件下，對列車運行進行調(diào)整是一項復雜的工作，調(diào)度員需要結(jié)合當前的列車運行狀況以及故障信息在很短的時間內(nèi)做出決策，同時需要考慮各種設備能力約束以及列車運行安全約束，此外，還需要遵守現(xiàn)場的各種調(diào)度規(guī)則。本文為了研究的方便，結(jié)合高速鐵路的調(diào)度實際，對該問題所做的假設如下：

(1)為了便于調(diào)度員操作以及保證行車安全，本文假設高速鐵路各車站的到發(fā)線分上下行分別使用，而且每條到發(fā)線都配有供旅客上下的站臺。此外，上下行的正線與車站所有的到發(fā)線都相連。

(2)雙線高速鐵路每一條線路都滿足組織雙向行車的條件，但是在正常情況下，上下行列車分線運行，互不干擾。

(3)對于區(qū)間故障發(fā)生時已經(jīng)進入故障區(qū)間的列車，需要結(jié)合現(xiàn)場的具體情況(故障具體的位置及故障類型等)從微觀層面上進行處理，本文對該類列車的處理不做詳細研究。假設進入故障區(qū)間的列車已經(jīng)通過了故障地點，可以繼續(xù)向前運行。

(4)由于在正常情況下高速列車基本上均能按圖運行，所以本文假設所有列車在區(qū)間故障發(fā)生之前都按照運行圖運行。

2 模型構建

2.1 問題抽象

為有效地解決區(qū)間能力部分失效情況下的列車運行調(diào)整這一大規(guī)模問題，本文從宏觀層面上將高速鐵路網(wǎng)絡抽象為由事件和活動構成的網(wǎng)絡N=(E，A)，其中E表示事件集合，A表示活動集合。事件e∈E表示列車在車站的到達或出發(fā)事件，因此可以將事件集合進一步劃分為：到達事件集合Earr?E和出發(fā)事件集合Edep?E；活動a∈A可以進一步分為列車活動a∈Atrain和間隔活動a∈Ahead。

(1)列車活動a∈Atrain：既可以為列車運行活動a∈Arun，表示列車從一個車站出發(fā)事件到該列車在下一個車站到達事件之間的一個運行；也可以是停站活動a∈Adwell，表示列車在一個車站到達事件和在同一個車站出發(fā)事件之間的停站活動。

(2)間隔活動a∈Ahead：表示相鄰的兩列同向或者反向列車在區(qū)間的運行間隔或者相鄰的兩列同向列車在車站同一條到發(fā)線上的發(fā)到間隔。

(1)

2.2 基本模型

對高速鐵路在干擾情況下列車運行進行調(diào)整的主要目標為列車盡可能少地偏離原來的運行計劃，體現(xiàn)為兩個方面：一方面，盡量最小化列車在車站到發(fā)的偏離時間(晚點時間和早點時間)，相比于列車早點而言，旅客更多地關注列車的晚點，所以，可給列車晚點時間更大的懲罰系數(shù)；另一方面，盡可能最小化取消列車的數(shù)量，取消列車運行雖然能夠消除晚點，但是它會對旅客的出行造成極大的影響，進而嚴重降低鐵路的服務質(zhì)量，因此，取消列車時需慎重。綜合兩方面考慮，本文目標為最小化加權求和列車取消和偏離計劃懲罰值。基于前面定義的符號，得到不考慮能力約束的基本模型如下：

(2)

s.t.

2M1yte-M1≤xe-qe≤M1

?e∈Ete∈T

(3)

xe≥qe?e∈Edep

(4)

?e∈Ete∈T

(5)

(6)

(7)

(8)

yt∈{0，1} ?t∈T

(9)

(10)

目標函數(shù)式(2)表示最小化加權求和列車取消和偏離計劃懲罰值。約束條件式(3)中：te表示事件e所對應的列車，此外，約束條件式(3)實現(xiàn)了把取消的列車移到研究范圍之后，這里表示把取消的列車移到一天之后，即取消列車的事件的實際發(fā)生時刻xe=qe+M1。將取消的列車移到研究范圍之后能很好地避免被取消的列車相互間以及被取消的列車與其他列車之間的干擾。約束條件式(4)表示列車的出發(fā)時刻不能早于圖定的出發(fā)時刻。約束條件式(5)表示事件e的晚點時間。約束條件式(6)表示到達事件e的早點時間，注意，結(jié)合鐵路的實際情況，本文允許列車提前到達車站，但是不允許列車在車站提前發(fā)車。約束條件式(7)和式(8)分別表示列車晚點時間和到達早點時間不能超過的最大允許值。約束式(9)和式(10)限定變量的取值范圍。

2.3 其他約束

列車在高速鐵路線路上運行需要占用設備資源，因此，必須要滿足設備的能力約束，此外，在干擾情況下列車的運行還需要遵守各種運營規(guī)則及安全約束。本文將這些約束大體上分為：單列列車運行及停站約束、相鄰列車運行間隔約束、車站能力約束、列車取消約束及列車運行均衡性約束等幾個方面。

(1)單列列車運行及停站約束

在線路能力部分失效情況下，雖然列車的運行受到區(qū)間故障的影響，但是對單列列車而言，其從始發(fā)站運行到終到站所經(jīng)過的所有事件e和活動a的順序都是固定的。每列車在運行過程中必須要滿足其在各區(qū)間的最小運行時間約束以及在各車站的停站時間約束。具體約束條件如下：

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

(11)

式中：e，f分別表示同一列車先后占用同一資源的兩個相鄰事件；a=(e，f)表示1個列車活動，既可以是列車在區(qū)間的運行活動，也可以是列車在車站的停站活動。當a表示區(qū)間運行活動時，La表示列車在區(qū)間的最小運行時間；當a表示車站停站活動時，La表示列車在車站的最小停站時間。

(2)相鄰列車運行間隔約束

為了保證行車安全，避免列車之間的沖突，相鄰列車之間必須要滿足運行間隔約束，主要有列車在區(qū)間的運行間隔約束和在車站同一條到發(fā)線的發(fā)到間隔約束。這里只對前者進行建模，后者將在車站能力約束部分進行分析。正常情況下，高速鐵路區(qū)間運行間隔只包括相鄰同向列車之間的出發(fā)間隔和到達間隔兩種，但當區(qū)間能力部分失效時，故障時段內(nèi)故障區(qū)間將組織雙向行車，因此，不僅相鄰同向列車之間需要滿足出發(fā)間隔和到達間隔約束，而且相鄰對向列車之間也需要滿足到發(fā)間隔約束?？紤]到區(qū)間能力部分失效情況下，不同等級列車間甚至同等級列車之間都可能存在越行，兩列車在車站的到發(fā)順序與原計劃相比可能發(fā)生變化，本文定義一個表示事件發(fā)生先后順序的0-1變量λef。

(12)

為了確保列車的運行安全，在任意區(qū)間任意時段內(nèi)同向相鄰列車之間以及故障區(qū)間故障時段內(nèi)反向相鄰列車之間必須要滿足最小區(qū)間運行間隔約束，如式(13)、式(14)所示。

xf-xe+M2(1-λef)≥La?a=(e，f)∈Ahead

(13)

λef+λfe=1 ?(e，f)∈Ahead∧(f，e)∈Ahead

(14)

式中：e、f為需要占用同一列車運行資源的兩個相鄰事件；M2是一個足夠大的正數(shù)，M2大于M1；a=(e，f)表示列車在區(qū)間的運行間隔活動，既可能是同向列車在同一站的出發(fā)間隔或者到達間隔，也可能是反向列車在同一站的到發(fā)間隔；La表示兩列車在同一區(qū)間的最小運行間隔時間。式(13)中M2必須大于M1，因為基本模型將取消的列車移到了一天的最后面，只有M2大于M1才能保證取消列車與其他列車的區(qū)間運行間隔也得到滿足。式(14)表示同向兩列車在同一站的出發(fā)或到達以及反向兩列車在同一站的到發(fā)必須滿足先后順序。式(13)和式(14)表示相鄰的兩列車te和tf在區(qū)間的最小運行間隔時間必須滿足。

te=te′tf=tf′(s，s′)∈Seg

(15)

式(15)表示對于任意兩個相鄰車站之間的區(qū)間(s，s′)，若同向運行的列車te先于tf在車站s出發(fā)，則列車te也先于tf在車站s′到達，由此，不會產(chǎn)生一列車在區(qū)間越行另一列車的情況。

(3)車站能力約束

每一列車在每個車站的到達停車或者通過(如果按照運行圖不需要停車)都需要占用車站的線路，由于資源的獨占性，一條車站線路在某一段時間內(nèi)只允許1列車占用，因此同一時間在每個站的列車的數(shù)量不能超過車站到發(fā)線數(shù)量。鑒于高速鐵路的始發(fā)站s1和終到站sn(線路的端點站)都是大站，本文假設其到發(fā)線能力充足，只考慮中間站的能力約束，定義Sm表示線路中間站集合，s∈Sm?S，s≠s1，s≠sn?；诒疚募僭O(1)，可以分別考慮車站上下行的到發(fā)線能力約束。

在車站到發(fā)線能力約束下，必須要為每一列下行(上行)到達列車分配一條下行(上行)車站線路，即需要保證每列下行列車(上行列車)到達車站時最少有一條空閑的下行(上行)線路可供使用。在每列下行列車到達每個中間站時可先統(tǒng)計出在該列車之前到達該車站的下行列車總數(shù)和在該列車到達之前從該車站發(fā)出的下行列車總數(shù)，進而，便可得到在該下行列車到達車站時停在車站的下行列車總數(shù)，然后把該車站下行線路數(shù)量減去停在車站的下行列車的數(shù)量就得到了車站下行方向的剩余能力，用相似的方式可以得到每個中間站在每列上行列車到達時該站的上行方向的剩余能力。

定義車站活動a=(e，f)∈Astation表示在某車站的某出發(fā)列車與后續(xù)同方向某到達列車之間的活動，Astation表示車站活動的集合，La表示從車站同一條到發(fā)線上出發(fā)的列車與后續(xù)同方向到達列車之間的最小間隔時間。對車站活動a定義0-1變量φa如下

(16)

(17)

(18)

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

?a=(e，f)∈Astation

(19)

(4)列車取消約束

根據(jù)我國高速鐵路運營的特點，在故障發(fā)生時已經(jīng)在線路上運行的列車一般不能被取消，因為取消這樣的列車將會導致大量的旅客滯留在中間車站而不能到達其目的地。但是，對于在故障發(fā)生時還沒有從始發(fā)站出發(fā)的列車，調(diào)度員可以結(jié)合列車實時運行狀況和現(xiàn)場故障信息來決定是否需要在這部分列車中選擇幾列列車取消運行，從而在設備能力允許的情況下，最小化故障對列車運行的影響。結(jié)合現(xiàn)場實際，增加列車取消約束如下

(20)

式中：tdep表示列車t在其始發(fā)站的發(fā)車時刻。

(5)列車運行均衡性約束

當故障導致線路能力部分失效時，可能有一部分列車由于線路通行能力下降而需要取消運行。在考慮取消列車運行時，與同時取消兩個方向的列車相比，只取消一個方向的列車更有利于提高線路的通過能力，從而減少取消列車的數(shù)量。但是，在實際的調(diào)度指揮過程中，鐵路運輸部門并不偏向于采用這種只考慮取消單方向列車的方式，因為這樣會造成雙向運輸?shù)臉O大不均衡性，不僅會導致一個方向的運輸質(zhì)量大為降低，而且還會導致動車組不能接續(xù)的問題。考慮到動車組的周轉(zhuǎn)要求，鐵路運輸部門更傾向于均衡地取消雙方向的列車，基于此，添加列車運行均衡性約束。定義上下行列車集(p，p′)，其中p和p′分別表示上下行兩個方向的同類型列車的集合，這里列車類型主要包括1類列車和2類列車，則列車運行均衡性約束可表示為

?t∈T

(21)

(22)

式中：δ為常量，表示上下行方向取消的同類型列車數(shù)量的允許差值，該值與始發(fā)終到站備用動車組的類型和數(shù)量有關。式(21)和式(22)表示雙向同類型列車取消的數(shù)量之差不能超過允許值δ。

此外，我國高速鐵路普遍配備CTCS-2或CTCS-3列控系統(tǒng)，采用自動閉塞，實行列車追蹤運行，此種列控模式顯著地提高了線路的通過能力。在高速鐵路某區(qū)間能力部分失效的情況下，線路的通行能力下降，雙向列車在故障區(qū)間可共線運行，此時，若組織同向列車以多列追蹤的方式通過故障區(qū)間能提高故障區(qū)間線路的通過能力，從而提高整條線路的通行能力。然而，同向列車多列追蹤運行的方式也可能會帶來一定的問題，比如說列車到發(fā)均衡性降低，可否組織多列車在故障區(qū)間追蹤運行以及組織多少列列車追蹤都值得探討。

需要說明的是，本文不直接建模列車到發(fā)的均衡性約束，但本文指出通過適當?shù)乜刂剖录畲笤试S偏離時間D的取值能夠間接地確保列車到發(fā)的均衡性，原因在于計劃列車運行圖在鋪畫時已經(jīng)考慮了列車到發(fā)的均衡性，通過控制參數(shù)D可限制列車運行偏離原計劃的程度，從而可以間接控制列車到發(fā)的間隔，以大體上維持列車在計劃運行圖中的到發(fā)均衡。

(6)故障前列車運行約束

根據(jù)本文假設(4)，由于在故障發(fā)生之前難以預測故障的發(fā)生，因此，假設所有列車在故障發(fā)生之前按計劃運行圖運行。該假設可以用式(23)表示

(23)

(7)有效不等式約束

顯然，若1列車在某個車站的出發(fā)在另一同向列車在該車站的到達之前，則該列車在該站的到達也一定在另一列車在該站的到達之前。雖然前面的約束已隱含了這一事實，但是，加上這個有效不等式有利于加快模型的求解速度。該有效不等式可以表示為

λef≥φa′?a=(e，f)∈Ahead

te，tf∈Tdown∨te，tf∈Tup

(24)

不等式(24)中：e，f分別表示同向列車te和tf在車站s的到達事件；e′表示列車te在車站s的出發(fā)事件。式(24)表示如果同向列車te在tf到達車站s之前從車站s出發(fā)，那么列車te也一定在列車tf之前在車站s到達。

2.4 現(xiàn)場調(diào)度策略建模

如前文所述，從理論上講，在高速鐵路區(qū)間由于故障導致部分能力失效的情況下，在故障區(qū)間對兩個方向的列車都實行追蹤運行最有利于提高線路的通過能力，從而最大程度地減小干擾對整個列車運行的影響。但是，根據(jù)我國高速鐵路調(diào)度指揮的實際情況，調(diào)度員并非同等程度地對待兩個方向的列車，而是給在正常線路上運行的列車更高的優(yōu)先權。具體地，假如某區(qū)間的上行線路在某時刻出現(xiàn)故障不能行車，由我國高速鐵路現(xiàn)場的調(diào)度策略，調(diào)度員允許下行列車(正向列車)在故障區(qū)間仍然追蹤運行，而上行列車(反向列車)不能繼續(xù)追蹤，只能按半自動閉塞非追蹤運行。顯然，現(xiàn)場調(diào)度策略不僅會導致上下行動車組不能很好地接續(xù)，還會降低整個線路的通過能力，具體將在后文的算例分析部分得到體現(xiàn)。

假設故障區(qū)間為(s，s′)， 其中，s′是s的沿列車運行方向的前方車站。為了滿足現(xiàn)場調(diào)度策略的要求，保證故障持續(xù)時間內(nèi)反向列車不能繼續(xù)在故障區(qū)間追蹤運行，在故障區(qū)間(s，s′)內(nèi)，兩列相鄰的反向列車t1和t2之間的最小發(fā)車間隔時間h1-2應大于等于前行列車t1在區(qū)間的運行時間h1，即后行列車t2在后方車站s的出發(fā)時刻應該不小于前行列車t1在前方車站s′的到達時刻，如圖2所示，其中，左右兩個子圖分別表示上行和下行線路故障下故障區(qū)間兩列相鄰的上行和下行反向列車的運行圖。

圖2 現(xiàn)場調(diào)度策略下相鄰同向列車之間的最小發(fā)車間隔時間

te=te′te≠tf(s，s′)∈Seg

(25)

需要說明的是，在現(xiàn)場調(diào)度策略下，故障區(qū)間的通過能力下降，同時也會導致原本在故障線路上運行的列車由于不能追蹤運行而使晚點量增加，所以，為了保證將現(xiàn)場調(diào)度策略約束式(25)加入標準模型后仍能找到可行解，需適當增大事件最大允許偏離時間參數(shù)D的值，具體分析如圖3所示。

圖3 不同調(diào)度策略下事件最大可能晚點時間

圖3表示了區(qū)間(s，s′)下行線路能力失效情況下，基于不同的調(diào)度策略，在兩列追蹤運行的上行列車t1和t2中，列車t2需要在車站s′的最大可能等待時間，左子圖為基于本文均衡調(diào)度策略的結(jié)果，右子圖為基于現(xiàn)場非均衡調(diào)度策略的結(jié)果，其中，t3和t4為兩列下行列車，I表示兩相鄰同向列車在故障區(qū)間(s，s′)的追蹤間隔，τ表示兩相鄰反向列車在故障區(qū)間端點車站s或車站s′的到發(fā)間隔。

令hi表示列車ti在故障區(qū)間(s，s′)的最小運行時間，在本文的均衡調(diào)度策略下，列車t2需要在車站s′的等待時間W2如式(26)所示。

W2=h3+τ

(26)

(27)

2.5 模型求解

從數(shù)學性質(zhì)來看，本文構建的高速鐵路區(qū)間能力部分失效情況下的列車運行調(diào)整模型屬于混合整數(shù)線性規(guī)劃模型(MILP)的范疇。近年來，隨著數(shù)學理論和計算機技術的發(fā)展，一些商業(yè)化的優(yōu)化軟件功能越來越強大，能夠求解數(shù)百萬計變量和約束的整數(shù)線性規(guī)劃問題。本文針對模型的特點，采用商業(yè)優(yōu)化軟件CPLEX來對模型進行求解，該軟件內(nèi)置的分支切割算法能夠很好地用于求解本文的混合整數(shù)線性規(guī)劃問題。

3 算例分析

3.1 算例描述

以京滬高速鐵路為例，根據(jù)2013年調(diào)整后的列車運行圖及相關數(shù)據(jù)進行算例分析。京滬高速鐵路從北京南站到上海虹橋站，沿線經(jīng)過23個車站(不包括天津西站)，這些車站將全線劃分為22個區(qū)間。京滬高速鐵路是我國的繁忙干線之一，列車開行密度大，日行車量超過100對。選擇上海虹橋站和北京南站之間的42對上下行長途列車(包括從杭州等地經(jīng)過上海虹橋到北京南的跨線列車)對本文提出的模型進行驗證，其中，速度250 km/h的2類列車4列，速度300 km/h的1類列車80列。需要說明的是，雖然考慮的84列列車中只有4列為2類列車，大部分列車都為1類列車，但是由于同等級列車也有不同的停站模式，導致同等級列車之間也存在一定的差異，也會有列車相互越行的情況。

算例參數(shù)按以下規(guī)則進行設置。目標函數(shù)中，考慮到列車取消對旅客服務產(chǎn)生的影響很大，列車取消懲罰值相對比較大，同時，相比于列車出發(fā)晚點而言，旅客更在意到達晚點，因此，給到達晚點更大的懲罰值。具體地，1類列車和2類列車取消運行的懲罰值按照其票價比率分別取為5 000和3 000，同時，兩類列車在車站到達晚點1 min的懲罰值分別取為5和3，出發(fā)晚點1 min的懲罰值分別取為3和2，到達早點1 min的懲罰值分別取為2和1。注意，懲罰系數(shù)的具體取值可以根據(jù)現(xiàn)場的經(jīng)驗靈活調(diào)整，本文不作重點研究，如果有需要可以對多組取值進行計算，有興趣的讀者可以參看文獻[19]。事件最大允許偏離時間D取為40 min，在3.4節(jié)將針對不同的D值進行討論。中間站可使用的到發(fā)線數(shù)量參照“京滬高速鐵路動車組停車站到發(fā)線安排”取值，見表1。注意，算例只考慮42對長途列車，該部分列車的數(shù)量大概占所有列車的一半，因此，中間站的能力大概設置為其實際能力的一半。另外，在減小車站能力時，充分保證計劃運行圖的可行性，即如果根據(jù)計劃運行圖在某站某方向存在列車越行，那么該站該方向必須要保證最少有兩條線路可以使用。表1中股道數(shù)所在列的第一個值表示下行方向列車可使用的股道數(shù)量，第二個值表示上行列車可以使用的車站股道數(shù)量。列車區(qū)間運行時間和車站停站時間由計劃列車運行圖給出，列車在區(qū)間運行時間取“京滬高鐵區(qū)間運行時間標準”相應數(shù)值，見表2，列車在車站的最小停站時間取為計劃運行圖上的停站時間。參考文獻[20]以及京滬高速鐵路的實際資料，同向列車的最小出發(fā)間隔和最小到達間隔分別取為2 min和3 min，同向列車在同一到發(fā)線的最小發(fā)到間隔取為3 min，反向列車在共用故障區(qū)間線路上的最小到發(fā)間隔取為3 min。上下行同類型列車取消數(shù)量的允許差值δ取為1，M1取為1 440，M2取為2 880。計劃列車運行圖如圖4所示。

表1 京滬高鐵中間站股道數(shù)量

表2 區(qū)間最小運行時間

注：同類列車在同一區(qū)間上下行最小運行時間相同。

注：紅色線表示1類列車，藍色線表示2類列車；車站沿下行方向從0開始依次編號。圖4 北京南和上海虹橋之間42對長途列車計劃運行圖

結(jié)合京滬高速鐵路的基本情況，通過調(diào)整故障發(fā)生的時間和地點設計3種故障場景，每種故障場景下再通過調(diào)整故障持續(xù)時間分別設置3種干擾情景。3種故障場景及其各自對應的3種干擾情景具體設置如下：

故障場景1：在10：30，由于某種原因?qū)е戮哞F德州東站—濟南西站之間的上行線路出現(xiàn)故障，區(qū)間上行通行能力喪失，調(diào)整故障持續(xù)時間設置3種干擾情景，其故障持續(xù)時間分別為60 min、90 min和120 min。

故障場景2：在13：30，徐州東站—宿州東站之間的線路區(qū)間下行線路出現(xiàn)故障，導致該區(qū)間下行線路通行能力失效60 min、90 min和120 min。

故障場景3：在17：30，南京南站—鎮(zhèn)江西站之間的線路區(qū)間由于故障導致該區(qū)間上行線路能力失效60 min、90 min和120 min。

為了便于描述不同故障場景下的干擾情景，定義1個三元組(a，b，c)，其中，a表示故障發(fā)生時刻，b表示故障所在區(qū)間，c表示故障持續(xù)時間。3種故障場景下的9種干擾情景用所對應的三元組進行表示的結(jié)果見表3。

3.2 計算結(jié)果

在CPU為Inter(R)Core(TM)i7-4600U 2.1 GHZ，內(nèi)存為8 GB，操作系統(tǒng)為Windows8.1的64位電腦上采用IBM ILOG OPL(Optimization Programming Language)編程，并調(diào)用CPLEX 12.6對所提出的模型進行求解。在CPLEX中，相關參數(shù)設置為其默認值，求解算法選擇內(nèi)置的將分支定界法和割平面法相結(jié)合的分支切割算法。鑒于列車運行調(diào)整的實時性要求，限制程序的最長運行時間為5 min。3.1節(jié)中3種故障場景下9種干擾情景的列車運行調(diào)整計算結(jié)果見表4。需要說明的是，通過初步計算測試發(fā)現(xiàn)，在故障結(jié)束較長時間之后列車基本上能夠恢復計劃圖運行，因此，為了減小干擾對列車正常運行的影響范圍，測試算例中假定故障結(jié)束5 h后列車恢復正常運行。

表4 不同干擾情境下的列車運行調(diào)整結(jié)果

表4續(xù)

從表4可以看出，不同的故障場景和干擾情景對列車運行的影響各不相同。接近中午時刻(13：30)發(fā)生在線路中部的干擾對列車運行的影響最為嚴重，如故障場景2中的干擾對列車運行的影響大于故障場景1、3。同一故障場景下，通常干擾持續(xù)時間越長，對列車運行的影響越大。但是，需指出的是，故障場景3中故障持續(xù)90 min和120 min產(chǎn)生的影響是一樣的，原因在于故障發(fā)生的比較晚，此時大多數(shù)列車都已經(jīng)通過了故障區(qū)間，受影響的列車很少。關于計算時間，本文模型對所有的干擾情景都可在100 s的時間內(nèi)快速獲得最優(yōu)的列車運行調(diào)整方案，可見該模型能較好地滿足現(xiàn)場調(diào)度員實時決策的需要。

接下來分析基于本文模型均衡調(diào)度策略的質(zhì)量，限于篇幅，只以干擾情景(13：30，11，120)為例，其基于本文模型的列車運行調(diào)整圖如圖5所示。如前文所述，理論研究成果已表明，相比于非追蹤運行，單線鐵路采用追蹤運行能力更大，所以對于區(qū)間能力部分失效情況，最佳的調(diào)度策略應是對故障區(qū)間在故障時段內(nèi)實行列車追蹤運行，以最小化列車運行受干擾的影響。圖5顯示了對于干擾情景(13：30，11，120)，本文模型首先調(diào)度1列上行列車運行，然后是3列下行列車追蹤，接著是2列上行列車追蹤，最后是3列下行列車追蹤，也就是說，間隔調(diào)度兩個方向的列車追蹤運行，體現(xiàn)了本文模型可獲得最佳的調(diào)度策略。

注：綠色塊表示故障，紅色和藍色線分別表示1和2類列車的運行線，黑色線表示列車運行線偏離了原始運行計劃。

圖5 干擾情景(13：30，11，120)的列車運行調(diào)整圖

3.3 與現(xiàn)場調(diào)度策略的比較

比較表4和表5可發(fā)現(xiàn)，在相同的故障場景下，相比于目前我國高速鐵路普遍采用的只允許故障區(qū)間故障時段內(nèi)單向追蹤的非均衡調(diào)度策略，本文提出的允許故障區(qū)間故障時段內(nèi)雙向追蹤的均衡調(diào)度策略可獲得更好的列車運行調(diào)整結(jié)果。當故障發(fā)生在接近中午并處于線路中部時，與現(xiàn)場的非均衡調(diào)度策略相比，本文的均衡調(diào)度策略能使列車由于干擾而偏離原計劃的懲罰值減小超過一半，更為直觀地比較如圖6所示。由此可見，當高速鐵路區(qū)間線路部分失效時，調(diào)度員應該在條件允許的情況下采用均衡調(diào)度策略，以在盡可能保證列車運行均衡性的前提下最大程度地減小故障對列車運行的影響。需要說明的是，高速鐵路的信號設備具備組織單條正線雙向追蹤運行的條件是實施均衡調(diào)度策略的前提。

表5 基于現(xiàn)場調(diào)度策略的列車運行調(diào)整結(jié)果

為了更為形象地顯示本文均衡調(diào)度策略與現(xiàn)場非均衡調(diào)度策略的區(qū)別， 干擾情景(13：30，11，120)基于現(xiàn)場非均衡調(diào)度策略的列車運行調(diào)整圖如圖7所示。從圖7可以看出，由于區(qū)間11下行線路故障，在現(xiàn)場調(diào)度策略下，只有上行列車可以追蹤，而下行列車由于線路故障不能追蹤，最終故障區(qū)間故障時段內(nèi)在正常的上行線路只放行了7列列車(上行3列，下行4列)。對于同樣的干擾情景，本文調(diào)度策略可放行9列列車。注意，這里只統(tǒng)計故障發(fā)生之后才進入故障區(qū)間的列車，因為由本文假設(4)，在故障發(fā)生時已經(jīng)進入故障區(qū)間的列車無論在哪種調(diào)度策略下都將按計劃運行圖運行。顯然，在信號設備允許的情況下，本文的均衡調(diào)度策略明顯優(yōu)于現(xiàn)場的非均衡調(diào)度策略。根據(jù)現(xiàn)場調(diào)研了解到，大部分高鐵的沿線技術設備都滿足組織雙向列車追蹤運行的條件，但是，由于目前的調(diào)度系統(tǒng)連鎖設備不滿足組織反向列車追蹤運行的條件，因此，高速鐵路非正常情況下行車組織中規(guī)定：在區(qū)間一條線路封鎖的情況下，只允許正向列車追蹤運行，反向列車只能按站間控制的方式來組織列車運行。

圖6 兩種調(diào)度策略下的目標函數(shù)值

3.4 事件最大允許偏離時間靈敏度分析

前文已述，在所提出的模型中，事件最大允許偏離時間D是很重要的參數(shù)，其值需合理設置。若參數(shù)D設置的相對比較小，則在故障區(qū)間故障時段內(nèi)，同向追蹤運行的列車數(shù)量將減少，以至于降低故障區(qū)間的通過能力，并惡化整個問題的目標函數(shù)。更為嚴重的是，若參數(shù)D設置的太小，因為本文假設在故障發(fā)生前已經(jīng)出發(fā)的列車不能取消運行，則有可能會導致整個問題無可行解。當然，小的參數(shù)D可以獲得列車到發(fā)相對均衡的列車運行調(diào)整方案。反之，若參數(shù)D設置的相對比較大，則在故障區(qū)間的故障時段內(nèi)，同向列車將盡可能多地追蹤運行，以提高故障區(qū)間的通過能力，并最小化整個問題的目標函數(shù)。但是，過大的參數(shù)D也有可能影響計劃運行圖中列車到發(fā)的均衡性，導致調(diào)整圖中列車運行極為不均衡，這同樣是需要避免的。

圖7 干擾情景(13：30，11，120)基于現(xiàn)場調(diào)度策略的列車運行調(diào)整圖

本節(jié)分別以故障場景1和2中的3個干擾情景為例，采用靈敏度分析方法評估參數(shù)D對整個問題目標函數(shù)的影響。對于故障場景1，通過計算測試發(fā)現(xiàn)，當D值小于24 min時，會導致原問題無解，所以D值最小取為24 min，逐步增加到30 min，步長為1 min，靈敏度分析結(jié)果如圖8所示。同理，針對故障場景2，從使原模型有解的最小D值37 min依次增加到41 min，所得的靈敏度分析結(jié)果如圖9所示。值得說明的是，由于故障場景3下，列車受故障影響很小，所以D值對最終結(jié)果的影響不大，不對其作靈敏度分析。

圖8 故障場景1下事件最大允許偏離時間靈敏度分析

圖9 故障場景2下事件最大允許偏離時間靈敏度分析

從圖8和圖9可以看出，當D值增加時，目標函數(shù)值下降，體現(xiàn)了D值與目標函數(shù)值的反相關關系。但是，當D值增加到一定數(shù)值之后，其對計算結(jié)果的影響已不明顯。對于故障場景1，當D值大于等于26 min時，其對目標函數(shù)值的影響基本保持不變，意味著場景1中3種干擾情景的D值都可設置為26 min，以最大程度地維持列車到發(fā)的均衡性。類似地，對于故障場景2，為盡量避免影響列車在計劃運行圖中的均衡性，其3種干擾情景的D值都可取為40 min?；陟`敏度分析結(jié)果，調(diào)度員可更為清楚地認識參數(shù)D的作用，從而更為有效地權衡列車運行調(diào)整的質(zhì)量與列車到發(fā)的均衡性。

4 結(jié)束語

本文引入事件和活動的概念將我國高速鐵路網(wǎng)絡從宏觀層面上抽象為由事件和活動構成的網(wǎng)絡，基于此對高速鐵路區(qū)間能力部分失效情況下列車運行實時調(diào)整問題進行了闡述。在考慮列車運行安全約束以及設備能力約束的基礎上，建立了基于列車均衡運行的高速鐵路區(qū)間能力部分失效情況下列車運行實時調(diào)整的MILP模型。結(jié)合我國高速鐵路列車運行調(diào)整的實際情況，模擬了在現(xiàn)場調(diào)度員普遍采用的非均衡調(diào)度策略。

以京滬高速鐵路全天上下行42對長途列車的實際數(shù)據(jù)為依據(jù)，考慮到高速鐵路線路故障的隨機性和不確定性，假設了三種不同故障場景，并又各自分別設置了三種不同干擾情景。采用本文模型對各種干擾情景下的列車運行實時調(diào)整方案進行了計算。同時，通過與目前我國高鐵調(diào)度員通常采用的只允許單向列車追蹤運行的非均衡調(diào)度策略進行了對比，突出了本文的均衡調(diào)度策略在減小故障對整個列車運行影響方面的優(yōu)越性。

區(qū)間能力部分失效情況下的列車運行調(diào)整是大規(guī)模組合優(yōu)化問題，整個問題的求解非常困難。為了滿足實時的需要，本文只針對列車運行圖調(diào)整從宏觀層面上進行了研究，通過建模列車運行的均衡性，間接地考慮了動車組的周轉(zhuǎn)。算例中也僅考慮了長途列車，還需要對所有列車包括短途和跨線列車進行研究。此外，本文是基于假設故障持續(xù)時間已知的情況下，對列車運行調(diào)整問題進行了研究，考慮到故障的不確定性，將本文模型擴展到處理故障持續(xù)時間不確定情況下的列車運行調(diào)整問題也是下一步研究的重點。

參考文獻：

[1]CACCHIANI V,HUISMAN D,KIDD M P,et al.Anoverview of Recovery Models and Algorithms for Real-time Railway Rescheduling[J].Transportation Research Part B:Methodological,2014,63(5):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,SCH?BELA.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,SCH?BELA.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,46(1):74-89.

[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 Railway Timetable Rescheduling Approachfor Handling Large Scale Disruptions[J].Transportation Science, 2016,50(3):841-862.

[13]文超.高速鐵路列車運行沖突管理研究[D].成都：西南交通大學,2011:12-16.

[14]MENG L Y，ZHOU X S.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):1 080-1 102.

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

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

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

MENG Lingyun,YANG Zhaoxia,LI Haiying.Train Dispatching Models Under Field Capacity Breakdowns on Single-track Railway Lines[J].Systems Engineering-Theory&Practice,202,32(4)：885-894.

[18]占曙光，趙軍，彭其淵，等.高速鐵路區(qū)間能力全失效條件下列車運行實時調(diào)整研究[J].鐵道學報，2015，37(11):1-9.

ZHAN Shuguang,ZHAO Jun,PENG Qiyuan,et al.Real-time Train Rescheduling on High-speed Railway under Complete Segment Blockages[J].Journal of the China Railway Society,2015，37(11):1-9.

[19]ZHAN S G,KROON L G,VEELENTURF LP,et al.Real-time High-speed Train Rescheduling in Case of a Complete Blockage[J].Transportation Research Part B:Methodological,2015,78(8):182-201.

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

SHI Feng,WEI Tangjian,ZHOU Wenliang,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.