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

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

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

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

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

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

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

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

1 引言

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

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

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

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

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

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

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

3.1 模型基本假設(shè)

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

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

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

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

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

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

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

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

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

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

3.3 約束條件分析

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

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

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

動(dòng)車組車型與交路適用車型必須匹配，即

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

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

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

在計(jì)算接續(xù)時(shí)間tij時(shí)，當(dāng)交路j是計(jì)劃開行交路且可以接續(xù)交路i時(shí)，，否則tij=0；當(dāng)交路j是虛擬結(jié)束交路，令tij=0，以避免將某些動(dòng)車組因?yàn)樘幱趲焱顟B(tài)而產(chǎn)生的時(shí)間計(jì)算在接續(xù)時(shí)間里.tij計(jì)算公式為

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

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

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

4 模型求解策略

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

4.1 模型的近似處理

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

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

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

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

4.3 模型求解的主要步驟

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

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

Step 2設(shè)置超期比例λ、換算系數(shù)ω、懲罰值Q0、粒子個(gè)數(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時(shí)表示生成初始解.轉(zhuǎn)Step3.

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

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

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

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

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

5 算例分析

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

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

表1 動(dòng)車組信息Table 1Motor trainset information

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

表2 交路信息Table 2Route information

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

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

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

表4 動(dòng)車組累計(jì)運(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編程平臺(tái)，采用C++語言，實(shí)現(xiàn)算法程序設(shè)計(jì).

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

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

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

6 研究結(jié)論

本文基于交路接續(xù)的思想，構(gòu)建了動(dòng)車組的接續(xù)網(wǎng)絡(luò)，建立了優(yōu)化模型，并設(shè)計(jì)了求解算法.通過算例分析，說明運(yùn)用本文提出的模型和算法可以生成動(dòng)車組運(yùn)用計(jì)劃的初始方案，為實(shí)際生產(chǎn)中動(dòng)車所編制動(dòng)車組運(yùn)用計(jì)劃提供參考依據(jù).然而，在實(shí)際中動(dòng)車組運(yùn)用計(jì)劃的編制不僅受檢修里程周期的約束，還受檢修時(shí)間周期的限制，尤其是對于備用時(shí)間較長的動(dòng)車組.此外，為了更好地提高動(dòng)車組運(yùn)用效率，不同型號動(dòng)車組之間的相互替代等情況也應(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]陳玲娟.遺傳算法在動(dòng)車組運(yùn)用計(jì)劃編制中的應(yīng)用[J].交通運(yùn)輸工程與信息學(xué)報(bào)，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]佟璐，聶磊，趙鵬.蟻群算法在動(dòng)車組運(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ò)的動(dòng)車組交路計(jì)劃優(yōu)化模型與算法研究[J].鐵道學(xué)報(bào)，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]李華.高速鐵路動(dòng)車組運(yùn)用計(jì)劃編制理論與方法研究[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)，張惟皎，等.動(dòng)車組運(yùn)用計(jì)劃和檢修計(jì)劃一體化編制模型及算法[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)專項(xiàng)資金資助（2014YJS069）；國家自然科學(xué)基金資助(51178031)；中國鐵路總公司科技研究開發(fā)計(jì)劃課題（2014J006-C）.

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

bllin@bjtu.edu.cn