袁才清

摘 要：本文以2015年京滬高速鐵路數(shù)據(jù)進(jìn)行實(shí)例驗(yàn)證，建立列車運(yùn)行圖結(jié)構(gòu)的優(yōu)化方案。計(jì)算結(jié)果表明：原方案開行39列列車最少需628 min，優(yōu)化方案的開行時(shí)間比原方案的開行時(shí)間減少了133 min，約21.2%，能更好地滿足高峰時(shí)段的客流要求以及車站突發(fā)性客流增加時(shí)需盡快密集發(fā)車的要求。

關(guān)鍵詞：列車運(yùn)行圖;高速鐵路列車;通過能力;遺傳算法

1 高速鐵路列車運(yùn)行圖參數(shù)描述

設(shè)高速鐵路某線路上的車站集為，為上行方向（或下行方向）列車從線路區(qū)段始發(fā)站到終到站依次經(jīng)過的車站，為線路上的車站總數(shù)。線路上的列車集為，線路上的列車數(shù)為。對于列車在車站只有停與不停兩種情況，用0-1變量描述：

表示列車的停站序列。表示高速列車在站的停站時(shí)分，表示不停站直達(dá)列車的旅行時(shí)分，表示起車附加時(shí)分，表示停車附加時(shí)分。

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

2 高速鐵路列車運(yùn)行圖結(jié)構(gòu)優(yōu)化模型

根據(jù)既定的高速鐵路停站方案，通過對列車進(jìn)行合理排序，優(yōu)化列車運(yùn)行圖結(jié)構(gòu)，可以提高鐵路通過能力。優(yōu)化目標(biāo)為使緊湊鋪畫的列車運(yùn)行圖中第一列列車從始發(fā)站出發(fā)至最后一列列車到達(dá)終到站之間的總間隔時(shí)間最短。將每條列車運(yùn)行線視為一個(gè)節(jié)點(diǎn)，構(gòu)造節(jié)點(diǎn)網(wǎng)絡(luò)完全圖。用表示節(jié)點(diǎn)編號（與其對應(yīng)的運(yùn)行線編號）。令從節(jié)點(diǎn)指向節(jié)點(diǎn)的路徑的費(fèi)用等于列車和的最小始發(fā)間隔時(shí)間，那么根據(jù)定義1和定義2，整個(gè)網(wǎng)絡(luò)完全圖中所有路徑的費(fèi)用可以根據(jù)既定的高速鐵路停站方案來確定。

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

節(jié)點(diǎn)網(wǎng)絡(luò)完全圖的費(fèi)用矩陣：

用變量表示邊是否存在于總費(fèi)用最小的巡回路徑中，若是=1，否則=0。這里有一種特殊情況，若時(shí)，取=0，因?yàn)檫@樣的邊在節(jié)點(diǎn)網(wǎng)絡(luò)完全圖中并不存在。所以待求解的矩陣：

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

式中：為巡回路徑子圖的邊的數(shù)目。

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

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

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

（2）適應(yīng)度函數(shù)。適應(yīng)度函數(shù)常取路徑長度的倒數(shù)，即。結(jié)合TSP的約束條件（每個(gè)節(jié)點(diǎn)經(jīng)過且只經(jīng)過一次），適應(yīng)度函數(shù)修正為：，式中：為對TSP路徑不合法的度量，這里取為未遍歷的節(jié)點(diǎn)的個(gè)數(shù);為懲罰系數(shù)，取值通常為節(jié)點(diǎn)之間最長距離的兩倍多，這里取2.1。

（3）遺傳算子。1）選擇算子。用適應(yīng)度函數(shù)對群體中所有個(gè)體進(jìn)行評估，將選擇算子作用于群體，選擇的目的是把優(yōu)化的個(gè)體直接遺傳到下一代，或通過配對交叉產(chǎn)生新的個(gè)體再遺傳到下一代。采用輪盤賭與精英個(gè)體保存的混合策略，選擇當(dāng)前種群中的最優(yōu)個(gè)體直接進(jìn)入下一代，剩余個(gè)體通過輪盤賭隨機(jī)選擇，這種方式能夠在一定程度上避免算法過早收斂。2）交叉算子。采用部分匹配交叉策略：隨機(jī)選擇兩個(gè)交叉點(diǎn)，將兩交叉點(diǎn)之間的基因段互換，將互換后的基因段以外的部分中與互換后基因段中沖突的節(jié)點(diǎn)用另一父代相應(yīng)位置的碼值代替，直至沒有沖突。3）變異算子。對群體中的個(gè)體，隨機(jī)選擇染色體中的兩點(diǎn)，交換其碼值。

（4）遺傳算法求解流程。具體步驟如下：1）設(shè)定參數(shù)，種群大小為，交叉概率為，變異概率為，最大遺傳代數(shù)為。2）按照染色體編碼方式生成初始種群，當(dāng)前代數(shù)。3）計(jì)算當(dāng)前種群中各染色體的適應(yīng)度，選擇最優(yōu)個(gè)體直接進(jìn)入下一代，剩余個(gè)體通過輪盤賭隨機(jī)選擇。4）根據(jù)給定的交叉概率，對種群進(jìn)行一致性交叉操作。5）根據(jù)給定的變異概率，對種群進(jìn)行變異操作，更新代數(shù)。6）算法終止條件。若，轉(zhuǎn)步驟3）;否則，輸出當(dāng)前種群中最優(yōu)染色體，并解碼為列車運(yùn)行圖編制方案。

4 實(shí)例分析

為了對該優(yōu)化模型的優(yōu)化效果進(jìn)行驗(yàn)證，以2015年京滬高鐵列車為案例進(jìn)行驗(yàn)證。以全路運(yùn)行圖中由北京南始發(fā)上海虹橋終到的全部39列速度為300 km/h的下行列車為研究對象。

全路運(yùn)行圖中京滬高鐵在各站的停站時(shí)間如表1所示，具體停站方案如表1所示。

將表2中各列車依次編碼為1至39，增加一個(gè)虛擬節(jié)點(diǎn)，其編號為40。設(shè)定遺傳算法參數(shù)，種群大小;交叉概率;變異概率;最大遺傳代數(shù)。

經(jīng)過300次迭代后，取當(dāng)代種群中，取當(dāng)?shù)胤N群中最優(yōu)染色體，其編碼為1-2-5-6-4-3-7-15-13-38-9-8-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é)點(diǎn)，解碼成列車運(yùn)行線的鋪畫順序。

5 結(jié)論

本文以列車通過能力最大為出發(fā)點(diǎn)來鋪畫高速列車的運(yùn)行圖，然后建立關(guān)于高速鐵路列車運(yùn)行圖結(jié)構(gòu)優(yōu)化的數(shù)學(xué)模型，再利用遺傳算法及其設(shè)計(jì)參數(shù)對模型進(jìn)行求解。高速鐵路在我國成為人們出行的主要交通工具以及我國的高速鐵路逐漸成網(wǎng)，而且條件更加復(fù)雜，對列車運(yùn)行圖的結(jié)構(gòu)還需進(jìn)一步深入研究。

參考文獻(xiàn)：

[1]胡思繼.列車運(yùn)行圖編制理論與方法[M].北京：中國鐵道出版社，2013.

[2]周文梁，史峰，陳彥，等.客運(yùn)專線網(wǎng)絡(luò)列車開行方案與運(yùn)行圖綜合優(yōu)化方法[J].鐵道學(xué)報(bào)，2011，33（2）：1-7.