考慮檢修能力約束的動車組交路計劃優化模型與算法

江政杰, 聶 磊，賀振歡，童佳楠

（1.北京交通大學?交通運輸學院，北京?100044；2.中鐵二院工程集團有限責任公司?土木建筑設計????研究二院，四川?成都?610036）

考慮檢修能力約束的動車組交路計劃優化模型與算法

江政杰1, 聶 磊1，賀振歡1，童佳楠2

（1.北京交通大學?交通運輸學院，北京?100044；2.中鐵二院工程集團有限責任公司?土木建筑設計????研究二院，四川?成都?610036）

我國高速鐵路動車段所數量較少且分布較為集中，動車組一級檢修能力成為編制動車組交路計劃的重要制約條件。鑒于此，對動車組交路計劃編制問題建立考慮動車段所一級檢修能力約束的多目標整數規劃模型。首先，依據動車組交路接續規則和一級檢修條件構造交路備選集，并將交路計劃編制問題表達為集合劃分問題；其次，采用基于重要性分級的分層序列法求解模型，即多目標模型被分解為主目標“動車組運用數量最小”，以及次目標“檢修次數最少”的?2?個單目標整數規劃模型，并采用傳統的精確算法求解；最后，通過算例分析驗證了模型與算法的有效性，為動車組交路計劃的優化編制提供依據。

高速鐵路；動車組交路；分層序列法；多目標整數規劃

0引言

隨著我國高速鐵路的快速成網，動車組列車開行數量不斷增加，動車組的運用和檢修是否合理在很大程度上影響鐵路部門的運營成本，動車段所的一級檢修能力已經成為動車組列車開行的重要制約條件。因此，優化動車組交路計劃，節省動車組運用數量，降低動車組檢修成本，成為高速鐵路運輸組織面臨的重要現實問題和技術難題。

在既有的研究中，我國大多數學者通過整數規劃模型對動車組交路計劃進行建模，并分別以動車組數量最少和動車組檢修次數最少為優化目標；求解算法則有分枝定價算法等精確算法，以及粒子群算法、蟻群算法等智能算法。在精確算法方面，王瑩等[1-2]通過研究動車組運用規程的特點，構建接續網絡模型，并采用分支定價算法進行求解；LU C等[3]基于貪婪算法構造接續網絡，并采用分支定界算法進行求解。在智能算法方面，李華等[4]、ZHOU Y等[5]基于給定成對列車運行圖建立多目標整數規劃模型，并采用改進的蟻群算法進行求解；王忠凱[6]將動車組交路計劃抽象為帶狀態約束的旅行商問題，構建相應的接續網絡，并且采用蟻群算法進行求解；李華等[7]、李建等[8]則主要基于列車運行圖構造動車組交路網絡，采用粒子群優化算法進行求解；苗建瑞等[9]將動車組交路計劃歸結為帶補給的多旅行商問題，采用分層優化啟發式算法進行求解；黃興亮[10]分析影響動車組交路計劃編制的因素，構建動車組交路計劃編制與列車運行圖協調優化的模型，并且采用改進的蟻群算法進行求解；陳然等[11]針對動車組列車網絡化運行條件下的復雜情況，將編制動車組運用計劃的經驗加入專家系統，通過設計基于專家系統指導的最大最小蟻群算法對模型進行求解；余曉園等[12]分析高速鐵路列車開行模式對動車組運用的影響，提出基于列車接續網絡的動車組交路計劃優化模型，并運用 Cplex 軟件進行求解。

既有研究中大都以動車組數量和檢修次數的線性加權最小為目標函數，但目標權重系數依賴于決策者的主觀判斷，在實際應用中難以客觀地確定；并且對于2個定位不同的目標，加權目標實際意義不明確。因此，首先基于王昕[13]提出的思路，通過分析交路生成的可行性和合理性約束，建立動車組交路備選集，從而將問題通過多目標整數規劃建模；進而，基于重要性將目標函數進行分級，并通過分層序列法對模型進行求解；最后通過算例驗證模型的有效性。

圖1　動車組交路計劃示例

1問題描述

定義動車組交路段為單個動車組或重聯動車組擔當的列車或列車組合；動車組交路則由單個或若干個動車組交路段組成，在動車組列車運營過程中周期性地重復執行。動車組交路計劃示例如圖 1 所示。在同一個交路中，2 個相鄰交路段中前一交路段的終到站必須與后續交路段的始發站一致；交路中最后 1 個交路段的終到站必須與第 1 個交路段的始發站一致。在圖1中，動車組 L1 所擔當交路段 1 的始發、終到站一致，因而交路段 1 構成單日交路；而交路段 2 的始發站和交路段 3 的終到站一致，并且交路段 2 和交路段 3 符合相鄰的接續關系，因而交路段 2 和交路段 3 組成 1 個雙日交路。動車組交路計劃是根據動車組管理和檢修規程規定、動車組配屬情況，以及給定的列車運行圖任務，制訂需要完成的列車擔當任務和動車組一級檢修任務的動車組運用計劃。

