馬 亮， 郭 進(jìn)， 張曉霞

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

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

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

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

1 多目標(biāo)混合整數(shù)非線性規(guī)劃模型

1.1 假設(shè)

為建立地鐵車輛預(yù)防性檢修計劃優(yōu)化模型，作如下假設(shè)：

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

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

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

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

1.2 變量

( 1 )

( 2 )

( 3 )

規(guī)定只要檢修在計劃時間范圍T內(nèi)開始，即可認(rèn)為此項檢修屬于本計劃，則本計劃時間范圍T內(nèi)安排檢修r(nóng)j的最少、最多次數(shù)分別為

( 4 )

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

車輛ci在時間T范圍內(nèi)所有檢修總的最少、最多次數(shù)分別為

( 5 )

令第l次檢修r(nóng)j的持續(xù)時間范圍為

( 6 )

在時間范圍T內(nèi)安排檢修r(nóng)j的最大的時間范圍和安排所有檢修的最大時間范圍分別為

( 7 )

1.3 目標(biāo)函數(shù)

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

( 8 )

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

( 9 )

1.4 約束

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

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

(10)

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

(11)

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

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

(12)

式中：pj1

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

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

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

(13)

式中：yj1、yj2分別為檢修r(nóng)j1、rj2的種類名稱。

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

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

oi,j1,l1>oi,j2,l2

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

(14)

(6) 檢修能力限制

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

(15)

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

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

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

(16)

式中：gk為tk時向正線的最大交車數(shù)量；ej為檢修r(nóng)j是否影響車輛的正線運行，ej=1表示影響，否則，表示不影響。

1.5 分層迭代算法

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

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

(17)

則上層優(yōu)化的最優(yōu)解集記為

(18)

(19)

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

分層迭代算法將多目標(biāo)優(yōu)化分解為兩個組合優(yōu)化過程，每層優(yōu)化的方法主要有確定型和啟發(fā)式算法，但由于本模型規(guī)模較大，為加快求解速度，需要改進(jìn)基本回溯算法。

2 改進(jìn)回溯算法

2.1 變量靜態(tài)排序啟發(fā)式

2.2 變量取值動態(tài)排序啟發(fā)式

2.3 約束傳播技術(shù)

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

(20)

則再依據(jù)傳播式

(21)

對第l次之后的檢修r(nóng)j的開始時刻與結(jié)束時刻的取值范圍進(jìn)行約減。

2.4 算法步驟

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

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

Step4如果i≥1且ni≥1，轉(zhuǎn)step5，否則，轉(zhuǎn)step10；

Step5當(dāng)oi,ni≥0，則oi,ni←oi,ni-1，如果oi,ni=1，則轉(zhuǎn)step6，如果oi,ni=0，轉(zhuǎn)step7；

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

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

3 算例分析

3.1 算例求解

表1 成都地鐵2號線預(yù)防性檢修

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

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

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

表2 檢修計劃安排情況 d

續(xù)表2 檢修計劃安排情況 d

3.2 結(jié)果分析

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

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

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

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

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

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

同理，嘗試安排其他檢修，最終得到最優(yōu)的預(yù)防性檢修計劃。

3.3 算法分析

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

4 結(jié)論

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

參考文獻(xiàn)：

[1] 吳強.地鐵車輛檢修修制改進(jìn)的探討[J].現(xiàn)代城市軌道交通,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] 吳胡俊實. 地鐵車輛檢修管理信息系統(tǒng)的設(shè)計與開發(fā)[D].成都:西南交通大學(xué),2012:13-56.

[3] 曾星瑜. 地鐵車輛檢修信息系統(tǒng)的開發(fā)[D].成都:西南交通大學(xué),2012:22-45.

[4] 唐登仕. 地鐵車輛檢修調(diào)度管理系統(tǒng)的設(shè)計與實現(xiàn)[D].廣州:華南理工大學(xué),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] 劉三明. 多目標(biāo)規(guī)劃的理論方法及其應(yīng)用研究[M]. 上海：上海交通大學(xué)出版社,2014:23-29.

[8] 胡長英. 雙層規(guī)劃理論及其在管理中的應(yīng)用[M]. 北京：知識產(chǎn)權(quán)出版社,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.