地鐵乘務(wù)排班計劃優(yōu)化的最短路快速算法

薛鋒，梁鵬，李海，陳崇雙，周天星

(1. 西南交通大學(xué) 交通運輸與物流學(xué)院，四川 成都 611756；2. 綜合交通運輸智能化國家地方聯(lián)合工程實驗室，四川 成都 611756；3. 綜合交通大數(shù)據(jù)應(yīng)用技術(shù)國家工程實驗室，四川 成都 611756；4. 西南交通大學(xué) 數(shù)學(xué)學(xué)院，四川 成都 611756；5. 中鐵二院工程集團有限責(zé)任公司 交通與城市規(guī)劃研究院，四川 成都 610031)

乘務(wù)計劃是地鐵運營組織計劃中的核心工作之一，一般分為排班計劃和輪班計劃；其中排班計劃是尋找列車車次與乘務(wù)任務(wù)之間的對應(yīng)關(guān)系，是輪班計劃的基礎(chǔ)，也是整個乘務(wù)計劃編制過程中較為復(fù)雜的工作。乘務(wù)排班計劃是交通運輸領(lǐng)域研究的熱點問題之一，目前對于乘務(wù)計劃編制問題的研究主要集中于鐵路、航空及城市公交方面。其中鐵路方面的研究可以為城市軌道交通乘務(wù)排班提供很好的參考。HANAFI 等[1]構(gòu)建了最小化乘務(wù)組費用的優(yōu)化模型以得到最優(yōu)乘務(wù)交路方案；LUCIC 等[2]將乘務(wù)排班計劃分為2 個階段，設(shè)計了基于啟發(fā)式算法與模擬退火技術(shù)的2種求解方法；FRELING等[3]利用價格分支算法對乘務(wù)排班計劃問題進行建模和求解；楊國元等[4]設(shè)計了基于遺傳算法的模型求解算法對鐵路客運乘務(wù)排班計劃進行編制；符卓等[5]建立了編制日乘務(wù)交路的0-1整數(shù)規(guī)劃模型，并給出了基于禁忌搜索算法的求解方法；林楓[6]將乘務(wù)交路計劃編制過程分為兩階段，并設(shè)計了MOMS求解算法；楊嘉寶等[7]建立了乘務(wù)交路回路優(yōu)化模型，給出了蟻群-遺傳混合求解算法。在城市軌道交通方面，CHU[8]從多個階段對乘務(wù)排班計劃進行研究，并分別采用了最短路算法、對稱匹配和改進遺傳算法進行求解；JANACEK 等[9]將根據(jù)時間段分成的多個區(qū)間作為列生成算法中的一個子問題進行并行求解；張增勇等[10]利用改進的Dijkstra 算法和離散粒子群算法給出了乘務(wù)作業(yè)段生成模型和乘務(wù)工作班生成模型的求解方法；石俊剛等[11]建立了城軌乘務(wù)任務(wù)配對模型，并基于列生成思想對其進行求解；許仲豪等[12]研究了基于列生成算法的乘務(wù)排班計劃優(yōu)化模型；豐富等[13]基于時間均衡度構(gòu)建了乘務(wù)排班計劃模型，并提出了基于遺傳算法的求解方法；金華等[14]研究建立了乘務(wù)排班計劃集合覆蓋模型，通過將定價子問題轉(zhuǎn)化為網(wǎng)絡(luò)圖集合的最短路問題設(shè)計了列生成法求解算法。本文基于最短路算法思想，提出一種乘務(wù)排班計劃優(yōu)化編制方法：在考慮便乘的情況下，建立了乘務(wù)排班計劃接續(xù)時間最少和總運營成本最小為目標(biāo)的優(yōu)化模型；以乘務(wù)作業(yè)段為頂點、乘務(wù)作業(yè)段之間的接續(xù)關(guān)系為弧，將乘務(wù)排班計劃轉(zhuǎn)化成求解網(wǎng)絡(luò)圖中的最短路問題，提出了一種基于SPFA 的求解算法。該方法計算簡便、快速，能實際應(yīng)用于城市軌道交通尤其是地鐵乘務(wù)排班計劃問題的求解。

