考慮接續(xù)可靠性的動(dòng)車(chē)組運(yùn)用計(jì)劃優(yōu)化方法

仝 碩，陳紹寬，劉葛輝，劉 爽，毛保華

(1.北京交通發(fā)展研究院,北京 100073; 2.北京交通大學(xué) 交通運(yùn)輸部綜合交通運(yùn)輸大數(shù)據(jù)應(yīng)用技術(shù)交通運(yùn)輸行業(yè)重點(diǎn)實(shí)驗(yàn)室,北京 100044)

動(dòng)車(chē)組運(yùn)用計(jì)劃是鐵路客運(yùn)日常工作的重要組成部分。隨著我國(guó)高速鐵路系統(tǒng)的快速發(fā)展，動(dòng)車(chē)組開(kāi)行密度不斷增大，在降低運(yùn)營(yíng)成本、提高運(yùn)營(yíng)可靠性的要求下，優(yōu)化動(dòng)車(chē)組運(yùn)用計(jì)劃具有重要的理論意義與實(shí)際價(jià)值。

既有研究中，動(dòng)車(chē)組運(yùn)用計(jì)劃編制優(yōu)化問(wèn)題主要涉及數(shù)學(xué)問(wèn)題轉(zhuǎn)化、運(yùn)用場(chǎng)景選取、目標(biāo)函數(shù)構(gòu)造以及求解算法設(shè)計(jì)4個(gè)方面。首先，將動(dòng)車(chē)組運(yùn)用計(jì)劃編制優(yōu)化問(wèn)題轉(zhuǎn)化為多商品流問(wèn)題和(多)旅行商問(wèn)題等處理，Abbink等[1]針對(duì)單線(xiàn)周期運(yùn)行圖建立了最小化動(dòng)車(chē)組數(shù)量和走行里程的雙目標(biāo)多商品流優(yōu)化模型，優(yōu)化了允許重聯(lián)和摘解列車(chē)的周轉(zhuǎn)計(jì)劃；Giacco等[2]研究了維修條件下動(dòng)車(chē)組運(yùn)用計(jì)劃，利用TSP問(wèn)題建立混合整數(shù)規(guī)劃模型；王超等[3]基于車(chē)輛線(xiàn)路問(wèn)題理論，構(gòu)建了動(dòng)車(chē)組運(yùn)行圖與運(yùn)用計(jì)劃一體化優(yōu)化模型。其次，基于實(shí)際情形，既有研究考慮了不同動(dòng)車(chē)組運(yùn)用方式、空車(chē)調(diào)撥、非單一編組和非單一車(chē)型等不同場(chǎng)景[4-5]，聶磊等[6]用實(shí)驗(yàn)證明空車(chē)調(diào)撥可以提高動(dòng)車(chē)組利用率，在運(yùn)行調(diào)整時(shí)可提高動(dòng)車(chē)組運(yùn)用的靈活性。然后，優(yōu)化目標(biāo)通常考慮動(dòng)車(chē)組數(shù)量、動(dòng)車(chē)組運(yùn)用均衡性、檢修均衡程度、檢修次數(shù)等指標(biāo)，例如，Canca等[7]以車(chē)底數(shù)最小和均衡性最大為目標(biāo)；張才春等[8]以動(dòng)車(chē)組數(shù)量最少和動(dòng)車(chē)組總檢修時(shí)間最小為目標(biāo)；Cadarso等[9]在目標(biāo)函數(shù)中考慮了運(yùn)營(yíng)中的延遲時(shí)間和人員需求，以?xún)?yōu)化路網(wǎng)車(chē)底運(yùn)用計(jì)劃的魯棒性，但列車(chē)運(yùn)用過(guò)程沒(méi)有考慮檢修約束；李建等[10]通過(guò)構(gòu)建0-1整數(shù)規(guī)劃模型實(shí)現(xiàn)了動(dòng)車(chē)組接續(xù)時(shí)間最小化和動(dòng)車(chē)組檢修前累計(jì)運(yùn)行里程最大化。最后，用于動(dòng)車(chē)組運(yùn)用計(jì)劃模型求解的方法主要包括解析算法和智能算法兩大類(lèi)，前者主要有商業(yè)求解器[3]、分支-切割算法[7]、改進(jìn)的分支定界法[11]等，后者則以蟻群算法[12]、模擬退火算法[13]、粒子群算法[10,14]等啟發(fā)式算法為主。

