蘇 銘，劉蘭芬，楊信豐，焦正玉

（蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州 730070)

0 引言

乘務(wù)排班計(jì)劃是城市軌道交通乘務(wù)計(jì)劃編制過程中的核心環(huán)節(jié)，即將運(yùn)行圖中的運(yùn)行任務(wù)分解后組合成乘務(wù)工作班。我國城市軌道交通運(yùn)營在管理制度、乘務(wù)制度、運(yùn)輸組織模式等方面均有獨(dú)特性，且排班計(jì)劃編制涉及的影響因素眾多，求解難度較大，屬于多項(xiàng)式復(fù)雜程度的非確定性問題。合理設(shè)計(jì)乘務(wù)排班計(jì)劃，為司機(jī)安排適合的工作與休息時(shí)間，對于提高運(yùn)營企業(yè)運(yùn)輸組織效率、服務(wù)水平與安全性具有重要意義。

城市軌道交通運(yùn)行交路短，發(fā)車間隔密度大，線路和運(yùn)營條件具有一定限制，都增加了計(jì)劃編制的難度，故合理高效的乘務(wù)計(jì)劃編制方法一直是城市軌道交通領(lǐng)域研究探索的重點(diǎn)。通常排班模型有集合覆蓋與分割模型、基于值乘區(qū)段接續(xù)關(guān)系模型、網(wǎng)絡(luò)圖模型等，求解算法主要包括解析算法和智能算法。在鐵路運(yùn)輸研究中，褚飛躍等[1]建立以集合分割模型為基礎(chǔ)的雙目標(biāo)排班模型；林楓等[2]以乘務(wù)交路總接續(xù)費(fèi)用和過夜費(fèi)用最小為目標(biāo)，設(shè)計(jì)改進(jìn)的蟻群優(yōu)化算法；Neufeld 等[3]建立混合整數(shù)規(guī)劃模型，采用遺傳算法與混合列生成算法求解。在城市軌道交通研究中，王瑩等[4-5]構(gòu)建集合覆蓋形式模型，將列生成嵌入分支定價(jià)算法進(jìn)行求解；張?jiān)鲇碌萚6]建立雙層規(guī)劃排班模型，設(shè)計(jì)改進(jìn)迪杰斯特拉算法和離散粒子群算法進(jìn)行計(jì)算；李獻(xiàn)忠等[7]運(yùn)用分解模型，分2 步運(yùn)用最短路和最小費(fèi)用最大流算法進(jìn)行求解；豐富[8]建立以時(shí)間均衡度為目標(biāo)排班模型；Chu、袁仁杰等[9-10]設(shè)計(jì)改進(jìn)遺傳算法；金華[11]建立多層網(wǎng)絡(luò)圖模型，許仲豪[12]等建立集合劃分模型，設(shè)計(jì)列生成算法求解；劉中舉[13]以司機(jī)數(shù)量最小及作業(yè)效率最高為目標(biāo)構(gòu)建優(yōu)化模型，結(jié)合樹枚舉和貪心算法求解；潘寒川等[14]以任務(wù)均衡為目標(biāo)，研究“隨乘”模式(DHM)與“虛擬班”模式(VGM)乘務(wù)計(jì)劃編制方法。Janacek，Moreno 等[15-16]分別將列生成算法、分支定界算法應(yīng)用于航空乘務(wù)排班、道路乘務(wù)排班與路徑問題。國內(nèi)研究主要側(cè)重于乘務(wù)制度優(yōu)缺點(diǎn)分析以及排班模型的構(gòu)建，國外主要側(cè)重于模型的求解算法，因城市軌道交通實(shí)際運(yùn)營中的乘務(wù)規(guī)則、限制條件與影響因素的不同，排班模型與求解方式方法也會有所差異。

旅行商問題(TSP 問題)利用弧和節(jié)點(diǎn)可對乘務(wù)任務(wù)的接續(xù)進(jìn)行很好的描述，在考慮避免出現(xiàn)乘務(wù)人員加班、保證休息時(shí)間的情況下，以乘務(wù)作業(yè)段間接續(xù)時(shí)間最小構(gòu)建排班模型，借鑒TSP 問題原理與求解思路將排班過程轉(zhuǎn)化為類TSP 問題，設(shè)計(jì)蟻群算法搜尋滿意解，并運(yùn)用案例驗(yàn)證模型和算法的有效性。

