高速鐵路車站列車進路分配方案的優化與調整

馬　駟，孫建康，魯工圓

(1.西南交通大學 交通運輸與物流學院，四川 成都　610031；2.西南交通大學 綜合交通運輸智能化國家地方聯合工程實驗室，四川 成都　610031)

高速鐵路車站列車進路分配是車站作業計劃的關鍵工作，也是維持運輸網絡穩定和高效的決定性因素。國外學者往往將經過簡化和抽象的列車進路排序模型應用于車站作業計劃自動化編制和動態調整工作當中。在列車進路分配模型構建方面，Zwaneveld等[1-2]和Kroon等[3]分別從不同的角度考慮列車進路排序問題，并抽象為節點封裝問題，建立了該問題的整數規劃模型；Lusby等[4]以車站的可行進路數最大化為主要目標，將列車在車站的可行進路排列問題抽象為加權的節點壓縮模型，并應用分枝定界方法求解，該模型可以處理許多大規模的進路。在列車進路分配方案調整方面，D’Ariano等[5]和Caprara等[6]考慮隨機擾動情況，深入研究列車進路分配方案調整方法；Chakroborty等[7]設定列車到達車站的最終時間點在列車到達車站前一段時間才能夠確定，通過產生列車延誤達到列車到發線分配方案動態調整的目的；Corman等[8]針對鐵路車站實際運營中出現突發事件的情況，以最小化列車延誤時間為優化目標，通過調整列車停站時間、列車速度、進站順序及進路分配等，實現車站作業計劃的動態調整。但以上這些研究對咽喉區和到發線的制約關系考慮較少。當然，部分學者在對鐵路通過能力的研究中探討了車站設備的運用關系，對理清咽喉區和到發線之間的關系具有一定的參考意義[9]。

我國高速鐵路車站采用平面布局形式，咽喉區結構復雜，列車進路交叉干擾大，對于列車進路分配問題的研究重點圍繞咽喉區和到發線展開。劉瀾等[10]將咽喉區線路抽象成1個多源多匯的網絡，建立車站咽喉作業占用安排網絡優化和咽喉作業能力復合遞階決策模型，并實現計算機運算；史峰等[11]通過構建咽喉區的有向網絡對咽喉區的進路進行優化；呂穎等[12]提出了具有普適性的高速鐵路車站到發線優化運用非線性規劃模型；王保山等[13]研究了以利于乘降作業和均衡使用車站設備為指標的到發線運用多目標優化模型。但是，文獻[10—11]中，單純的咽喉區網絡化研究未充分考慮多項作業同時進行時，到發線對咽喉網絡占用的制約性，難以應用于實踐；文獻[12—13]中，單純的到發線運用優化研究僅僅針對的是列車占用到發線，未考慮咽喉區使用的合理性。

基于以上分析，建立咽喉區和到發線一體化運用模型至關重要，相關研究也逐漸跟進，如趙鵬等[14]建立到發線和咽喉區綜合優化模型，運用模擬退火算法求解，但模型對部分作業過程進行了簡化處理。總體來說，這種咽喉區和到發線的一體化研究尚不成熟。

本文依據高速鐵路車站平面圖和列車運行圖，考慮咽喉區和到發線的連通性、車站設備的運用，以及各種類型列車的車站作業過程與列車進路的關系，結合道岔分組的方法，建立咽喉區和到發線一體化運用的列車進路分配方案優化模型及其動態調整模型，采用運籌學軟件LINGO中內置的分支定界算法求解，得到高速鐵路車站列車進路分配的優化方案和動態調整方案。

1　車站作業過程與列車進路關系

列車進路是指列車在車站到、發、通過、折返、動車出入段過程中占用的車站內部一段線路。部分學者認為“當列車通過咽喉區的進路確定后，到發線也隨之確定”[15-16]，這里的“進路”指的就是列車進路。車站作業過程與列車進路是一一對應的，不同種類列車的車站作業過程與列車進路的對應關系見表1。

表1　不同種類列車車站作業過程與列車進路對應關系

從車站設備角度考慮，列車進路包括過咽喉區徑路和到發線兩部分。

(1)過咽喉區徑路。過咽喉區徑路由若干道岔組組成，以圖1為例對過咽喉區徑路進行簡要分析。辦理接車作業可以占用的過咽喉區徑路為①→②，①→③，辦理站前折返作業可以占用的過咽喉區徑路為②→①→④，③→④；由于①→②，①→③，②→①→④這3條徑路共用道岔組①，故這3條徑路相互干擾，不可同時被占用；②→①→④和③→④這2條徑路共用道岔組④，故這2條徑路亦相互干擾，不可同時被占用；①→②和③→④這2條徑路不存在共用道岔組，故這2條徑路不相互干擾，可以同時被占用；此外，同一過咽喉區徑路占用的道岔組完全一致，亦可視為相互干擾、不可同時被2個車站作業過程占用；依據這樣的原則，可逐步理清整個車站所有過咽喉區徑路之間的關系。