1.1動車組交路的數學描述

1.2構建動車組交路的約束條件

動車組交路計劃是高速鐵路/客運專線的基本運輸計劃之一，編制過程中的影響因素很多。為簡化問題，主要考慮以下約束條件。

（1）接續條件。由同一動車組擔當的相鄰 2 個交路段的間隔時間必須大于動車組在車站進行接續作業需要的最小時間；由同一動車組擔當的相鄰 2個交路段中，前一交路段的終點必須和后一交路段的起點相同。假定 Rh1, w1和 Rh2, w2為符合接續條件的任意 2 個交路段，tmin為最小接續時間，則有

（2）一級檢修條件。根據動車組檢修規程，由同一動車組擔當的交路段中，列車的累計走行里程不能超過規定的一級檢修累計里程 (一般為4 000 km，允許上下浮動各 10%)；同時，列車的累計運行時間不能超過規定的一級檢修累計運行時間 48 h。以給定的 2 d 列車運行圖為基礎構造的動車組交路段必然滿足規定的一級檢修累計運行時間約束，因而只需滿足一級檢修累計里程約束。

2動車組交路計劃優化模型

定義動車組交路備選集合為 Rf；cr為擔當動車組交路 r 的動車組數量，組，r?∈?Rf；xr為 0-1 決策變量，如果動車組交路被選擇，則 xr= 1，否則為 xr= 0；Q 為動車段所集合；bq, r表示交路 r 在動車段所 q 占用的一級檢修能力，組，q?∈?Q；nq表示動車段所 q 的一級檢修能力，組；L 為給定運行圖中的所有運行線的集合；δl, r為 0-1 變量，表示交路 r 是否覆蓋列車任務 l，l?∈?L，如果覆蓋則 δl, r= 1，否則為 δl, r= 0；nr表示動車組交路 r 的檢修次數，如果交路里程超過一級檢修里程，則檢修次數為 2 次，否則為 1 次。

以動車組數量最少為主要優化目標、以檢修次數最少為次要優化目標構建多目標整數規劃模型。

（1）以動車組數量最少為主要優化目標建立整數規劃模型 (以下簡稱“M-1 模型”)。

式中：公式 ⑷ 為目標函數，表示以交路方案的動車組數量最少為目標；公式 ⑸ 為動車段所檢修能力約束；公式 ⑹ 為列車任務覆蓋約束，要求每個列車任務必須被覆蓋，并且只覆蓋 1 次。

（2）從 M-1 模型可以求出當前動車組交路方案下所需的最少動車組數量，以此為約束，以動車組檢修次數最少為目標建立整數規劃模型 (以下簡稱“M-2 模型”)。

式中：公式 ⑺ 表示所選擇交路方案的總檢修次數最少；公式 ⑻ 表示當前選擇的交路方案所需的動車組數量不能超過 M-1 模型求解得到的最少動車組數量；公式 ⑼ 和 ⑽ 與模型 M-1 的約束定義一致。

3動車組交路計劃優化模型求解

3.1交路備選集構造算法

交路備選集是指具有實際開行可能的、合理的動車組交路集合，它是以列車運行圖為輸入，以動車組一級檢修里程和時間規定、動車段所檢修能力為約束條件得到的備選交路集合。以 2 d 列車運行圖為基礎構造交路備選集，則擔當任意可行交路的列車累計運行時間滿足一級檢修時間周期約束。交路備選集構造算法的流程如下。

（1）以單條運行線構造交路段，得到單條運行線構成的交路段集合 R1，置迭代次數 n = 1。

（2）逐層進行廣度優先搜索過程，即以 n 條運行線構成的可行交路段集合 Rn構造 ( n + 1) 條運行線的可行交路段集合 Rn+1：遍歷可行交路段集合 Rn，任取 Rn中的第 i 個交路段 Rn, i，再遍歷集合 R1的任意交路段 R1,j，如果滿足公式 ⑴ 和公式 ⑵ 的約束條件，則將交路段 R1,j拼接到交路段 Rn, i之后，構成 ( n + 1) 條運行線組成的可行交路段，并添加到集合 Rn+1。

（3）對于 ( n + 1) 條運行線構成的可行交路段集合 Rn+1，如果交路段的始發和終到站一致，則該交路段為合理交路，將該交路添加到交路備選集 Rf中。如果存在里程超過一級檢修里程的交路，則進行超修程交路的修正，將該交路的檢修次數增加1 次，并將該交路分解為不超修程的 2 個交路段，擔當該交路段的動車組滿足約束條件 ⑶ 的里程約束。

