基于專家系統的網絡化動車組運用計劃的編制

陳　然，周磊山，樂逸祥，路　超，周　宇

(北京交通大學 交通運輸學院，北京　100044)

隨著高速鐵路新線的開通，動車組的使用數量逐漸增大，但動車組的成本高昂，如何安全、經濟地運用動車組越來越受到人們的關注。

國外學者對動車組或機車運用進行了研究[1-6]，主要關注在為旅客提供足夠多的客車座席以及保證列車足夠牽引動力情況下，盡量減少客車和機車的使用數量。但國外鐵路線路里程短、客流量較少、運行線結構規律性明顯，而且旅客列車非固定編組，可以通過重聯、分解、連掛、無動力回送等方式增減編組輛數或機車數以適應客流變化，動車組運用情況與國內有較大不同，因此借鑒性較少。

國內專家重點研究動車組的交路計劃、檢修計劃和分配計劃，目的是減少動車組使用數量或提高動車組使用效率。王瑩等研究二級修以上的動車組檢修計劃，以檢修前累計運行里程最大為目標，通過構建接續網絡建立數學模型，以廣深線為例運用列生成算法求解[7]；在后續的研究[8]中，將動車組周轉計劃編制問題在列車運行圖可作微調的前提下進一步優化，實現動車組運用計劃與運行圖編制優化的協調。趙鵬等以京滬高鐵為實例，利用局域搜索產生單個動車基地的運用計劃初始解，再通過列車分組、路段交換形成多動車基地下的動車組運用計劃[9]。王忠凱等以動車組運用交路與檢修規程為約束，以減少動車組數和檢修成本為目標，設計了運用計劃與檢修計劃一體化編制的整數規劃模型，先求解約束條件生成可行的運用路徑集合，再以此為基礎設計模擬退火算法[10]。史峰等為描述動車組運用均勻性，以環形排列為動車交路建立模型，將檢修約束以罰值函數代入目標函數用基于三交換法的模擬退火算法求解[11]；在后續的研究中[12]，建立以車站作業時間、動車組接續時間和到發線數為約束條件,以列車旅行時間和動車組接續時間最小化為目標函數的綜合優化模型，將動車組周轉、到發線運用與運行圖整體優化。林柏梁等研究了固定區段和不固定區段動車組二級檢修特點，建立了相關模型[13]。李華等以設計接續邊的累計時間和里程為約束建立整數規劃模型，以武廣線為例引入動車組運用最優接續網絡為粒子飛行參考，運用粒子群算法求解[14]。張才春提出了基于簇式運用方式和動態備用方式編制動車組運用計劃，將動車組運用計劃優化問題轉化為多個小周期內的優化問題并使用蟻群算法求解[15]。這些研究多數使用智能算法求解單條線路的動車組運用計劃，在列車網絡化運行背景下可能會出現不適應的情況。

本文借鑒鐵路現場使用的機車周轉圖，突出網絡化運行下動車的累計運行里程和時間，以及需要擔當的各條運行線的里程和時間，提出網絡化動車組運用計劃圖。以動車組累計運行里程和時間、動車段(所)檢修能力、接續作業時間與檢修作業時間為約束條件，以動車組運用數量最少為最優目標、檢修次數最少為次優目標，建立動車組運用計劃雙目標規劃優化模型；設計基于專家系統的最大最小蟻群算法進行求解。以含有6條高速鐵路線的路網為例，求解動車組運用計劃。

1　問題描述

1.1　網絡化運行下動車組運用計劃的編制

隨著高速鐵路新線的開通，高速鐵路線路逐漸形成網絡布局，動車組在網狀線路間運行，大量跨線列車開行導致運行圖結構更復雜，更多不同類型的動車組運行在同一路網上而導致動車組運用計劃編制也更困難。然而，動車組運用問題的可優化范圍也變得更大。主要表現在：動車組不固定區段運行，將有更多的運行線接續組合，適當選擇接續運行線(如采用大小交路套跑模式)可以充分運用動車組；適當選擇檢修地點和檢修時機，讓動車組盡量運行到檢修里程的上界，在檢修次數不變的前提下多擔當運行任務。例如圖1所示，按線路分別編制動車組運用計劃需要4列動車組，若按圖2網絡化方式編制動車組運用計劃，可以讓動車組擔當更多線路的運輸任務，雖增加了動車組運行里程，但可節省2列動車組；由圖3(圖中數字表示運行線里程)也可知，適當選擇檢修作業的時間和地點，同樣能夠達到充分運用動車組、減少檢修次數的目的。總之，從路網角度求解動車組運用計劃，可以得到更多初始解空間，搜索到更優解，最終使全局優化效果大于各線優化效果之和[16]。