圖1　某車站一端部分咽喉區道岔分組圖

(2)到發線。到發線之間相互獨立，1個車站作業過程只能占用1條到發線，相鄰2個車站作業過程占用同一條到發線，則需滿足到發線使用最小間隔時間的要求。

過咽喉區徑路和到發線之間的關系可表述為：1條過咽喉區徑路通常連接多條到發線；列車到達固定到發線往往有多條過咽喉區徑路可以選擇；二者相互聯系、相互制約。

基于以上分析，本文的研究重點是在咽喉區和到發線一體化運用的基礎上，通過建立列車進路分配方案的優化模型和動態調整模型，確定某一時段從第1個車站作業過程開始占用車站設備時起至最后1個車站作業過程清空車站設備時止列車占用咽喉區和到發線的時序排列方案。

2　列車進路分配方案優化模型的建立

2.1　模型假設

(1)已知高速鐵路車站站場布置、到發線固定使用方案、列車種類及到發時刻。

(2)列車嚴格按照高速鐵路車站各項時間標準進行作業。

(3)不考慮軌道電路的分段解鎖，通過道岔分組表達列車進路間的邏輯關系。

2.2　變量及參數說明

P為車站在某時段接發所有列車的集合，按照列車開始占用車站設備的時刻進行排序，記P={1,…,p,…,W}，其中W為列車總數，對于同時占用車站設備的不同列車，任取其1個優先排序；I為車站在該時段辦理所有車站作業過程的集合，根據其開始占用車站設備的時刻對車站作業過程進行排序，記I={1,…,ip,…,hp+q,…,M}，其中q為整數，M為車站作業過程總數，對于同時占用車站設備的不同車站作業過程，任取其1個優先排序；在已知列車運行圖的前提下，車站作業過程序號與列車序號均可推知且相互對應，這里將列車序號p作為車站作業過程序號ip的一項屬性。J為車站可用于接發列車的所有到發線集合，記J={1,…,j,…,m},其中m為到發線數量。K為車站接發列車的過咽喉區徑路集合，記K={1,…,k,…,k′,…,n}，其中n為過咽喉區徑路數量。U為車站咽喉區道岔組集合，記U={1,…,u,…,v}，其中v為咽喉區道岔組總數量。

(1)定義以下參量描述列車占用車站設備的時間狀況。

(2)定義以下0-1參量描述車站設備關系及到發線固定使用方案。

akj表示過咽喉區徑路與到發線之間的連通性關系，若過咽喉區徑路k與到發線j直接連通，則akj=1，否則akj=0；則有過咽喉區徑路和到發線的連通性矩陣An×m。bkk′表示過咽喉區徑路之間的關系，若2條過咽喉區徑路k與k′相互干擾，則bkk′=1，否則bkk′=0；則有各過咽喉區徑路之間的關系矩陣Bn×n。cipj表示車站作業過程ip可占用的到發線狀況，若車站作業過程ip可以占用到發線j，則cipj=1，否則cipj=0；則有車站作業過程可占用的到發線矩陣CM×m。dipk表示車站作業過程ip可占用的過咽喉區徑路狀況，若車站作業過程ip可以占用過咽喉區徑路k，則dipk=1，否則dipk=0；則有車站作業過程可占用的過咽喉區徑路矩陣DM×n。eku表示過咽喉區徑路與道岔組之間的關系，若過咽喉區徑路k包含道岔組u，則eku=1，否則eku=0；則有過咽喉區徑路與道岔組關系矩陣En×v。δrs為克羅內克爾符號，若r=s，則δrs=1；否則δrs=0。

(3)定義如下0-1決策變量，描述車站作業過程與過咽喉區徑路、到發線的關系。

2.3　列車進路分配方案優化模型

從設備利用率的角度考慮，為減少出現部分設備能力緊張而部分設備能力空費的情況，同類設備應均衡運用；從車站作業計劃質量的角度考慮，列車進路分配方案中到發線被占用的均衡性越強，其抗干擾能力往往越強[17]。因此，以車站作業過程占用到發線不均衡性最小為優化目標1，采用各到發線被占用時間的方差表示該不均衡性，即

