公交司機排班問題的混合元啟發(fā)算法研究

侯彥娥，孔云峰，朱艷芳，馬 瑞

(河南大學(xué)a.計算機與信息工程學(xué)院；b.黃河中下游數(shù)字地理技術(shù)教育部重點實驗室，河南開封475004)

0 引言

公共交通在城市交通體系中占據(jù)重要的地位.大力發(fā)展公共交通不僅能夠減少交通擁堵，而且還能提倡人們綠色出行減少大氣污染.公交車輛調(diào)度與司機排班是公交企業(yè)編制生產(chǎn)作業(yè)計劃的基礎(chǔ)，也是公交企業(yè)運營管理中的一個重要環(huán)節(jié).良好的生產(chǎn)作業(yè)計劃不僅能夠減少公交線路所需公交車的數(shù)量，還能在滿足國家相關(guān)政策法規(guī)的條件下達到企業(yè)和司機各方面的需求，為安全和高效的公交運營提供保障.因此，研究公交車輛調(diào)度和司機排班問題具有現(xiàn)實意義.

針對公交車調(diào)度和司機排班問題，國內(nèi)外學(xué)者展開了深入的研究.國外學(xué)者針對此類問題的研究相對比較成熟[1-4].針對此類問題，有些文獻[5-7]將問題分成車輛調(diào)度和司機排班2個子問題分階段求解，先基于線路時刻表完成車輛調(diào)度，再進行司機任務(wù)分配，最后編制司機輪班計劃作業(yè).文獻[8-9]同時考慮車輛調(diào)度和司機排班，力求獲得更優(yōu)的公交作業(yè)方案.然而，國外現(xiàn)有的解決方案和算法難以適應(yīng)于我國的車輛調(diào)度和司機排班問題.其原因在于：國外公交企業(yè)中司機和車輛關(guān)系不固定，1個司機在1天內(nèi)可以駕駛多個車輛；而國內(nèi)的公交企業(yè)通常采用“人車綁定”模式，即1位司機在同一個工作日內(nèi)駕駛同一輛車.

國內(nèi)學(xué)者也展開多樣化的研究[10-16].王鵬飛[10]和陳程[11]設(shè)計遺傳算法求解車輛調(diào)度和司機排班問題.陳明明等[12]設(shè)計了一種禁忌算法求解多車場公交乘務(wù)排班問題；魏金麗[13]、王森磊[14]等均采用生成與選擇方法優(yōu)選司機排班方案，劉濤[15]研究司機調(diào)度和輪班問題的元啟發(fā)算法；陳明明[16]針對多種公交管理模式系統(tǒng)地討論了相關(guān)的問題模型和算法.這些研究均表明使用優(yōu)化算法比人工排班具有一定的優(yōu)勢，但也存在一些不足：測試案例單一并且規(guī)模較小，難以驗證算法的優(yōu)化性能和通用性；多數(shù)研究并未兼顧車輛和司機的成本，不能反映實際應(yīng)用的需求.

本文針對國內(nèi)“人車綁定”模式下的公交司機排班問題進行研究，同時考慮車輛和司機的成本，設(shè)計1個迭代局部搜索算法(Iterated Local Search,ILS)和集合覆蓋模型(Set Cover Problem,SCP)混合的元啟發(fā)算法尋找最小車輛數(shù)和最少司機數(shù)量的排班方案，并驗證算法的有效性.

1 問題描述