既有研究較少涉及動(dòng)車(chē)組運(yùn)用計(jì)劃中相鄰列車(chē)任務(wù)接續(xù)的可靠性問(wèn)題。動(dòng)車(chē)組一般按時(shí)刻表執(zhí)行交路段中的各運(yùn)行任務(wù)，但實(shí)際中可能出現(xiàn)由突發(fā)事件或隨機(jī)擾動(dòng)造成的晚點(diǎn)情況，如列車(chē)到達(dá)晚點(diǎn)、檢修(整備)任務(wù)完成晚點(diǎn)和空車(chē)調(diào)撥到達(dá)晚點(diǎn)。這類(lèi)晚點(diǎn)會(huì)影響動(dòng)車(chē)組在要求時(shí)間內(nèi)完成接續(xù)和周轉(zhuǎn)，即降低了接續(xù)可靠性。作為動(dòng)車(chē)組運(yùn)用計(jì)劃的一部分，動(dòng)車(chē)組接續(xù)延誤會(huì)產(chǎn)生額外的運(yùn)營(yíng)調(diào)整和人員費(fèi)用，所以在編制動(dòng)車(chē)組運(yùn)用計(jì)劃時(shí)，應(yīng)在降低接續(xù)時(shí)間成本的同時(shí)保證較高的接續(xù)可靠性。

本文結(jié)合我國(guó)動(dòng)車(chē)組日常運(yùn)用中的需求，基于運(yùn)用網(wǎng)絡(luò)圖，應(yīng)用晚點(diǎn)分布函數(shù)和概率論分析動(dòng)車(chē)組接續(xù)可靠性，構(gòu)建考慮動(dòng)車(chē)組檢修和熱備的運(yùn)用計(jì)劃優(yōu)化模型，設(shè)計(jì)基于蟻群算法的模型求解算法，并通過(guò)案例研究驗(yàn)證本文提出的方法。

1 動(dòng)車(chē)組運(yùn)用網(wǎng)絡(luò)圖構(gòu)建

本文通過(guò)引入接續(xù)可靠性?xún)?yōu)化動(dòng)車(chē)組的日計(jì)劃，這一計(jì)劃是動(dòng)態(tài)的，即日計(jì)劃均需根據(jù)動(dòng)車(chē)組的初始狀態(tài)、任務(wù)情況進(jìn)行優(yōu)化。動(dòng)車(chē)組日計(jì)劃需要基于維修歷史數(shù)據(jù)、綜合接續(xù)時(shí)間、檢修里程和動(dòng)車(chē)段所能力等約束，安排動(dòng)車(chē)組在新的日計(jì)劃中執(zhí)行的各類(lèi)任務(wù)，包括列車(chē)、檢修(整備)和熱備任務(wù)。其中，動(dòng)車(chē)組在上一個(gè)日計(jì)劃中的最后任務(wù)是新的日計(jì)劃的初始任務(wù)，新的日計(jì)劃的初始時(shí)刻為t0。動(dòng)車(chē)組任務(wù)的接續(xù)關(guān)系見(jiàn)圖1。

圖1 反映各任務(wù)之間接續(xù)關(guān)系的動(dòng)車(chē)組運(yùn)用網(wǎng)絡(luò)圖

圖1中k為動(dòng)車(chē)組的編號(hào)；K為動(dòng)車(chē)組總數(shù)；M為動(dòng)車(chē)組集合；t為計(jì)劃周期中的時(shí)刻，t∈[t0,T]，T為日計(jì)劃的結(jié)束時(shí)刻。

1.1 任務(wù)節(jié)點(diǎn)

(1)

1.2 任務(wù)接續(xù)有向弧

動(dòng)車(chē)組執(zhí)行完列車(chē)任務(wù)后必須執(zhí)行檢修(整備)任務(wù)，一般情況下需要在車(chē)站進(jìn)行整備，之后執(zhí)行后續(xù)列車(chē)任務(wù)。當(dāng)累計(jì)運(yùn)行里程達(dá)到檢修規(guī)定的里程后，需要在運(yùn)用所進(jìn)行一級(jí)或二級(jí)檢修。熱備車(chē)在運(yùn)用動(dòng)車(chē)組故障時(shí)執(zhí)行列車(chē)任務(wù)，執(zhí)行熱備任務(wù)的動(dòng)車(chē)組需要定期更換且每隔一段時(shí)間內(nèi)需要進(jìn)行一次一級(jí)檢修，以保證熱備車(chē)良好的運(yùn)行狀態(tài)。各任務(wù)之間的接續(xù)弧分為圖2所示的5種類(lèi)型。

圖2 任務(wù)之間的接續(xù)關(guān)系圖