（4）每層循環結束后，將由 ( n + 1) 條運行線構成的可行交路段集合 Rn+1保存到 R 集合中，此時如果 Rn+1中仍然有交路段存在，令 n = n + 1，轉到步驟（3），否則退出循環。

（5）為提高動車組運用效率，設定每個動車組的日均車公里數不少于 1 300 km，刪除交路備選集 Rf中日均車公里小于 1 300 km 的交路，得出合理的交路備選集。

3.2整數規劃模型求解

整數規劃求解的流程如下。

（1）根據給定的交路備選集 Rf，利用模型M-1 求解出最少動車組使用數量。

（2）根據當前交路方案求出的最少動車組使用數量，利用模型 M-2 求出當前交路方案最少檢修次數，如果無解，轉到步驟（3）；否則退出循環，得出最少檢修次數。

（3）松弛公式 ⑻ 的約束上界 F1，使最少動車組數量加 1，如果當前動車組數量超過限定的最大動車組使用數量 Fmax，則當前交路方案無解，退出循環；否則轉到步驟（2）。

多目標整數規劃求解流程如圖2所示。

圖2　多目標整數規劃求解流程

4算例分析

以 2013年7月列車運行圖上全部交路均在京廣(北京西—廣州南)、廣深 (廣州南—深圳北) 高速鐵路上的高速和動車組列車作為研究對象，應用構建的模型和算法編制動車組交路計劃，對模型進行驗證。

4.1數據準備

（1）列車運行圖數據。①始發、終到站包括北京西、石家莊、鄭州東、濟南西、西安北、信陽東、武漢、漢口、岳陽東、長沙南、廣州南、深圳北站共 12 個。②各折返站的最小折返作業時間為tmin= 15 min。③開行列車 38 對/d，列車最高運行速度 300 km/h。

（2）動車組數據。①動車組一級檢修里程為4 000±400 km。②動車段所檢修能力。京廣、廣深高速鐵路沿線設置的動車段所不僅承擔 2 條線路上運行動車組的一級檢修任務，而且還承擔其他線路上的動車組檢修任務。由于動車組交路的特點，每個動車段所每日實際檢修的動車組數量不是定值，并且不同時段的動車段所檢修能力占用情況也不同，因而應分時段考慮動車段所檢修能力。實際上，由于動車組一級檢修工作主要集中在 20 : 00 到次日 8 : 00 之間進行，該時段的檢修能力最為緊張，因而以該時間段的動車段所一級檢修能力作為檢算數據。京廣、廣深高速鐵路沿線動車段所檢修能力如表1所示。

表1　京廣、廣深高速鐵路沿線動車段所檢修能力及檢修數量計算結果 　　　組

4.2計算結果

根據原運行圖數據，完成算例中的全部列車運行任務實際共需要動車組 38 組，檢修 36 次。依據設計的模型和算法重新編制動車組交路計劃，共構造交路備選集 11 375 個，構造時間為 0.43 s；按照模型 M-1 求出最少動車組使用數量為 38 組，以此為約束條件按照模型 M-2 求解得出最少檢修次數為 32 次，比原運行圖規定的檢修次數少 4 次，說明采用該模型能夠進一步優化動車組交路計劃。最后求解得到動車組交路共 31個，其中單日單條交路 24 條，兩日交路 7 條，動車組日均車公里2 526 km，平均一級檢修里程為 3 000 km。計算得到的各動車段所檢修數量如表1所示，繪制的動車組交路如圖3所示。

圖3　動車組交路方案

5結束語

在動車組交路計劃編制過程中考慮了動車段所的一級檢修能力，運用多目標整數規劃模型按照最少動車組數為主要優化目標，最少檢修次數為次要目標，使用 Cplex 軟件進行精確求解，得到滿足約束條件的最少運用動車組數和最少檢修次數。求解結果表明，該模型與算法可有效求解動車組交路計劃編制問題，獲得較優的可行解。但是，目前的動車組交路計劃優化模型中考慮的約束較少，未考慮空車回送、動車組車型等條件；此外，在運行圖結構固定的條件下動車組運用效率仍然存在提高空間。從優化角度出發，列車運行圖與動車組交路計劃應同步編制，協同優化，才能最終實現動車組運用與列車運行的最優結合。

[1] 王 瑩，劉 軍，苗建瑞. 基于列生成算法的動車組檢修計劃優化[J]. 中國鐵道科學，2010，31 (2)：115-120.

WANG Ying，LIU Jun，MIAO Jian-rui. Column Generation Algorithms based Optimization Method for Maintenance Scheduling of Multiple Unit[J]. China Railway Science，2010，31(2)：115-120.