圖1　按線路分別編制動車組運用計劃

圖2　按路網編制動車組運用計劃

圖3　適當選擇檢修時機和地點節省用車

1.2　專家系統及其基于專家系統的改進蟻群算法

專家系統擁有某專業領域內大量的專家級知識，通過運用這些知識進行判斷及推理，可以解決該領域內的復雜問題。專家系統主要包含知識庫和推理機兩部分，其中，知識庫存儲專家的經驗知識，推理機負責響應用戶的查詢[17]。

成網條件下動車組運用計劃編制優化模型的求解較復雜，智能算法已經不能滿足模型求解的質量和速度，因此引入專家系統，設計基于專家系統的改進蟻群算法。該算法的原理為：若專家系統的知識庫中存在相應的經驗知識，則采用專家系統求解，否則采用蟻群算法求解；在編制完成動車組運用計劃后，對編制過程進行總結，得到新的知識經驗，并將其加入知識庫，以豐富知識庫。該算法的流程如圖4所示。

圖4　基于專家系統的改進蟻群算法的流程圖

2　網絡化動車組運用計劃圖的提出

既有動車組交路計劃圖的結構與運行圖結構較為相似，展示了單條線路的列車運行線信息，以及運行線的接續關系?？紤]到在編制動車組運用計劃過程中，編制人員更加關注整個路網上動車組運行里程或時間是否超過檢修規定，能否繼續擔當下次運行線任務。因此，基于既有的動車組運用計劃圖，提出網絡化動車組運用計劃圖。網絡化動車組運用計劃圖包括：運行線車次、擔當該車次的動車組車號、到發時刻、到發站、運行里程、運行時間和運行線間的接續關系，以及車站、動車段(所)在物理路網中的相對位置。網絡化動車組運用計劃圖避免了傳統繪制多線路動車周轉圖時需分塊鋪畫的情況，突出了動車組運行的里程、時間，以及累計運行的里程、時間等信息。

圖5為含有4座車站(S1，S2，S3和S4)、4條線路和1個動車運用所的路網結構圖。圖6為該路網圖的網絡化動車組運用計劃圖，圖中兩圓相連的折線表示接續對應的運行線，若折線是虛線則表示為檢修接續。圖7為圖6中數字含義的解釋示意圖。圖7中：圓內字符代表車次/擔當此次運行線的動車組車號；與圓相連的箭頭代表運行方向，指向圓為到達該車站，背離圓為離開該車站；箭頭線上下的4組字符中，靠近圓一側上方的字符代表該運行線的里程，靠近圓一側下方的為運行線的運行時間，遠離圓一側上方的為出發或到達時刻，遠離圓一側下方的為出發或到達車站站名；在指向圓的箭頭線的另一邊，線上方的表示動車組累計運行里程，線下方的表示動車組累計運行時間。

圖5　路網結構圖(單位：km)

圖6　網絡化動車組運用計劃圖

圖7　針對圖6中數字的含義解釋圖

圖8為圖6虛線框內箭頭線的解釋示意圖，圖8中各箭頭線線段的長短表示對應運行線運行里程的長短，箭頭指在豎線上的位置是按照對應運行線在該站到達或從該站出發時間順序等比例排布的。圖9為圖6中粗箭頭線所表示的動車交路段信息解釋圖。

圖8　針對圖6中虛線框內箭頭線的解釋示意圖

圖9　對應圖6中粗箭頭線所包含的動車組交路段信息(以001號動車組為例)

3　動車組運用計劃雙目標規劃優化模型

3.1　前提假設

