李建，林柏梁*，耿令乾，陳雷，王家喜，武建平

(1.北京交通大學(xué)交通運(yùn)輸學(xué)院，北京100044；2.沈陽鐵路局運(yùn)輸處，沈陽110001)

基于交路接續(xù)的動車組運(yùn)用計劃優(yōu)化模型與算法

李建1，林柏梁*1，耿令乾2，陳雷1，王家喜1，武建平1

(1.北京交通大學(xué)交通運(yùn)輸學(xué)院，北京100044；2.沈陽鐵路局運(yùn)輸處，沈陽110001)

針對動車組運(yùn)用計劃優(yōu)化編制的問題，本文采用接續(xù)網(wǎng)絡(luò)的方法，構(gòu)建了動車組運(yùn)用計劃優(yōu)化編制的0-1整數(shù)規(guī)劃模型.該模型在動車組初始運(yùn)用狀態(tài)和歷史檢修數(shù)據(jù)的基礎(chǔ)上，以動車組擔(dān)當(dāng)交路的接續(xù)時間總和最小化和動車組檢修前累計運(yùn)行里程最大化為優(yōu)化目標(biāo)，以動車組檢修里程周期和動車組交路接續(xù)時間標(biāo)準(zhǔn)為主要約束，并充分考慮動車組與交路的匹配關(guān)系，以及客流高峰時期增加開行交路的情況.在模型的求解方面，本文基于粒子群算法設(shè)計了模型的求解策略.最后通過算例分析驗證了模型與算法的有效性，為動車組運(yùn)用計劃的優(yōu)化編制提供參考依據(jù).

鐵路運(yùn)輸；動車組運(yùn)用計劃；交路接續(xù)；0-1整數(shù)規(guī)劃模型；粒子群算法

1 引言

隨著我國高速鐵路的發(fā)展，投入運(yùn)營的動車組數(shù)量逐漸增多.優(yōu)化編制動車組運(yùn)用計劃，對于加強(qiáng)動車組管理，提高其運(yùn)用效率，降低運(yùn)用和檢修成本具有重要意義.

在該方面的研究中，國外的ErwinAbbink等人以荷蘭鐵路短缺能力最小化為目標(biāo)，考慮動車組車型等因素，構(gòu)建了動車組分配的優(yōu)化模型[1].Luis Cadarso等人將動車組分配與交路計劃優(yōu)化結(jié)合起來進(jìn)行優(yōu)化研究[2].Giovanni Luca Giacco等人從動車組擔(dān)當(dāng)運(yùn)輸任務(wù)、檢修和空駛等方面研究了動車組車底周轉(zhuǎn)與檢修計劃[3].國內(nèi)大多以列車運(yùn)行線和交路生成為基礎(chǔ)，將動車組周轉(zhuǎn)運(yùn)用問題轉(zhuǎn)化為TSP問題進(jìn)行研究[4,5].苗建瑞等人將交路計劃歸結(jié)為帶補(bǔ)給的多人旅行商問題，以動車組數(shù)量最少化為目標(biāo)構(gòu)建優(yōu)化模型，設(shè)計了分層優(yōu)化的啟發(fā)式算法[6].李華將動車組運(yùn)用計劃分為交路計劃和檢修計劃，進(jìn)而予以分別優(yōu)化[7].王忠凱等人從動車組運(yùn)用和檢修計劃一體化編制的角度構(gòu)建了優(yōu)化模型，并設(shè)計了模擬退火算法[8].在現(xiàn)有研究的基礎(chǔ)上，本文基于動車組交路接續(xù)的思想，對動車組運(yùn)用計劃優(yōu)化編制方法進(jìn)行研究.

2 動車組交路接續(xù)網(wǎng)絡(luò)

