基于定序優化的高速鐵路網絡列車運行圖優化

周文梁，屈林影，史峰，鄧連波

(中南大學 交通運輸工程學院，湖南 長沙 410075)

在我國高速鐵路網絡化運營背景下，構建高速鐵路網絡化運輸組織優化方法迫切需要，特別是網絡列車運行圖的鋪劃，由于需要在叉點站銜接多個線路方向，使本來難度很大的列車運行圖鋪劃方法變得更為復雜。目前，針對網絡列車運行圖鋪劃方法的研究仍然較少。馬建軍等[1]將鐵路路網表示為分層節點圖，將列車運行圖表示為時間序列，基于離散事件方法計算列車到發時間；彭其淵等[2?3]通過不斷向子路網增加區段，使運行圖鋪劃范圍不斷擴大，最終獲得整個路網運行圖；同時通過在列車運行圖時空局域內設置和滾動窗口，每次優化窗口中運行線來動態地完成網絡運行圖鋪劃；Dorfman等[4]將各種列車優先策略融合到列車離散事件仿真框架中來解決路網列車運行圖鋪劃問題；王濤等[5]采用分層多級優化分枝定界算法，針對列車調度問題給出了一種基于替代圖的列車運行圖修正及優化方法；Eva等[6]進一步引用了ANLS算法對旅客等待時間進行優化；文超等[7]給出了在運行圖鋪化過程中單個列車化解沖突的方法；白紫熙等[8]在給定列車車站到發順序的基礎上，進一步采用原始對偶算法優化列車車站到發時間；史峰[9]基于分層鋪化的思想確定速度優先級，給出相同徑路的運行圖編制；而周文梁等[10]通過設計高鐵線路列車運行圖的有向圖表示形式，以此結合文獻[8]和[9]方法優化列車到發作業順序以及到發時刻；Kaspi等[11]采用交叉熵算法對列車運行圖和開行方案進行綜合優化，而ZHOU等[12]基于拉格朗日松弛分解方法協同優化列車車站徑路與車站到發時刻。本文在文獻[10]研究方法的基礎上，通過在車站對各銜接區間的接發列車作業進行組合約束，以列車旅行時間最少為目標，建立高鐵網絡運行圖優化模型；通過擴展高鐵網絡松弛運行圖的有向圖表示形式，建立網絡松弛運行圖的定序優化線性規劃模型，在網絡松弛運行圖中以平移作業組、交換作業順序、變更停站方案等方法優化網絡運行圖。

1　網絡運行圖優化模型與求解思想

高速鐵路網絡由客運站和各相鄰客運站間的線路區間組成，記為N=(S,E)，其中S為客運站集，為區間集。每個客運站至少銜接一個區間(或方向)，車站 sk銜接的區間集為

描述網絡運行圖最關鍵的環節在于描述作業間隔時間時必須考慮作業的銜接區間。對于車站sk的2個銜接區間，不同列車分別經過區間e1和e2并同在車站sk作業時，作業之間需要滿足如下時間間隔：

以上各項作業時間間隔查定值與車站布局和列車過站徑路等因素有關。一些作業對之間因為有足夠的安全保障，可以不作時間間隔約束。

設高速鐵路網絡 N = ( S,E)上開行旅客列車集為?。對于列車i∈?，記oi為始發站，di為終到站，分別表示其經由的區間序列與車站序列，為始發時間域分別為列車i在區的啟動附加時間、純運行時間和停止附加時間；列車i在車站的最少停站時間；列車i在車站的停站標志，若列車i在車站sk停車，則列車i從車站sk經區間開往車站的出發、到達作業時刻分別記為另記區間 e的維修天窗為

以列車旅行時間最少為優化目標，結合線路運行圖優化模型[10]和網絡運行圖中作業間隔的銜接區間屬性，建立高速鐵路網絡列車運行圖優化模型如下：

以上模型中目標函數式(1)為最小化列車旅行時間，其中符號Θ表示兩整數關于運營周期T的模運算；式(2)~(5)分別為不同時出發時間間隔、不同時到達時間間隔、不同時發到時間間隔以及不同時到發時間間隔約束，式(6)和(7)分別為列車區間運行時間、車站停留時間約束，式(8)為列車始發時間約束，式(9)為區間天窗時間約束，式(10)與(11)為變量取值約束。

