基于遺傳算法的高鐵列車運行圖結構優化研究

袁才清

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

關鍵詞：列車運行圖;高速鐵路列車;通過能力;遺傳算法

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

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

表示列車的停站序列。表示高速列車在站的停站時分，表示不停站直達列車的旅行時分，表示起車附加時分，表示停車附加時分。

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

2 高速鐵路列車運行圖結構優化模型

根據既定的高速鐵路停站方案，通過對列車進行合理排序，優化列車運行圖結構，可以提高鐵路通過能力。優化目標為使緊湊鋪畫的列車運行圖中第一列列車從始發站出發至最后一列列車到達終到站之間的總間隔時間最短。將每條列車運行線視為一個節點，構造節點網絡完全圖。用表示節點編號（與其對應的運行線編號）。令從節點指向節點的路徑的費用等于列車和的最小始發間隔時間，那么根據定義1和定義2，整個網絡完全圖中所有路徑的費用可以根據既定的高速鐵路停站方案來確定。

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

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

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

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

式中：為巡回路徑子圖的邊的數目。

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

3 遺傳算法參數設計

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

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

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

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

4 實例分析

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

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

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

經過300次迭代后，取當代種群中，取當地種群中最優染色體，其編碼為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，去除最末的虛擬節點，解碼成列車運行線的鋪畫順序。

5 結論

本文以列車通過能力最大為出發點來鋪畫高速列車的運行圖，然后建立關于高速鐵路列車運行圖結構優化的數學模型，再利用遺傳算法及其設計參數對模型進行求解。高速鐵路在我國成為人們出行的主要交通工具以及我國的高速鐵路逐漸成網，而且條件更加復雜，對列車運行圖的結構還需進一步深入研究。

參考文獻：

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

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