本文旨在通過動車組交路接續(xù)網(wǎng)絡(luò)確定每列動車組擔(dān)當(dāng)交路的接續(xù)關(guān)系及檢修作業(yè)的安排，因此構(gòu)造了動車組交路接續(xù)網(wǎng)絡(luò)，如圖1所示.圖中以動車組擔(dān)當(dāng)?shù)慕宦泛蛢纱谓宦方永m(xù)之間檢修作業(yè)為節(jié)點，以動車組在交路之間的接續(xù)關(guān)系為弧.同時，為了表示計劃的開始和結(jié)束狀態(tài)，分別設(shè)置虛擬開始節(jié)點和虛擬結(jié)束節(jié)點.

圖1 動車組交路接續(xù)網(wǎng)絡(luò)Fig.1 Route connection network of motor trainset

結(jié)合動車組交路接續(xù)網(wǎng)絡(luò)，定義計劃編制周期集合D={d|d=1,2,…,ND}，d為日期索引，ND為計劃天數(shù)；動車組集合E={k|k=1,2,…,NE}，k為動車組索引，NE為動車組數(shù)量.將網(wǎng)絡(luò)中的交路劃分為虛擬初始交路、計劃開行交路、虛擬結(jié)束交路三種類型，每條交路都有一個開始時間和結(jié)束時間.按交路開始時間進(jìn)行先后排序，并根據(jù)排序結(jié)果給每條交路設(shè)定一個編號.基于此，定義交路集合W=W1?W2?W3，W1、W2和W3分別為三類不同交路的集合.虛擬初始交路集合W1={} 1,2,…,NE，即將每列動車組的初始狀態(tài)看作一條交路；計劃開行交路集合W2={} NE+1,NE+2,…,NE+NR，NR表示計劃開行交路數(shù)量，由于高峰客流時增加開行交路，每天交路數(shù)量不盡相同，令NR(d)為第d天開行交路數(shù)量，則；虛擬結(jié)束交路集合W3={}NE+NR+1,NE+NR+2,…,2NE+NR，其數(shù)量等于動車組數(shù)量NE.因此，接續(xù)網(wǎng)絡(luò)中交路集合還可以表示為W={} 1,2,…,i,…,j,…,2NE+NR，i和j為交路編號，設(shè)定分別表示交路i的開始時間和結(jié)束時間，對于任意交路i有一個運(yùn)行里程Si.

3 數(shù)學(xué)優(yōu)化模型構(gòu)建

3.1 模型基本假設(shè)

(1)不考慮動車所的檢修能力，理論優(yōu)化方案超出檢修能力時，通過人工干預(yù)進(jìn)行調(diào)整.

(2)一般動車組的里程周期比時間周期要先到期，故暫不考慮檢修時間周期限制.

(3)以動車組列車為最小單元，不考慮其重聯(lián)與分解，同型號動車組列車的相同檢修包的檢修時間相同.

(4)動車組車型、初始運(yùn)用狀態(tài)、歷史檢修數(shù)據(jù)、檢修包和交路信息等數(shù)據(jù)已知.

3.2 優(yōu)化目標(biāo)分析

為了提高動車組運(yùn)用效率，在交路接續(xù)網(wǎng)絡(luò)構(gòu)建的基礎(chǔ)上，以所有動車組擔(dān)當(dāng)交路的接續(xù)時間總和最小化作為主要優(yōu)化目標(biāo)，如式(1)所示.

式中tij為交路i和j之間的接續(xù)時間為動車組k擔(dān)當(dāng)完交路i后是否擔(dān)當(dāng)交路j的決策變量，若是=1，否則=0.

為了減少檢修次數(shù)，降低檢修成本，以動車組檢修前相對于對應(yīng)檢修包里程周期的累計運(yùn)行里程最大化為另一個優(yōu)化目標(biāo).在不超期檢修前提下，這可以轉(zhuǎn)化為動車組檢修前相對于對應(yīng)檢修包里程周期損失的可用里程（即檢修包的里程周期減去檢修前的累計運(yùn)行里程）最小化，如式(2)所示.

式中P為檢修包集合；m為檢修包索引；Lm為檢修包m的里程周期為動車組k在擔(dān)當(dāng)交路i和j之間是否安排檢修包m作業(yè)的決策變量，若是為動車組k擔(dān)當(dāng)完交路i后，相對于檢修包m最近一次檢修的累計運(yùn)行里程；λ為檢修里程允許超期比例.