1 問題分析

城市軌道交通乘務(wù)排班計(jì)劃是在列車開行計(jì)劃、運(yùn)行圖以及車底周轉(zhuǎn)計(jì)劃已經(jīng)確定的前提下進(jìn)行編制。計(jì)劃編制過程一般包括確定乘務(wù)基地及值乘車站(即確定換乘點(diǎn))、劃分乘務(wù)片段、生成乘務(wù)作業(yè)段、生成乘務(wù)工作班4 個(gè)步驟。因劃分乘務(wù)片段步驟的結(jié)果只作為排班計(jì)劃輸入的最初條件，其組合方案優(yōu)劣對后續(xù)計(jì)劃整體優(yōu)化影響不大，在計(jì)劃編制時(shí)將第2 步與第3 步合并為1 個(gè)步驟。

乘務(wù)基地一般設(shè)在車輛段，實(shí)際運(yùn)營中由于線路較短，為了保障運(yùn)行效率和合理的換乘間隔，值乘車站的選取一般靠近車輛段。在運(yùn)行圖中去掉非輪乘站僅留下?lián)Q乘點(diǎn)與相關(guān)時(shí)刻，第3 步生成乘務(wù)作業(yè)段過程簡化示意圖，排班過程簡化示意圖如圖1 所示。以車底編號“2001”的運(yùn)行任務(wù)為例，該線路有車輛段與值乘車站2 個(gè)換乘點(diǎn)，以司機(jī)一次作業(yè)最長時(shí)間限制將運(yùn)行任務(wù)分割為乘務(wù)作業(yè)段，圖中黑色粗線即代表1 個(gè)乘務(wù)作業(yè)段。不同的乘務(wù)作業(yè)段再依據(jù)相應(yīng)的規(guī)則約束組合成乘務(wù)工作班。

圖1 排班過程簡化示意圖Fig.1 Simplified scheduling process

在編制乘務(wù)排班計(jì)劃過程中，主要影響因素有：①乘務(wù)作業(yè)段覆蓋的唯一性，即所有乘務(wù)作業(yè)段均必須被乘務(wù)任務(wù)所覆蓋，有且僅有一次；②乘務(wù)作業(yè)段間接續(xù)規(guī)則，即不可連續(xù)工作，前后接續(xù)的作業(yè)段間需預(yù)留交接班、基本休息時(shí)間、整備時(shí)間等相應(yīng)的時(shí)間間隔；③工作時(shí)間限制，根據(jù)《勞動法》規(guī)定的工時(shí)制度，工作班時(shí)間與司機(jī)工作時(shí)間具有相應(yīng)的時(shí)長限制；④就餐約束，運(yùn)營企業(yè)應(yīng)在規(guī)定時(shí)段內(nèi)安排司機(jī)吃飯。

2 模型構(gòu)建

2.1 符號定義

2.2 乘務(wù)作業(yè)段的生成

乘務(wù)排班計(jì)劃編制過程如圖2 所示。城市軌道交通中，車輛啟動停止頻繁，駕車環(huán)境相對較差，司機(jī)容易疲勞而產(chǎn)生安全隱患，一般需設(shè)定司機(jī)出勤一次最大連續(xù)作業(yè)時(shí)間，即1 個(gè)乘務(wù)作業(yè)段的時(shí)間跨度。休息間隔時(shí)間過短不利于乘務(wù)人員休息，時(shí)間過長則增加了乘務(wù)人員的日工作時(shí)間。依據(jù)勞動法規(guī)定，設(shè)置乘務(wù)作業(yè)段最長時(shí)間限制Tzc與最短時(shí)間限制Tzd。

圖2 乘務(wù)排班計(jì)劃編制過程Fig.2 Formulation process of crew scheduling plan

設(shè)置xij為0-1 變量表示乘務(wù)片段i被乘務(wù)作業(yè)段j選中時(shí)為1，否則為0，切割乘務(wù)作業(yè)段時(shí)，需滿足以下約束。

