基于交路單元的高速鐵路乘務交路編制模型與算法

李 雯，賈富強，楊 睿，何東東

（蘭州交通大學交通運輸學院，甘肅 蘭州 730070）

0 引言

乘務交路計劃編制是高速鐵路乘務部門組織、管理工作的重要環(huán)節(jié)，是運營管理的核心問題之一。在實際工作中，乘務交路計劃是基于經(jīng)驗和乘務工作要求，由人工編制而成，存在編制方案單一、效率低下的問題，無法適應我國高速鐵路快速發(fā)展、運行圖變化調整的客觀需要。

國內外學者針對乘務交路計劃編制問題進行了大量研究。王瑩等[1]通過構建時空網(wǎng)絡模型對該問題進行描述，并設計了列生成法嵌入分支定界算法，對京津城際列車數(shù)據(jù)進行了驗證計算。陳巖巖[2]將列生成算法引入該問題中，并在求解中使用了Dijkstra算法。田志強[3]將這一問題看作一類特殊的旅行商問題（Travelling Salesman Problem,TSP），并建立了基于費用最小的交路段生成模型。楊國元等[4]通過改進的Dijkstra算法求解交路與車次的匹配問題。郭璞[5]針對機車乘務排班問題，分別用模擬退火算法和拉格朗日松弛算法對該問題進行了計算。李獻忠等[6]、豐富等[7]建立了廣義費用排班優(yōu)化模型，并將時間均衡度作為排班模型的重要組成部分。胡汪源[8]將該問題看作一個車輛路徑問題（Vehicle Routing Problem,VRP），以乘務人數(shù)最少、總等待時間最少為目標構建模型，并使用遺傳算法對該問題進行解決。石俊剛等[9]將任務之間的連接看作網(wǎng)絡，并使用列生成算法對問題進行了計算。石剛[10]建立了乘務交路總接續(xù)時間最短和乘務人員的實際工作時間與工作時間標準相適應的雙目標問題模型，并使用遺傳算法對問題進行求解。張哲銘等[11]將該問題歸類為僅考慮“相對時間”約束的組合優(yōu)化問題，提出了基于時空接續(xù)網(wǎng)絡和網(wǎng)絡流模型的求解策略。Oketch[12]針對航空乘務排班的特殊性，通過啟發(fā)式算法實現(xiàn)了乘務交路的自動化編制。Hoffmann等[13]針對德國鐵路客運實際問題，應用混合列生成方法，通過遺傳算法解決定價問題。Shen等[14]構建了基于費用最小的集合覆蓋交路生成模型，并使用遺傳算法使求解目標班組數(shù)目不斷接近期待值。?ahin等[15]用時空網(wǎng)絡最小流模型對該問題進行了描述，并從計算結果和計算時間兩個方面比較了序貫算法和貪心算法求解該問題的優(yōu)劣。

本文在已有研究的基礎上，從更貼近工作實際和管理需求的角度出發(fā)，構造以交路單元為基本單位的乘務交路編制模式，在區(qū)分車體接續(xù)的基礎上，以花費最小為目標，通過計算機自動生成乘務交路的優(yōu)化模型及算法。

1 乘務交路編制問題分析

高速鐵路乘務交路計劃編制問題是指根據(jù)列車開行方案、動車組車體運用計劃、乘務基地設置等相關條件對各值乘任務進行組合的計劃編制過程。在編制過程中要對人員工作能力、勞動強度、出退乘地點、交接作業(yè)流程等進行統(tǒng)籌考慮，力求實現(xiàn)值乘任務全覆蓋、降低成本的編制目標。

結合工作實際，本文提出交路單元的概念。交路單元是指同組列車車體及乘務人員從乘務基地車站出發(fā)行駛至折返站，并在最短時間內由折返站出發(fā)返回至乘務基地車站的過程。本文將交路單元作為編制乘務交路的基本單位，主要原因如下。

（1）客運乘務交路優(yōu)化的核心問題是客運乘務人員的異車體換乘作業(yè)?？瓦\乘務人員要對始發(fā)至終到的所有旅客及隨車備品負責，這就要求異車體換乘作業(yè)只能在全程作業(yè)結束后執(zhí)行，因此換乘作業(yè)只能在折返站或者乘務基地站執(zhí)行。

（2）乘務基地站與折返站在功能上存在不同，除具備指揮、出退乘、學習、住宿、餐飲功能外，乘務基地還具有應對各類突發(fā)事件時啟動熱備車體、班組及各類應急處置的功能。

因此，通過交路單元的形式，將換乘作業(yè)執(zhí)行地點設置在乘務基地站，能保證突發(fā)情況時應急處置的需要，從而最大程度地提高乘務交路計劃的穩(wěn)定性。值乘區(qū)間見圖1，交路單元見圖2。

