地鐵車輛預防性檢修計劃優化模型與算法

馬 亮， 郭 進， 張曉霞

(1. 電子科技大學 光電信息學院，四川 成都 610054；2.西南交通大學 信息科學與技術學院，四川 成都 610031)

地鐵車輛運行一段時間或者一定距離后需要進行檢修，車輛檢修是車輛基地(包括車輛段和停車場)的工作重點。據統計，車輛檢修成本約占地鐵總維修成本的40%，檢修效率將直接影響列車正線運營能力，有必要通過編制車輛檢修計劃，統籌安排各類修程的檢修作業，降低檢修成本和延長車輛使用壽命。

目前，主要采用人工方式安排檢修作業，效率較低且易出現問題。因此，需要研究地鐵車輛檢修計劃的優化理論及方法，以智能形式編制檢修計劃。文獻[1]系統地提出改進地鐵檢修制度的措施，壓縮檢修停時和提高車輛周轉效率；在檢修制度確定的前提下，文獻[2-4]通過計算機技術建立車輛檢修信息系統，輔助檢調指揮日常檢修作業。但文獻[2-3]中信息系統的功能僅限于檢修計劃的增、刪、改以及派工等；文獻[4]建立檢修工單調度0-1規劃模型，通過改良的遺傳算法生成檢修工單，實現檢修作業和人員間的最大匹配，但模型存在技能指標無法確定和不斷變化的情況；文獻[5]建立考慮檢修車輛路由問題的混合整數規劃模型，使用分支定界和列生成策略確定每一路徑的列車開行方案；文獻[6]針對線路維護班組調度問題，建立時空網絡模型，并使用多鄰域搜索算法求解。但是文獻[5-6]沒有考慮檢修與列車運行之間的協調問題，且沒有為每輛車安排檢修計劃。

地鐵車輛的檢修包括預防性檢修和事后維修。相對于預防性維修，事后維修的隨機性比較大，無法在檢修計劃中考慮；在預防性維修中，日檢是每個次日上線運行車輛必須進行的。預防性檢修計劃是根據車輛的運行狀態、運行周期、正線列車運行需求和班組檢修能力，確定每日車輛的預防性檢修內容、時間、班組等。因此，本文討論的檢修是指不包含日檢的預防性檢修，主要研究內容為當地鐵車輛檢修制度、正線列車運行需求、班組檢修能力等因素確定時，以檢修修程、檢修周期、班組檢修能力、上線運行車數為限制條件，以安排的檢修作業總數最多為主要目標，以車輛的平均利用率最高為次要目標，建立地鐵車輛預防性檢修計劃的多目標混合整數非線性規劃模型，并設計改進的回溯算法快速迭代求解，從整體上提高車輛基地檢修作業的效率和車輛的利用率。

1 多目標混合整數非線性規劃模型

1.1 假設

為建立地鐵車輛預防性檢修計劃優化模型，作如下假設：

(1) 檢修制度、日運行圖、日班組檢修能力和每輛投入運行車輛的時間等數據確定且不變；

(2) 每項檢修只要開始即不可被中斷，直到結束；

(3) 每項檢修從開始至結束僅由1個檢修班組承擔，1個班組同一時間僅承擔1項檢修；

(4) 僅有1個檢修基地，即1個車輛段，沒有附屬停車場，表示車輛檢修沒有分場要求。

1.2 變量

( 1 )

( 2 )

( 3 )

規定只要檢修在計劃時間范圍T內開始，即可認為此項檢修屬于本計劃，則本計劃時間范圍T內安排檢修rj的最少、最多次數分別為

( 4 )

式中：tNT為計劃階段T的結束時刻。

車輛ci在時間T范圍內所有檢修總的最少、最多次數分別為

( 5 )

令第l次檢修rj的持續時間范圍為

( 6 )

在時間范圍T內安排檢修rj的最大的時間范圍和安排所有檢修的最大時間范圍分別為

( 7 )

1.3 目標函數

編制車輛檢修計劃時受限于檢修周期、檢修班組能力、向正線交車數量等，不能保證每項檢修均可以成功進行。因此，車輛檢修計劃的主要目的是在滿足各種限制的前提下盡量多地安排檢修作業，即

( 8 )

為合理減少車輛的檢修次數和過多檢修帶來的額外損耗，提高車輛的周轉率，保證檢修基地向正線交車能力，檢修計劃優化的次要目標為車輛的平均停修時間最短，等價于車輛的平均利用率最高，即

( 9 )

1.4 約束

編制檢修計劃需要滿足檢修制度要求，即包括修程自身的周期和停修時間要求、不同修程之間的周期限制、正線交車數量限制、日檢修量不得超過班組檢修能力等。

(1) 任意車輛在同一時間只能進行一項檢修，即檢修唯一性約束表達式b1為

(10)

(2) 相鄰的同類檢修之間需要滿足檢修周期限制，則檢修周期約束表達式b2為

(11)

(3) 大修程后跟隨小修程時，需要滿足小修程的檢修周期限制的約束表達式b3為