1 問題的描述與分析

地鐵乘務(wù)排班計劃編制是將地鐵線路的乘務(wù)段經(jīng)過計算與編排，得到乘務(wù)排班日計劃的過程。其編制步驟為：

1) 根據(jù)地鐵的運行區(qū)段及其到發(fā)點確定乘務(wù)片段；

2) 根據(jù)乘務(wù)片段構(gòu)建乘務(wù)作業(yè)段；

3) 根據(jù)乘務(wù)作業(yè)段編制乘務(wù)任務(wù)。

輪乘站是地鐵線路上特殊的車站，是乘務(wù)員交接班、用餐的固定地點，因此可以作為劃分乘務(wù)作業(yè)段的依據(jù)。乘務(wù)作業(yè)段是乘務(wù)員值乘的基本單元，代表著相鄰2個輪乘站之間的一段駕駛?cè)蝿?wù)。乘務(wù)任務(wù)是一名乘務(wù)員當(dāng)班值乘的乘務(wù)作業(yè)段的組合，乘務(wù)排班日計劃即為所有乘務(wù)任務(wù)的組合。

以圖1 為例，“110”等為車底編號，該線路上的輪乘站將此線路劃分為一個個乘務(wù)作業(yè)段，而各個乘務(wù)作業(yè)段由一個或多個乘務(wù)片段組成，滿足接續(xù)時間要求(即，休息時間滿足約束)的乘務(wù)作業(yè)段即可組合形成乘務(wù)任務(wù)，多個乘務(wù)任務(wù)即可組成乘務(wù)排班日計劃。

2 數(shù)學(xué)模型的建立

以輪乘站為分割點將以列車運行線為依據(jù)的乘務(wù)活動分割成一系列的乘務(wù)作業(yè)段，以日為時間周期，將一天之內(nèi)的乘務(wù)作業(yè)段按照時間分為早班、白班、夜班3個時間段的乘務(wù)作業(yè)段，以此構(gòu)建乘務(wù)作業(yè)段的接續(xù)時間矩陣，如表2所示。

表2 乘務(wù)作業(yè)段接續(xù)時間矩陣Table 2 Connecting time matrix of crew work-pieces

表2 中，行與列均表示不同組的乘務(wù)作業(yè)段。其中Pi(i=1，…，a)為早班時間段的乘務(wù)作業(yè)段(共有a個)；Qi(i=a+1，…，a+b)為白班時間段的乘務(wù)作業(yè)段(共有b個)；Ri(i=a+b+1，…，a+b+c)為夜班時間段的乘務(wù)作業(yè)段(共有c個)。令n=a+b+c為乘務(wù)作業(yè)段的總數(shù)，Cij(i，j=1，…，n)為乘務(wù)作業(yè)段Pi(或Qi，Ri)與乘務(wù)作業(yè)段Pj(或Qj，Rj)之間的接續(xù)時間。

由于乘務(wù)作業(yè)段根據(jù)作業(yè)時間被分為了早、白、夜3個班次，乘務(wù)作業(yè)段只能按照時間順序向后接續(xù)，同一班次或不同班次的乘務(wù)作業(yè)段不能逆時接續(xù)；同時約定不同班次的乘務(wù)作業(yè)段之間不能接續(xù)，其接續(xù)時間用一個足夠大的正整數(shù)M表示。同時，若乘務(wù)作業(yè)段間的接續(xù)時間不滿足休息時間約束，則這樣的乘務(wù)作業(yè)段無法相互接續(xù)，其接續(xù)時間也用M表示。

2.1 最小化乘務(wù)排班計劃總接續(xù)時間優(yōu)化模型