圖1 值乘區(qū)間

圖2 交路單元

乘務交路計劃編制流程如下：①根據(jù)列車運行圖，將乘務任務分割為由乘務基地至折返站及由折返站至乘務基地的值乘區(qū)間；②由值乘區(qū)間按FIFO（先進先出）的原則組合成為交路單元；③將交路單元組合成為乘務交路。

在文獻[3]的基礎上，對編制乘務交路計劃時需要考慮的各項費用進行如下分析。

（1）出乘、退乘費用

乘務員出乘、退乘費用主要包括乘務員班組一次值乘任務所需耗材等支出的相關費用，通常為定值Cct。出乘、退乘費用的多少取決于乘務班組數(shù)量，而乘務班組數(shù)量優(yōu)化關鍵點在于縮短交路單元間的銜接時間。

（2）值乘費用

根據(jù)現(xiàn)行鐵路值乘費用Czc核算標準，其主要取決于執(zhí)行交路的始發(fā)時刻和終到時刻的時間差，優(yōu)化關鍵點在于縮短交路單元間的銜接時間。

（3）換乘與便乘費用

在乘務交路j中的換乘次數(shù)aj影響乘務計劃的穩(wěn)定性，且會導致乘務工作質量的下降和備品的遺失，同時異車體換乘需要滿足一定的接續(xù)時長。令乘務班組一次換乘的費用為chc，則交路j的換乘基本費用為ajchc。便乘涉及乘務員便乘車次和座位，涉及客票的扣除，一般不提倡出現(xiàn)便乘。

2 優(yōu)化模型的建立

2.1 分解列車運行圖

根據(jù)列車運行圖，將其中的運行任務按方向摘出，并劃分為A,B兩個集合，分別代表離開乘務基地方向和到達乘務基地方向的值乘區(qū)間。劃分后的值乘區(qū)間由下式表示：

式（1）和式（2）中：Ni為離開基地方向的值乘區(qū)間序號；Si為離開基地方向值乘區(qū)間的折返站；TNi為離開基地方向值乘區(qū)間的車次；RNi為離開基地方向值乘區(qū)間的車體號；為離開基地方向值乘區(qū)間的列車基地始發(fā)時刻；為離開基地方向值乘區(qū)間的列車終到折返站時刻；nj為到達基地方向值乘區(qū)間的車次；sj為到達基地方向值乘區(qū)間的始發(fā)站；tnj為到達基地方向值乘區(qū)間的車次；rnj為到達基地方向值乘區(qū)間的車體號；tsj為到達基地方向值乘區(qū)間的列車折返站始發(fā)時刻；為到達基地方向值乘區(qū)間的列車終到時刻。

2.2 交路單元生成模型

由于乘務員班組折返時遵守列車運行圖“先進先出”的原則，因而按照列車運行圖將值乘區(qū)間組合成為交路單元，交路單元生成模型為：

式（3）～式（6）中：xij為0-1變量，當值乘區(qū)間i和值乘區(qū)間j在同一交路單元時為1，否則為0；aijk為0-1變量，當交路單元k覆蓋值乘區(qū)間i和j時為1，否則為0；目標函數(shù)（3）為最小化折返站接續(xù)時間（min），即求符合運行圖“先進先出”原則列車；約束條件（4）表示值乘車體相同；約束條件（5）表示折返站相同；約束條件（6）表示值乘區(qū)間全部被覆蓋且無重復選擇。

交路單元的集合U，由下式表示：式（7）中：Nk為交路單元序號；TNk為交路單元覆蓋車次；RNk為車體號；Tks為交路單元的基地始發(fā)時刻且=；為交路單元的基地終到時刻且=；Sk=Si=sj表示交路單元的折返站。

2.3 乘務交路優(yōu)化模型

最小化費用的首要問題是減少值乘班組的數(shù)量及縮短整體值乘時長。在文獻[3]的基礎上，本文建立了針對客運乘務組同車體換乘和異車體換乘接續(xù)時間差異的最小費用乘務交路生成優(yōu)化模型，并以交路單元為模型生成最小單位，具體如下。

式（8）～式（16）中：m為覆蓋所有交路單元的最小乘務交路數(shù)目（個），等于完成任務需要的班組數(shù)；xi為0-1變量，當交路單元i被選擇進入一條乘務交路時取1，否則取0；aij為0-1變量，當交路單元j包含交路單元i時取1，否則取0；Zj為每條交路的值乘時長（min），其值為常數(shù)；Qj為每條交路所含的交路單元數(shù)（個），其值為常數(shù)，其中，i=1,2,…,n，j=1,2,…,m，w=1,2,…,Qj；Tjx為不同車體的換乘時間要滿足的最小接續(xù)時間（min）；Tzd為單次交路最大時長（min）。通常，當接續(xù)時間相同時，優(yōu)先選擇同車體。