模型式(1)~(11)是一個大規模優化問題，本文借助于文獻[10]求解思想設計求解算法。首先在忽略各列車車站作業間隔約束關系下，根據列車始發時間分布和列車區間運行時間等確定初始網絡松弛運行圖，然后在保持其它作業之間的順序關系的條件下，按一定沖突選擇策略逐步選擇化解列車作業沖突，直至所有沖突全部化解為止，獲得完整的高鐵網絡運行圖。

2　網絡松弛運行圖的有向圖表示形式

線路松弛運行圖的多平行四邊形表示形式的構造可通過將一端邊界上沖突相關的運行線在另一端添加該運行線的副本(與原運行線段相差一個時間周期T的運行線段)以準確反映列車作業之間的位置關系。對于網絡松弛運行圖，需通過判斷增加必要的運行線副本來保持叉點站各銜接方向運行線的位置關系，形成網絡松弛運行圖的擴展多平行四邊形。銜接4個方向的網絡松弛運行圖的多平行四邊形如圖 1 所示，其中，BDD′B′和 CEE′C′分別表示相交在車站中心線AA′的2個平面，4個銜接方向的運行圖鋪劃在這4個半平面上，其中，列車1與2經由站均為車站E，A與C，而列車3與4經由站分別為車站D，A與B。此外，以虛線表示的列車1與3運行線作為平行四邊形表示形式的右邊界，與其對應的左邊界構成一個周期，如1 d1 440 min。

圖1　網絡松弛運行圖的多平行四邊形表示形式Fig. 1　Multi-parallelogram of relaxed train diagram on rail network

記各列車在車站的到發作業為點集Vz，各列車的始發時間域上下限時間為點集Vs，各區間兩端車站相應的天窗起始、終止時間為點集Vw，獲得點集V=Vz∪Vs∪Vw；將車站所有存在作業間隔時間限制的相鄰定序列車作業間(沖突運行線段的相關作業除外)沿時間增加方向作弧得相鄰作業弧集 Ap，將各區間運行線段兩端作業沿時間增加方向作弧的區間運行弧集Ay，將各列車在同一車站的到達作業至發車作業間作弧得停站弧集At，將各列車始發作業至其始發時間域上限時間、列車始發時間域下限時間至其始發作業間作弧得始發時間域弧集As，將列車運行圖中各區間兩端車站相應的天窗時間與其緊前或緊后列車作業間沿時間增加方向作弧得天窗弧集Aw，將一段邊界線上列車作業與另一端邊界線上對應作業沿時間增加方向作弧得周期約束弧集Az，獲得弧集，由此便得網絡松弛運行圖的有向圖表示形式 G = ( V,A)。圖 1中多平行四邊形運行圖對應的有向圖如圖 2所示(圖中包含區間運行弧、停站弧、作業時間間隔弧及周期約束弧)，其中，區間弧對應于列車區間運行，如區間弧(1,2)與(3,4)分別對應于列車1在兩區間的運行；停站弧對應于列車車站停車過程，如停站弧(2,3)與(6,7)分別對應于列車1與3在車站A的停車過程，若列車不停車，則將其權值設為0即可；作業間隔弧對應于列車作業之間的間隔，如間隔弧(1,9)與(2,6)分別對應于同徑路列車1和2進入區間間隔與不同徑路列車1和3離開區間間隔；而周期弧為邊界約束，如周期弧(1,17)保證了同一列車在相鄰周期的時間間隔正好為周期長度。值得說明的是，在網絡狀態下不同運行徑路列車在叉點站存在作業時間間隔要求，如圖2中間隔弧(2,6)與(3,7)描述的正是列車1與3從不同區間進入車站A的時間間隔要求，以及它們離開車站A進入不同區間的時間間隔要求。

圖2　網絡松弛運行圖的有向圖表示形式Fig. 2　Digraph of relaxed train diagram on rail network