(1)入檢(整備)接續(xù)弧aij∈ANF(i∈VN,j∈VF,φj=0，且滿(mǎn)足式(1))，ANF為入檢(整備)接續(xù)弧集合。

(2)出檢(整備)接續(xù)弧aij∈AFN(i∈VF,j∈VN,φj=0)，AFN為出檢(整備)接續(xù)弧集合。

(3)入備接續(xù)弧aij∈AFB(i∈VF,j∈VB,φj=0，且滿(mǎn)足式(1))，AFB為入備接續(xù)弧集合。

(4)出備接續(xù)弧aij∈ABN(i∈VB,j∈VN,φj=0)，ABN為出備接續(xù)弧集合。

2 基于接續(xù)可靠性的運(yùn)用計(jì)劃優(yōu)化模型

2.1 假設(shè)和符號(hào)定義

為簡(jiǎn)化問(wèn)題的復(fù)雜性，提出以下合理假設(shè)：

(1)研究的動(dòng)車(chē)組運(yùn)用計(jì)劃基于給定的運(yùn)行圖，暫未考慮運(yùn)行圖的調(diào)整。

(2)動(dòng)車(chē)組運(yùn)用模式為不固定區(qū)段方式，各站之間允許空車(chē)調(diào)撥。

(3)動(dòng)車(chē)組日計(jì)劃的制定主要考慮運(yùn)用檢修，運(yùn)用檢修包括一級(jí)檢修和二級(jí)檢修。一級(jí)檢修周期為3 300 ～4 000 km，二級(jí)檢修周期為27 000 ～30 000 km。本文未考慮其他高級(jí)檢修，因?yàn)楦呒?jí)檢修的停時(shí)均大于1 d，超過(guò)日計(jì)劃的計(jì)劃范圍，同時(shí)日計(jì)劃主要針對(duì)當(dāng)日可用動(dòng)車(chē)組，進(jìn)行高級(jí)檢修的動(dòng)車(chē)組可以在計(jì)劃前進(jìn)行排除。

(4)采用最高允許速度為350 km/h的單一型號(hào)且編組固定動(dòng)車(chē)組，暫不考慮動(dòng)車(chē)組重聯(lián)、解編的情形。

(5)列車(chē)任務(wù)完成后需要檢修(整備)時(shí)，列車(chē)將在當(dāng)前車(chē)站進(jìn)行檢修(整備)。

為方便模型構(gòu)建，定義如下符號(hào)。

Lr,min(Lr,max):r(r=1,2)級(jí)檢修任務(wù)的最小(最大)累計(jì)運(yùn)行里程限制。

2.2 接續(xù)可靠性分析與計(jì)算

(2)

(3)

根據(jù)晚點(diǎn)時(shí)間分布和最小接續(xù)時(shí)間可計(jì)算動(dòng)車(chē)組完成列車(chē)任務(wù)i-j接續(xù)的可靠性為

j∈VN,φj=0

(4)

(5)

全部動(dòng)車(chē)組運(yùn)用日計(jì)劃由K列動(dòng)車(chē)組的交路段組成，運(yùn)用日計(jì)劃的接續(xù)可靠性定義為全部交路段可靠性的平均值，計(jì)算方法為

(6)

考慮工程方案可行性要求，本文設(shè)定任一動(dòng)車(chē)組的交路段接續(xù)可靠性均需要滿(mǎn)足最低可靠度的要求。

2.3 優(yōu)化目標(biāo)與約束條件

基于上述對(duì)列車(chē)接續(xù)可靠性的分析，本文目標(biāo)函數(shù)為動(dòng)車(chē)組運(yùn)營(yíng)總懲罰費(fèi)用最小

(7)

式中：z1為單位計(jì)劃接續(xù)時(shí)間對(duì)應(yīng)的懲罰費(fèi)用，元/min；z2為空車(chē)調(diào)撥單位運(yùn)行里程對(duì)應(yīng)的懲罰費(fèi)用，元/km；z3為單位接續(xù)可靠性下降對(duì)應(yīng)的懲罰費(fèi)用，元。z1和z2通過(guò)調(diào)研獲得。

式(7)第一項(xiàng)表示動(dòng)車(chē)組的計(jì)劃接續(xù)時(shí)間總懲罰費(fèi)用，除了必要的運(yùn)行時(shí)間，計(jì)劃中的接續(xù)時(shí)間主要表示動(dòng)車(chē)組的在站等待時(shí)間，接續(xù)時(shí)間越小表示動(dòng)車(chē)組的運(yùn)用效率越高；第二項(xiàng)表示由空車(chē)調(diào)撥產(chǎn)生的懲罰費(fèi)用；第三項(xiàng)表示由接續(xù)風(fēng)險(xiǎn)產(chǎn)生的懲罰費(fèi)用，通過(guò)接續(xù)可靠性表示接續(xù)風(fēng)險(xiǎn)。由于接續(xù)可靠性覆蓋了全部接續(xù)的列車(chē)任務(wù)，本文假設(shè)接續(xù)可靠性指標(biāo)與前兩項(xiàng)費(fèi)用具有同等重要度，因此費(fèi)用結(jié)果具有相同的數(shù)量級(jí)。