本文研究“人車綁定”管理模式下的單條公交線路的司機排班問題，其實質(zhì)是同時兼顧車輛調(diào)度和司機排班2個問題.假設(shè)公交車可以停靠在某個車場(具有出發(fā)的起始車站或終點車站)且在起點或終點可以為司機提供就餐或車輛充電等服務(wù).1條公交線路上有若干個班次任務(wù)的集合，每個班次任務(wù)具有起始站點、終點站點、發(fā)車時間、結(jié)束時間、運行時間等屬性.1輛公交車從車場出發(fā)，依次執(zhí)行若干個班次任務(wù)，然后再回到車場.車場與若干個班次任務(wù)構(gòu)成的集合稱為1個班次鏈，所有班次鏈的集合構(gòu)成1條公交線路的作業(yè)方案.每個班次鏈表示車輛從車場出發(fā)，依次完成若干班次任務(wù)，再回到車場；每個班次鏈需要1輛公交車，1位或2位司機.每個班次鏈的成本由固定成本和日常成本2部分組成，其中車輛和司機數(shù)量屬于固定成本，車輛行駛里程和停留等待成本等屬于日常成本.目標(biāo)即通過安排合理的班次鏈組合，使公交作業(yè)方案的成本最低.每個班次鏈要滿足以下約束條件：1個班次任務(wù)完成后，車輛需停運若干時間保證司機的休息時間；在司機上班時間內(nèi)需要在合適的時間和地點就餐；同時根據(jù)司機的工作班制要求，司機工作時間不能超過規(guī)定的最長時間.

2 算法設(shè)計

2.1 算法總體設(shè)計

迭代局部搜索算法是一種基于鄰域搜索的元啟發(fā)算法，具有簡單有效、易于與其他算法混合等優(yōu)點.本文設(shè)計的混合元啟發(fā)算法在多啟動的ILS算法框架內(nèi)，從初始解出發(fā)，迭代地應(yīng)用局部搜索算子、破壞重建擾動進行解的改進，并記錄發(fā)現(xiàn)的可行班次鏈的集合；然后，根據(jù)記錄的班次鏈集合構(gòu)造SCP模型進行全局尋優(yōu).算法的基本流程如圖1所示.

由圖1可知，本文算法包含以下3部分：

(1)初始解構(gòu)造.

根據(jù)任務(wù)班次、司機班制及約束條件，建立以車輛數(shù)為目標(biāo)的車輛調(diào)度模型，得到僅滿足司機休息時間的非可行解.

(2)解的改進.

迭代地應(yīng)用單班次移動、雙班次移動、班次鏈交叉及合并等局部搜索算子對當(dāng)前解進行調(diào)整，嘗試將非可行解調(diào)整為可行解，并降低排班成本.同時，記錄搜索過程中發(fā)現(xiàn)的所有可行的班次鏈集合.局部搜索完成后，使用破壞重建的方法進行擾動.

(3)SCP模型全局尋優(yōu).

根據(jù)記錄的可行班次鏈集合，建立SCP模型并求解，選擇更優(yōu)的班次鏈組合.

圖1 算法流程圖Fig.1 Algorithm work flow diagram

2.2 初始解構(gòu)造

由于同時考慮車輛調(diào)度和司機排班2個問題，因此直接獲得問題的初始解非常困難.為此，本文先建立1個以車輛數(shù)最少為主要優(yōu)化目標(biāo)的車輛調(diào)度模型(Bus Scheduling Problem,BSP)，通過模型求解獲得1個僅滿足司機休息時間且車輛數(shù)最少的初始非可行解.該初始解可以在后續(xù)的局部搜索過程中逐漸調(diào)整為滿足司機排班要求的可行解.

令D={d1,d2,…,dl}、V={v1,v2,…,vn}分別表示停車場和所有班次的集合；ti為班次i的運行時間；tij為班次i與j的時間間隔；tmin為班次間的最小休息時間；Ni為班次i執(zhí)行完畢后可繼續(xù)執(zhí)行的班次任務(wù)集合，即Ni={j|j∈V,tij≥tmin}.由此，建立的車輛調(diào)度模型(BSP)為

式中：xki，xik和xij為決策變量，xki表示某輛車是否從停車場k出發(fā)去執(zhí)行班次i；xik表示某輛車完成班次i后是否回到停車場k；xij表示某輛車執(zhí)行班次i后是否接著執(zhí)行班次j.