(1)

以車站作業過程占用咽喉區道岔組的不均衡性最小作為優化目標2，并采用各道岔組被占用時間的方差表示該不均衡性，即

(2)

采用線性加權求和的方法，將多目標轉化為單目標，得到列車進路分配方案優化模型M1，即

minZ3=λ1Z1+λ2Z2

(3)

s.t.

(4)

(5)

(6)

xipj=cipjxipjip∈I;j∈J

(7)

yipk=dipkyipkip∈I;k∈K

(8)

δp(p+q)xipj=δp(p+q)xhp+qjip,hp+q∈I;j∈J

(9)

(1-δp(p+q))xhp+qjT1

ip,hp+q∈I且ip

(10)

bkk′yhp+qk′T2

ip,hp+q∈I且ip

(11)

(12)

目標函數式(3)中，λ1和λ2分別為目標函數Z1和Z2的權重。約束條件中：式(4)表示1個車站作業過程占用過咽喉區徑路和到發線有唯一方案；式(5)表示列車進路確定以后，到發線唯一確定；式(6)表示列車進路確定以后，過咽喉區徑路唯一確定；式(7)表示任意1個車站作業過程僅在其可以占用的到發線或正線上辦理；式(8)表示任一車站作業過程僅在其可以占用的過咽喉區徑路上辦理；式(9)表示同一方向、同一列車的不同車站作業過程必然占用同一條到發線；式(10)表示占用同一到發線的不同列車的前后2個車站作業過程之間的時間間隔必須不小于到發線安全使用間隔時間；式(11)表示占用2條相互干擾的過咽喉區徑路的前后2個車站作業過程之間的間隔時間必須不小于過咽喉區徑路安全使用間隔時間。

2.4　列車進路分配方案動態調整模型

定義集合Ωip={(j,k)|j=j*,k=k*}，表示模型M1所得的優化結果中車站作業過程ip的列車進路分配方案，該方案包含車站作業過程ip占用到發線j和過咽喉區徑路k的序號信息。引入決策變量Δtip，表示疏解列車進路的過程中車站作業過程ip產生的延誤時間。當某列車發生意外晚點，需為后續列車提供實時更新的列車進路分配方案，以保證車站接發車作業的流暢性。此外，由于允許后續列車發生延誤，后續車站作業過程占用同類車站設備的選擇性會更多，車站設備運用均衡性的可優化空間可能會進一步增大。以車站作業過程占用車站設備的不均衡性最小[模型M1中目標函數式(3)]和車站作業過程平均延誤時間最少為目標函數，建立后續列車進路分配方案的動態調整模型M2，即

模型M1中的目標函數式(3)

(13)

s.t.

模型M1中的式(4)—式(9)和式(12)。

模型M1中的式(10)和式(11)需考慮車站作業過程延誤時間，轉化為以下2個公式。

(1-δp(p+q))xhp+qjT1

ip,hp+q∈I且ip

(14)

ip,hp+q∈I且ip

(15)

這里要求列車嚴格按照時間標準作業，則同一列車包含的不同車站作業過程的延誤時間一致，即

δp(p+q)Δtip=δp(p+q)Δthp+qip,hp+q∈I

(16)

車站作業過程延誤時間屬于自然數集合Ν，且為避免個別列車過度延誤，需設定列車延誤時間的上限τ，則有

(17)

Δtip≤τip∈I

(18)

(19)

3　模型求解

分析所建立的模型M1和模型M2可知：2個模型均為非線性整數規劃模型，且目標函數中的式(3)和式(13)均為或可視為凸函數，不等式約束條件中的式(10)、式(11)、式(14)、式(15)、式(18)均為或可視為凹函數，等式約束條件中的式(4)—式(9)、式(16)—式(18)均為線性函數，因此2個模型均為凸非線性整數規劃模型。針對這一模型，本文運用LINGO軟件中內置的分支定界算法對模型加以求解，在提高求解效率的前提下尋求得到全局最優解。

在求解模型M2過程中，考慮到有2個量綱不一致的目標函數，而LINGO無法直接求解多目標規劃模型。由于這里需要優先保證后續車站作業過程占用設備的不均衡性最小，因此采取分層序列法將多目標規劃模型轉化為分層的單目標規劃模型求解，即首先在不考慮目標函數式(13)的前提下，將目標函數式(3)作為唯一目標，求出最優值，然后將此最優值作為約束條件，再求解目標函數式(13)的最優值，從而得到最優解。

4　算　例