按照上述思路，可建立以乘務(wù)排班計劃總接續(xù)時間最小為優(yōu)化目標(biāo)的模型，如式(1)所示。其中Z為乘務(wù)排班計劃總接續(xù)時間，Cij為乘務(wù)作業(yè)段之間的接續(xù)時間；xij為0-1 變量，當(dāng)其為1 時，表示乘務(wù)作業(yè)段i接續(xù)乘務(wù)作業(yè)段j；當(dāng)其為0 時，表示乘務(wù)作業(yè)段i不接續(xù)乘務(wù)作業(yè)段j。

同時對乘務(wù)作業(yè)段的接續(xù)進行約束，使得2個乘務(wù)作業(yè)段之間最多只能接續(xù)一次。式(2)表示每個乘務(wù)作業(yè)段在排班計劃中有且僅有一個緊前作業(yè)段；式(3)表示每個乘務(wù)作業(yè)段在排班計劃中有且僅有一個后續(xù)作業(yè)段，也就是乘務(wù)作業(yè)段i和j最多配對接續(xù)一次，求和均為0時表示該乘務(wù)作業(yè)段未能與其他乘務(wù)作業(yè)段接續(xù)，成為單個乘務(wù)作業(yè)段的乘務(wù)任務(wù)。

對乘務(wù)作業(yè)段之間的接續(xù)時間進行約束，使其滿足乘務(wù)作業(yè)段間的休息時間約束，如式(4)所示；對乘務(wù)任務(wù)中的司機連續(xù)工作時長進行約束，使其工作時長不能超過給定的連續(xù)工作時長限制，如式(5)所示；對乘務(wù)任務(wù)中的吃飯時間進行約束，使其滿足吃飯時間標(biāo)準(zhǔn)，如式(6)所示。

式中：Cmin為乘務(wù)作業(yè)段間的最短休息時間；Cmax為乘務(wù)作業(yè)段間的最長休息時間；tj為乘務(wù)作業(yè)段j的司機工作時間；t0為乘務(wù)任務(wù)的第一個乘務(wù)作業(yè)段的工作時間；T為司機連續(xù)工作時間限制；tcf為一個乘務(wù)任務(wù)中的吃飯時間；tcfmin為最短吃飯時間；tcfmax為最長吃飯時間。

式中：K為便乘時間；ebc為便乘時間的懲罰因子，其取值視便乘的實際成本而定，tbc為乘務(wù)作業(yè)段i與乘務(wù)作業(yè)段j之間的便乘時間，aij為0-1 變量，當(dāng)其為1時，表示乘務(wù)作業(yè)段i與乘務(wù)作業(yè)段j之間存在便乘，當(dāng)其為0時則不存在便乘。

將2個優(yōu)化目標(biāo)結(jié)合，形成一個總時間最少的優(yōu)化模型。

2.2 最小化乘務(wù)排班計劃總運營成本優(yōu)化模型

由于各乘務(wù)作業(yè)段的起止時間都已確定，且乘務(wù)員的總在車時間也為固定值，則乘務(wù)排班計劃的運營成本都體現(xiàn)在乘務(wù)員的工資上。所以，要減少乘務(wù)排班計劃所需的費用，就需要盡量減少乘務(wù)任務(wù)的數(shù)量，即增加每個乘務(wù)任務(wù)包含的乘務(wù)作業(yè)段的數(shù)量，使得乘務(wù)作業(yè)段之間的接續(xù)數(shù)量最大，如式(9)所示。

由此構(gòu)成了一個最小化乘務(wù)排班計劃總時間和總費用的雙目標(biāo)優(yōu)化模型，此模型以式(9)為主要優(yōu)化目標(biāo)，式(8)為次要優(yōu)化目標(biāo)，更具有通用性。

3 求解算法

