高速鐵路列車運行圖結構優化研究

（1.西南交通大學交通運輸與物流學院，四川成都610031；2.全國鐵路列車運行圖編制研發培訓中心，四川成都610031）

（1.西南交通大學交通運輸與物流學院，四川成都610031；2.全國鐵路列車運行圖編制研發培訓中心，四川成都610031）

為提高高速鐵路列車運行圖的通過能力，通過緊湊鋪畫列車運行圖，合理安排列車運行線順序，優化了列車運行圖結構；將列車運行圖結構優化問題轉化為旅行商問題，以巡回路徑總費用最小化為目標建立0-1整數規劃模型，并利用遺傳算法求解.用2015年京滬高速鐵路數據進行實例驗證，求得列車運行圖結構的優化方案.計算結果表明：原方案開行39列列車最少需628 min，優化方案的開行時間比原方案的開行時間減少了133 min，約21.2%，能更好地滿足客流高峰時段或突發性客流激增時需盡快密集發車的要求.

鐵路運輸；列車運行圖；遺傳算法；高速鐵路；通過能力；旅行商問題

我國高速鐵路網正在大規模和高速度建設中，截至2014年底，總營業里程已經超過1.6萬km.高速鐵路運營組織是高速鐵路安全平穩運行、滿足旅客需求、確保鐵路經濟效益和社會效益的重要保障，高速鐵路列車運行圖是運營組織工作的基礎.

國內外學者對列車運行圖編制做了大量的研究，建立了豐富的數學理論和計算方法，這些成果對編制高速鐵路列車運行圖具有重大的借鑒意義.文獻［1-8］對既有鐵路單線、雙線和網狀線路的列車運行圖進行了深入的研究；文獻［9］系統地研究了基于網狀線路的京滬高速鐵路列車運行圖編制理論，設計了高中速列車分層始發區域滾動鋪畫算法對運行圖數學模型進行求解；文獻［10］提出基于不同種類列車運行圖鋪劃的分層疊加數學模型，設計了改進型遺傳算法對其進行求解；文獻［11-12］對周期性列車運行圖進行優化，通過鋪畫某線路的周期性列車運行圖驗證了模型的可行性；文獻［13-14］在考慮旅客列車始發時間域和維修天窗的基礎上，建立了客運專線列車運行圖優化模型，設計了基于定序優化的客運專線列車運行圖鋪畫方法，并基于旅客列車開行方案和列車運行圖的換乘網絡進行客流分配，將旅客列車開行方案和列車運行圖相結合進行了優化.

在既定高速鐵路停站方案的前提下，列車運行圖結構在很大程度上影響鐵路的通過能力.緊湊鋪畫列車運行圖，合理布線進而優化其結構，可以提高鐵路通過能力，有利于滿足客流高峰時段或突發性客流激增情況下盡快密集發車的需求.本文將高速鐵路列車運行圖的結構優化問題轉化為旅行商問題（traveling salesman problem，TSP），建立數學模型并用遺傳算法［15］求解.以京滬高速鐵路為實例，編制出優化的列車運行圖方案.

1 高速鐵路列車運行圖數學描述

｛xi1，xi2，…，xin｝表示列車Ti的停站序列.tj表示高速列車在站Sj的停站時分，tZC表示不停站直達列車的旅行時分，tQF表示起車附加時分，tTF表示停車附加時分.

定義1 對任意兩列車Ti1和Ti2，當Ti2為Ti1的緊后行列車時，找不到比Δti1i2更小的始發站發車間隔時間，使得這兩列車在任意車站均滿足相應的車站間隔時間，稱Δti1i2為列車Ti1和Ti2的最小始發間隔時間.

根據高速鐵路已定的停站方案，由列車運行標尺、起車和停車附加時分、停站時分等已知參數，可以計算出任意兩列車Ti1和Ti2的最小始發間隔時間Δti1i2，具體方法參照文獻［10］.

定義2 列車運行圖中的任意兩條相鄰列車運行線在始發站的間隔時間等于這兩列車的最小始發間隔時間，這種鋪畫方式稱為緊湊鋪畫.

2 高速鐵路列車運行圖建模

根據既定的高速鐵路停站方案，通過對列車進行合理排序，優化列車運行圖結構，可以提高鐵路通過能力.優化目標為使緊湊鋪畫的列車運行圖中第一列列車從始發站出發至最后一列列車到達終到站之間的總間隔時間最短.

將每條列車運行線視為一個節點，構造節點網絡完全圖.用k表示節點編號（與其對應的運行線編號）.令從節點k1指向節點k2的路徑的費用等于列車Ti1和Ti2的最小始發間隔時間，那么根據定義1和定義2，整個網絡完全圖中所有路徑的費用可以根據既定的高速鐵路停站方案來確定.