i=1,2,…,NCj1,j2=1,2,…,NR

(12)

式中：pj1

(4) 某檢修一旦開始即不能被中斷直至結束，則檢修作業不可中斷約束表達式b4為

vi,j1,k1×yj1=vi,j2,k2×yj2

i=1,2,…,NCj1,j2=1,2,…,NR

(13)

式中：yj1、yj2分別為檢修rj1、rj2的種類名稱。

(5) 大修程檢修覆蓋小修程檢修約束

如果計劃時間段內某時刻某車輛既可安排小修程，又可安排大修程，則安排大修程，如：每4次定修后需進行1次架修等。大修程覆蓋小修程的約束表達式b5為

oi,j1,l1>oi,j2,l2

i=1,2,…,NCj1,j2=1,2,…,NR

(14)

(6) 檢修能力限制

每天班組的車輛檢修總能力是有限的，即每天同時檢修的總車輛數是有限的。因此，班組檢修能力的約束表達式b6為

(15)

式中：ak為tk時扣除日檢班組后剩余班組檢修能力。

(7) 向正線交車數量限制

為滿足運行圖要求，每天從車輛檢修基地送往正線運行的車輛數是確定的，即向正線交車數量限制的約束表達式b7為

(16)

式中：gk為tk時向正線的最大交車數量；ej為檢修rj是否影響車輛的正線運行，ej=1表示影響，否則，表示不影響。

1.5 分層迭代算法

本模型中兩個目標函數的優化是沖突的，只有在目標函數式( 8 )基礎上再優化目標函數式( 9 )才有意義。因此，依據兩個目標函數之間的優先級，設計分層迭代算法[7-8]求解整個模型。

