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

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

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

1 問題的描述與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 求解算法

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)例分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

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