由于優化目標還涉及到運行線的運行時分，而這部分內容并沒有在節點網絡完全圖中得以體現，這將導致在后續的建立模型和求解過程中陷入困境.

為便于研究，增設一個虛擬節點，編號為m+ 1.令之前的m個節點到節點m+1的路徑費用等于各列車運行線的運行時分，設節點m+1到其他各節點的路徑費用為0，由此形成擴展的節點網絡完全圖.

在新的節點網絡完全圖中，從任一節點出發，遍歷所有節點1次并回到該節點，該巡回路徑的拓撲結構是一個環.若將該環在節點m+1處斷開并去掉節點m+1，將形成一條鏈，這時可以確定各節點的順序.按照此順序緊湊鋪畫各節點對應的列車運行線，所有相鄰列車運行線的間隔時間與最末一條運行線的運行時分之和正好等于該巡回路線的總費用.也就是說，為了優化列車運行線順序，使得相鄰列車運行線的各間隔時間與最末一條運行線的運行時分之和最小，即在節點網絡完全圖中尋找總費用最小的巡回路徑.

由構造的節點網絡完全圖尋找最優巡回路徑 的過程如圖1所示，優化結果的節點順序為3241.

圖1 優化過程Fig.1 Optimization process

緊湊鋪畫時列車運行圖結構的優化問題可轉化為經典的旅行商問題（TSP）.設G=（V，E）是帶正權的完全圖，V=（1，2，…，m+1），E表示完全圖中所有邊的集合，邊（k1，k2）的費用記為Ck1k2.

節點網絡完全圖的費用矩陣

用變量λk1k2表示邊（k1，k2）是否存在于總費用最小的巡回路徑中，若是λk1k2=1，否則λk1k2=0.這里有一種特殊情況，若k1=k2時，取λk1k2=0，因為這樣的邊在節點網絡完全圖中并不存在.所以待求解的矩陣

為了優化緊湊鋪畫列車運行圖的結構，確定最優的列車運行線順序，實現第一列車從始發站出發至最末列車到達終到站的間隔時間最小化的目標，巡回路徑總費用最小化的TSP問題表達為

式（1）和式（2）表示任一節點在巡回路徑中只能出現一次，式（3）表示巡回路徑必須遍歷所有節點.

3 遺傳算法參數設計

3.1 染色體編碼

采用以遍歷節點的次序進行編碼的方法，如碼串123456表示從節點1開始，依次經節點2、3、4、5和6，最后返回節點1的遍歷路徑，這是針對TSP問題的最自然的編碼方式.

3.2 適應度函數

適應度函數常取路徑長度Td的倒數，即f= 1/Td.結合TSP的約束條件（每個節點經過且只經過一次），適應度函數修正為

f=1/（Td+αNt），

式中：Nt為對TSP路徑不合法的度量，這里取Nt為未遍歷的節點的個數；

α為懲罰系數，取值通常為節點之間最長距離dmax的兩倍多，這里取2.1dmax；

3.3 遺傳算子

（1）選擇算子

用適應度函數對群體中所有個體進行評估，將選擇算子作用于群體，選擇的目的是把優化的個體直接遺傳到下一代，或通過配對交叉產生新的個體再遺傳到下一代.采用輪盤賭與精英個體保存的混合策略，選擇當前種群中的最優個體直接進入下一代，剩余個體通過輪盤賭隨機選擇，這種方式能夠在一定程度上避免算法過早收斂.

（2）交叉算子

采用部分匹配交叉策略：隨機選擇兩個交叉點，將兩交叉點之間的基因段互換，將互換后的基因段以外的部分中與互換后基因段中沖突的節點用另一父代相應位置的碼值代替，直至沒有沖突.

（3）變異算子

對群體中的個體，隨機選擇染色體中的兩點，交換其碼值.

3.4 遺傳算法求解流程

具體步驟如下：

（1）設定參數，種群大小為Mpop，交叉概率為Pc，變異概率為Pm，最大遺傳代數為nmax.

（2）按照染色體編碼方式生成初始種群，當前代數n=1.

（3）計算當前種群中各染色體的適應度，選擇最優個體直接進入下一代，剩余個體通過輪盤賭隨機選擇.

（4）根據給定的交叉概率Pc，對種群進行一致性交叉操作.

（5）根據給定的變異概率Pm，對種群進行變異操作，更新代數n=n+1.

（6）算法終止條件.若n≤nmax，轉步驟（3）；否則，輸出當前種群中最優染色體，并解碼為列車運行圖編制方案.

