基于遺傳算法的高鐵列車運(yùn)行圖結(jié)構(gòu)優(yōu)化研究

袁才清

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

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

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

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

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

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

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

根據(jù)既定的高速鐵路停站方案，通過(guò)對(duì)列車進(jìn)行合理排序，優(yōu)化列車運(yùn)行圖結(jié)構(gòu)，可以提高鐵路通過(guò)能力。優(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)編號(hào)（與其對(duì)應(yīng)的運(yùn)行線編號(hào)）。令從節(jié)點(diǎn)指向節(jié)點(diǎn)的路徑的費(fèi)用等于列車和的最小始發(fā)間隔時(shí)間，那么根據(jù)定義1和定義2，整個(gè)網(wǎng)絡(luò)完全圖中所有路徑的費(fèi)用可以根據(jù)既定的高速鐵路停站方案來(lái)確定。

緊湊鋪畫時(shí)列車運(yùn)行圖結(jié)構(gòu)的優(yōu)化問(wèn)題可轉(zhuǎn)化為經(jīng)典的旅行商問(wèn)題。設(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問(wèn)題表達(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開(kāi)始，依次經(jīng)節(jié)點(diǎn)2、3、4、5和6，最后返回節(jié)點(diǎn)1的遍歷路徑，這是針對(duì)TSP問(wèn)題的最自然的編碼方式。

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

（3）遺傳算子。1）選擇算子。用適應(yīng)度函數(shù)對(duì)群體中所有個(gè)體進(jìn)行評(píng)估，將選擇算子作用于群體，選擇的目的是把優(yōu)化的個(gè)體直接遺傳到下一代，或通過(guò)配對(duì)交叉產(chǎn)生新的個(gè)體再遺傳到下一代。采用輪盤賭與精英個(gè)體保存的混合策略，選擇當(dāng)前種群中的最優(yōu)個(gè)體直接進(jìn)入下一代，剩余個(gè)體通過(guò)輪盤賭隨機(jī)選擇，這種方式能夠在一定程度上避免算法過(guò)早收斂。2）交叉算子。采用部分匹配交叉策略：隨機(jī)選擇兩個(gè)交叉點(diǎn)，將兩交叉點(diǎn)之間的基因段互換，將互換后的基因段以外的部分中與互換后基因段中沖突的節(jié)點(diǎn)用另一父代相應(yīng)位置的碼值代替，直至沒(méi)有沖突。3）變異算子。對(duì)群體中的個(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è)體通過(guò)輪盤賭隨機(jī)選擇。4）根據(jù)給定的交叉概率，對(duì)種群進(jìn)行一致性交叉操作。5）根據(jù)給定的變異概率，對(duì)種群進(jìn)行變異操作，更新代數(shù)。6）算法終止條件。若，轉(zhuǎn)步驟3）;否則，輸出當(dāng)前種群中最優(yōu)染色體，并解碼為列車運(yùn)行圖編制方案。

4 實(shí)例分析

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

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

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

經(jīng)過(guò)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é)論

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

參考文獻(xiàn)：

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

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