高速鐵路動車組運用計劃編制數學模型及優化

羅榮輝，王煥民，秦慧芳

（蘭州交通大學 機電技術研究所，蘭州 730070）

high-speed railway LUO Ronghui, WANG Huanmin, QIN Huifang

高速鐵路動車組運用計劃編制數學模型及優化

羅榮輝，王煥民，秦慧芳

（蘭州交通大學 機電技術研究所，蘭州 730070）

分析影響動車組運用計劃編制的主要因素，在不固定動車組運用區段的前提下，根據列車運行圖，以動車組的運用交路和檢修模式為約束條件，以減少動車組的使用數量、降低檢修成本為優化目標，建立動車組運用計劃和檢修計劃的一體化優化模型，設計求解模型的遺傳算法。

動車組運用計劃；檢修計劃；旅行商問題；遺傳算法

動車組運用計劃是根據給定的列車運行圖、有關動車組檢修修程的規定以及檢修基地條件等，對動車組在什么時間、在哪個車站、擔當哪次列車，在什么時間、在哪個車站、進行哪種類型的檢修等作出具體安排，以確保運用狀態良好的動車組完成列車運行任務。考慮動車組本身在鐵路運營費用中所占比重較大，其檢查維修花費大量的人力、物力，因此，在保證動車組安全運行的前提下，如何努力提高動車組的高效運行，減少動車組使用的數量以及檢查維修的次數對高速鐵路動車組運用計劃具有十分重要意義。目前，我國動車組運用計劃編制仍采用傳統的人工勾畫方式，既耗費了巨大的人力、物力，運用計劃的編制效率又低，需要進行繁雜的重復工作，因此，研究適合我國高速鐵路發展的動車組運行模式和算法具有重大的意義。我國不少專家對動車組運用計劃的編制方法進行了研究，例如文獻[1]以動車組的運用交路和檢修規程為主要約束，采用了模擬退火算法，文獻[2-4]將動車組運用計劃分為交路計劃和檢修計劃分別編制。文獻[5]提出了動車組周期性運用思想，文獻[6]分析了檢修能力不同時動車組運用計劃的編制優化。

本文在動車組不固定運行區段的前提下，以檢修模式和運行交路為約束，對動車組運用計劃的數學模型和優化進行研究。動車組的使用數量與列車運行時間、列車車底接續時間之和與運行圖周期的比值相等，并且列車運行時間與運行圖周期為給定常數，所以，動車組使用數量最少可以轉化為列車之間車底接續時間最少。“檢修成本最低”即為動車組“必須的檢修次數最少”，根據動車組1級檢修修程規定，為其選擇合適的檢修地點。

1 動車組運用計劃編制的理論

動車組運用計劃的編制以列車運行圖為基礎，建立高速鐵路動車組與列車運用任務間的對應關系。高速鐵路動車組的運用任務，表現為運用任務間的車底接續關系，也就是運用任務間的組合關系。可以將動車組運用計劃編制問題歸納為組合優化問題的一種。在組合優化問題中，動車組運用計劃編制又可以近似看作旅行商問題進行求解。把每一個運用任務看成一座城市，高速鐵路動車組相當于旅行商，動車組擔當運用任務相當于旅行商走訪城市，那么動車組運用過程就相當于旅行商的旅行過程。因此，動車組運用計劃編制問題可以歸納為類似旅行商的問題。

根據動車組本身的運用過程分析，動車組運用計劃編制又有本身的特點，具體表現如下。

1.1 有多個旅行商

動車組運用計劃中需要多個動車組，對應的旅行商問題中應有多個旅行商。

1.2 城市間接續的方向性

運用任務的完成有時間作為約束，動車組要按照已編制列車運行圖上的時間約束來擔當各次的運輸任務，對應的旅行商問題中的城市間的接續具有方向性。

1.3 不是所有的城市都必須訪問

動車組的運用任務分為“運營”和“檢修”，對應的城市也就需要分開對待。動車組運用任務為“檢修”時，旅行商即動車組只有在需要時才會訪問該城市。動車組運用任務為“運營”時，旅行商即動車組必須進行訪問。

1.4 多旅行商多起點多終點

多旅行商問題是由多條不同起點出發，并結束于不同終點的單向路徑。

2 數學模型

參數設定：

S：高速鐵路線上始發、終到的車站數，用集合S={1, 2, …, m}表示。

L：始發終到列車數，用集合L={L1, L2, …, Ln}表示。

V：列車，所有列車運行線集合為V={vi}。

E：列車之間的接續時間，集合E{eij|eij=(vi, vj)}。

其中，tai—高速列車vi的最終到達時間；

tdj—高速列車vjj的開始出發時間；

sai—列車vi的最終終到達車站；

sdj—列車vj的開始出發車站；

式（1）為目標函數，表示列車間車底接續時間的總和最小、列車的檢修次數最小，ω1和ω2為權重系數；

式（2）～式（8）為動車組運用計劃模型的約束函數，其中，式（2）和式（3）用于保證每列列車節點處有且只有一次應該被覆蓋；