公式 ⑴ 至公式 ⑶ 表示1 個(gè)乘務(wù)作業(yè)段必須由相同車底、且時(shí)間與空間上相互銜接均無間隔的乘務(wù)片段組成；公式 ⑷ 至公式 ⑸ 表示每個(gè)乘務(wù)作業(yè)段時(shí)長應(yīng)滿足最短時(shí)間與最長時(shí)間限制。

2.3 乘務(wù)工作班的生成

根據(jù)乘務(wù)工作班生成步驟，考慮避免出現(xiàn)加班情況，安排司機(jī)正點(diǎn)就餐，構(gòu)建作業(yè)段接續(xù)關(guān)系模型；根據(jù)乘務(wù)工作班的約束規(guī)則，1 個(gè)工作班可以由不同的車底、不相關(guān)聯(lián)的乘務(wù)作業(yè)段組成，通常1個(gè)司機(jī)當(dāng)天的乘務(wù)任務(wù)只需值乘1個(gè)工作班。定義yqj為0-1 變量表示作業(yè)段j被工作班q選中時(shí)為1，否則為0。乘務(wù)工作班生成模型以乘務(wù)作業(yè)段間接續(xù)時(shí)間最小為目標(biāo)，可表示為

需考慮乘務(wù)作業(yè)段間接續(xù)關(guān)系、休息時(shí)間限制、乘務(wù)作業(yè)段完全覆蓋等約束條件，具體如下。

（1）所有乘務(wù)作業(yè)段必須全部被乘務(wù)工作班所覆蓋，有且僅有一次，可表示為

（2）司機(jī)在不同換乘點(diǎn)間交接班需要預(yù)留必要時(shí)間取值為Tab。定義β為0-1 變量表示接續(xù)前后乘務(wù)作業(yè)段的終止、起始車站一致即，取值為1，否則為0；司機(jī)值乘從車輛段出發(fā)的乘務(wù)作業(yè)段前需要一定的整備時(shí)間，取值為T1。定義α為0-1 變量表示當(dāng)接續(xù)的下一乘務(wù)作業(yè)段起始地點(diǎn)為車輛段時(shí)取1，否則取0；定義γ為0-1 輔助變量，1 個(gè)乘務(wù)工作班內(nèi)前后均被接續(xù)的乘務(wù)作業(yè)段時(shí)間跨度較短，其前后均在同一就餐時(shí)間段內(nèi)時(shí)僅安排在前一間隔就餐。就餐時(shí)間取值為T2，就餐時(shí)間安排如圖3 所示。設(shè)置司機(jī)最短的間休時(shí)間為T。

圖3 就餐時(shí)間安排Fig.3 Dining time arrangement

故2 個(gè)連續(xù)的乘務(wù)作業(yè)段接續(xù)時(shí)，應(yīng)滿足間隔約束可表示為

（3）根據(jù)勞動法規(guī)定，設(shè)置1 個(gè)乘務(wù)工作班的工作時(shí)間、時(shí)間跨度分別為T3，T4，乘務(wù)工作班的工作時(shí)間約束與時(shí)間跨度約束表示為

3 求解算法

3.1 類TSP 問題轉(zhuǎn)化思路

1 個(gè)商人要拜訪n個(gè)城市，每個(gè)城市只能拜訪1 次，且最后要回到原來出發(fā)的城市，如何規(guī)劃路線使得總行程最短，即為TSP 問題。在乘務(wù)工作班生成過程中，將乘務(wù)作業(yè)段抽象為帶有時(shí)空屬性的節(jié)點(diǎn)，將乘務(wù)作業(yè)段間的接續(xù)抽象為弧，每個(gè)節(jié)點(diǎn)有且只有1 次被選擇并按照接續(xù)時(shí)間及規(guī)則依次選擇節(jié)點(diǎn)，通過首尾虛擬點(diǎn)相連將此過程轉(zhuǎn)化為類TSP 問題，將乘務(wù)排班計(jì)劃問題轉(zhuǎn)化為類TSP問題時(shí)需考慮以下2 個(gè)方面。