為了便于模型求解，設(shè)置時間與里程的換算系數(shù)ω，將雙目標(biāo)優(yōu)化轉(zhuǎn)化為單目標(biāo)優(yōu)化，最終的目標(biāo)函數(shù)如式(3)所示.

3.3 約束條件分析

任意一條計劃開行交路和虛擬結(jié)束交路，有且只有一條由唯一動車組擔(dān)當(dāng)?shù)那袄m(xù)交路，即

同理，任意一條虛擬初始交路和計劃開行交路，有且只有一條由唯一動車組擔(dān)當(dāng)?shù)暮罄m(xù)交路，即

任意一條計劃開行交路，其前續(xù)交路和后續(xù)交路由同一列動車組擔(dān)當(dāng)，即

動車組車型與交路適用車型必須匹配，即

同理，動車組車型與檢修包適用車型必須匹配，且只有當(dāng)動車組k接續(xù)擔(dān)當(dāng)交路i和j時，才可以在二者間安排檢修作業(yè)，即有

動車組必須滿足接續(xù)時間標(biāo)準(zhǔn)T0，若動車組k在交路i和j間進(jìn)行m包檢修，還必須滿足m包檢修時間Tm的限制，即2

累計運(yùn)行里程lkj(m)必須滿足對應(yīng)檢修包的檢修里程周期Lm的限制，避免超期檢修，即

在計算接續(xù)時間tij時，當(dāng)交路j是計劃開行交路且可以接續(xù)交路i時，，否則tij=0；當(dāng)交路j是虛擬結(jié)束交路，令tij=0，以避免將某些動車組因為處于庫停狀態(tài)而產(chǎn)生的時間計算在接續(xù)時間里.tij計算公式為

決策變量都滿足0-1整數(shù)約束，即

綜合考慮式（3）～式（13），將優(yōu)化目標(biāo)函數(shù)和約束條件進(jìn)行整合，可以得到動車組運(yùn)用計劃編制的數(shù)學(xué)優(yōu)化模型為

s.t.式（4）～式（13）

4 模型求解策略

本文基于具有操作簡單、收斂速度快等特點的粒子群算法，根據(jù)模型的具體特點設(shè)計模型的優(yōu)化求解策略.

4.1 模型的近似處理

為了便于模型求解策略的設(shè)計，首先對模型進(jìn)行部分近似處理.基于模型構(gòu)建之初交路排序的預(yù)處理，設(shè)置一個動車組擔(dān)當(dāng)交路的決策變量，r為交路索引，用于替代模型中決策變量，若動車組k擔(dān)當(dāng)交路r，則=1，否則=0.同理，設(shè)置一個動車組檢修安排的決策變量(m)，用于替代模型中決策變量，若動車組k在擔(dān)當(dāng)完交路r后安排m包檢修，則在求解中，首先確定)的取值，再據(jù)此確定的取值，最終得到動車組運(yùn)用計劃的優(yōu)化方案.對于模型中涉及到的相應(yīng)決策變量的問題，在求解策略設(shè)計和程序編寫中進(jìn)行具體處理.

模型中式(4)和式(5)共同說明任意交路都必須要有動車組去擔(dān)當(dāng).在求解策略設(shè)計中，將該約束條件進(jìn)行軟化處理，并設(shè)置一個懲罰值M0，當(dāng)出現(xiàn)一條交路無動車組擔(dān)當(dāng)時就在適應(yīng)函數(shù)值中增加一個M0，假設(shè)有N0條交路無動車組擔(dān)當(dāng)，則總懲罰值為M0N0.

4.2 粒子群算法的具體應(yīng)用