將列車車站作業時間、列車始發時間域上下限值以及天窗起始、終止時間作為圖G中相應點v上的加權 t(v)，同時將每條弧(u,v)尾節點加權與首節點加權的差值定義為該弧上的加權w(u,v)=t(v)?t(u)，確定所有有向弧(u,v)上加權的下限w0(u,v)，便得到網絡松弛列車運行圖的加權有向圖G。

3　網絡松弛運行圖的定序優化線性規劃模型

網絡松弛運行圖的定序優化指在忽略所有沖突的相關作業之間的順序關系、保持與沖突外不相關作業之間的順序關系的條件下，使得列車旅行時間最小化。記Uk為網絡松弛運行圖的擴展有向圖中左端邊界線上車站Ssk∈的邊界作業集。對于xik∈ Uk或 yik∈ Uk，記 xi′k或 yi′k為其相應右端邊界線上作業，根據各類有向弧加權函數約束，建立網絡松弛運行圖的定序優化線性規劃模型如下：

其中：約束式(28)表示列車停站變量與列車車站到發時刻之間一致性約束，即當列車在車站停留，即=1時，列車停留時間至少大于1 min；否則列車停留時間為0。

4　基于定序優化的網絡運行圖鋪劃方法

基于定序優化的網絡運行圖鋪劃方法是在鋪劃松弛網絡運行圖的基礎上，每次選擇一定數量沖突進行化解；在化解沖突時，先確定其相關作業順序，然后構造當前松弛運行圖的有向圖，在此有向圖中，保持非沖突作業之間的關系，利用作業平移的方法化解沖突，如此反復，直至獲得不存在沖突的網絡運行圖。若平移作業仍無法完全滿足最小作業時間間隔，可進一步結合交換列車作業順序、變更停站方案或擴大列車始發時間域等優化手段。

4.1　化解沖突及化解方案的選擇

根據沖突發生位置將松弛運行圖中沖突分為區間沖突和車站沖突。對于區間沖突，可通過讓速度等級高的列車在前方或后方車站越行速度等級低列車而化解；對于車站沖突，只需讓速度等級高的列車在該車站越行速度等級低列車化解。故沖突化解均需使得沖突運行線平移一定時間距離而滿足最小作業間隔時間要求。通常沖突化解平移時間之和越少，所帶動平移的運行線數量越少，這既對運行圖質量影響較小，也容易實現沖突化解。因此，對于區間沖突應優先選擇化解平移時間之和最少越行站進行化解。

每次化解沖突的選擇，可簡單從松弛運行圖中隨機選擇一定數量沖突，或者根據沖突化解時平移時間以概率方式選擇一定數量沖突，這兩種方法易操作，但運行圖優化質量不明顯。為了提高運行圖優化質量，這里設計兩種沖突選擇原則：沖突化解平移時間總和最小原則和沖突化解平移時間差距最大原則。

1) 平移時間總和最小原則

采用平移時間總和最小原則選擇數量為λ的化解沖突集C滿足：

2) 平移時間差距最大原則采用平移時間差距最大原則選擇數量為λ的化解沖突集C滿足：

4.2　松弛運行圖的定序優化方法

根據當前化解沖突及其化解方案確定當前所有化解沖突作業之間的時間先后順序后，進而基于有向圖調整其作業時間使得其滿足最小作業時間間隔要求。可采用的方法主要有平移列車作業、交換列車作業順序、變更停站方案和調整列車始發時間域等關鍵技術。文獻[10]詳細介紹了區段列車運行圖鋪劃過程中這些關鍵技術的實現方法。由于網絡運行圖鋪劃與區段運行圖鋪劃主要區別在于同時考慮了叉點站對各銜接區間的接發(或通過)作業之間的時間間隔約束，而有向圖構造已經完全反映了作業之間的先后關系，因此，文獻[10]中關于這些關鍵技術的實現方法同樣適應于網絡運行圖鋪劃，因篇幅有限，不再敘述。只是在化解沖突作業平移時，不僅帶動一條線路上相關作業平移，也帶動所有銜接線路上的相關作業一起平移。

5　網絡運行圖鋪劃算例