（1）節(jié)點(diǎn)具有時(shí)空屬性。TSP 問題中城市節(jié)點(diǎn)僅具有空間位置屬性，乘務(wù)排班計(jì)劃中節(jié)點(diǎn)代表著一段時(shí)間的運(yùn)行任務(wù)，選擇城市時(shí)除距離限制外無其他約束，而乘務(wù)作業(yè)段間接續(xù)時(shí)前后段的終止、起始車站不一定相同，互相接續(xù)的乘務(wù)作業(yè)段需滿足后者起始時(shí)刻在前者終止時(shí)刻之后，故節(jié)點(diǎn)間距離矩陣也并非TSP 問題中的對稱矩陣，將不可接續(xù)的矩陣位置設(shè)置為極大值。

（2）乘務(wù)工作班具有時(shí)間限制。生成乘務(wù)工作班時(shí)，對駕駛時(shí)間、工作時(shí)間、每個(gè)乘務(wù)工作班時(shí)長均有限制，故需設(shè)置虛擬點(diǎn)。轉(zhuǎn)化為類TSP 問題，乘務(wù)作業(yè)段組合過程示意圖如圖4 所示，虛擬點(diǎn)無具體含義僅用于按照約束條件隔開工作班，所有節(jié)點(diǎn)都被選擇、覆蓋后再返回虛擬點(diǎn)1 形成完整的回路。

圖4 乘務(wù)作業(yè)段組合過程示意圖Fig.4 Combination process of crew sections

3.2 蟻群算法及流程

將生成乘務(wù)工作班步驟轉(zhuǎn)化為類TSP 問題，采用求解TSP 問題、指派問題、著色圖問題等取得較好效果的蟻群算法，以乘務(wù)作業(yè)段集合為輸入條件，設(shè)計(jì)乘務(wù)工作班模型的求解算法如下。

（1）初始化參數(shù)。螞蟻數(shù)量m，信息素重要程度因子α，啟發(fā)函數(shù)重要程度因子β，信息素釋放因子Q、最大迭代次數(shù)iter_max，迭代次數(shù)初值iter=1。根據(jù)導(dǎo)入的乘務(wù)作業(yè)段集合數(shù)據(jù)，計(jì)算兩兩作業(yè)段間的時(shí)間差，得到距離矩陣。但該問題與TSP問題計(jì)算的對稱矩陣不同，后接續(xù)的乘務(wù)作業(yè)段起始時(shí)間在被接續(xù)的乘務(wù)作業(yè)段終止時(shí)間之前時(shí)，二者不可組合在一起，將此處與對角線上的值設(shè)置為一個(gè)極大值。啟發(fā)函數(shù)為ηij(t)=1/dij，其中ηij(t)表示螞蟻在作業(yè)段i時(shí)接續(xù)作業(yè)段j的期望程度。

（2）構(gòu)建解空間。將螞蟻隨機(jī)置于不同出發(fā)點(diǎn)，將每個(gè)螞蟻訪問的第一個(gè)乘務(wù)作業(yè)段編號記錄在路徑表。設(shè)置禁忌表記錄已訪問過的作業(yè)段編號，集合allowk用于存放該螞蟻待訪問的乘務(wù)作業(yè)段編號，s為集合allowk中的一個(gè)編號。τij(t)為時(shí)間t時(shí)由節(jié)點(diǎn)i到節(jié)點(diǎn)j的信息素強(qiáng)度，對于每個(gè)螞蟻k按照公式 ⑾ 計(jì)算選出其下一個(gè)訪問的乘務(wù)作業(yè)段，將其對應(yīng)的編號記為target2，對其進(jìn)行相關(guān)約束條件判斷，計(jì)算工作時(shí)間與駕駛時(shí)間，滿足規(guī)定的間隔且一個(gè)工作班內(nèi)工作時(shí)間與駕駛時(shí)間未超過相應(yīng)限制時(shí)，記錄在路徑表內(nèi)。之后繼續(xù)選擇下一個(gè)乘務(wù)作業(yè)段，當(dāng)超過工作班相關(guān)時(shí)間限制時(shí)，當(dāng)前工作班內(nèi)作業(yè)段的選擇結(jié)束，繼續(xù)進(jìn)行下一工作班的選擇。