以某高速鐵路車站A為例，采用本文提出的方法為該站高峰時段13對列車制定列車進路分配方案。對車站A兩端咽喉區進行道岔分組，得到如圖2所示車站平面圖。

圖2　高速鐵路車站A平面圖

圖2中：Ⅰ，3，5，7道接發下行列車；Ⅱ，4，6，8道接發上行列車；正線Ⅰ、Ⅱ兩側無站臺，只接發上、下行不停站通過列車；①，②，…，為咽喉區道岔組。

車站A在18:00—19:40客流高峰時段辦理的上、下行方向列車種類及到發時刻見表2。

采用CTCS-3級列車運行控制系統關于300 km·h-1等級高速列車車站技術作業時間標準[18]，見表3。對于通過列車，占用1個通過進路和1條正線，總的時間為3 min。取到發線安全使用間隔時間為2 min，過咽喉區徑路安全使用間隔時間為1 min。

結合列車到發時刻表，推算車站作業過程序號與列車序號的一一對應關系，見表4。

表2　18:00—19:40時段車站A接發列車時刻表

表3　各種類型列車所對應車站作業過程占用咽喉區和到發線的時間標準　min

表4　車站作業過程序號與列車序號間的對應關系表

根據車站咽喉區和到發線布置圖，剔除無必要過咽喉區徑路，得到車站可行列車進路，見表5。

基于以上分析，可得到描述車站設備關系及到發線固定使用方案的矩陣關系：過咽喉區徑路和到發線的連通性矩陣A22×8；各過咽喉區徑路之間的關系矩陣B22×22；車站作業過程可占用的到發線矩陣C46×8；車站作業過程可占用的過咽喉區徑路矩陣D46×22；過咽喉區徑路與道岔組之間的關系矩陣E22×14。

表5　車站列車進路表

以上參數確定之后，在CPU為Intel(R) Core(TM) i5-2430M 2.4GHz、內存為4G的電腦上，采用LINGO軟件在較短時間內實現對模型M1和模型M2的求解。

(1)情況1：列車按照運行圖正點進出車站，無列車意外晚點。

進一步分析模型M1的優化結果可知，各到發線被占用時間的方差為340.86，各道岔組被占用時間的方差為69.09。

(2)情況2：列車G9次意外晚點4 min，不能夠按照運行圖時刻表正點進出車站。

圖3　無列車意外晚點情況下到發線占用方案

結合情況1中模型M1的求解結果，在列車G9次之前的列車進路分配方案不變的前提下，列車延誤時間的上限τ取5 min，采用模型M2對后續車站作業過程的起止時刻進行調整。

表6　無列車意外晚點情況下列車進路分配方案

表7　列車G9次晚點4 min情況下列車進路分配方案

注：列車編號后的括號表示列車延誤時間，無括號表示列車正點運行。

圖4　列車G9次晚點4 min情況下到發線占用方案

進一步分析模型M2的優化結果可知，各到發線被占用時間的方差為310.61，各道岔組被占用時間的方差為69.09。該列車進路分配方案與情況1中模型M1所解得的方案相比，雖然道岔組使用均衡性沒有進一步優化，但是到發線被占用時間的方差由340.86減少到了310.61，即到發線使用均衡性提高了8.87%，而車站作業過程平均延誤時間由0 min增加到了1.61 min。

5　結　語

本文分析了高速鐵路車站各種類型列車的車站作業過程和列車進路，建立了咽喉區和到發線一體化運用的列車進路分配方案優化模型及其動態調整模型。前者應用于車站列車進路分配方案的制定過程，可有效保證列車按照運行圖進出站；但當出現列車意外晚點時，原列車進路分配方案中可能出現列車進路交叉干擾的情況；此時應采用后者對后續列車的進路分配方案進行調整，在保證后續列車延誤時間控制在一定范圍之內的條件下，實時更新列車進路分配方案，以有效保證列車進路的暢通，并使車站設備運用均衡性更優。本文暫未考慮這部分列車延誤對車站技術作業和客運作業協調性的影響，該問題將在下一步工作中繼續研究。

[1]ZWANEVELD P J, KROON L G, HOESEL S P M V. Routing Trains through a Railway Station Based on a Node Packing Model[J]. European Journal of Operational Research, 2001,128(1):14-33.

[2]ZWANEVELD P J, KROON L G, ROMEIJN E, et al. Routing Trains through Railway Stations Model Formulation and Algorithms [J]. Transportation Science, 1996, 30 (3) :181-194.

[3]KROON L G, ROMEIJN H E, ZWANEVELD P J. Routing Trains through Railway Stations: Complexity Issues[J]. European Journal of Operational Research, 1997, 98(3):485-498.