約束條件為

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

2.4 模型求解算法

本文針對(duì)所建立的優(yōu)化模型設(shè)計(jì)蟻群算法：一只螞蟻的路徑表示一列動(dòng)車(chē)組的運(yùn)用日計(jì)劃，所有螞蟻的路徑可表示全部動(dòng)車(chē)組的運(yùn)用日計(jì)劃。算法設(shè)置最大迭代次數(shù)，每一次迭代中，設(shè)置時(shí)間步長(zhǎng)t∈[t0,T]推動(dòng)計(jì)算。根據(jù)各弧的轉(zhuǎn)移概率實(shí)現(xiàn)列車(chē)任務(wù)的分配，并根據(jù)信息素濃度的變化不斷更新轉(zhuǎn)移概率，在系統(tǒng)時(shí)間結(jié)束時(shí)完成一次迭代，需要保證安排全部的列車(chē)任務(wù)。計(jì)算當(dāng)前代的目標(biāo)函數(shù)值并更新最優(yōu)方案，之后更新全局信息素并繼續(xù)迭代，在迭代達(dá)到最大次數(shù)時(shí)終止算法。其中，轉(zhuǎn)移概率公式和全局信息素更新規(guī)則采用文獻(xiàn)[15]的方法。

上述過(guò)程中可以通過(guò)接續(xù)控制保證約束式(8)～式(16)，為了保證解的可行性，將約束式(17)構(gòu)造為懲罰函數(shù)并加入目標(biāo)函數(shù)

(18)

式中：z4為懲罰系數(shù)，由于全部動(dòng)車(chē)組的日計(jì)劃接續(xù)可靠度小于目標(biāo)要求是不可接受的情形，因此設(shè)定懲罰系數(shù)z4的數(shù)量級(jí)為連續(xù)接續(xù)任務(wù)可靠度懲罰系數(shù)z3的3倍，以剔除不滿(mǎn)足約束式(17)的解。

解空間的構(gòu)造方法和啟發(fā)式信息素的設(shè)置如下：

(1)構(gòu)造解空間

Step1初始化變量和參數(shù)，按照2.1節(jié)生成非列車(chē)任務(wù)的相關(guān)參數(shù)和接續(xù)條件，設(shè)置初始時(shí)間為t0、時(shí)間步長(zhǎng)為1 min。

Step5令t=t+1，如果t≤T，進(jìn)行Step2，直到t>T，結(jié)束算法。

(2)啟發(fā)式信息素更新

(19)

式中：b為啟發(fā)式因子重要程度參數(shù)。

3 案例研究

本文以某客運(yùn)專(zhuān)線(xiàn)A、B、C 3站間的動(dòng)車(chē)組運(yùn)用日計(jì)劃編制進(jìn)行案例研究。3站都有配屬的動(dòng)車(chē)運(yùn)用所，且3站間開(kāi)行AB、AC兩條線(xiàn)路的列車(chē)，通過(guò)調(diào)研已知28對(duì)列車(chē)(編號(hào)為1～56)的時(shí)刻表、各動(dòng)車(chē)組初始任務(wù)(初始列車(chē)任務(wù)編號(hào)首位為0)和3站配屬動(dòng)車(chē)組情況、檢修能力、晚點(diǎn)分布等基本數(shù)據(jù)。假設(shè)熱備任務(wù)和檢修任務(wù)之間的距離(時(shí)間)忽略不計(jì)，與本文研究直接相關(guān)的其他主要參數(shù)設(shè)置見(jiàn)表1。

表1 案例研究相關(guān)參數(shù)取值

文本采用MATLAB 2014a實(shí)現(xiàn)所設(shè)計(jì)的蟻群算法，算法中信息素重要程度參數(shù)α=1，啟發(fā)式因子重要程度參數(shù)b=10，信息素增加強(qiáng)度系數(shù)Q=10 000，信息素蒸發(fā)系數(shù)v=0.3，迭代代數(shù)為150代，多次求解運(yùn)算后獲得結(jié)果見(jiàn)表2。