目標(biāo)函數(shù)式(1)是最小化所需車輛數(shù)和司機休息時間，前者表示車輛數(shù)目，參數(shù)M是一個足夠大的正整數(shù)，M取值較大，能夠保證模型求解時車輛數(shù)最少；后者是車輛執(zhí)行班次任務(wù)間的休息時間，參數(shù)ε是一個很小的隨機擾動量，使模型多次求解結(jié)果有一定的差異.約束條件：式(2)要求每個班次j僅被某車輛訪問1次；式(3)要求某車輛完成班次j后必須去執(zhí)行下一個任務(wù)或回到停車場.

2.3 局部搜索

基于初始解提供的班次鏈集合，迭代地使用鄰域算子對其進行改進.改進過程中，將滿足司機的最少休息時間、最少就餐時間和班制的最長工作時間等約束的班次鏈集合認為是可行解，同時盡可能地降低排班的總成本.

本文設(shè)計了4種鄰域搜索算子在班次鏈間進行調(diào)整，定義如下：

(1)單班次移動.將1個班次鏈中的某個班次刪除，插入到另一個班次鏈中.

(2)雙班次移動.將1個班次鏈中2個相鄰的班次刪除，插入到另外一個班次鏈中.

(3)班次鏈交叉.將2個班次鏈分別從某個位置截斷，然后再將斷開的班次鏈進行交叉組合.

(4)班次鏈合并.將2個班次鏈合并生成1個新的班次鏈.

假設(shè)班次鏈b1和b2的表示形式為0-a-b-c-d-s和0-u-v-w-s，其中0和s表示出發(fā)和停止車場；這4種鄰域搜索算子的操作示意如表1所示.

表1 鄰域算子操作示意Table 1 Example of neighborhood operators

在局部搜索過程中，迭代地依次調(diào)用單班次移動、雙班次移動、班次鏈交叉和班次鏈合并這4種局部搜索算子.每個算子執(zhí)行過程中，優(yōu)先將不可行的班次鏈調(diào)整為可行的班次鏈，其次再調(diào)整班次鏈降低其成本.同時，記錄局部搜索過程中發(fā)現(xiàn)的所有可行班次鏈.

2.4 破壞重建擾動

為了避免局部搜索算法陷入局部最優(yōu)，通常在局部搜索算法中引入擾動機制.本文采用破壞重建的擾動方法，即對當(dāng)前局部最優(yōu)的班次鏈集合進行破壞而后再重建的方式，擴大搜索空間，嘗試發(fā)現(xiàn)更優(yōu)的班次鏈集合.本文設(shè)計2種破壞重建方法：①隨機選擇班次鏈集合中1個不可行的班次鏈，將其截斷為2個班次鏈，并保證這2個班次鏈都是可行的.這種方法需要增加1輛車生成1條新的班次鏈.②隨機選擇2個班次鏈的2個隨機位置將其截斷，而后再將截斷的班次鏈片段交叉重組得到2個新的班次鏈.這2種方法在擾動階段隨機選擇其中1種執(zhí)行.

2.5 SCP模型改進

局部搜索算法具有天生的“短視”局限，且搜索過程中僅記錄當(dāng)前最優(yōu)解.為充分利用算法所探索過的解空間，可采用集合覆蓋問題(SCP)模型從全局的角度選擇全局最優(yōu)解.基本思路是：根據(jù)局部搜索過程中所發(fā)現(xiàn)的可行班次鏈集合，從歷史班次鏈中尋找最優(yōu)的班次鏈組合.令集合Ω={b1,b2,…,bn}為局部搜索過程中發(fā)現(xiàn)的所有可行班次鏈集合，班次鏈bi滿足車輛調(diào)度和司機排班的約束條件，其成本為ci.定義決策變量xi，當(dāng)xi=1，表示班次鏈bi包含在問題的解中；否則，xi=0.由此，建立的SCP模型為

目標(biāo)函數(shù)式(5)用于選擇成本最低的班次鏈組合；約束條件式(6)保證班次集合中每一個班次均被所選擇的某個班次鏈覆蓋；約束式(7)限定了決策變量xi的取值.

根據(jù)建立的SCP模型，然后使用優(yōu)化工具求解該模型，并將模型求解的結(jié)果作為算法最終的全局最優(yōu)解.

3 實驗與分析