首先做如下假設：動車組車型不可以混用；2列短編組的動車組重聯后不分解，按1列動車組考慮；在每個車站始發的列車數等于終到的列車數，只考慮列車在本站進行接續；在動車段(所)不計調車所用的時間；動車組只在每天的6:00—23:30之間開行；動車組運用采用不固定區段的運行方式。

3.2　集合定義

3.3　參數定義

(1)

(2)

(3)

(4)

3.4　變量說明

(2)決策變量xe,i(e∈E，i∈A)。若動車組e擔當運行線i的運輸任務，則xe,i=1，否則xe,i=0。

(3)變量xi,j(i,j∈A)。若運行線i為運行線j的緊前接續線，則xi,j=1，否則xi,j=0。

3.5　數學模型

以動車組使用數量最少為最優目標、動車組入段(所)檢修次數最少為次優目標，構建動車組運用計劃雙目標規劃優化模型，即

e∈E，i∈A

(5)

i∈A，j∈A，d∈D，e∈E

(6)

s.t.

(7)

(8)

(9)

(10)

(11)

(12)

約束條件中：式(7)表示對任意1條運行線，有且只有1列動車組擔當；式(8)和式(9)表示動車組最大運行時間和運行里程不允許超過《鐵路動車組運用維修規程》的規定；式(10)表示在動車段(所)d進行M檢修作業的動車組數量不能大于動車段(所)的檢修能力；式(11)表示運行線i和運行線j進行非檢修接續時，接續時間必須大于TR；式(12)表示運行線i和運行線j進行檢修接續時，接續時間必須大于從車站到動車段(所)往返運行時間與在動車段(所)檢修所需的時間之和。

4　求解算法

因為建立的動車組運用計劃雙目標規劃優化模型具有解空間龐大的特點，因此設計基于專家系統的改進蟻群算法對模型求解。

4.1　知識庫內經驗知識的豐富

在編制完成動車組運用計劃后，總結得到如下5條經驗知識。

(1)在選擇后續運行線時，避免選擇節省用車選擇范圍之外的運行線。

圖10　節省用車選擇范圍示意圖

(2)經驗知識只考慮動車組的累計運行里程。當選取的動車組的最大檢修里程較小時，只考慮緊湊接續，即將滿足接續時間要求和檢修里程最小的運行線接續。

(3)在節省用車選擇范圍之內，對于最大檢修里程較短的運行線，應優先選擇最大檢修里程較長的運行線接續；對于最大檢修里程較長的運行線，應優先選擇最大檢修里程較短的運行線接續。

(4)若動車組需入段進行某項檢修作業，則判斷其他檢修作業里程或時間是否也同時達到檢修要求，若達到則同時進行檢修。

(5)在夜間非行車期間，對到達動車組按最大檢修里程從大到小排序，在不超過動車段所檢修能力情況下，按照此順序對動車組進行檢修。

4.2　最大最小蟻群算法原理

參照文獻[19—20]中的最大最小蟻群算法，將運行線類比為城市，運行線接續時間類比為城市之間的距離，求解所有螞蟻遍歷所有城市后行走總距離最小的問題。該算法的轉移概率準則和信息素更新準則如下。

1)轉移概率準則

(13)

2)全局信息素更新規則(信息素遺留規則)

(14)

(15)

(16)

3)局部信息素更新規則(信息素揮發規則)

τij=(1-ζ)τij+ζτ0

(17)

(18)

式中：n為運行線的條數；tnn為在滿足接續作業時間要求前提下最短的接續時間；ζ為權重參數，滿足0<ζ<1。

增加如下2條防止算法過早收斂或停滯的規則。

(2)當系統接近停滯狀態(通過對各條邊的信息素大小的統計來測定)，或者在一定數量的迭代過程中不再有更優的路徑出現，則所有的信息素都被重新初始化。

4.3　基于專家系統指導的最大最小蟻群算法

動車組運用計劃雙目標規劃優化模型有動車組運用數量最少和檢修次數最少2個目標函數，考慮到1列動車組的購置成本遠大于其檢修成本，因此在求解時首先求解滿足動車組使用數量最少的解，多次求解后，若存在相同運用數量的解則比較檢修次數，取檢修次數較少的解為最優解，若不存在相同的解，則直接取動車組使用數量最少的解。

