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

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

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

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

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

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

1 動車組運用網(wǎng)絡(luò)圖構(gòu)建

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

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

圖1中k為動車組的編號；K為動車組總數(shù)；M為動車組集合；t為計劃周期中的時刻，t∈[t0,T]，T為日計劃的結(jié)束時刻。

1.1 任務(wù)節(jié)點

(1)

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

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

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

(1)入檢(整備)接續(xù)弧aij∈ANF(i∈VN,j∈VF,φj=0，且滿足式(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，且滿足式(1))，AFB為入備接續(xù)弧集合。

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

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

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

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

(1)研究的動車組運用計劃基于給定的運行圖，暫未考慮運行圖的調(diào)整。

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

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

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

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

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

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

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

(2)

(3)

根據(jù)晚點時間分布和最小接續(xù)時間可計算動車組完成列車任務(wù)i-j接續(xù)的可靠性為

j∈VN,φj=0

(4)

(5)

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

(6)

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

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

基于上述對列車接續(xù)可靠性的分析，本文目標(biāo)函數(shù)為動車組運營總懲罰費用最小

(7)

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

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

約束條件為

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

2.4 模型求解算法

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

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

(18)

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

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

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

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

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

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

(19)

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

3 案例研究

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

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

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

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

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

表2 考慮列車接續(xù)可靠性的運用日計劃方案

表3 動車組運用計劃優(yōu)化前后指標(biāo)對比

4 小結(jié)

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

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