本文算法使用Python 2.7實現(xiàn)，測試環(huán)境為PC機，配置為core i7-6 700 3.40GHz，8G內(nèi)存、Windows 10、64位操作系統(tǒng).BSP模型和SCP模型采用PuLP模型工具創(chuàng)建，并使用CBC 2.9進行求解.BSP模型中，M=106,|ε|≤0.001；限定SCP模型求解時間不超過200 s.算法的參數(shù)設(shè)置如下：Mstart=10、Niter=1 500.算法使用排班參數(shù)判斷班次鏈?zhǔn)欠窨尚?，排班參?shù)及其取值為：司機最短休息時間為4 min(tmin=4)；司機最短就餐時間為30 min，且僅在上行出發(fā)站就餐；正常班制最長工作時間為8.5 h(510 min)；長班班制最長工作時間為11 h(tlong=660min).考慮到算法的隨機性，約定每個案例運行10次.

3.1 測試案例

測試案例選擇國內(nèi)某城市的13條公交線路的運行時刻表，均為雙向發(fā)車線路.案例的基本描述如表2所示.

3.2 實驗結(jié)果

針對每個案例，分別使用本文設(shè)計的算法(記做ILS-SCP)和去掉SCP模型改進的迭代局部搜索算法(ILS)進行求解.統(tǒng)計結(jié)果如表3所示，黑體部分表示ILS-SCP相對于ILS算法有所改進.

表2 測試案例基本描述Table 2 Description of benchmarks

表3 2種算法的運算結(jié)果比較Table 3 Comparison of the best solution obtained by two algorithms

由表3可知：應(yīng)用了SCP模型的ILS-SCP算法比ILS算法具有更好的尋優(yōu)能力.ILS-SCP算法的總車輛數(shù)和總司機數(shù)為219輛和327人，比ILS算法分別少了2輛車和2位司機；而在司機總的工作時間上，比ILS算法減少了1 890 min.由于車輛數(shù)和司機數(shù)量是排班方案中的主要優(yōu)化目標(biāo)，因此ILS-SCP算法能夠更好地降低司機排班的總成本.從執(zhí)行時間上來看，ILS-SCP算法因為增加了SCP模型，使得整體算法的運算時間有所增加.

為了驗證本文算法的有效性，將算法的排班結(jié)果和某公交企業(yè)的實際排班結(jié)果進行比較.由于實際排班方案中，大部分司機工作時間通常在12 h以上，因此將本文算法在最長工作時間為12 h時的排班方案與實際排班方案進行比較.統(tǒng)計結(jié)果如表4所示，其中NR、DR為實際車輛數(shù)和司機數(shù)，NA、DA為本算法規(guī)劃的結(jié)果.

由表4的結(jié)果可知，當(dāng)司機最長工作時間限定為12 h時，本文算法在13個案例上所需的總車輛數(shù)和總司機人數(shù)為219輛和319人，比實際方案的總車輛數(shù)和總司機數(shù)減少了0.9%和10.1%.當(dāng)司機最長工作時間降低到11 h時，本文算法排班的車輛數(shù)和司機數(shù)量為219輛和327人(表2)，仍然優(yōu)于實際的排班方案.與實際排班方案相比，本文所提算法在嚴(yán)格滿足司機休息時間和工作時長的約束下，能夠減少公交線路所需的車輛數(shù)和司機數(shù)，進而減輕司機的工作負擔(dān).

表4 算法排班與實際排班的結(jié)果比較Table 4 Comparison of two bus and drivers scheduling plans

4 結(jié)論

本文研究了人車綁定管理模式下的司機排班問題，同時考慮了車輛調(diào)度和司機排班的總成本，并設(shè)計迭代局部搜索和SCP模型混合的元啟發(fā)算法進行求解.實驗結(jié)果表明，混合SCP算法能夠在嚴(yán)格滿足司機休息時間、工作時間等約束下，在增加少量運算時間的基礎(chǔ)上提高算法的求解質(zhì)量；并且算法排班方案優(yōu)于實際排班方案.該算法將排班參數(shù)作為判定可行解的主要條件，通過設(shè)置合適的排班參數(shù)就能夠適應(yīng)實際企業(yè)靈活多樣的排班管理需求.由于本文算法僅考慮單條線路的司機排班問題，因此如何將本文算法擴展到求解跨線運營的公交司機排班問題將是下一步的研究方向.

