基于TSP 問題思想的城市軌道交通乘務(wù)排班計劃研究

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

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

0 引言

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

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

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

1 問題分析

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

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

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

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

2 模型構(gòu)建

2.1 符號定義

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

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

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

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

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

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

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

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

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

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

圖3 就餐時間安排Fig.3 Dining time arrangement

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

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

3 求解算法

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

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

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

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

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

3.2 蟻群算法及流程

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

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

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

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

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

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

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

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

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

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

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

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

4 案例分析

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

表2 排班計劃時間標準參數(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è)段時長分布如圖6所示。切割運行圖后共得到248 個乘務(wù)作業(yè)段，平均作業(yè)段時長為85.7 min，最長時長為119.77 min，最短時長為46.98 min，符合最長時間與最短時間約束。

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

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

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

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

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

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

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

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

5 結(jié)束語

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