檢修條件下動車組運用計劃編制研究

安 琪，王建英

（1.中國鐵道科學研究院 研究生部，北京 100081；2.中國鐵道科學研究院 通信信號研究所，北京 100081）

動車組檢修是保障列車運行安全的重要手段，優化動車組的運用和檢修計劃對于提高客運專線運輸生產效益具有重要意義。目前，提高動車組使用效率是各國學者普遍關注的問題，我國也對動車組運用問題進行了大量研究，如各種條件下動車組運用計劃編制的優化模型[1-3]，模擬退火算法在解決 TSP問題中的具體應用[4]。還有學者在研究解決商旅問題幾種算法的比較中，分析了蟻群算法、遺傳算法和模擬退火算法在解決問題時的優缺點[5]。因此，在考慮這3種算法的不同適用范圍的情況下，通過采用模擬退火算法結合有向圖的方法，研究檢修條件下根據接續時間和接續地點的優化模型，從而實現動車組運用計劃的編制。

1 模型的建立

1.1 問題的描述

采用有向圖 G＝(C，L) 表示動車組的運用網絡，如圖1所示。

圖1 有向圖 G＝(C，L)表示動車組的運用網絡

C＝{cis∣cis＝(tif，ξif，tid，ξid)}∪{ckr∣ckr＝(τkf，ζk，τkd)}是點的集合，包含cis和ckr兩部分。其中，點cis對應給定運行圖中的運行線 i，包括運行線的始發時刻 tif、終到時刻tid、始發車站 ξif和終到車站 ξid；點ckr對應動車組的一項檢修作業 k，包括檢修點 ζk、從車站去檢修點的離站時刻τkf和檢修完畢后從檢修點返回車站的到站時刻τkd。

式中：τid＝tid＋T作業＋T走行，T作業為擔當運行線i任務后在車站必要的作業時間；τif＝τid＋τ標＋T走行，T走行為出入檢修點的走行時間。

1.2 約束條件

1.2.1 檢修條件

一級修條件 X1：

二級修條件 X2：

三級修條件 X3：

如果動車組 i 滿足上述檢修條件 X2或X3，說明動車組應該檢修，如果當時正處在具有二、三級檢修能力的車站，則應立即進行檢修；否則，下次運行的終點站必須為具有二、三級檢修能力的車站。如果動車組i滿足條件 X1，則應在動車組當前所處車站進行檢修。3種檢修能力的判斷順序依次為X3、X2、X1。

1.2.2 接續條件

運行接續條件 X4：

式中：t標表示動車組連續運行的標準接續時間；tjf表示運行線j 下一次可接續運行的最早時刻；tid表示運行線 i的終到時刻。

檢修接續條件 X5：

式中：τ標表示進行第 k 級動車組檢修的標準持續時間。

1.2.3 運用條件

始發車站運用條件 X6：

式中：ξid表示動車組 i 當前所位于的車站；ξjf表示運行圖中第j條運行線的始發車站。

1.3 模型優化

在保證完成列車運行計劃規定的運輸任務和進行必要檢修作業的情況下，以投入動車組數量最少為目標，建立動車組周轉優化數學模型。在一個編制周期內，動車組數量最少可以用動車組周轉接續時間總和最小來表達，因此，考慮檢修條件下的動車組周轉優化模型可表示為：

式中：T 為動車組周轉接續時間總和，包含動車組擔當運行線的接續時間和必要的檢修作業時間；Nd為給定運輸任務中到達的動車組總數；Nf為給定運輸任務中出發的動車組總數；M 為可能的檢修作業數。

該約束表示對一條未被擔當的運行線j，或者由擔當運行線 i 的動車組擔當，或者由檢修后返回車站的動車組擔當。

該約束表示擔當運行線 i 的動車組，或者繼續擔當運行線j 的任務，或者去檢修地進行檢修作業。

該約束表示對于檢修作業 k，只能安排一組動車組，也可以不安排動車組，因此，檢修弧屬于非強制性的。

該約束表示完成檢修作業 k 的動車組，只能擔當一條運行線任務，也可以暫不擔當運行線任務。

xik為動車組擔當運行線 i 后是否進行檢修作業 k的控制變量，其值為：當滿足約束條件 X1、 X2、X3或同時滿足X1、 X2、X3時，xik＝1；否則，xik＝0。

xij為動車組擔當運行線 i 后是否接續運行線j 的控制變量，其值為：當不滿足約束條件 X1、 X2、X3，且滿足 X4、 X6時，xij＝1；否則，xij＝0。

xkj為動車組完成檢修作業 k 是否接續運行線j的控制變量，其值為：當滿足約束條件 X5時，xkj＝1；否則，xkj＝0。

2 算法求解