為了降低下一工作班內(nèi)搜索解時(shí)的盲目性與匹配時(shí)的無效性，以及盡量減少單個(gè)乘務(wù)作業(yè)段單獨(dú)成班的情況出現(xiàn)，增加選擇節(jié)點(diǎn)的方式：下一乘務(wù)工作班內(nèi)起點(diǎn)選擇集合allowk中起始時(shí)刻最早的作業(yè)段，將其對應(yīng)編號記為target3，target3 選擇方式示意圖如圖5 所示。直接記錄在路徑表內(nèi)，更新路徑表、禁忌表、集合allowk。

圖5 target3 選擇方式示意圖Fig.5 target3 selection mode

之后繼續(xù)按照公式 ⑾ 概率以輪盤賭方式計(jì)算下一接續(xù)乘務(wù)作業(yè)段，判斷相應(yīng)約束和限制條件，如此往復(fù)直至所有乘務(wù)作業(yè)段都被選擇，集合allowk為空。由于dij中設(shè)置了極大值，可能會出現(xiàn)集合allowk中所有乘務(wù)作業(yè)段的轉(zhuǎn)移概率均為0，輪盤賭失效，表示無可接續(xù)乘務(wù)作業(yè)段，此時(shí)結(jié)束當(dāng)前工作班內(nèi)乘務(wù)作業(yè)段的選擇。

為了區(qū)分乘務(wù)工作班，Table中依據(jù)螞蟻行走的路徑依次記錄乘務(wù)作業(yè)段編號并為循環(huán)過程中禁忌表賦值；Table中賦值時(shí)增加虛擬點(diǎn)0，按照工作班時(shí)間與駕駛時(shí)間限制將乘務(wù)工作班間隔開。2 個(gè)路徑表同一行數(shù)據(jù)對比如表1 所示，Table1 中“0—5—10—34—0”之間即為1 個(gè)乘務(wù)工作班，該乘務(wù)工作班共包含3 個(gè)乘務(wù)作業(yè)段。

表1 2 個(gè)路徑表同一行數(shù)據(jù)對比Tab.1 Comparison of the same row of data in two path tables

綜上所述，在計(jì)算篩選可接續(xù)節(jié)點(diǎn)時(shí)共有4種情況：該節(jié)點(diǎn)滿足全部約束可被選擇；該節(jié)點(diǎn)滿足接續(xù)順序但不滿足間隔約束；該節(jié)點(diǎn)滿足接續(xù)順序與間隔約束但超出工作時(shí)間或乘務(wù)工作班時(shí)間限制；上一節(jié)點(diǎn)無法選出可與其接續(xù)的節(jié)點(diǎn)，需單獨(dú)成班。

（3）更新信息素、迭代尋找最佳路徑。計(jì)算每個(gè)螞蟻路徑的乘務(wù)工作班內(nèi)乘務(wù)作業(yè)段間時(shí)間間隔總和，以公式 ⑹ 作為蟻群算法的評價(jià)函數(shù)，所有乘務(wù)作業(yè)段間接續(xù)時(shí)間總和最小的解即為該問題最優(yōu)解。每次迭代后按照公式 ⑿ 和公式 ⒀ 實(shí)時(shí)更新節(jié)點(diǎn)間的信息素濃度。經(jīng)過循環(huán)迭代，記錄最優(yōu)的路徑及時(shí)間長度。

式中：ρ表示信息素的揮發(fā)程度；表示第k只螞蟻在乘務(wù)作業(yè)段i與j連接路徑上釋放的信息素濃度；Δτij表示所有螞蟻在乘務(wù)作業(yè)段i與j連接路徑上釋放的信息素濃度之和。

（4）判斷算法終止條件。若iter＜iter_max，則iter=iter+1，清空2 個(gè)路徑表，并返回步驟（2）；否則，終止計(jì)算，輸出最優(yōu)解。

4 案例分析