本文采用最短路方法進行求解，分早、白、夜班3個部分分別構(gòu)成網(wǎng)絡(luò)圖。將乘務(wù)作業(yè)段作為網(wǎng)絡(luò)圖的頂點，乘務(wù)作業(yè)段的接續(xù)關(guān)系作為弧，與xij相乘的數(shù)作為網(wǎng)絡(luò)圖中弧上的權(quán)值，即ωij=Cij+ebctbcaij，一條網(wǎng)路圖中的最短路徑即為一個乘務(wù)任務(wù)，因此乘務(wù)排班日計劃即為網(wǎng)絡(luò)圖中多個最短路徑的集合。圖2為乘務(wù)作業(yè)段形成的網(wǎng)絡(luò)圖(中間的時間點已省略)。對于乘務(wù)排班網(wǎng)絡(luò)，采用SPFA 算法[15]進行最短路徑的求解。SPFA 算法是求解單源最短路徑問題的一種算法，采用了動態(tài)優(yōu)化逼近的思想。算法的基本步驟如下。

Step 1：以輪乘站為起止點，將乘務(wù)片段集合組合成乘務(wù)作業(yè)段的集合Pi(或Qi，Ri)。

Step 2：以乘務(wù)作業(yè)段為頂點，乘務(wù)作業(yè)段之間的接續(xù)關(guān)系為邊，ωij=Cij+ebctbcaij作為邊上的權(quán)值，構(gòu)成早班、白班及夜班的3個網(wǎng)絡(luò)圖。

Step 3：初始化一個D數(shù)組，由頂點和頂點對應(yīng)的權(quán)值構(gòu)成，數(shù)組中的頂點為Pi，除了起點P1賦值為0外，其他頂點對應(yīng)的權(quán)值都賦予無窮大，這樣有利于后續(xù)的松弛。同時把起點P1加入循環(huán)隊列，從此處開始進入循環(huán)，直到隊列為空才退出循環(huán)。

Step 4：首先進行第一次循環(huán)，循環(huán)隊列的第一個頂點P1出列，然后對以P1為弧尾的邊對應(yīng)的弧頭頂點進行松弛操作，若P1到該頂點的最短路徑變短了，則更新循環(huán)數(shù)組中該頂點的權(quán)值為新的最短路徑。當(dāng)頂點都被松弛了，而且不在隊列中時，就把它們加入循環(huán)隊列中。

Step 5：進行第2 次循環(huán)，新的隊首元素出列，然后對以隊首元素為弧尾的邊對應(yīng)的弧頭頂點進行松弛操作，步驟與Step 4類似，數(shù)組的權(quán)值及循環(huán)隊列中的頂點再次更新。

Step 6：按照上述方法對隊列進行更新，一直到隊列為空才退出循環(huán)，此時數(shù)組里就保存了從源點到各頂點的最短路徑值，以此得到起點P1到各個頂點的最短路徑的值。

Step 7：先在其中選取滿足式(9)的路徑，此時被選擇的路徑為運營成本最小的路徑，在此基礎(chǔ)上，再從被選擇的路徑中選取滿足式(8)的路徑，作為最終求得的以P1為起點的最短路徑。

Step 8：更換起點為Pi，將以P1為起點的最短路徑經(jīng)過的點去除，從Step 4重新開始循環(huán)，一直到退出循環(huán)，再求得以Pi為起點的最短路徑。

Step 9：遍歷早班時間段的a個頂點，直到所有頂點均被求得的路徑包含其中，由此求得的各個最短路徑即為早班時間段的乘務(wù)任務(wù)。

Step 10：將白班時間段與夜班時間段的各個乘務(wù)作業(yè)段按照上述方法進行求解，由此求得的所有最短路徑即為一天的乘務(wù)排班計劃。

4 實例分析

本文以成都地鐵5 號線為例編制乘務(wù)排班計劃。采用C++編程實現(xiàn)上述模型和算法，并在CoreTMi5 2.3 GHz主頻、16 G內(nèi)存的計算機上運行。

成都地鐵5 號線共設(shè)有41 個車站，其中輪乘站8 個，用S1-S8 來表示，將乘務(wù)片段組合成乘務(wù)作業(yè)段的3個時間段集合，其中早班時間段的乘務(wù)作業(yè)段有267 個，白班時間段的乘務(wù)作業(yè)段有201個，夜班時間段的乘務(wù)作業(yè)段有218個，乘務(wù)作業(yè)段總數(shù)為686個，如表3所示。

