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

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

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

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

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

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

1.1 假設(shè)

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

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

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

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

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

1.2 變量

( 1 )

( 2 )

( 3 )

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

( 4 )

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

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

( 5 )

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

( 6 )

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

( 7 )

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

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

( 8 )

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

( 9 )

1.4 約束

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

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

(10)

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

(11)

(3) 大修程后跟隨小修程時(shí)，需要滿足小修程的檢修周期限制的約束表達(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) 大修程檢修覆蓋小修程檢修約束

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

oi,j1,l1>oi,j2,l2

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

(14)

(6) 檢修能力限制

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

(15)

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

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

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

(16)

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

1.5 分層迭代算法

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

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

(17)

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

(18)

(19)

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

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

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

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

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

2.3 約束傳播技術(shù)

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

(20)

則再依據(jù)傳播式

(21)

對第l次之后的檢修r(nóng)j的開始時(shí)刻與結(jié)束時(shí)刻的取值范圍進(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個(gè)車輛的第1個(gè)檢修構(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∪{}，否則，嘗試為下一個(gè)車輛安排檢修作業(yè)，令i←i+1，并轉(zhuǎn)step4；

3 算例分析

3.1 算例求解

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

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

由圖1可得，在11.8 s的時(shí)候迭代收斂到第1個(gè)最優(yōu)解，總的回溯次數(shù)為1 271 次，此時(shí)車輛最多需要進(jìn)行1 225次檢修，平均停修時(shí)間為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個(gè)，在此基礎(chǔ)上再求目標(biāo)函數(shù)式( 9 )的最優(yōu)解，直到求解時(shí)間上限的60 s的最小取值為1 d，最后得到整個(gè)規(guī)劃模型的最優(yōu)解，見表2。

表2 檢修計(jì)劃安排情況 d

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

3.2 結(jié)果分析

在最優(yōu)檢修計(jì)劃中，每輛車的登頂次數(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次三月檢，也不會(huì)安排之后的三月檢。同理，其他車輛也沒有三月檢計(jì)劃。由于定修、大修和架修的檢修周期均超過1年，因而檢修計(jì)劃中不包含定修、大修和架修。

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

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

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

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

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

3.3 算法分析

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

4 結(jié)論

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

參考文獻(xiàn)：

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

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

[4] 唐登仕. 地鐵車輛檢修調(diào)度管理系統(tǒng)的設(shè)計(jì)與實(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.