算法輸入：列車運行線的到發時刻、到發站、車次、運行里程和運行時間；動車組的初始運行里程和運行時間。

算法輸出：動車組運用計劃。

算法參數：可以接續運行線i的后續運行線集合Aallow，螞蟻數pmax，最大循環次數Kmax；經驗知識權重系數λ(一般0.55<λ<1.00)。循環次數K的初始值為0。

算法原理：在確定1條運行線的后續運行線時，先產生1個隨機數λ′，若λ′≤λ，則檢索知識庫中是否有滿足條件的經驗知識，如果有則按照經驗確定接續關系，否則按照智能算法確定接續關系；若λ′>λ，則采用最大最小蟻群算法確定接續關系；直到所有運行線都已確定后續運行線。在算法初期，λ應賦以較大值，以產生較優初始解，后期則應賦以較小值，同時配以較大ρ，以充分利用啟發式信息搜索。

具體算法步驟如下。

步驟2：p=p+1，取車站集合S中的1個元素s作為當前車站，取s站第1條到達運行線i為當前運行線。

步驟4：在(0,1)中產生隨機數λ′，若λ′≤λ，則采用知識庫的經驗知識求解，轉步驟5；否則采用最大最小蟻群算法求解，轉步驟6。

步驟5：檢測是否有符合下述經驗知識的情況。

(5)將24:00之后到達s站的動車組按最大檢修里程從大到小排序，若達到檢修里程下限的動車組有nlow個，則取前min{Cd,nlow}個動車組進行檢修作業。轉步驟6。

步驟7：按式(1)更新動車組各檢修的實際運行里程。若后續運行線j的Aallow為空集，則轉步驟8，否則轉步驟4。

步驟8：若仍存在沒有搜索過的車站，則選取下一個未被搜索的車站，記為s，取s站第1條未被接續的到達運行線i，轉步驟3；否則，若p

步驟9：按照全局信息素更新規則，對兩兩接續的運行線進行更新，若存在信息素大于τmax的，則將其修改為τmax；按照局部信息更新規則，對兩兩能夠接續的運行線接續信息素進行信息素揮發，若存在信息素小于τmin的，將其修改為τmin。

步驟10：記錄此次循環中的最優解，將當前最優解的動車組使用數量與歷史最優解的進行比較。若比歷史最優解的少，則將當前最優解賦給歷史最優解；若比歷史最優解的多，則保留當前歷史最優解；若與歷史最優解的相等，則再比較檢修次數，若比歷史最優解的少，則將當前最優解賦給歷史最優解，否則保留當前歷史最優解。

步驟11：若K=Kmax，則轉步驟12；否則K=K+1，轉步驟1。

步驟12：總結編制過程，得到新的知識經驗，并將其加入知識庫。

步驟13：輸出歷史最優解的動車組運用計劃，算法結束。

5　算例分析

本文以京滬、滬杭、寧杭、京津、滬寧、膠濟線組成實例路網，以北京、天津、濟南、青島、南京、上海、杭州為始發終到站，各站配備動車段或動車運用所。該路網中有432條列車運行線，始發終到信息見表1。其中北京和上海動車運用段(所)的檢修能力均為100列·d-1，南京和天津動車運用段(所)的檢修能力為30列·d-1，其余的均為20列·天-1。

表1　車站間始發終到運行線數表

由于動車組車型不可混用，不同車型動車組運用計劃需要分別制定，因此本實例只考慮其中的1種車型。考慮到二級檢修的大部分作業檢修里程較長，因此本實例只考慮二級檢修中檢修里程相對較短的M1作業，規定的其檢修作業里程[21-23]見表2。

表2　動車組檢修作業里程表

參數取值：螞蟻個數pmax=100只，循環次數Kmax=20次，經驗知識權重系數λ=0.70， 重要性參數α=1.1，β=1.1，信息素揮發因子ρ=0.2。