由13個客運站和20個復線線路區間組成的高鐵網絡如圖3所示(圖中標記了以km為單位的路段里程)。在該網絡上鋪劃兩種速度等級列車，其中高速度等級列車191對、低速度等級列車158對。高、低速等級列車在各區間的啟停附加時分均設為 1分，在各區間的技術速度分別為 320 km/h和 250 km/h。在此基礎上，結合區間里程便可計算出2種速度列車在區間的純運行時間，進一步結合列車區間前后車站停車情況與啟停附加時分便可獲得其區間運行時分。車站不同銜接方向列車的不同時出發、不同時到達、不同時發到及不同時到發時間間隔為3 min。

圖3　高速鐵路網絡結構示意圖Fig. 3　Structure schematic of an example rail network

利用基于定序優化的網絡運行圖鋪劃方法求解網絡上的列車運行圖，下面僅以車站S6銜接的4個區間S4-S6-S5,S3-S6-S8在12:00-18:00時間段內的運行圖展示如圖4和圖5所示。圖中很容易看出列車先后通過S4-S6和S6-S5，S3-S6和S6-S8的銜接關系，篇幅所限，列車先后通過其它線路的銜接關系并未畫出來，讀者可以通過組合這兩個圖看出它們的銜接關系，如列車Z147先通過區間S4-S6，再通過區間S6-S8。

1) 沖突選擇策略對算法優化效率與質量比較

首先隨機產生165個運行圖鋪劃實例，分別采用隨機策略、最小平移時間策略和最大平移差距策略選擇化解沖突優化列車運行圖，確定算法計算時間與其列車總旅行時間，統計各策略使得列車總旅行時間、計算時間以及兩者為3種策略中最小值的次數以及所占比例如表1所示。由于各沖突選擇策略下計算的列車總旅行時間或計算時間可能相等，所以表中各策略次數之和大于鋪劃實例數 165，百分率之和也不等于1。

圖4　區段S4-S6-S5的列車運行圖Fig. 4　Train diagram of section S4-S6-S5

圖5　區段S3-S6-S8的列車運行圖Fig. 5　Train diagram of section S3-S6-S8

表1　在運行實例數165條件下3種沖突選擇策略效果比較Table 1　Compare of three conflict-selection strategies used for 165 instances

由表1數據可知：3種沖突選擇策略中，最小平移時間策略使列車總旅行時間最小的次數達到84次，占到實例總數的51%；而計算時間最小的次數達到103次，占到實例總數的62%，而使得兩者均最小的次數達到63次，占到實例總數的38%。由此可見，相比隨機策略和最大平移差距策略，采用最小平移時間策略選擇化解沖突能夠以最大概率花費較較少的計算時間而獲得列車總旅行時間較小的列車運行圖。

圖6　計算時間隨一次同時化解沖突數的變化關系圖Fig. 6　Change relation of computing time with the number of disposed conflicts

圖7　列車平均延誤時間隨一次同時化解沖突數的變化關系圖Fig. 7　Change relation of average train delay time with the number of disposed conflicts

2) 一次同時化解沖突數量對算法優化效率與質量的影響

分別采用隨機策略、最小平移時間策略和最大平移差距策略，依次選擇一次同時化解沖突數為 1至 50優化網絡運行圖，確定各沖突選擇策略下計算時間與其列車平均延誤時間(列車旅行時間與技術時間之差)隨一次同時選擇化解沖突數的變化曲線關系分別如圖6和圖7所示。

由圖5和圖6可知：每次選擇化解沖突的數量對運行圖鋪劃時間和列車平均延誤時間的影響不是很明顯。這是因為作業沖突化解過程中，沖突作業之間的定序工作量很少，而大部分工作量是調整兩作業間隔時間使之滿足最小作業間隔時間，所以若將多個沖突進行一次定序，所節約的計算時間相比調整列車作業間隔所花的時間是非常小的。

6　結論

1) 建立了以列車旅行時間最少為目標的網絡運行圖優化模型，同時考慮了車站上各銜接方向列車到發或通過作業之間約束關系，確保了列車運行圖的整體優化質量。