S(xi,j,l)={xi,j,l|bm(xi,j,l)=1

(17)

則上層優化的最優解集記為

(18)

(19)

則ψ2(xi,j,l)為整個規劃模型的最優解集。

分層迭代算法將多目標優化分解為兩個組合優化過程，每層優化的方法主要有確定型和啟發式算法，但由于本模型規模較大，為加快求解速度，需要改進基本回溯算法。

2 改進回溯算法

2.1 變量靜態排序啟發式

2.2 變量取值動態排序啟發式

2.3 約束傳播技術

為動態約減臨時解空間，在基本回溯算法中引入約束傳播技術。約束傳播包括減域和傳播兩部分，主要思想：當某1個變量論域被修改，則所有與之相關的變量都要調用減域算法修改論域，如此反復，直到所有變量的論域都約減到最小。依據檢修周期約束式(11)和約束式(12)，以及相鄰檢修開始時刻與結束時刻關系，見式( 2 )。假設第l-1次檢修rj的開始時刻和結束時刻確定，那么第l次檢修rj的開始時刻和結束時刻的范圍將縮小為

(20)

則再依據傳播式

(21)

對第l次之后的檢修rj的開始時刻與結束時刻的取值范圍進行約減。

2.4 算法步驟

假設模型的最優解集記為ψ1，所有約束bm(m=1,…,7)組成的約束集記為B，調用約束傳播算法記為Cpr(B)，則改進回溯算法(Improved-BT)求解以式( 8 )為目標函數的上層模型的步驟為:

Step3從第1個車輛的第1個檢修構成的搜索樹第1層開始深度搜索i←1，ni←1；

Step4如果i≥1且ni≥1，轉step5，否則，轉step10；

Step5當oi,ni≥0，則oi,ni←oi,ni-1，如果oi,ni=1，則轉step6，如果oi,ni=0，轉step7；

Step7對變量取值進行合法性檢查。如果?m=1,…,8, (bm(xi,ni)=1)，則轉step8，否則，如果oi,ni=1轉step6；

Step9如果i=NC，則返回最優解ψ1←ψ1∪{}，否則，嘗試為下一個車輛安排檢修作業，令i←i+1，并轉step4；

3 算例分析

3.1 算例求解

表1 成都地鐵2號線預防性檢修

本算例的檢修總數為1 575次，變量有4 725個，約束的數量級大約為百萬，總迭代次數的數量級為億。在Inter Core i3-2310M 2.1GHz & DRAM 2G & Windows XP & NET Framework 4.5環境下的PC機上運行本模型及算法。圖1為改進回溯算法求解以式( 8 )為目標函數的上層模型，并得到最優解集ψ1。

由圖1可得，在11.8 s的時候迭代收斂到第1個最優解，總的回溯次數為1 271 次，此時車輛最多需要進行1 225次檢修，平均停修時間為1 d。由目標函數式( 8 )優化得到最優解之后，再求解以ψ1為可行解集和以式( 9 )為目標函數的下層模型，圖2為求解過程。

本算例目標函數式( 8 )最大值1 225的最優解只有1個，在此基礎上再求目標函數式( 9 )的最優解，直到求解時間上限的60 s的最小取值為1 d，最后得到整個規劃模型的最優解，見表2。

表2 檢修計劃安排情況 d

續表2 檢修計劃安排情況 d

3.2 結果分析

在最優檢修計劃中，每輛車的登頂次數為59次，第1～10輛車的雙周檢次數為22次，第11～15輛車的雙周檢次數為23次。

第1輛車的第1次三月檢開始和結束日期的取值范圍分別為[83,99]和[85,101]，在[83,101]之間沒有連續3 d的總檢修次數滿足檢修能力約束式(15)和向正線交車約束式(16)。因此，第1輛車沒有安排第1次三月檢，也不會安排之后的三月檢。同理，其他車輛也沒有三月檢計劃。由于定修、大修和架修的檢修周期均超過1年，因而檢修計劃中不包含定修、大修和架修。

(1) 安排第1輛車的第1次雙周檢之后，依據2.3節約束傳播算法，第1輛車的第2次雙周檢開始日期的取值范圍由[26,38]變為[29,32]；

(2) 依據變量取值動態排序啟發式優先賦值為29 d，但是第6～10輛車的第1次雙周檢起止日期均為29 次。因此，依據檢修能力約束式(15)和向正線交車約束式(16)排除第29 d；

(3) 再依據變量取值動態排序啟發式嘗試賦值為30 d，但是第11～15輛車的第1次雙周檢起止日期都為30 d。因此，依據檢修能力約束式(15)和向正線交車約束式(16)排除第30 d；

(4) 再嘗試賦值為31 d，滿足所有約束。

同理，嘗試安排其他檢修，最終得到最優的預防性檢修計劃。

3.3 算法分析

在BT1、BT2和BT3算法中嘗試引入不同于本算法的變量靜態排序啟發式和變量取值動態排序啟發式，生成不同結構的搜索樹，使得前3個算法在前期收斂到較差解的概率較大，通過圖3驗證可得本算法求得的最優解和求解效率比前3個算法明顯好。引入約束傳播技術，在搜索過程中約減變量的臨時論域，使得總迭代次數比算法BT4減少數10倍，經統計兩種算法總迭代次數分別為3 992 次和44 529 次。即使約束傳播技術消耗一定時間，但是總求解效率比BT4高。

4 結論

本文綜合考慮地鐵車輛檢修制度、正線運行需求、班組檢修能力等因素，建立車輛預防性檢修計劃多目標混合整數非線性規劃模型，并設計改進回溯算法快速求解，提高車輛的檢修效率，保障車輛正線運行的安全性。在預防性檢修計劃優化基礎上再考慮每日事后性維修的不確定性和每日不同時刻向正線的交車數量限制，動態優化日檢修計劃。今后，進一步研究地鐵車輛運行計劃與車輛檢修計劃的綜合優化問題，使之全面提高地鐵車輛基地服務正線運行的水平。

參考文獻：

[1] 吳強.地鐵車輛檢修修制改進的探討[J].現代城市軌道交通,2007(2):53-54.

WU Qiang. Discussion for Improvement of Inspection and Maintenance System for Metro Vehicles[J]. Modern Urban Transit, 2007(2):53-54.

[2] 吳胡俊實. 地鐵車輛檢修管理信息系統的設計與開發[D].成都:西南交通大學,2012:13-56.

[3] 曾星瑜. 地鐵車輛檢修信息系統的開發[D].成都:西南交通大學,2012:22-45.

[4] 唐登仕. 地鐵車輛檢修調度管理系統的設計與實現[D].廣州:華南理工大學,2013:6-19.

[5] ANDRES J, CADARSO L, MARIN A. Maintenance Scheduling in Rolling Stock Circulations in Rapid Transit Networks[J]. Transportation Research Procedia, 2015, 10:524-533.

[6] PENG F, OUYANG Y. Track Maintenance Production Team Scheduling in Railroad Networks[J]. Transportation Research Part B:Methodological, 2012, 46(10):1 474-1 488.

[7] 劉三明. 多目標規劃的理論方法及其應用研究[M]. 上海：上海交通大學出版社,2014:23-29.

[8] 胡長英. 雙層規劃理論及其在管理中的應用[M]. 北京：知識產權出版社,2012:12-38.

[9] GOLOMB S W, BAUMERT L D. Backtrack Programming[J]. Journal of the ACM, 1965, 12(4):516-524.

[10] BACCHUS F, RUN P V. Dynamic Variable Ordering in CSPs [C]//ACM Sigart Sigplan. 1st International Conference on Principles and Practice of Constraint Programming. Berlin Heidelberg, German:Springer Berlin Heidelberg, 1995:258-275.

[11] HUANG J, DARWICHE A. A Structure-based Variable Ordering Heuristic for SAT[C]//The International Joint Conferences on Artificial Intelligence (IJCAI). Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. United States: International Joint Conferences on Artificial Intelligence, 2003:1 167-1 172.

[12] HOOKER J. Logic, Optimization and Constraint Programming[J]. Informs Journal on Computing, 2002, 14(4): 295-321.

[13] ROSSI F, VAN BEEK P, WALSH T. Handbook of Constraint Programming[M]. Pisa: Elsevier, 2006:103-109.