計算環境為：64位Win7系統，CPU主頻2.80 GHz，開發工具為Visual Studio 2010，開發語言為C#。用基于專家系統的最大最小蟻群算法求解，對模型重復進行5次求解，得到結果分別見表3。表3中動車利用率的計算公式為

(19)

優先選擇動車組數最少的解，若存在相同動車組使用數量的解。則再選擇檢修次數少的解，綜合以上2點，選擇第1次解或第4次解作為最終算法的解。

為了對比分析本文方法的有效性，僅使用蟻群算法對動車組運用計劃雙目標規劃優化模型求解，結果見表4。

對比表3和表4可知，采用基于專家系統的最大最小蟻群算法可以得到更優的解，并且計算的收斂速度更快。

再按線路分別編制動車組運用計劃。將杭州站(寧杭線和滬杭線上到達杭州站的除外)和青島站的到發的列車分別單獨作為1條線路處理，南京與上海間的列車計入滬寧線，北京與天津之間的計入京津線。結果見表5。由表5可知，按照線路分別編制動車組運用計劃，則全路網共需要動車組132列，多于網絡化編制的113列。

表4　僅使用蟻群算法的求解結果

表5　按線路分別編制動車組運用計劃的結果

6　結　語

在動車組網絡化運行背景下，提出了強化動車組運用信息的、更直觀的“網絡化動車組運用計劃圖”，為編制人員提供一個網絡化動車組運用計劃編制更便捷的界面。建立動車組運用計劃雙目標規劃優化模型，設計基于專家系統的最大最小蟻群算法對模型求解，編制出網絡化條件下動車組使用數和檢修次數均較少的網絡化動車組運用計劃。案例求解結果證明：采用本文模型和算法比僅采用最大最小蟻群算法結果更優；采用網絡化編制動車運用計劃比分別編制各線路動車組運用計劃更優。文中提出的網絡化動車組運用計劃圖和基于專家系統的最大最小蟻群算法可用于開發人機界面更加友好、更加智能化的網絡化動車組運用計劃編制系統，方便編制人員編制高質量的動車組運用計劃。

[1]RAVINDRA K Ahuja, JIAN Liu, JAMES B Orlin, et al. Solving Real-Life Locomotive-Scheduling Problems[J]. Transportation Science, 2005, 39(4)：503-517.

[2]PIETER-JAN Fioole, LEO Kroon, GABOR Maroti, et al. A Rolling Stock Circulation Model for Combining and Splitting of Passenger Trains[J]. European Journal of Operational Research, 2006, 174: 1281-1297.

[3]MARC Peeters, LEO Kroon. Circulation of Railway Rolling Stock: a Brach-and-Price Approach[J]. Computers & Operations Research, 2008, 35:538-556.

[4]ERWIN Abbink, BIANCA van den Berg, LEO Kroon, et al. Allocation of Railway Rolling Stock for Passenger Trains[J]. Transportation Science, 2004, 38(1): 33-41.

[5]TOMOSHI Otsuki, HIDEYUKI Aisu, TOSHIAKI Tanaka. A Search-Based Approach to Railway Rolling Stock Allocation Problems[J]. Discrete Math Algorithm, 2011(3):443-456.

[6]ARIANNA Alfieri, RUTGER Groot, LEO Kroon, et al. Efficient Circulation of Railway Rolling Stock[J]. Transportation Science, 2006, 40(3)：378-391.

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

(WANG Ying, LIU Jun, MIAO Jianrui. Column Generation Algorithms Based Optimization Method for Maintenance Scheduling of Multiple Units[J]. China Railway Science, 2010, 31(2):115-120. in Chinese)

[8]王瑩，劉軍，苗建瑞. 基于運行線可調的動車組周轉計劃優化研究[J].中國鐵道科學，2012，33(4)：112-119.

(WANG Ying, LIU Jun, MIAO Jianrui. Optimization of the Circulation Plan for Multiple Units Based on Adjustable Train Path[J]. China Railway Science, 2012, 33(4):112-119. in Chinese)

[9]趙鵬，富井規雄. 基于路段交換的多基地動車組運用計劃的編制算法[J]. 鐵道學報，2004，26(1)：7-11.