表2中，方案1是未考慮列車(chē)接續(xù)可靠性的運(yùn)用方案，方案2是考慮列車(chē)接續(xù)可靠性的優(yōu)化運(yùn)用方案。方案1中交路段可靠性低于50%的交路段有3個(gè)，分別是1、3和8號(hào)動(dòng)車(chē)組交路段，特別地有交路段1的可靠性非常低，執(zhí)行這些交路段的動(dòng)車(chē)組在任務(wù)到達(dá)(完成)晚點(diǎn)時(shí)不能正常接續(xù)下一列車(chē)任務(wù)的概率很大；而方案2中不存在接續(xù)可靠性低于50%的交路段，一方面全部交路的整體可靠性有所提高，另一方面低可靠性的交路段數(shù)量減少，整體上較大幅度地降低了動(dòng)車(chē)組接續(xù)的風(fēng)險(xiǎn)。

兩個(gè)方案的進(jìn)一步指標(biāo)分析結(jié)果見(jiàn)表3。由表3可知，方案2中已經(jīng)不存在0～49%的交路段，比方案1減少了3個(gè)，而可靠性大于90%的交路段個(gè)數(shù)增加了7個(gè)；兩個(gè)方案使用的動(dòng)車(chē)組總數(shù)沒(méi)有變化，表明適當(dāng)提高接續(xù)可靠性的優(yōu)化方案不會(huì)額外增加動(dòng)車(chē)組數(shù)量。方案2的動(dòng)車(chē)組接續(xù)時(shí)間懲罰費(fèi)用比方案1多199 600元，即增加1 996 min的接續(xù)時(shí)間，主要原因是方案2中部分熱備車(chē)承擔(dān)運(yùn)行任務(wù)，而接續(xù)時(shí)間是以列車(chē)任務(wù)為基準(zhǔn)進(jìn)行計(jì)算的，因此相比方案1會(huì)增加較多的接續(xù)時(shí)間。例如，動(dòng)車(chē)組10、23的初始接續(xù)時(shí)間之和為1 992 min，說(shuō)明方案2不會(huì)對(duì)既有運(yùn)營(yíng)條件有較大的影響。方案2的空車(chē)?yán)锍逃兴黾樱瑢?shí)際上為1個(gè)AC方向的空車(chē)運(yùn)行變?yōu)?個(gè)AB方向的空車(chē)調(diào)撥。接續(xù)可靠度方面，方案2將平均接續(xù)可靠性提高了16.74%，從而有效優(yōu)化了接續(xù)風(fēng)險(xiǎn)總懲罰費(fèi)用和總費(fèi)用。以上分析表明運(yùn)營(yíng)條件基本不改變的情況下提高動(dòng)車(chē)組接續(xù)可靠性可以有效避免因?yàn)橥睃c(diǎn)等運(yùn)行波動(dòng)造成的運(yùn)營(yíng)風(fēng)險(xiǎn)。

表2 考慮列車(chē)接續(xù)可靠性的運(yùn)用日計(jì)劃方案

表3 動(dòng)車(chē)組運(yùn)用計(jì)劃優(yōu)化前后指標(biāo)對(duì)比

4 小結(jié)

本文定量分析了動(dòng)車(chē)組運(yùn)用計(jì)劃的列車(chē)接續(xù)可靠性，以總懲罰費(fèi)用最小建立了運(yùn)用計(jì)劃優(yōu)化模型，設(shè)計(jì)基于蟻群算法的求解方法，通過(guò)算例驗(yàn)證了模型算法。結(jié)果表明：考慮列車(chē)接續(xù)可靠性的動(dòng)車(chē)組運(yùn)用計(jì)劃可以減少接續(xù)可靠性低的任務(wù)接續(xù)的數(shù)量，雖然會(huì)增加空車(chē)運(yùn)行里程和接續(xù)時(shí)間，但可以有效降低接續(xù)風(fēng)險(xiǎn)總懲罰費(fèi)用。

提高動(dòng)車(chē)運(yùn)用計(jì)劃中的列車(chē)接續(xù)可靠性，減少因動(dòng)車(chē)運(yùn)用計(jì)劃未實(shí)現(xiàn)而重新調(diào)整接續(xù)的列車(chē)數(shù)量，可為優(yōu)化動(dòng)車(chē)組運(yùn)用計(jì)劃提供依據(jù)，也能更好地適應(yīng)運(yùn)營(yíng)環(huán)境的變化。今后將進(jìn)一步研究未實(shí)現(xiàn)可靠接續(xù)的動(dòng)車(chē)組運(yùn)用計(jì)劃的優(yōu)化調(diào)整方案。