粒子數(shù)量為NQ，任意粒子q都有一個J維的位置矢量Xq=(xq1,xq2,…,xqJ)，在本文中每一個維度上粒子位置的取值代表動車組k是否擔(dān)當(dāng)交路r的決策變量的值，即為0-1整數(shù).根據(jù)模型的目標(biāo)函數(shù)值和懲罰值，計算粒子的適應(yīng)函數(shù)值Fq(x)，并據(jù)此進(jìn)行解的迭代更新.每個粒子具有一個飛行速度矢量Vq=(vq1,vq2,…,vqJ)和個體歷史最優(yōu)解Pq=(pq1,pq2,…,pqJ)，整個粒子群具有一個全局歷史最優(yōu)解Pg=(pg1,pg2,…,pgJ).根據(jù)xkr的定義確定粒子維度大小J=NE×(2NE+NR)，在第j個維度上j=k×r.粒子速度更新公式為

式中t為迭代次數(shù)；r1和r2是[0，1]之間的隨機(jī)數(shù)；c1和c2是學(xué)習(xí)因子；粒子速度滿足區(qū)間[-vmax,vmax]；ω(qt)是慣性權(quán)重，根據(jù)式(15)進(jìn)行更新.

式中ωmax和ωmin分別表示最大和最小慣性權(quán)重；tmax表示最大迭代次數(shù).

式中ρ為[0，1]之間的隨機(jī)數(shù)，每次迭代中隨機(jī)產(chǎn)生.Sigmoid函數(shù)是一種模糊函數(shù)，其公式為

通過對粒子在各維度上的位置所代表的動車組擔(dān)當(dāng)交路的解進(jìn)行迭代更新，最終得到動車組運(yùn)用方案的近似最優(yōu)解.

4.3 模型求解的主要步驟

基于粒子群算法的主要求解步驟如下：

Step 1根據(jù)基礎(chǔ)數(shù)據(jù)確定計劃開行交路集合，并按開始時間進(jìn)行先后排序.轉(zhuǎn)Step2.

Step 2設(shè)置超期比例λ、換算系數(shù)ω、懲罰值Q0、粒子個數(shù)NQ、迭代次數(shù)tmax、粒子速度區(qū)間[Vmin,Vmax]、慣性權(quán)重區(qū)間[ωmin,ωmax]、隨機(jī)數(shù)r1和r2、學(xué)習(xí)因子c1和c2等參數(shù)取值.將決策變量和取值均置零；隨機(jī)生成粒子初始速度.設(shè)定迭代次數(shù)t=0時表示生成初始解.轉(zhuǎn)Step3.

Step 3對于第t次迭代中的粒子q，根據(jù)動車組初始運(yùn)用狀態(tài)，確定當(dāng)r≤NE時的取值，同時更新m).轉(zhuǎn)Step4.

Step 4對于計劃開行交路或虛擬結(jié)束交路r，為其隨機(jī)分配動車組k，從動車組車型與交路是否匹配、接續(xù)時間是否滿足、檢修里程周期限制是否滿足三方面判斷動車組是否可以擔(dān)當(dāng)該交路.在該過程中，若動車組k對于交路r，不滿足檢修包m的檢修里程周期限制，則令，并更新為動車組k最近一次擔(dān)當(dāng)?shù)慕宦?若動車組k不可以擔(dān)當(dāng)交路r，則令，繼續(xù)隨機(jī)分配下一列動車組.若動車組k可以擔(dān)當(dāng)交路r，轉(zhuǎn)Step5；若所有動車組均不擔(dān)當(dāng)交路r，則令r=r+1，直到交路遍歷完畢，轉(zhuǎn)Step7.

Step 5對于任意迭代次數(shù)t，判斷t是否等于0.若t=0，則令，同時更新和最近一次擔(dān)當(dāng)?shù)慕宦穜′；若交路遍歷完畢，則轉(zhuǎn)Step7，否則令r=r+1，轉(zhuǎn)Step4.若t≠0，則轉(zhuǎn)Step6.

Step 8根據(jù)Fq(x)更新粒子的個體歷史最優(yōu)值Pq和粒子群的全局歷史最優(yōu)值Pg.轉(zhuǎn)Step9.

Step 9若已達(dá)到最大迭代次數(shù)tmax，則計算結(jié)束，輸出方案；否則令t=t+1，轉(zhuǎn)Step3，進(jìn)行下一次迭代.

5 算例分析