(ZHAO Peng, TOMII Norio. An Algorithm for Multiple-Bases Train-Set Scheduling Based on Path-Exchange[J]. Journal of the China Railway Society, 2004, 26(1):7-11. in Chinese)

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

(WANG Zhongkai, SHI Tianyun, ZHANG Weijiao, et al.Model and Algorithm for the Integrative Scheduling of EMU Utilization Plan and Maintenance Plan[J].China Railway Science, 2012, 33(3):102-108. in Chinese)

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

(SHI Feng, ZHOU Wenliang, YU Yuwei, et al. Optimized Model and Algorithm of Motor Train-Sets Scheduling for Dedicated Passenger Lines[J]. Journal of the China Railway Society,2011,33(1):8-13.in Chinese)

[12]史峰，魏堂建，周文梁，等. 考慮動車組周轉和到發線運用的高速鐵路列車運行圖優化方法[J].中國鐵道科學，2012，33(2)：107-114.

(SHI Feng, WEI Tangjian, ZHOU Wenliang, et al.Optimization Method for Train Diagram of High-Speed Railway Considering the Turnover of Multiple Units and the Utilization of Arrival-Departure Tracks[J].China Railway Science, 2012, 33(2):107-114. in Chinese)

[13]林柏梁，陳雷，孫卿，等. 動車組二級檢修計劃優化模型[J/OL].中國科技論文在線， http://www.paper.edu.cn/html/releasepaper/2013/12/470/.

(LIN Boliang, CHEN Lei, SUN Qing, et al.Study on Optimization Model of EMU Grade 2 Maintenance Plan[J/OL].Science Paper Online，http://www.paper.edu.cn/html/releasepaper/2013/12/470/. in Chinese)

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

(LI Hua, HAN Baoming, 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. in Chinese)

[15]張才春. 成網條件下客運專線動車組運用的研究[D].北京：北京交通大學，2010.

(ZHANG Caichun. Study on the Train Units Operation Problems of Passenger Dedicated Rail Network[D]. Beijing:Beijing Jiaotong University, 2010. in Chinese)

[16]鄭鋰，宋瑞，肖赟，等. 網絡化運營下城市軌道交通列車車底運用計劃編制的優化方法[J].中國鐵道科學，2014，35(2)：104-110.

(ZHENG Li, SONG Rui, XIAO Yun, et al. Optimization Method for Working out Vehicle Scheduling Plan of Urban Rail Transit under Network Operation[J]. China Railway Science, 2014, 35(2):104-110. in Chinese)

[17]李焱. 應用軟件工程和專家系統的列控中心仿真研究[D].北京：北京交通大學，2012.

(LI Yan. Simulation of Train Control Center Applying Software Engineering and Expert System[D].Beijing:Beijing Jiaotong University, 2012. in Chinese)

[18]中國鐵路總公司. TG/CL 127—2013 鐵路動車組運用維修規程[S]. 北京：中國鐵道出版社，2013.

[19]梁旭，黃明. 現代智能優化混合算法及其應用[M].北京：電子工業出版社，2011.

[20]趙玉新,Xin-She Yang,劉利強. 新興元啟發式優化方法[M].北京：科學出版社，2013.

[21]焦風川，王斌杰. 動車組運用與維修[M]. 北京：北京交通大學出版社，2012.

[22]王連森，連蘇寧. 動車組維護與檢修[M]. 成都：西南交通大學出版社，2010.

[23]李華，韓寶明，趙鵬. 面向我國鐵路實際的動車組運用計劃編制問題[J].北京交通大學學報，2012，36(6)：8-14.

(LI Hua, HAN Baoming, ZHAO Peng. Train-Set Scheduling Problem Geared to Practical Production Process of Railway in China[J]. Journal of Beijing Jiaotong University, 2012, 36(6)：8-14.in Chinese)

[24]張惟皎,史天運,陳彥. 動車運用所存車線運用方案優化模型與算法[J].中國鐵道科學，2013，34(1)：121-125.

(ZHANG Weijiao, SHI Tianyun, CHEN Yan. Optimization Model and Algorithm for the Operation Plan of the Stabling Track at EMU Running Shed[J].China Railway Science, 2013, 34(1):121-125. in Chinese)