4 實例驗證與結果分析

為檢驗算法效果，用2015年京滬高鐵為例進行驗證.以全路運行圖中由北京南始發上海虹橋終到的全部39列速度為300 km/h的下行列車為研究對象.

tZC=276 min，

tQF=2 min，

tTF=3 min.

全路運行圖中京滬高鐵在各站的停站時間如表1所示，具體停站方案如表2所示.

表1 京滬高鐵各站停站時間Tab.1 Train stop time of Beijing-Shanghai high-speed railway min

全路運行圖中各列車的鋪畫順序為：G101、G103、G105、G11、G107、G109、G111、G1、G113、G115、G117、G13、G119、G121、G15、G123、G125、G411、G127、G129、G131、G133、G135、G137、G3、G139、G141、G17、G143、G145、G19、G147、G149、G151、G21、G153、G155、G157、G159.若這些運行線緊湊鋪畫，總用時628 min.

將表2中各列車依次編碼為1至39，增加一個虛擬節點，其編號為40.設定遺傳算法參數，種群大小

Mpop=60，

交叉概率

Pc=0.4，

變異概率

Pm=0.05，

最大遺傳代數nmax=300.

經300次迭代后，取當代種群中最優染色體，其編碼為1-2-5-6-4-3-7-15-13-38-9-8-18-26-24-14-31-35-37-10-22-36-25-16-12-20-32-33-30-17-39-19-34-27-21-11-28-23-29-40，去除最末的虛擬節點，解碼成列車運行線的鋪畫順序：G1、G3、G15、G17、G13、G11、G19、G113、G109、G159、G101、G21、G119、G135、G131、G111、G145、G153、G157、G103、G127、G155、G133、G115、G107、G123、G147、G149、G143、G117、G411、G121、G151、G137、G125、G105、G139、G129、G141，總用時495 min，比現行方案縮短133 min，約21.2%，大幅度地提高了列車運行圖的通過能力.

表2 京滬高鐵停站方案Tab.2 Stop schedule plan of Beijing-Shanghai high-speed railway

5 結 論

本文從緊湊鋪畫列車運行圖力求通過能力最大為出發點，建立了高速鐵路列車運行圖結構優化數學模型，并設計了遺傳算法參數進行求解.以2015年京滬高鐵為例，編制出結構更合理的列車運行圖方案，得到以下主要結論：

（1）通過實例計算，確定了更合理的運行線順序.優化方案總用時比現行方案縮短了133 min，優化方案有重要的現實意義，可以較好地滿足客流高峰時段或突發性客流激增時需盡快密集發車的需求.

（2）以2015年京滬高鐵高速列車為研究對象，是基于不存在越行情況，若不同速度的高速列車沒有越行現象，本文方法同樣適用.

對于我國逐漸成型的高速鐵路網絡，條件更加復雜，列車運行圖的結構還需進一步深入研究.

［1］ 彭其淵，王慈光.鐵路行車組織［M］.北京：中國鐵道出版社，2007：266-275.

［2］ 孫焰.單線列車運行圖優化理論及計算機編制方法［D］.長沙：長沙鐵道學院，1997.

［3］ 周磊山，胡思繼.計算機編制網狀線路列車運行圖方法研究［J］.鐵道學報，1998，20（5）：15-21.

ZHOU Leishan，HU Siji.Network hierarchy parallel algorithm of automatic train scheduling［J］.Journal of the China Railway Society，1998，20（5）：15-21.

［4］ 倪少權，呂紅霞，楊明倫.全路列車運行圖編制系統設計的研究［J］.西南交通大學學報，2003，38（3）：332-335.

NI Shaoquan，LV Hongxia，YANG Minglun.Research on design of train diagram-making system of railways in China［J］.Journal of Southwest Jiaotong University，2003，38（3）：332-335.

［5］ 彭其淵，楊明倫，倪少權.單線實用貨物列車運行圖計算機編制系統［J］.西南交通大學學報，1995，30（5）：537-542.

PENG Qiyuan，YANG Minglun，NI Shaoquan.A system of making train working graph on single-track lines with computer［J］.Journal of Southwest Jiaotong University，1995，30（5）：537-542.

［6］ 彭其淵，朱松年.網絡列車運行圖的數學模型及算法研究［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.

［7］ 史峰，黎新華，秦進，等.單線列車運行圖鋪劃的時間循環迭代優化方法［J］.鐵道學報，2005，27（1）：1-5.

SHI Feng，LI Xinhua，QIN Jin，et al.A timing-cycle iterative optimizing method for drawing single-track railway train diagrams［J］.Journal of the China Railway Society，2005，27（1）：1-5.