[4]LUSBY R, LARSEN J, RYAN D, et al. Routing Trains through Railway Junctions: a New Set-Packing Approach[J]. Transportation Science, 2011, 45(2):228-245.

[5]D’ARIANO A, CORMAN F, PACCIARELLI D, et al. Reordering and Local Rerouting Strategies to Manage Train Traffic in Real Time[J]. Transportation Science, 2008, 42(4):405-419.

[6]CAPRARA A, GALLI L, TOTH P. Solution of the Train Platforming Problem[J]. Transportation Science, 2011, 45(2):246-257.

[7]CHAKROBORTY P, VIKRAM D. Optimum Assignment of Trains to Platforms under Partial Schedule Compliance[J]. Transportation Research Part B:Methodological, 2008,42(2):169-184.

[8]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.

[9]JAVADIAN N, SAYARSHAD H R, NAJAFI S. Using Simulated Annealing for Determination of the Capacity of Yard Stations in a Railway Industry[J]. Applied Soft Computing, 2011, 11(2):1899-1907.

[10]劉瀾,王南,杜文. 車站咽喉通過能力網絡優化模型及算法研究[J]. 鐵道學報, 2002, 24(6):1-5.

(LIU Lan, WANG Nan, DU Wen. A Study of Network Optimization Model and Algorithm for Carrying Capacity of Station Throat[J]. Journal of the China Railway Society, 2002, 24(6):1-5. in Chinese)

[11]史峰,謝楚農,于桂芳. 鐵路車站咽喉區進路排列優化方法[J]. 鐵道學報, 2004,26(4):5-9.

(SHI Feng,XIE Chunong, YU Guifang. Optimization Methods for Arranging Train Routes in Station Bottleneck[J]. Journal of the China Railway Society, 2004, 26(4):5-9. in Chinese)

[12]呂穎,馬駟,王琳. 關于高速鐵路車站到發線運用優化研究[J]. 鐵道運輸與經濟, 2014, 36(8):26-31.

(Lü Ying, MA Si, WANG Lin. Study on Optimization of Arrival-Departure Line Using for High-Speed Railway Stations[J] . Railway Transport and Economy, 2014, 36(8):26-31. in Chinese)

[13]王保山, 侯立新, 劉海東. 客運專線車站到發線運用優化方法[J]. 交通運輸系統工程與信息, 2012, 12(2):105-110.

(WANG Baoshan, HOU Lixin, LIU Haidong. Optimized Utilization of Arrival and Departure Tracks in Dedicated Passenger Lines[J]. Journal of Transportation Systems Engineering and Information Technology, 2012, 12(2):105-110. in Chinese)

[14]趙鵬, 宋文波, 陳霞,等. 大型鐵路客運站到發線與咽喉區綜合運用優化[J]. 北京交通大學學報, 2015, 39(6):1-7.

(ZHAO Peng, SONG Wenbo, CHEN Xia, et al. Comprehensive Optimization for Utilization of Arrival-Departure Tracks and Throat Area in Large Railway Passenger Station[J]. Journal of Beijing Jiaotong University, 2015, 39(6):1-7. in Chinese)

[15]史峰, 陳彥, 秦進,等. 鐵路客運站到發線運用和接發車進路排列方案綜合優化[J]. 中國鐵道科學, 2009, 30(6):108-113.

(SHI Feng, CHEN Yan, QIN Jin, et al. Comprehensive Optimization of Arrival-Departure Track Utilization and Inbound-Outbound Route Assignment in Railway Passenger Station [J]. China Railway Science, 2009, 30(6):108-113. in Chinese)

[16]陳彥, 史峰, 秦進,等. 旅客列車過站徑路優化模型與算法[J]. 中國鐵道科學, 2010, 31(2):101-107.

(CHEN Yan,SHI Feng, QIN Jin, et al. Optimization Model and Algorithm for Routing Passenger Trains through a Railway Station [J]. China Railway Science, 2010, 31(2):101-107. in Chinese)

[17]趙茜芮, 張琦. 基于同站臺換乘的高鐵車站作業計劃優化編制[J]. 鐵道科學與工程學報, 2016, 13(1):20-27.

(ZHAO Xirui, ZHANG Qi. Optimization of High-Speed Railway Station Operation Plan Based on Across-Platform Transfer[J]. Journal of Railway Science and Engineering, 2016, 13(1):20-27. in Chinese)

[18]鐵道第三勘察設計院. 京滬高速鐵路設計暫行規定[M]. 北京：中國鐵道出版社, 2003.