[2] 王 瑩. 動車組運用計劃和乘務計劃的優化方法研究[D].北京：北京交通大學，2009.

[3] LU C， ZHOU L S， YUE Y X，et al. A Branch and Bound Algorithm for the Exact Solution of the Problem of EMU Circulation Scheduling in Railway Network[J]. Mathematical Problems in Engineering，2016 (2)：1-14.

[4] 李 華，韓寶明，李得偉，等. 求解動車組交路計劃的改進型蟻群算法[J]. 物流技術，2013，32(2)：145-147，160.

LI Hua，HAN Bao-ming，LI De-wei，et al. Research on Improved Ant Colony Algorithm in EMU Routing Schemes[J]. Logistics Technology，2013，32(2)：145-147，160.

[5] ZHOU Y，ZHOU L S，WANG Y，et al. Using Improved Ant Colony Algorithm to Investigate EMU Circulation Scheduling Problem[J]. Discrete Dynamics in Nature and Society，2014(2)：1-13.

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

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

LI Hua，HAN Bao-ming，ZHANG Qi，et al. Research on Optimization Model and Algorithm of EMU Circulation Plan[J]. Journal of the China Railway Society，2013， 35(3)：1-8.

[8] 李 建，林柏梁，耿令乾，等. 基于交路接續的動車組運用計劃優化模型與算法[J]. 交通運輸系統工程與信息，2015，15(5)：172-177，194.

LI Jian，LIN Bo-liang，GENG Ling-qian，et al. Optimization Model and Algorithm for Motor Trainset Utilization Scheduling based on Routes Connection[J]. Journal of Transportation Systems Engineering and Information Technology，2015，15(5)：172-177，194.

[9] 苗建瑞，王 瑩，楊肇夏. 基于最優接續網絡的動車組交路計劃優化模型與算法研究[J]. 鐵道學報，2010，32(2)：1-7.

MIAO Jian-rui，WANG Ying，YANG Zhao-xia. Research on the Optimization of EMU Circulation based on Optimized Connecting Network[J]. Journal of The China Railway Society，2010，32(2)：1-7.

[10] 黃興亮. 動車組交路計劃編制優化理論與方法研究[D]. 成都：西南交通大學，2012.

[11] 陳 然，周磊山，樂逸祥，等. 基于專家系統的網絡化動車組運用計劃的編制[J]. 中國鐵道科學，2016，37(1)：108-116.

CHEN Ran，ZHOU Lei-shan，YUE Yi-xiang，et al. Network EMU Scheduling based on Expert System[J]. China Railway Science，2016，37(1)：108-116.

[12] 余曉園，王 瑩，李元凱. 高速鐵路列車開行模式對動車組運用的影響研究[J]. 鐵道運輸與經濟，2016，38(7)：1-6，46.

YU Xiao-yuan，WANG Ying，LI Yuan-kai. Study on Influence of High-Speed Railway Train Operation Mode on Utilization of EMU[J]. RailwayTransport and Economy，2016，38(7)：1-6，46.

[13] 王 昕. 高速鐵路動車組交路與列車運行方案圖協調優化方法研究[D]. 北京：北京交通大學，2015.

責任編輯：劉 新

Optimization Model and Algorithm for EMU Routing Plan with Constraint of Maintenance Capacity

JIANG Zheng-jie1, NIE Lei1, HE Zhen-huan1，TONG Jia-nan2

(1.School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China；2.The Second Civil Engineering Design & Research Institute，China Railway Eryuan Engineering Group CO.LTD, Chengdu 610036, Sichuan, China)

With less and unbalanced distribution of EMU depots in China, the capacity for Level-1 maintenance is becoming an important constraint of EMU routing plan. A multi-objective integer model for EMU routing plan is constructed with consideration of Level-1 maintenance capacity of EMU depot. Firstly, a potential set is constructed by considering the EMU route connection rule and the constraint of Level-1 maintenance condition, and the EMU routing plan is formulated as set partitioning problem. Secondly, based on the importance of the objectives, stratified sequencing method is used to decompose the multi-objective model into two single integral objective models by taking minimum number of EMU as the main objective and minimum maintenance as the secondary one, both of which can be solved by using the exact algorithm. Thirdly, a case study verifies the effectiveness of the optimization model and algorithm, and provides reference for the scheduling optimization of EMU routing plan.

High-Speed Railway; EMU Routing; Stratified Sequencing Method; Multi-Objective Integer Programming

1003-1421(2016)10-0077-06

U292.6

A

10.16668/j.cnki.issn.1003-1421.2016.10.16

2016-05-05

2016-08-29

國家自然科學基金資助項目(U1434207)；中國鐵路總公司科技研究開發計劃課題(2013X014-C)