目標函數(shù)（8）為最小化費用；式（9）為任一交路的乘務時長；式（10）為每個交路中包含的交路單元個數(shù)k；式（11）表示每個交路單元僅能屬于一個交路；式（12）表示在同車體值乘不考慮接續(xù)時間限制，而異車體換乘接續(xù)時間要大于最小接續(xù)時長；式（13）表示交路時長小于單次交路最大時長限制；式（14）表示交路數(shù)大于1、小于交路單元數(shù)；式（15）表示換乘次數(shù)小于等于交路單元數(shù)減1；式（16）表示交路中交路單元的次序。

3 模型的求解

3.1 基于貪婪思想的啟發(fā)式算法設計

基于模型特點和手工編制乘務交路計劃的實際，本文設計了基于貪婪思想的乘務交路生成的啟發(fā)式算法。貪婪算法基本思想為：從問題的初始解出發(fā)，通過一系列的貪婪選擇，逐步達到求解目標。通過每一次的迭代，要求解問題的規(guī)模都會縮小，且在每次迭代的過程中，都會保證得到最優(yōu)解。通過貪婪算法求得的最優(yōu)解是局部最優(yōu)解，但它無需回溯和計算簡單的優(yōu)點對于求解乘務交路計劃問題是便捷可行的。算法步驟設計如下：

（1）將列車運行圖離開乘務基地方向和駛向乘務基地方向的列車分別按到達基地時刻和離開基地時刻進行排序。

（2）按照相同車體搜索并按照時間差最小組合，生成交路單元集合U。

（3）從U中選出發(fā)車時間最早的交路單元。

（4）選出發(fā)車時間與其最為接近的下一個交路單元，即滿足接續(xù)時間最小。由于同車體不需要換乘和交接，故先在車體一致的交路單元中搜索，找到終到時間與發(fā)車時間差最小的交路單元。

（5）再在車體不同的交路單元中搜索，由于換車體值乘涉及換乘和交接作業(yè)，故需要在滿足接續(xù)時間標準的前提下找到接續(xù)時間最小的交路單元。

（6）比較步驟（2）和步驟（3）中接續(xù)時間的長短，選擇接續(xù)時間最短的交路單元與之相連接，當接續(xù)時間相等時，優(yōu)先選擇同車體交路單元。

（7）重復以上步驟，直到交路終到時間和始發(fā)時間之差大于單次最佳值乘時長Tzj時，停止形成一個交路，其中，Jw為交路編號；為交路始發(fā)時刻；tdw為交路終到時刻。

3.2 乘務交路優(yōu)化調整

生成結果中會存在一些由值乘時長極短的單元構成的乘務交路。參照人工編制流程，以最大允許單次值乘時長Tzd為限制，對已生成的值乘時長過短的小交路進行人工調整。由于乘務班組數(shù)量與交路數(shù)量直接相關，優(yōu)化調整交路的目的在于在時間允許范圍內生成的交路數(shù)量最少，即保證了值乘班組數(shù)量最少。

4 算例分析

將京津城際數(shù)據(jù)作為算例進行分析。采用Java語言對所設計的啟發(fā)式算法進行了實現(xiàn)。將京津城際時刻表錄入，所生成的乘務交路單元數(shù)據(jù)如表1所示。乘務交路生成參數(shù)設置如下：Tzj=480min,Tzd=600min,Tjx=15min,Tzd=600min。對乘務交路計劃進行人工優(yōu)化調整后，結果如表2所示，交路時長分布效果見圖3。

表1 乘務交路單元生成結果

表1（續(xù)）

表2 乘務交路優(yōu)化調整結果

從表2可知，所有乘務交路按照發(fā)車時間先后順序排列，換乘次數(shù)在0～2之間，值乘時間在8h之內，經(jīng)調整后不超過10h。由圖3可直觀看出各交路排布均勻整齊、便于管理，且每個交路值乘時長分布較為均衡。

圖3 交路時長分布圖

5 結論

實例研究表明，本文以交路單元作為基本單位的優(yōu)化模型在縮小了該問題計算量的同時滿足了實際工作中出現(xiàn)突發(fā)情況時應急處置的需要，且能從乘務作業(yè)穩(wěn)定性、可行性及管理便捷性方面滿足編制要求。基于貪婪思想的乘務交路生成算法能夠在短時間內自動化生成客運乘務交路計劃，但在求解質量方面仍然存在改進空間，將進一步開展后續(xù)研究。