以某地鐵4 號線為例，該線路全長20.8 km 全部為地下線，共設(shè)18 座車站，含1 個(gè)車輛段(換乘點(diǎn)1)，一個(gè)值乘車站(換乘點(diǎn)2)，運(yùn)行圖中有2列車次在非值乘車站(車站3)退出服務(wù)，故司機(jī)需到換乘點(diǎn)1、換乘點(diǎn)2 交接班。排班計(jì)劃時(shí)間標(biāo)準(zhǔn)參數(shù)取值如表2 所示。

表2 排班計(jì)劃時(shí)間標(biāo)準(zhǔn)參數(shù)取值Tab.2 Time standard parameter value of scheduling plan

（1）生成乘務(wù)作業(yè)段方案。根據(jù)表2 相關(guān)數(shù)據(jù)以及乘務(wù)作業(yè)段生成的思路，求得乘務(wù)作業(yè)段部分方案如表3 所示，求得乘務(wù)作業(yè)段時(shí)長分布如圖6所示。切割運(yùn)行圖后共得到248 個(gè)乘務(wù)作業(yè)段，平均作業(yè)段時(shí)長為85.7 min，最長時(shí)長為119.77 min，最短時(shí)長為46.98 min，符合最長時(shí)間與最短時(shí)間約束。

表3 乘務(wù)作業(yè)段部分方案Tab.3 Partial scheme of crew section program

圖6 乘務(wù)作業(yè)段時(shí)長分布Fig.6 Time distribution of crew sections

（2）生成乘務(wù)工作班方案。根據(jù)蟻群算法求解思路，以生成的乘務(wù)作業(yè)段集合為輸入數(shù)據(jù)進(jìn)行編程。蟻群算法參數(shù)取值如表4 所示。求得的乘務(wù)工作班部分方案如表5 所示，接續(xù)時(shí)間、駕駛時(shí)間、工作時(shí)間、工作班時(shí)間分布如圖7 所示，迭代收斂圖如圖8 所示。

表4 蟻群算法參數(shù)取值Tab.4 Parameter value of ant colony algorithm

表5 乘務(wù)工作班部分方案Tab.5 Partial scheme of crew shift program

計(jì)算共得到90 個(gè)乘務(wù)工作班，從圖7 中可以看出最后存在乘務(wù)作業(yè)段單獨(dú)成班的情況，并且接續(xù)時(shí)間存在長短差距較大部分，說明由于不同地點(diǎn)交接班、就餐安排等約束較多而導(dǎo)致某些時(shí)間段編制較為困難。從圖8 中可看出計(jì)算已得到穩(wěn)定的最優(yōu)解，工作班內(nèi)平均接續(xù)時(shí)間為70.97 min，平均駕駛時(shí)間為236.14 min，平均工作時(shí)間為246.14 min，平均工作班時(shí)間為307.11 min，平均工作時(shí)間低于最高限制300 min，每個(gè)工作班中平均有3 個(gè)作業(yè)段。

圖7 接續(xù)時(shí)間、駕駛時(shí)間、工作時(shí)間、工作班時(shí)間分布Fig.7 Distribution of connection time,driving time,working time,and crew shift time

圖8 迭代收斂圖Fig.8 Iterative convergence diagram

5 結(jié)束語

隨著城市軌道交通運(yùn)營規(guī)模、建設(shè)的快速增長，乘務(wù)排班計(jì)劃的質(zhì)量對于提升企業(yè)運(yùn)輸組織效率及成本效益具有重要意義。以乘務(wù)工作班內(nèi)接續(xù)時(shí)間最小為目標(biāo)，將排班問題轉(zhuǎn)化為類TSP 問題，設(shè)計(jì)包含虛擬點(diǎn)的雙路徑表及蟻群算法，以提高乘務(wù)人員利用率和降低運(yùn)營企業(yè)人力成本。未來可在單線城市軌道乘務(wù)排班計(jì)劃編制基礎(chǔ)上，對乘務(wù)員人數(shù)最少、工作強(qiáng)度均衡等多目標(biāo)需求，乘務(wù)規(guī)則、運(yùn)營條件等不同環(huán)境下高效優(yōu)質(zhì)乘務(wù)排班計(jì)劃的編制進(jìn)行深入研究。