模擬退火算法 (Simulated Annealing，SA) 是基于所求解問題的求解過程與熔化物體退火過程的相似性進行的，其中 Metropolis 準則是 SA 算法收斂于全局最優解的關鍵，該準則以一定的概率接受惡化解，這樣就使算法跳離局部最優的陷阱。將固體內能 E 模擬為動車組周轉接續總時間 T，溫度 t 演化成動車組數量 N，運行線之間的接續關系用 Metropolis 準則來描述。模擬退火算法的詳細步驟如下。

步驟 1：初始化。①輸入列車運行計劃，包括動車組始發時刻 tif、始發車站 ξif、終到時刻 tid、終到車站 ξid。②輸入檢修作業時間標準，包括往返走行時間T走行、在車站必要的作業時間 T作業。③輸入基本參數，如 L1、L2、L3、t標、τ標等。④根據運行接續條件 X4和始發車站運用條件 X6，得到所有具有接續可能的交路數量 JN。⑤設置動車組下降量 η，動車組最少數量ZN 和評價值 δ。

步驟 2：生成初始解。初始動車組周轉接續總時間 T(0)＝T0，動車組初始數量為 N。

步驟 3：根據檢修條件X1、X2和 X3開啟或關閉控制變量 xik。

步驟 4：根據接續條件和運用條件 X4、X5和 X6開啟或關閉控制變量 xij和xkj，并根據控制變量狀態，調用 Metropolis 抽樣算法。返回狀態 T 作為本算法的當前解，Ti＝T。

步驟 5：按照下降量 η 減少動車組的數量，即 N＝Ni+1＝Ni－η，其中 Ni+1＜Ni，i＝i＋1。

步驟 6：判斷是否 N＞ZN，如果是，轉至步驟2，繼續進行任務；否則，得到不同動車組數量下最優的周轉接續時間的目標值 T。

步驟 7：對得到的不同動車組數量下周轉接續時間進行統計和比較。

Metropolis 抽樣算法描述如下。

（1）令 k＝0 時，當前解 T(0)＝T，在一定動車組數量 N下，進行以下各步操作。

（2）按照運行圖采用2-opt運算得到 L種不同接續方案下的周轉接續時間，并把這些時間作為當前解 T (k) 的所處狀態 T的一個臨域子集 N (T(k))＋T，從中隨機得到一個新狀態T (k＋1) 作為下一個候選解，計算時間之差Δt＝|1－T (k) / T (k＋1)|。

（3）如果Δt＜δ，則接受 T (k) 作為下一個當前解，否則，以概率 exp (－Δt/N) 接受 T (k＋1) 作為下一個當前解。

（4）k＝k＋1，如果 k＜L，則轉到（2）繼續進行；否則，繼續下一步。

（5）返回得到的一定動車組數量下的周轉接續時間 T(i)，結束。

3 仿真應用

以目前已有武廣高速鐵路資料為基礎，編制相應的列車運行圖，采用本文建立的優化模型和求解算法對所編制的運行圖進行動車組運用計劃優化。動車組檢修條件[6]為每走行 30 000 km 進行一次一級修，需耗時 4 h，最短立刻折返時間為 24 min。利用高速鐵路國家工程實驗室——運營調度仿真實驗室進行模擬仿真，在仿真過程中，通過改變動車組的運用數量，得到動車組平均利用率。其仿真結果如表1和圖2所示。

由表1可知，方案4為最優方案，說明在給定列車運行圖后，采用該模型和求解算法，通過不斷減少動車組的使用數量能夠得到優化的動車組運用計劃。由圖2可知，隨著動車組運用數量的等額減少，動車組平均利用率的提高幅度變小。

表1 不同動車組數量和接續方案下的動車組平均利用率

圖2 動車組平均在線運行時間和運用數量之間的關系

4 結束語

通過研究高速鐵路動車組運用的一般方法，重點了討論動車組運用計劃編制理論。以動車組接續時間、接續地點、動車組定檢里程為約束條件，以需要動車組數量最少和總的動車組周轉接續時間最短為目標函數，建立動車組運用計劃的數學模型，采用模擬退火算法進行求解，給出了動車組運用計劃編制算法流程，為實現動車組運用計劃的自動編制提供一種可供選擇的技術。

[1]張才春，花 偉，陳建華. 雙修制下的動車組運用計劃編制研究[J]. 鐵道學報，2010，32(3)：16-19.

[2]耿敬春. 客運專線動車組運用計劃編制優化研究[J]. 西華大學學報(自然科學版)，2008，27(6)：83-86.

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

[4]馮 劍，岳 琪. 模擬退火算法求解TSP問題[J]. 深林工程，2008，24(1)：94-96.

[5]李 敏，吳 浪，張開碧. 求解旅行商問題的幾種算法的比較研究[J]. 重慶郵電大學學報(自然科學版)，2008，20(5)：624-626.

[6]中華人民共和國鐵道部. 新建時速300～350公里客運專線鐵路設計暫行規定[Z]. 北京：中國鐵道出版社，2007.