基于我國某動車運(yùn)用所的部分實際數(shù)據(jù)進(jìn)行動車組運(yùn)用周計劃編制的案例分析，并且周五、周六、周日三天在平日交路開行的基礎(chǔ)上增加高峰交路.

選擇CRH380CL型和CRH380AL型的動車組各5列.考慮到交路的結(jié)束時間一般都在當(dāng)天24:00以前，同時為了簡化算例計算，設(shè)定所有動車組的可用時間均為00:00.動車組信息如表1所示.

表1 動車組信息Table 1Motor trainset information

為CRH380CL型和CRH380AL型動車組分別選擇3條可擔(dān)當(dāng)?shù)钠饺战宦贰?條高峰交路.交路信息如表2所示.

表2 交路信息Table 2Route information

每種型號的動車組都有多個不同的檢修包，例如一級修、I2修、M1修、牽引機(jī)注油、輪對鏇修、空心軸探傷等，每個檢修包的檢修里程周期及檢修時間不盡相同.本文只選擇一級修、I2修、M1修三個檢修項目進(jìn)行計算試驗，其信息如表3所示.

表3 檢修包信息Table 3Maintenance project information

根據(jù)動車所統(tǒng)計的動車組當(dāng)前總運(yùn)行里程和每個檢修包最近一次檢修時的總運(yùn)行里程，可以計算出動車組相對于每個檢修包最近一次檢修后的累計運(yùn)行里程，具體如表4所示.

表4 動車組累計運(yùn)行里程（km）Table 4Accumulated mileage of motor trainset(km)

其他相關(guān)參數(shù)設(shè)置如下：設(shè)定λ=10%，ω=1.1，Q0=100 000，NQ=30，r1=r2=0.5，c1=c2=2.0，tmax=2 000，速度區(qū)間為[-4,4]，慣性權(quán)重區(qū)間為[0.4,0.9].借助visual studio 2010編程平臺，采用C++語言，實現(xiàn)算法程序設(shè)計.

由于啟發(fā)式算法計算結(jié)果具有一定的波動性，本文進(jìn)行10次優(yōu)化求解，從中選擇最優(yōu)解作為最終優(yōu)化方案.在4G內(nèi)存、i5處理器、Win8操作系統(tǒng)的PC機(jī)環(huán)境下，經(jīng)過112秒計算，得到動車組運(yùn)用計劃的近似最優(yōu)方案，如圖2所示.

圖2 動車組運(yùn)用計劃優(yōu)化方案Fig.2 Optimization scheme of motor trainset utilization scheduling

對于圖2所示的動車組運(yùn)用計劃優(yōu)化方案，動車組的總接續(xù)時間為61 230 min，檢修時總損失的可運(yùn)用里程為27246 km.交路都有對應(yīng)的動車組擔(dān)當(dāng)，保證了計劃周期內(nèi)運(yùn)輸任務(wù)的正常完成，并且動車組在檢修前其累計運(yùn)行里程都盡可能地貼近了檢修里程周期上限.由于動車組的一級修檢修里程周期較短，計劃中一級修安排較多，只有動車組e3和e5進(jìn)行了I2修.一般而言，動車組的一級修安排在夜間進(jìn)行，在該優(yōu)化方案中，對于一級修完成后沒有立即去擔(dān)當(dāng)交路的動車組，可根據(jù)動車所檢修能力適當(dāng)調(diào)整動車組的一級修時間.

6 研究結(jié)論

本文基于交路接續(xù)的思想，構(gòu)建了動車組的接續(xù)網(wǎng)絡(luò)，建立了優(yōu)化模型，并設(shè)計了求解算法.通過算例分析，說明運(yùn)用本文提出的模型和算法可以生成動車組運(yùn)用計劃的初始方案，為實際生產(chǎn)中動車所編制動車組運(yùn)用計劃提供參考依據(jù).然而，在實際中動車組運(yùn)用計劃的編制不僅受檢修里程周期的約束，還受檢修時間周期的限制，尤其是對于備用時間較長的動車組.此外，為了更好地提高動車組運(yùn)用效率，不同型號動車組之間的相互替代等情況也應(yīng)該考慮.在未來的研究中將對這些問題做進(jìn)一步探討.