［8］ 史峰，黎新華，秦進，等.單線列車運行調整的最早沖突優化方法［J］.中國鐵道科學，2005，26（1）：106-113.

SHI Feng，LI Xinhua，QIN Jin，et al.The earliest conflict optimal method for train operation adjustment on single track［J］. China Railway Science， 2005，26（1）：106-113.

［9］ 馬建軍.基于網狀線路的京滬高速鐵路列車運行圖編制理論的研究［D］.北京：北方交通大學，2002.

［10］ 許紅，馬建軍，龍建成.客運專線列車運行圖編制模型及計算方法研究［J］.鐵道學報.2007，29（2）：1-7.

XU Hong，MA Jianjun，LONG Jiancheng.Research on the model and algorithm of the train working diagram of dedicated Passenger line［J］.Journal of the China Railway Society，2007，29（2）：1-7.

［11］ 謝美全，聶磊.周期性列車運行圖優化模型研究［J］.鐵道學報，2009，31（4）：7-13.

XIE Meiquan，NIE Lei. Modelofcyclic train timetable［J］.Journal of the China Railway Society，2009，31（4）：7-13.

［12］ 汪波，楊浩，牛豐，等.周期運行圖編制模型與算法研究［J］.鐵道學報，2007，29（5）：1-6.

WANG Bo，YANG Hao，NIU Feng，et al.Study on modeland algorithm of periodic train diagram generation［J］.Journal of the China Railway Society，2007，29（5）：1-6.

［13］ 周文梁，史峰，陳彥.基于定序優化的客運專線列車運行圖鋪劃方法［J］.鐵道學報，2010，32（1）：1-7.

ZHOU Wenliang，SHI Feng，CHEN Yan.A method for drawing train diagram of deticated passenger line based on fixed order optimization［J］.Journal of the China Railway Society，2010，32（1）：1-7.

［14］ 周文梁，史峰，陳彥，等.客運專線網絡列車開行方案與運行圖綜合優化方法［J］.鐵道學報，2011，33（2）：1-7.

ZHOU Wenliang，SHI Feng，CHEN Yan，et al. Method of integrated optimization of train operation plan and diagram for network of dedicated passenger lines［J］.Journal of the China Railway Society，2011，33（2）：1-7.

［15］ 周明，孫權棟.遺傳算法原理及應用［M］.北京：國防工業出版社，1999：143-155.

高速鐵路列車運行圖結構優化研究

張小炳1，2， 倪少權1，2， 潘金山1，2

Optimization of Train Diagram Structure for High-Speed Railway

ZHANG Xiaobing1，2， NI Shaoquan1，2， PAN Jinshan1，2
（1.School of Transportation and Logistics，Chengdu 610031，China；2.National Railway Train Diagram Research and Training Center，Southwest Jiaotong University，Chengdu 610031，China）

To improve the carrying capacity of high-speed railway，the structure of the train diagram was optimized by drawing compact train diagram and designing reasonable operation scheduling for trains.The optimization problem of the train diagram structure was transformed into a traveling salesman problem（TSP）.Taking the total cost of the all routes as a goal，a 0-1 integer programming model was proposed，and then solved using the genetic algorithm.Finally，the model was verified through a real case study using the data of Beijing-Shanghai high-speed railway in 2015，and the optimized train diagram was compared with the original scheme.Computation results show that the total operation time of 39 trains was reduced from the 628 min in the original scheme to the 495 min in the optimized schedule，a reduction by about 21.2%.Therefore，the optimal alternative can meet better the demand for intensive dispatching during the peak period or in sudden burst condition of passenger flow.

railway transportation；train diagram；genetic algorithm；high-speed railway；carrying capacity；TSP

張小炳，倪少權，潘金山.高速鐵路列車運行圖結構優化研究［J］.西南交通大學學報，2016，51（5）：938-943.

0258-2724（2016）05-0938-06

10.3969/j.issn.0258-2724.2016.05.017

U292.41

A

2015-10-07

國家自然科學基金資助項目（61273242，61403317）；四川省科技廳軟科學計劃資助項目（2015ZR0141）；中國鐵路總公司科技研究計劃資助項目（2013X010-A，2014X004-D）

張小炳（1984—），男，博士研究生，研究方向為運輸組織理論與系統優化，E-mail：zxbisme3@163.com

倪少權（1967—），男，教授，博士，博士生導師，研究方向為運輸組織理論與系統優化，E-mail：shaoquanni@163.com

（中文編輯：秦萍玲 英文編輯：蘭俊思）