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

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

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

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

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

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

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

1 高速鐵路列車運行圖數(shù)學(xué)描述

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

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

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

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

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

根據(jù)既定的高速鐵路停站方案，通過對列車進(jìn)行合理排序，優(yōu)化列車運行圖結(jié)構(gòu)，可以提高鐵路通過能力.優(yōu)化目標(biāo)為使緊湊鋪畫的列車運行圖中第一列列車從始發(fā)站出發(fā)至最后一列列車到達(dá)終到站之間的總間隔時間最短.

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

由于優(yōu)化目標(biāo)還涉及到運行線的運行時分，而這部分內(nèi)容并沒有在節(jié)點網(wǎng)絡(luò)完全圖中得以體現(xiàn)，這將導(dǎo)致在后續(xù)的建立模型和求解過程中陷入困境.

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

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

由構(gòu)造的節(jié)點網(wǎng)絡(luò)完全圖尋找最優(yōu)巡回路徑 的過程如圖1所示，優(yōu)化結(jié)果的節(jié)點順序為3241.

圖1 優(yōu)化過程Fig.1 Optimization process

緊湊鋪畫時列車運行圖結(jié)構(gòu)的優(yōu)化問題可轉(zhuǎn)化為經(jīng)典的旅行商問題（TSP）.設(shè)G=（V，E）是帶正權(quán)的完全圖，V=（1，2，…，m+1），E表示完全圖中所有邊的集合，邊（k1，k2）的費用記為Ck1k2.

節(jié)點網(wǎng)絡(luò)完全圖的費用矩陣

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

為了優(yōu)化緊湊鋪畫列車運行圖的結(jié)構(gòu)，確定最優(yōu)的列車運行線順序，實現(xiàn)第一列車從始發(fā)站出發(fā)至最末列車到達(dá)終到站的間隔時間最小化的目標(biāo)，巡回路徑總費用最小化的TSP問題表達(dá)為

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

3 遺傳算法參數(shù)設(shè)計

3.1 染色體編碼

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

3.2 適應(yīng)度函數(shù)

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

f=1/（Td+αNt），

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

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

3.3 遺傳算子

（1）選擇算子

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

（2）交叉算子

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

（3）變異算子

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

3.4 遺傳算法求解流程

具體步驟如下：

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

（2）按照染色體編碼方式生成初始種群，當(dāng)前代數(shù)n=1.

（3）計算當(dāng)前種群中各染色體的適應(yīng)度，選擇最優(yōu)個體直接進(jìn)入下一代，剩余個體通過輪盤賭隨機(jī)選擇.

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

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

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

4 實例驗證與結(jié)果分析

為檢驗算法效果，用2015年京滬高鐵為例進(jìn)行驗證.以全路運行圖中由北京南始發(fā)上海虹橋終到的全部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，增加一個虛擬節(jié)點，其編號為40.設(shè)定遺傳算法參數(shù)，種群大小

Mpop=60，

交叉概率

Pc=0.4，

變異概率

Pm=0.05，

最大遺傳代數(shù)nmax=300.

經(jīng)300次迭代后，取當(dāng)代種群中最優(yōu)染色體，其編碼為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，去除最末的虛擬節(jié)點，解碼成列車運行線的鋪畫順序：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，比現(xiàn)行方案縮短133 min，約21.2%，大幅度地提高了列車運行圖的通過能力.

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

5 結(jié) 論

本文從緊湊鋪畫列車運行圖力求通過能力最大為出發(fā)點，建立了高速鐵路列車運行圖結(jié)構(gòu)優(yōu)化數(shù)學(xué)模型，并設(shè)計了遺傳算法參數(shù)進(jìn)行求解.以2015年京滬高鐵為例，編制出結(jié)構(gòu)更合理的列車運行圖方案，得到以下主要結(jié)論：

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

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

對于我國逐漸成型的高速鐵路網(wǎng)絡(luò)，條件更加復(fù)雜，列車運行圖的結(jié)構(gòu)還需進(jìn)一步深入研究.

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

［2］ 孫焰.單線列車運行圖優(yōu)化理論及計算機(jī)編制方法［D］.長沙：長沙鐵道學(xué)院，1997.

［3］ 周磊山，胡思繼.計算機(jī)編制網(wǎng)狀線路列車運行圖方法研究［J］.鐵道學(xué)報，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］ 倪少權(quán)，呂紅霞，楊明倫.全路列車運行圖編制系統(tǒng)設(shè)計的研究［J］.西南交通大學(xué)學(xué)報，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］ 彭其淵，楊明倫，倪少權(quán).單線實用貨物列車運行圖計算機(jī)編制系統(tǒng)［J］.西南交通大學(xué)學(xué)報，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］ 彭其淵，朱松年.網(wǎng)絡(luò)列車運行圖的數(shù)學(xué)模型及算法研究［J］.鐵道學(xué)報，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ìn)，等.單線列車運行圖鋪劃的時間循環(huán)迭代優(yōu)化方法［J］.鐵道學(xué)報，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ìn)，等.單線列車運行調(diào)整的最早沖突優(yōu)化方法［J］.中國鐵道科學(xué)，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］ 馬建軍.基于網(wǎng)狀線路的京滬高速鐵路列車運行圖編制理論的研究［D］.北京：北方交通大學(xué)，2002.

［10］ 許紅，馬建軍，龍建成.客運專線列車運行圖編制模型及計算方法研究［J］.鐵道學(xué)報.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］ 謝美全，聶磊.周期性列車運行圖優(yōu)化模型研究［J］.鐵道學(xué)報，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］.鐵道學(xué)報，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］ 周文梁，史峰，陳彥.基于定序優(yōu)化的客運專線列車運行圖鋪劃方法［J］.鐵道學(xué)報，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］ 周文梁，史峰，陳彥，等.客運專線網(wǎng)絡(luò)列車開行方案與運行圖綜合優(yōu)化方法［J］.鐵道學(xué)報，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］ 周明，孫權(quán)棟.遺傳算法原理及應(yīng)用［M］.北京：國防工業(yè)出版社，1999：143-155.

高速鐵路列車運行圖結(jié)構(gòu)優(yōu)化研究

張小炳1，2， 倪少權(quán)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

張小炳，倪少權(quán)，潘金山.高速鐵路列車運行圖結(jié)構(gòu)優(yōu)化研究［J］.西南交通大學(xué)學(xué)報，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

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

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

倪少權(quán)（1967—），男，教授，博士，博士生導(dǎo)師，研究方向為運輸組織理論與系統(tǒng)優(yōu)化，E-mail：shaoquanni@163.com

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