[1]Erwin Abbink,Bianca van den Berg,Leo Kroon,et al. Allocationofrailwayrollingstockforpassenger trains[J].Transportation Science,2004,38(1):33-41.

[2]Luis Cadarso,ángel Marín.Improving robustness of rolling stock circulations in rapid transit networks[J]. Computers&Operations Research,2014,51:146-159.

[3]Giovanni Luca Giacco,Donato Carillo.Short-term rail rolling stock rostering and maintenance scheduling[J]. Transportation Research Procedia,2014,3:51-659.

[4]陳玲娟.遺傳算法在動車組運(yùn)用計劃編制中的應(yīng)用[J].交通運(yùn)輸工程與信息學(xué)報，2009，7(2)：67-71. [CHEN L J,Application of genetic algorithms to electric multiple unit scheduling[J].Journal of Transportation Engineering and Information,2009,7(2):67-71.]

[5]佟璐，聶磊，趙鵬.蟻群算法在動車組運(yùn)用問題中的應(yīng)用[J].交通運(yùn)輸系統(tǒng)工程與信息，2009，9(4)：161-167.[TONG L,NIE L,ZHAO P.Application of ant colony algorithm in train-set scheduling problem[J]. Journal of Transportation Systems Engineering and Information Technology,2009,9(4):161-167.]

[6]苗建瑞，王瑩，楊肇夏.基于最優(yōu)接續(xù)網(wǎng)絡(luò)的動車組交路計劃優(yōu)化模型與算法研究[J].鐵道學(xué)報，2010，32 (2)：1-7.[MIAO J R,WANG Y,YANG Z X.Research on the optimization of EMU circulation based on optimized connecting network[J].Journal of the China Railway Society,2010,32(2):1-7.]

[7]李華.高速鐵路動車組運(yùn)用計劃編制理論與方法研究[D].北京交通大學(xué)，2013.[LI H.Theory and method studies on EMU scheduling problem for high speed railway[D].Beijing Jiaotong University,2013.]

[8]王忠凱，史天運(yùn)，張惟皎，等.動車組運(yùn)用計劃和檢修計劃一體化編制模型及算法[J].中國鐵道科學(xué)，2012，33(3)：102-108.[WANG Z K,SHI T Y,ZHANG W J, 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.]

Optimization Model and Algorithm for Motor Trainset Utilization Scheduling Based on Routes Connection

LI Jian1,LIN Bo-liang1,GENG Ling-qian2,CHEN Lei1,WANG Jia-xi1,WU Jian-ping1

(1.School of Traffic and Transportation,Beijing Jiaotong University,Beijing 100044,China;2.Transportation Division, Shenyang Railway Bureau,Shenyang 110001,China)

A 0-1 integer programming model is constructed for the motor trainset utilization scheduling by using switching network method,on the basis of initial utilization state and historical maintenance data.The model minimizes the total connection time and maximizes the accumulated mileage before maintenance of all motor trainset.The model takes the matching degree between the trainset and the route into consideration, as well as the additional routes at passenger flow peak.It also takes the maintenance mileage standard of motor trainset and connection time standard of route as the key constraint condition.In terms of the solution method for the model,a fast solving method is put forward based on particle swarm optimization.A case study verifies the effectiveness of the optimization model and solving method,and provides a reference for the motor trainset utilization scheduling.

railway transportation;motor trainset utilization scheduling;routes connection;0-1 integer programming model;particle swarm optimization

1009-6744（2015）05-0172-06

U279.2

A

2015-04-07

2015-07-01錄用日期：2015-07-06

中央高?；究蒲袠I(yè)務(wù)費(fèi)專項資金資助（2014YJS069）；國家自然科學(xué)基金資助(51178031)；中國鐵路總公司科技研究開發(fā)計劃課題（2014J006-C）.

李建（1989-），男，四川宜賓人，博士生. ＊

bllin@bjtu.edu.cn