式（4）保證僅當 需要進行檢修時，安排檢修任務；

式（5）和式（6）表示高速動車組擔當任何列車i后，走行距離和所用的累計時間都不大于1級檢修修程標準；

式（7）表示動車組擔當任意列車i后，總的走行里程和總的時間不可以是零。

3 算法框架

（1）編碼：對每個車站的接續進行編碼。

（2）種群初始化：初始化的參數有種群個數（即各個車站的接續方式）、染色體基因個數（即運用任務的個數）、迭代次數、交叉概率和變異概率。

（3）適應度函數：任意兩車站的距離已知，每個染色體（即運用任務的隨機排列）可計算出總距離，將總距離的倒數作為適應度函數。

（4）選擇操作：采用以適應度比例為基礎的選擇方法，即適應度越高的個體被選中的幾率也就越大，同時在選擇中保留適應度最高的個體。

（5）交叉操作：在種群中兩兩一對隨機交換“基因片段”。

（6）變異操作：設計算法時，會給每個基因設置一個非常小的突變概率。

算法流程框圖如圖1所示。

圖1 算法流程圖

4 算例

模擬高速鐵路專線，對本文中的模型及算法進行驗證。使用Intel(R) Core(TM) i5-4210M CPU @ 2.60 GHz內存4.00 GB的個人計算機，在MATLAB2012開發環境下編程實現。兩動車段分別設立在武漢和新廣州，高速鐵路動車組運用所設立在郴州和新韶關；檢修修程及檢修時間如表1所示。

表1 動車組檢修

編制武漢至新廣州動車組運行圖，把算法編制結果與人工編制的結果進行對比。如表2所示。

表2 動車組運用計劃編制結果比較

由表2可知，遺傳算法與人工編制動車運用計劃相比，減少了動車組的使用數量，增加了動車組日總走行公里，提高了動車組的利用效率。

5 結束語

動車組運用計劃的編制直接影響高速動車組的運用效率，本文結合當前動車組運用的實際問題，將動車組運用計劃的編制看作旅行商尋找最優路徑問題，應用遺傳算法對問題進行分析優化，以達到減少動車組接續時間和提高動車組運用效率的目的。

[1]王忠凱. 動車組運用檢修計劃優化方法的研究[D].北京：中國鐵道科學研究院，2012.

[2]李 華. 高速鐵路動車組運用計劃編制理論與方法研究[D].北京：北京交通大學，2013.

[3]王忠凱,史天運,張惟皎,等. 動車組運用計劃和檢修計劃一體化編制模型及算法[J]. 中國鐵道科學，2012（3）：102-108.

[4]蔣繼磊,楊志杰. 動車組運用計劃編制及其優化[J]. 鐵道運輸與經濟，2010（4）：37-40 ，48.

[5]耿敬春，肖榮國，倪少權，等. 客運專線動車組周期性運用計劃編制的研究[J]. 鐵道學報，2006（4）：17-21.

[6]張才春，陳建華，花 偉. 基于不同檢修能力的動車組運用計劃研究[J]. 中國鐵道科學，2010（5）：130-133.

[7]史 峰，周文梁，郁宇衛，等. 客運專線動車組運用計劃優化模型與算法[J]. 鐵道學報，2011（1）：8-13.

[8]陳華群. 動車組運用計劃編制系統相關問題研究[D].成都：西南交通大學，2007.

[9]張 杰，陳 韜，施福根. 客運專線動車組運用計劃的計算機編制[J]. 西南交通大學學報，2006（5）：635-640.

[10]李 華，韓寶明，張 琦，等. 動車組交路計劃優化模型與算法研究[J]. 鐵道學報，2013，35（3）：1-8.

[11]郁宇衛. 客運專線動車組運用計劃優化研究[D].長沙：中南大學，2009.

[12]耿敬春. 京滬高速鐵路動車組運用計劃編制相關問題研究[D].成都：西南交通大學，2009.

[13]陳玲娟. 遺傳算法在動車組運用計劃編制中的應用[J]. 交通運輸工程與信息學報，2009（2）：67-71.

責任編輯徐侃春

Mathematical model and optimization for EMU operation scheduling of

( Mechatronics and T&R, Lanzhou Jiaotong University, Lanzhou 730070, China )

The paper analyzed the main factors that affected the EMU operation scheduling, established an integrated optimization model of EMU operation plan and maintenance plan. The model was established under the premise of unsettled operating zone of EMU, according to the train operation diagram, constrained by EMU operation routing and maintenance mode, aimed to reduce the operation number of EMU and maintenance costs. The Genetic Algorithm was used to solve the model.

EMU operation plan; maintenance plan; traveling salesman problem; Genetic Algorithm

U266∶U268.2∶TP39

A

1005-8451（2016）12-0008-04

high-speed railway LUO Ronghui, WANG Huanmin, QIN Huifang

2016-05-03

羅榮輝，在讀碩士研究生；王煥民，講師。