[1]PINE NIEMEYER J,CHISHOLM R.Transit scheduling:basic and advanced manuals[M].Washington:Transportation Research Board,1998.

[2]CEDER A.Transit scheduling[J].Journal of Advanced Transportation,1991,25(2):137-160.

[3]GUIHAIRE V,HAO J.Transit network design and scheduling:A global review[J].Transportation Research Part A-Policy and Practice,2008,42(10):1251-1273.

[4]IBARRAROJAS O J,DELGADO F,GIESEN R,et al.Planning,operation and control of bus transport systems:A literature review[J].Transportation Research Part B-Methodological,2015,77(2015):38-75.

[5]LOURENCO H R,PAIXAO J M,PORTUGAL R,et al.Multiobjective metaheuristics for the bus driver scheduling problem[J].Transportation Science,2001,35(3):331-343.

[6]DE LEONE R,FESTA P,MARCHITTO E,et al.A bus driver scheduling problem:A new mathematical model and a GRASP approximate solution[J].Journal of Heuristics,2011,17(4):441-466.

[7]LIN D,HSU C.A column generation algorithm for the bus driver scheduling problem[J].Journal of Advanced Transportation,2016,50(8):1598-1615.

[8]MESQUITA M,MOZM,PAIAA,etal.A decomposition approach for the integrated vehicle-crew-roster problem with days-off pattern[J].European Journal of Operational Research,2013,229(2):318-331.

[9]VALOUXIS C,HOUSOS E.Combined bus and driver scheduling[J].Computers&Operations Research,2002,29(3):243-259.

[10]王鵬飛.智能公交車輛人員排班算法的研究與應(yīng)用[D].濟南:山東大學(xué),2006.[WANG P F.Research on intelligent bus driver scheduling problem optimization algorithm[D].Jinan:Shandong University,2006.]

[11]陳程.基于多目標(biāo)優(yōu)化算法的公交車輛調(diào)度研究[D].北京：北京郵電大學(xué),2014.[CHEN C.The research on vehicle scheduling problem based on multi-objective optimization algorithms[D].Beijing:Beijing University of Posts and Telecommunications,2014.]

[12]陳明明,?；菝?多車場公交乘務(wù)排班問題優(yōu)化[J].交通運輸系統(tǒng)工程與信息,2013,13(5):159-166.[CHEN M M,NIU H M.An optimization model for bus crew scheduling with multiple depots[C].Journal of Transportation Systems Engineering and Information Technology,2013,13(5):159-166.]

[13]魏金麗,郭亞娟,張萌萌.基于集合覆蓋理論的公交線路駕駛員排班優(yōu)化方法[J].公路交通科技,2016,33(1):125-129.[WEI J L,GUO Y J,ZHANG M M.A method of optimizing work schedule of bus drivers based on set covering theory[J].Journal of Highway and Transportation Research and Development,2016,33(1):125-129.]

[14]王森磊.基于生成與選擇模式的公交駕駛員排班問題研究[D].北京：北京交通大學(xué),2016.[WANG S L.The research on bus driver scheduling problem based on the pattern of generation and selection[D].Beijing:Beijing Jiaotong University,2016.]

[15]劉濤.公交駕駛員排班與輪班問題的模型與算法研究[D].北京:北京交通大學(xué),2013.[LIU T.Models and algorithms for bus driver run cutting and rostering[D].Beijing:Beijing Jiaotong University,2013.]

[16]陳明明.城市公共交通乘務(wù)調(diào)度優(yōu)化理論和方法[D].蘭州：蘭州交通大學(xué),2016.[CHEN M M.Theory and method for crew scheduling problem of urban public transport[D].Lanzhou:Lanzhou Jiaotong University,2016.]