表3 乘務(wù)作業(yè)段集合Table 3 Collection of crew work-pieces

由于各個乘務(wù)作業(yè)段的起止時間已經(jīng)確定，在休息時間約束Cmin=10 min，Cmax=30 min 的情況下，接續(xù)時間矩陣中Cij的取值便可以確定。不同時間段的乘務(wù)作業(yè)段不能接續(xù)，因此其接續(xù)時間均為一個足夠大的正整數(shù)M，各乘務(wù)作業(yè)段之間的接續(xù)時間便可以確定，如表4所示。以乘務(wù)作業(yè)段為頂點，乘務(wù)作業(yè)段之間的接續(xù)關(guān)系為邊，結(jié)合便乘情況確定各邊的權(quán)值，構(gòu)成成都地鐵5號線早班、白班及夜班的3個網(wǎng)絡(luò)圖。隨后按照上述算法步驟進行求解，經(jīng)過若干次循環(huán)，求得早班、白班及夜班的乘務(wù)排班計劃表如表5所示。

表4 5號線乘務(wù)作業(yè)段接續(xù)時間矩陣Table 4 Connecting time matrix of metro line 5’s crew work-pieces

表5 乘務(wù)排班計劃Table 5 Crew scheduling

在最終求得的乘務(wù)排班計劃中，早班有乘務(wù)任務(wù)53 個，白班有乘務(wù)任務(wù)41 個，夜班有乘務(wù)任務(wù)49 個，乘務(wù)任務(wù)總數(shù)為143 個。早班任務(wù)時長為280 h 34 min 57 s，白班任務(wù)時長為199 h 54 min 51 s，夜班任務(wù)時長為215 h 25 min 37 s，總?cè)蝿?wù)時長為695 h 55 min 25 s。早班、白班、夜班的乘務(wù)任務(wù)時長統(tǒng)計圖如圖3～5 所示，從中可以看出求得的乘務(wù)任務(wù)時長較為均衡。

采用本文所給出的模型與算法求得的乘務(wù)排班日計劃結(jié)果與手工方法所求得的結(jié)果對比情況如表6和表7所示。

從表6 和表7 可以看出，本文所提出的乘務(wù)排班計劃算法具有以下優(yōu)點：

表6 乘務(wù)任務(wù)數(shù)量對比Table 6 Comparison of the number of crew tasks

表7 乘務(wù)任務(wù)工作時長對比Table 7 Comparison of the duration of crew tasks

1) 在滿足相應(yīng)約束條件的同時，該算法所求得的乘務(wù)任務(wù)數(shù)量較小，使得乘務(wù)排班計劃的總成本較小。

2) 該算法所求得的各乘務(wù)任務(wù)的總接續(xù)時間較小，使得乘務(wù)排班計劃的總工作時間較小，效率較高。

3) 該算法減少了便乘情況的發(fā)生，使得乘務(wù)人員的乘務(wù)任務(wù)執(zhí)行效率較高。

上述結(jié)果表明，在滿足同樣的運輸需求前提下，本文算法可提高乘務(wù)計劃的效率，降低乘務(wù)員的實際工作量。

5 結(jié)論

1) 通過本文所提出的模型算法及實例分析表明：相比于手工編制，本文方法編制的乘務(wù)排班計劃中，總乘務(wù)任務(wù)個數(shù)減少了大約4.03%，總工作時長減少了大約1.97%，由此可以看出，本文方法可以有效減少乘務(wù)排班計劃的成本及工作時長。

2) 將乘務(wù)作業(yè)段按照時間分成了早班、白班、夜班3部分，使得算法求解的時候不需要再遍歷所有乘務(wù)作業(yè)段，只需要進行各個時間段內(nèi)的乘務(wù)作業(yè)段的相互配對，顯著減少了算法的搜索時間。