2) 設計基于定序優化的網絡列車運行圖鋪劃方法，在鋪劃初始網絡松弛運行圖的基礎上，通過最小平移時間策略和最大平移差距策略等各種沖突化解策略能夠有效地化解網絡松弛運行圖中沖突，獲得完整的網絡運行圖。

3) 算例分析表明，定序優化沖突化解策略的方法能提高運行圖鋪化速率并獲得較優的列車運行圖。而如何進一步將車站到發線、進路等約束考慮到模型和算法中，是有待擴展的重要研究內容。

參考文獻：

[1] 馬建軍, 周磊山, 胡思繼. 計算機編制網狀線路列車運行圖系統研究[J]. 鐵道學報, 2000, 22(1): 7?11.MA Jianjun, ZHOU Leishan, HU Siji. Research on train working diagram system of railway netted lines worked out with computer[J]. Journal of the China Railway Society, 2000, 22(1): 7?11.

[2] 彭其淵, 朱松年. 網絡列車運行圖的數學模型及算法研究[J]. 鐵道學報, 2001, 23(1): 1?8.PENG Qiyuan, ZHU Songnian. Study on a general optimization model and its solution for railway network train diagram[J]. Journal of the China Railway Society,2001, 23(1): 1?8.

[3] 彭其淵, 王寶杰, 周黨瑞. 基于實用的一種網絡列車運行圖計算方法[J]. 西南交通大學學報, 1999, 34(5):588?593.PENG Qiyuan, WANG Baojie, ZHOU Dangrui. A practical algorithm for making train diagram of railway network[J]. Journal of Southwest Jiaotong University,1999, 34(5): 588?593.

[4] Dorfman M J, Medanic J. Scheduling trains on a railway network using a discrete event model of railway traffic[J].Transportation Research Part B, 2004(38): 81?98.

[5] 王濤, 張琦, 趙宏濤, 等. 基于替代圖的列車運行調整計劃編制及優化方法[J]. 中國鐵道科學, 2013, 34(5):126?133.WANG Tao, ZHANG Qi, ZHAO Hongtao. A method for generation and optimization of train operation adjustment plan based on alternative graph[J]. China Railway Science, 2013, 34(5): 126?133.

[6] Eva Barrena, David Canca. Single-line rail rapid transit timetabling under dynamic passenger demand[J].Transportation Research Part B, 2014(70): 134?150.

[7] 文超, 彭其淵, 陳芋宏. 高速鐵路單個列車運行沖突消解研究[J]. 鐵路技術與工程, 2013, 13(10): 2741?2747.WEN Chao, PENG Qiyuan, CHEN Yuhong. Train operation adjustment based on conflict resolution for high-speed rail[J]. Science Technology and Engineering,2013, 13(10): 2741?2747.

[8] 白紫熙, 邵靜靜. 相同徑路的高速列車運行圖編制方法[J]. 中國鐵道科學, 2015, 36(6): 135?140.BAI Zixi, SHAO Jingjing. Drawing method for working diagram of high speed train with same path[J]. China Railway Science, 2015, 36(6): 135?140.

[9] 史峰. 定序單線列車運行圖的原始－對偶算法[J]. 鐵道學報, 1996, 18(1): 8?20.SHI Feng. A primal-dual algorithm for making train diagram fixed order on single-track rail lines [J]. Journal of the China Railway Society, 1996, 18(1): 8?20.

[10] 周文梁, 史峰, 陳彥. 基于定序優化的客運專線列車運行圖鋪劃方法[J]. 鐵道學報, 2010, 32(1): 1?7.ZHOU Wenliang, SHI Feng, CHEN Yan. A method for drawing train diagram of dedicated passenger line based on fixed order optimization[J]. Journal of The China Railway Society, 2010, 32(1): 1?7.

[11] Kaspi M, Raviv T. Service-oriented line planning and timetabling for passenger trains[J]. Transport Science,2013, 47(3): 295?311.

[12] ZHOU Wenliang, TENG Hualiang. Simultaneous passenger train routing and timetabling using an efficient train-based Lagrangian relaxation decomposition[J].Transportation Research Part B, 2016(11): 409?439.