多目標(biāo)公交車輛與司機(jī)調(diào)度問(wèn)題元啟發(fā)算法設(shè)計(jì)*

孔云峰

（河南大學(xué)黃河中下游地理信息技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室 河南 開(kāi)封475000）

0 引 言

我國(guó)城市公共交通事業(yè)近年發(fā)展快速。①城市道路、公交專道、停車場(chǎng)、充電設(shè)施、公交站臺(tái)等基礎(chǔ)設(shè)施不斷完善；②運(yùn)營(yíng)公交車輛數(shù)量保持增長(zhǎng)，車輛性能和舒適度得到明顯提升，且環(huán)保清潔的電動(dòng)車輛占比越來(lái)越高；③公交信息化日益普及，大多數(shù)公交企業(yè)已建成信息化平臺(tái)，提供車輛與司機(jī)管理、車輛跟蹤、收銀結(jié)算、客戶服務(wù)等，部分城市建成目標(biāo)更高的智慧公交系統(tǒng)。整體上，城市公交服務(wù)水平得到明顯提升。

公交線網(wǎng)優(yōu)化是公交企業(yè)提升服務(wù)水平和生產(chǎn)效率的關(guān)鍵，也是智慧公交系統(tǒng)的核心功能。A.Ceder等[1]將公交線網(wǎng)優(yōu)化劃分為5個(gè)過(guò)程：公交網(wǎng)絡(luò)設(shè)計(jì)、發(fā)車頻率設(shè)置、時(shí)刻表確定、車輛調(diào)度和司機(jī)排班等過(guò)程。K.Kepaptsoglou等[2]詳細(xì)地歸納了公交線網(wǎng)設(shè)計(jì)問(wèn)題的模型定義、主要特征和求解方法。針對(duì)發(fā)達(dá)國(guó)家公交企業(yè)車輛與司機(jī)調(diào)度問(wèn)題，R.Pine等[3]完成的專題報(bào)告及后續(xù)更新報(bào)告[4]提供了1套解決方案，基本步驟如下：①車輛調(diào)度（blocking）：根據(jù)公交班次任務(wù)進(jìn)行車輛調(diào)度，最小化車輛數(shù)量及行駛成本，形成若干班次鏈（block）；②司機(jī)調(diào)度（runcutting）：劃分班次鏈為若干任務(wù)段，分段點(diǎn)作為潛在的司機(jī)交接班時(shí)間和地點(diǎn)；根據(jù)司機(jī)工作時(shí)間、休息、就餐、報(bào)酬制度等，為司機(jī)分派任務(wù)，目標(biāo)是降低所需司機(jī)數(shù)量和薪酬成本；③司機(jī)輪班（rostering）：根據(jù)司機(jī)休假時(shí)間規(guī)定，按月安排司機(jī)輪班工作和休息。其中，司機(jī)調(diào)度問(wèn)題最為困難，原因在于任務(wù)段組合空間巨大，且司機(jī)工作規(guī)范及薪酬規(guī)定企業(yè)間差異很大。通常采用“生成與選擇”方法求解司機(jī)調(diào)度問(wèn)題：生成是根據(jù)調(diào)度經(jīng)驗(yàn)生成數(shù)以十萬(wàn)計(jì)的班次鏈，選擇是求解1個(gè)覆蓋集問(wèn)題模型，從候選班次鏈中選擇1個(gè)成本較低的方案。除了使用遺傳算法求解覆蓋集問(wèn)題，學(xué)者也提出了其他優(yōu)化方法，如基于禁忌搜索與遺傳算法的混合元啟發(fā)算法［5］、貪婪隨機(jī)自適應(yīng)搜索（GRASP）算法［6］、列生成算法［7］等。另外，C.Valouxis等[8]提出使用混合算法進(jìn)行車輛與司機(jī)一體化調(diào)度。

我國(guó)學(xué)者也開(kāi)展了多樣化的研究。針對(duì)公交車輛調(diào)度問(wèn)題，魏明等［9］針對(duì)跨線車輛調(diào)度問(wèn)題，以車輛數(shù)量、車輛等待和空駛時(shí)間最少為目標(biāo)，考慮車場(chǎng)容量、車輛加油等因素，設(shè)計(jì)了蟻群算法，并使用5條線路上238個(gè)公交班次對(duì)算法進(jìn)行了驗(yàn)證；李一凡等［10］構(gòu)建了多車場(chǎng)多車型公交車調(diào)度問(wèn)題的線性規(guī)劃模型，使用Gurobi優(yōu)化器求解，并討論了電動(dòng)車輛使用成本的變化對(duì)公交運(yùn)營(yíng)總成本的影響；姚恩建等［11］針對(duì)電動(dòng)車輛跨線調(diào)度問(wèn)題，設(shè)計(jì)遺傳算法進(jìn)行求解，并以北京市大興區(qū)4條公交線路進(jìn)行算法驗(yàn)證；滕靖等［12］采用粒子群算法求解單條線路上純電動(dòng)公交車輛運(yùn)營(yíng)時(shí)刻表設(shè)計(jì)和車輛調(diào)度問(wèn)題，在上海市的1條公交線路驗(yàn)證了算法的可用性；唐春艷等［13］設(shè)計(jì)遺傳算法求解電動(dòng)公交車輛調(diào)度問(wèn)題，在靈活調(diào)整發(fā)車時(shí)間的前提下減少所需車輛數(shù)量，提升車輛利用率。

針對(duì)司機(jī)調(diào)度問(wèn)題，劉濤［14］系統(tǒng)地研究了公交司機(jī)排班問(wèn)題的模型，比較了3種算法的求解性能；陳明明等［15］以最小化乘務(wù)組成本、停留等待成本和空駛成本為目標(biāo)，采用禁忌搜索算法優(yōu)化多車場(chǎng)公交乘務(wù)排班問(wèn)題；陳程［16］探討了兼顧車輛和司機(jī)的多目標(biāo)公交車輛調(diào)度優(yōu)化算法，力圖找到Pareto最優(yōu)集；陳明明［17］針對(duì)多種公交管理模式系統(tǒng)地討論了相關(guān)的問(wèn)題模型和算法；侯彥娥等［18］針對(duì)人車固定管理模式，提出混合元啟發(fā)算法求解車輛調(diào)度與司機(jī)排班問(wèn)題，通過(guò)13個(gè)案例測(cè)試驗(yàn)證了算法的有效性。

國(guó)內(nèi)外學(xué)者長(zhǎng)期關(guān)注城市公交線網(wǎng)優(yōu)化與運(yùn)營(yíng)管理，但針對(duì)我國(guó)城市公交管理模式的算法研究仍充滿挑戰(zhàn)：①我國(guó)公交企業(yè)通常采用單條線路且人車固定的運(yùn)營(yíng)管理模式，導(dǎo)致國(guó)際上按車輛調(diào)度、司機(jī)排班和司機(jī)輪班順序進(jìn)行作業(yè)規(guī)劃的方法難以直接使用；②面向國(guó)內(nèi)公交企業(yè)的車輛調(diào)度與司機(jī)排班問(wèn)題研究存在若干局限，如問(wèn)題定義過(guò)于簡(jiǎn)化導(dǎo)致算法適用性差，車輛調(diào)度未考慮司機(jī)排班，算法功能單一，測(cè)試案例偏少且案例規(guī)模偏小等，難以為公交企業(yè)提供1套較為完整的解決方案。基于此，筆者設(shè)計(jì)了1個(gè)混合元啟發(fā)算法，用于求解多個(gè)公交車輛與司機(jī)調(diào)度問(wèn)題，支持燃油車輛或電動(dòng)車輛、單線或跨線、人車國(guó)定或人車分離模式的調(diào)度模式。使用62個(gè)單線案例和11個(gè)跨線案例，從多個(gè)角度測(cè)試算法的功能和性能，力圖為公交企業(yè)提供1個(gè)功能齊全、性能優(yōu)良、靈活通用的生產(chǎn)作業(yè)計(jì)劃編制工具。

1 問(wèn)題定義

令集合R={r1，r2，…，rm}、V={v1，v2，…，v n}、D={d1，d2，…，d p}和S={s1，s2，…，s q}分別表示m條公交線路、n個(gè)班次任務(wù)、p個(gè)停車場(chǎng)q個(gè)公交線路起訖點(diǎn)。每條公交線路上具有若干班次的公交任務(wù)，任務(wù)vi具有以下屬性：線路編號(hào)、起點(diǎn)站、終點(diǎn)站、起始時(shí)間和結(jié)束時(shí)間。令t ij表示車輛從站點(diǎn)i空駛到站點(diǎn)j的時(shí)間（i，j∈D∪S）。

令班次鏈B k={d k，v k1，v k2，…，v ku，d k}，表示公交車輛k從車場(chǎng)d k（d k∈D）出發(fā)，依次完成u個(gè)公交任務(wù)，最終回到出發(fā)車場(chǎng)。當(dāng)司機(jī)固定駕駛某1輛車（人車固定）時(shí)，可按司機(jī)工作要求為B k配置1～2名司機(jī)。當(dāng)允許司機(jī)換駕車輛（人車分離）時(shí)，先進(jìn)行車輛調(diào)度，再進(jìn)行司機(jī)調(diào)度。車輛運(yùn)行線路和司機(jī)駕駛?cè)蝿?wù)均使用班次鏈表達(dá)。

班次鏈B k的可行性定義如下：①針對(duì)車輛行駛，2個(gè)連續(xù)任務(wù)之間的時(shí)間間隔需大于某1個(gè)預(yù)先給定的數(shù)值，如前1個(gè)任務(wù)運(yùn)行時(shí)間的百分比10%。該值設(shè)置較大時(shí)，車輛在公交線路起訖點(diǎn)的等待時(shí)間偏長(zhǎng)，可能導(dǎo)致需要較多的車輛；反之，需要較少的車輛，但當(dāng)某1輛車出現(xiàn)晚點(diǎn)時(shí)，將影響后續(xù)班次任務(wù)的執(zhí)行，也會(huì)導(dǎo)致司機(jī)休息時(shí)間得不到保證；②當(dāng)車輛為電動(dòng)車輛時(shí)，假設(shè)車輛在夜間完成充電，在運(yùn)行過(guò)程中，可能需要在合適的時(shí)間和地點(diǎn)進(jìn)行快速充電；③針對(duì)司機(jī)調(diào)度，班次鏈B k需考慮司機(jī)休息和就餐，例如，司機(jī)連續(xù)駕駛超過(guò)4 h，必須休息0.5 h以上；在規(guī)定的就餐時(shí)間段內(nèi)，必須有0.5 h以上的就餐時(shí)間。

定義如下班次鏈參數(shù)：2個(gè)相鄰班次的時(shí)間間隔為前1個(gè)任務(wù)時(shí)間的某一百分比gap，是車輛到站后執(zhí)行下1個(gè)任務(wù)的等待時(shí)間，用于司機(jī)休息或交接班；司機(jī)連續(xù)駕駛超過(guò)t ltmin必須休息至少t lbmin；司機(jī)在11∶00—13∶00和17∶00—20∶00之間必須提供至少t mmin就餐時(shí)間；針對(duì)電動(dòng)車輛，給定電池有效電量G，kW·h、平均每分鐘耗電g1，kW·h、每分鐘可充電g2，kW·h，用于判斷電池是否需要充電、是否能夠充電及充電時(shí)長(zhǎng)。基于這些參數(shù)判斷班次鏈的可行性。

與班次鏈B k相關(guān)的成本如下：①車輛固定成本cbf，包括車輛的年折舊成本、維護(hù)費(fèi)用和保險(xiǎn)費(fèi)用；②車輛運(yùn)行成本f1(B k)，包括行駛成本、空駛懲罰成本、充電成本等。給定班次鏈B k，車輛行駛時(shí)間、空駛時(shí)間、充電時(shí)間和時(shí)長(zhǎng)均已知，可通過(guò)定義單位成本計(jì)算運(yùn)行成本：車輛每分鐘行駛成本cbd、車輛空駛每分鐘懲罰成本c be、電池充電1次折舊成本c ec及浮動(dòng)電價(jià)c0，c1，…，c23（代表0時(shí)，1時(shí)，…，23時(shí)的電價(jià)）；③司機(jī)固定成本f2(B k)。為班次鏈B k分派司機(jī)，一般有4種可能：1名正常班司機(jī)、1名高峰班司機(jī)、1名長(zhǎng)班司機(jī)或2名正常班司機(jī)?？紤]司機(jī)輪班作業(yè)，該班次鏈B k所需司機(jī)數(shù)量分別約為1.4，1.5，2.0和2.8。定義司機(jī)固定成本為c df，4種司機(jī)配置方式的司機(jī)固定成本分別為1.4c df，1.5cdf，2.0cdf和2.8cdf；④司機(jī)津貼成本f3(B k)，如加班津貼、異地收工津貼、換車懲罰等。企業(yè)對(duì)于司機(jī)的津貼政策可能差異很大，根據(jù)實(shí)際需要計(jì)算司機(jī)津貼成本。

基于以上成本定義，構(gòu)造多成本目標(biāo)函數(shù)。對(duì)于“人車固定”問(wèn)題，采用班次鏈集合B={B1，B2，…，B K}表示該案例的1個(gè)解。其目標(biāo)函數(shù)為：f(B)=∑b∈B(cbf+f1(b)+f2(b)+f3(b))。對(duì)于“人車分離”問(wèn)題，先求解車輛行駛班次鏈B'，再求解司機(jī)班次鏈B''，其目標(biāo)函數(shù)分別為f(B')=∑b∈B'(cbf+f1(b))和f(B'')=∑b∈B''(f2(b)+f3(b))。若班次鏈不滿足約束條件，賦予其足夠大的成本，阻止非可行班次鏈的出現(xiàn)。

根據(jù)實(shí)際需要，定義司機(jī)工作班制：正常班、高峰班和長(zhǎng)班。①正常班司機(jī)駕駛車輛時(shí)間小于t dn1且上下班時(shí)間間隔小于t dn2，如分別取值為7.5，10 h；②高峰班司機(jī)駕駛車輛時(shí)間小于t dp1，上下班時(shí)間間隔小于t dp2，且高峰間休息時(shí)間大于t dp3，如三者取值分別為7.5，13，3 h；③長(zhǎng)班司機(jī)駕駛車輛時(shí)間小于t dl1，且上下班時(shí)間間隔小于t dl2，如分別取值為10.5，13 h。

2 算法設(shè)計(jì)

筆者基于迭代局部搜索（ILS）設(shè)計(jì)了1個(gè)混合元啟發(fā)算法求解車輛調(diào)度與司機(jī)排班問(wèn)題。ILS算法從1個(gè)初始解開(kāi)始，迭代地進(jìn)行擾動(dòng)和局部搜索。局部搜索能夠不斷地改進(jìn)當(dāng)前解，但容易陷入局部最優(yōu)；對(duì)當(dāng)前解的擾動(dòng)能夠使算法脫離局部最優(yōu)，進(jìn)而提升搜索性能。為進(jìn)一步提升ILS算法性能，對(duì)其進(jìn)行2個(gè)方面的擴(kuò)展：群解搜索和變鄰域下降（VND）搜索。給定參數(shù)群大?。╬size）和連續(xù)未更新最好解循環(huán)數(shù)（mloops），算法流程步驟見(jiàn)圖1。

與基于單解的鄰域搜索算法相比，本文算法維護(hù)1組精英解。首先，算法步驟1生成1組初始解；其次，在每1次迭代搜索中，從群解中隨機(jī)選擇1個(gè)解進(jìn)行搜索（步驟2）進(jìn)行擾動(dòng)（步驟3）和搜索（步驟4）；再次，搜索完成后，使用新解更新群解（步驟5）。群解更新時(shí)，優(yōu)先考慮解的目標(biāo)值，其次考慮解的差異程度，保持解之間有一定的差異。維護(hù)1組具有差異度的精英解，能夠擴(kuò)大解空間搜索范圍，有利于改進(jìn)求解質(zhì)量。最后，由步驟6判斷連續(xù)未更新最好解循環(huán)次數(shù)是否達(dá)到閾值（mloops），若是則算法終止，否則繼續(xù)搜索。

ILS中使用VND搜索能夠使每輪搜索達(dá)到局部最優(yōu)。VND方法反復(fù)使用鄰域搜索算子進(jìn)行搜索，直到所有算子均不能提升當(dāng)前解，獲得局部最優(yōu)解。ILS中頻繁使用擾動(dòng)方法，若當(dāng)前解不是局部最優(yōu)，下輪搜索中很容易被破壞，減少了到達(dá)局部最優(yōu)的機(jī)會(huì)。因此，VND搜索用于ILS算法，有利于提成算法求解質(zhì)量。

算法中，步驟1使用車輛調(diào)度問(wèn)題（VSP）模型產(chǎn)生初始解。車輛調(diào)度要求：所有任務(wù)必須被執(zhí)行、車輛在任務(wù)間等待時(shí)間滿足參數(shù)Gap要求；調(diào)度目標(biāo)是車輛固定成本和運(yùn)行成本最低。實(shí)驗(yàn)表明，商用CPLEX優(yōu)化器（https：//www.ibm.com/analytics/cplex-optimizer）或開(kāi)源CBC優(yōu)化器（https：//coin-or.Github.io/cbc/）均能夠高效地求解VSP模型。對(duì)于人車分離模式，VSP模型求解結(jié)果即可用于車輛調(diào)度。此時(shí)，車輛班次鏈通常不滿足司機(jī)休息和就餐時(shí)間規(guī)定，可將其分拆，直到滿足要求為止。分拆后的班次鏈集合作為后續(xù)問(wèn)題的初始解。

班次鏈操作采用4種方式［18］：①單班次移動(dòng)，即將1個(gè)班次鏈中的某個(gè)班次刪除，插入到另1個(gè)班次鏈中；②雙班次移動(dòng)，即將1個(gè)班次鏈中2個(gè)相鄰的班次刪除，插入到另外1個(gè)班次鏈中；③班次鏈交叉，即將2個(gè)班次鏈分別從某個(gè)位置截?cái)?，然后再將斷開(kāi)的班次鏈進(jìn)行交叉組合；④班次鏈合并，即將2個(gè)班次鏈合并生成1個(gè)新的班次鏈。以上操作用于步驟4的搜索改進(jìn)，其中，班次鏈交叉用于步驟3的擾動(dòng)操作。

針對(duì)不同的調(diào)度模式，采用不同的成本目標(biāo)函數(shù)。人車分離模式，分別使用司機(jī)固定成本和司機(jī)津貼成本。而人車固定模式，使用車輛和司機(jī)總成本。

基于以上算法原理，筆者實(shí)現(xiàn)了1個(gè)通用算法，滿足單條線路或多條線路、燃油車輛或電動(dòng)車輛、人車固定或人車分離等情形下的問(wèn)題求解?；灸K如下。

1）基礎(chǔ)數(shù)據(jù)管理模塊。管理公交車場(chǎng)、線路、首尾車站、班次任務(wù)時(shí)刻表、站點(diǎn)/站場(chǎng)間距離和空駛時(shí)間等基礎(chǔ)信息。

2）問(wèn)題定義模塊。使用配置文件，設(shè)置問(wèn)題類型和參數(shù)。問(wèn)題類型包括：燃油車輛人車固定作業(yè)、電動(dòng)車輛人車固定作業(yè)、燃油車輛人車分離作業(yè)和電動(dòng)車輛人車分離作業(yè)。問(wèn)題參數(shù)較多，包括車輛相關(guān)成本、司機(jī)相關(guān)成本、司機(jī)班制定義、司機(jī)休息及就餐時(shí)間規(guī)定等。

3）班次鏈評(píng)價(jià)模塊。將問(wèn)題解表達(dá)為班次鏈集合，針對(duì)每個(gè)班次鏈，進(jìn)行可行性判斷操作，包括班次間隔時(shí)間可行性判斷，電動(dòng)車輛是否需要充電判斷，電動(dòng)車輛需要充電時(shí)是否有合適的地點(diǎn)和時(shí)段進(jìn)行充電，司機(jī)就餐可行性判斷，司機(jī)休息可行性判斷等。第二類操作包括各類成本的計(jì)算，重點(diǎn)是根據(jù)班次鏈匹配最優(yōu)司機(jī)班制，按成本順序依次判斷該班次鏈?zhǔn)欠駶M足1名正常班司機(jī)、1名高峰班司機(jī)、1名長(zhǎng)班司機(jī)或2名正常班司機(jī)。

4）初始解構(gòu)造。依據(jù)車輛運(yùn)行時(shí)間間隔設(shè)置要求，構(gòu)造車輛調(diào)度問(wèn)題模型，求解模型獲得若干車輛班次鏈。若某個(gè)班次鏈不滿足司機(jī)休息及就餐要求，將該班次鏈分拆，直到班次鏈具有可行性。

5）班次鏈搜索算子。包括單班次移動(dòng)、雙班次移動(dòng)、班次鏈交叉、班次鏈合并、班次鏈拆分等班次鏈調(diào)整算子，循環(huán)調(diào)用算子改進(jìn)車輛調(diào)度和司機(jī)排班方案。

6）參數(shù)設(shè)置模塊。提供算法參數(shù)，如解群規(guī)模、計(jì)算時(shí)間限制、目標(biāo)值未改進(jìn)的連續(xù)循環(huán)次數(shù)等。

3 案例測(cè)試

3.1 案例數(shù)據(jù)及作業(yè)參數(shù)設(shè)置

筆者收集了62條公交線路數(shù)據(jù)對(duì)本文算法進(jìn)行測(cè)試。數(shù)據(jù)來(lái)源于3個(gè)大型城市H、G和Z，多是城市干線公交線路，均為雙向發(fā)車；線路長(zhǎng)度處于8.9～60.4 km之間，平均26.1 km；線路班次行駛時(shí)間處于25.8～145.3 min，平均83.0 min，詳細(xì)情況見(jiàn)表1。表1中，單程時(shí)間為所有班次的平均運(yùn)行時(shí)間。大部分案例中，線路起點(diǎn)和終點(diǎn)均設(shè)置停車場(chǎng)；個(gè)別案例中，停車場(chǎng)與線路起點(diǎn)或終點(diǎn)間需要5～10 min的行駛時(shí)間。

表1 單線案例基本特征Tab.1 Main features of the single-route instances

為測(cè)試跨線作業(yè)，設(shè)計(jì)了11條跨線案例，見(jiàn)表2。設(shè)計(jì)方法如下：在1個(gè)城市選擇2～4條公交線路，假定其上行方向的起點(diǎn)站相同，作為樞紐站點(diǎn)進(jìn)行跨線調(diào)度。

表2 跨線案例基本特征Tab.2 Main features of the multi-route instances

使用以上案例，進(jìn)行車輛與司機(jī)調(diào)度實(shí)驗(yàn)。每個(gè)案例數(shù)據(jù)對(duì)應(yīng)4個(gè)問(wèn)題類型：①燃油車輛人車固定作業(yè)；②電動(dòng)車輛人車固定作業(yè)；③燃油車輛人車分離作業(yè)；④電動(dòng)車輛人車分離作業(yè)。針對(duì)電動(dòng)車輛，選擇2種車型，電池有效容量分別為150，120 kW·h。應(yīng)當(dāng)注意，電動(dòng)汽車耗電情況較為復(fù)雜，將充電、耗電模型簡(jiǎn)化為線性函數(shù)，未考慮地形、車輛載重、行駛速度變化、環(huán)境溫度、電池衰減等因素。實(shí)際應(yīng)用中，應(yīng)根據(jù)電池理論性能和作業(yè)監(jiān)測(cè)數(shù)據(jù)建立更精細(xì)的能耗模型。

實(shí)驗(yàn)設(shè)計(jì)的主要參數(shù)如下：車輛固定成本cbf=200 000元，車輛每分鐘行駛成本cbd=1元，車輛空駛每分鐘懲罰成本cbe=1 000元；電動(dòng)車輛電池有效電量G=150或120 kW·h、行駛平均每分鐘耗電g1=0.3 kW·h、每分鐘可充電g2=2.0 kW·h；電池1次充電折舊成本cec=30，浮動(dòng)電價(jià)c0，c1，…，c23處于0.5～1.0元之間。司機(jī)固定成本c df=100 000元；司機(jī)班制規(guī)定如下：正常班t dn1=7.5 h，t dn2=10 h；高峰班tdp1=7.5 h，tdp2=14 h和tdp3=3 h；長(zhǎng)班tdl1=10.5 h和tdl2=13 h；司機(jī)休息規(guī)定參數(shù)tlt=4 h和tlb=0.5 h，就餐時(shí)間t m=0.5 h。車輛或司機(jī)班次鏈中，2個(gè)連續(xù)任務(wù)的停車間隔不小于前1個(gè)任務(wù)時(shí)長(zhǎng)的10%，即gap=10%。另外，要求車輛完成班次任務(wù)后，必須回到出發(fā)地。

本文算法使用Python語(yǔ)言編程實(shí)現(xiàn)，測(cè)試環(huán)境為PC機(jī)，配置Core i7-6 700 3.40GHz CPU、8G內(nèi)存、Windows10 64位操作系統(tǒng)。VSP模型采用CPLEX 12.6優(yōu)化器求解。為加快算法執(zhí)行速度，在PyPy（https：//www.pypy.org）環(huán)境中運(yùn)行算法。

3.2 單線調(diào)度結(jié)果

針對(duì)62條單線案例，進(jìn)行車輛與司機(jī)調(diào)度。每個(gè)案例設(shè)置調(diào)度場(chǎng)景如下：采用燃油車輛、配置150 kWh電池的電動(dòng)車輛（“電動(dòng)1”）和配置120 kWh電池的電動(dòng)車輛（“電動(dòng)2”），并分別按人車固定和人車分離模式進(jìn)行調(diào)度。這樣，每個(gè)案例獲得6個(gè)調(diào)度結(jié)果，調(diào)度結(jié)果滿足前節(jié)設(shè)置的參數(shù)約束。因數(shù)據(jù)量較大，表3按案例分組列出主要指標(biāo)，即每組案例所需車輛數(shù)量、單日所需司機(jī)數(shù)量、輪班所需司機(jī)數(shù)量及車輛空駛次數(shù)。根據(jù)司機(jī)數(shù)量和班制估算輪班司機(jī)數(shù)量，按照前述定義，司機(jī)數(shù)量出現(xiàn)了小數(shù)。

表3 單條線路作業(yè)計(jì)劃統(tǒng)計(jì)Tab.3 Scheduling results from the single-route instances

比較調(diào)度模式可以發(fā)現(xiàn)：①使用電動(dòng)車輛取代燃油車輛，人車固定模式下，大多數(shù)線路無(wú)需增加車輛，個(gè)別線路需增加1輛車，平均增加0.8%；而人車分離模式，平均增加0.3%較高性能車輛或0.7%較低性能車輛；所需司機(jī)數(shù)量，總體上無(wú)明顯變化；②與人車固定調(diào)度模式相比，人車分離調(diào)度能夠減少所需車輛3.8%，減少司機(jī)0.4%，減少空駛次數(shù)20.3%，但司機(jī)在1個(gè)工作日內(nèi)需要換車約2次；③針對(duì)燃油車輛人車固定模式，車輛日均行駛10.3 h,行程189.6 km，司機(jī)日均駕車6.7 h,行程123.6 km，表明車輛利用率較高，司機(jī)工作時(shí)間安排合理。

3.3 跨線調(diào)度結(jié)果

針對(duì)11個(gè)跨線案例進(jìn)行車輛與司機(jī)調(diào)度。每個(gè)案例設(shè)置調(diào)度場(chǎng)景如下：采用燃油車輛或電動(dòng)車輛，并分別按人車固定和人車分離模式進(jìn)行調(diào)度。表4為全部案例4種調(diào)度場(chǎng)景的主要結(jié)果，包括所需車輛數(shù)量、所需司機(jī)數(shù)量和車輛空駛次數(shù)，并與單線調(diào)度結(jié)果進(jìn)行比較。結(jié)果比較發(fā)現(xiàn)：①與單線調(diào)度相比，跨線調(diào)度減少車輛4.6%，減少司機(jī)2.4%，但平均增加1.5次空駛；同時(shí)，每車日均運(yùn)營(yíng)由201 km提升到211 km，司機(jī)日均駕車服務(wù)里程由123 km提升到126 km；②使用電動(dòng)車輛取代燃油車輛，人車固定模式需增加0～2輛車，平均增加1.6%，而人車分離不需增加車輛；③與人車固定調(diào)度模式相比，人車分離減少車輛2.6%，司機(jī)數(shù)量保持基本不變，空駛減少7.9%，但每個(gè)司機(jī)在1個(gè)工作日內(nèi)需要換車約2次?？傮w上，因長(zhǎng)短線路相協(xié)調(diào)，車輛調(diào)度更加靈活，能顯著地減少所需車輛；同樣，司機(jī)工作時(shí)間更為均衡，且容易為司機(jī)安排合理的休息和就餐時(shí)間?？缇€調(diào)度使調(diào)度規(guī)模大幅度增加，作業(yè)計(jì)劃編者更為困難，手工作業(yè)難以勝任，必須依靠性能良好的調(diào)度算法工具。

表4 跨線調(diào)度結(jié)果及與單線調(diào)度比較Tab.4 Scheduling results from the multi-route instances

3.4 參數(shù)分析

本文實(shí)現(xiàn)的算法不僅滿足多模式公交車輛與司機(jī)調(diào)度，而且支持公交運(yùn)營(yíng)參數(shù)的設(shè)置。為驗(yàn)證參數(shù)設(shè)置對(duì)調(diào)度結(jié)果的影響，選擇3個(gè)單線案例和1個(gè)跨線案例進(jìn)行測(cè)試。表5是改變車輛中停時(shí)間參數(shù)gap的計(jì)算結(jié)果，其他參數(shù)與前節(jié)案例測(cè)試相同，調(diào)度模式為燃油車輛人車固定。表中，車輛、司機(jī)和空駛分別表示所需車輛輛數(shù)、所需司機(jī)個(gè)數(shù)和車輛空駛次數(shù)。可以看出：隨gap增加，所需車輛數(shù)量增加，增加幅度顯著；隨gap增加，單日公交作業(yè)所需司機(jī)數(shù)量、空駛數(shù)量有一定的波動(dòng)。

表5 車輛中停時(shí)間（gap）對(duì)車輛調(diào)度的影響Tab.5 Effects of the waiting time(gap)for buses on scheduling results

進(jìn)一步測(cè)試司機(jī)班制設(shè)計(jì)對(duì)車輛與司機(jī)調(diào)度的影響。針對(duì)4個(gè)案例，設(shè)計(jì)5種班制，除司機(jī)班制定義外，其他參數(shù)與前節(jié)案例測(cè)試相同，調(diào)度模式為燃油車輛人車固定。計(jì)算結(jié)果見(jiàn)表6?？梢钥闯觯核柢囕v與司機(jī)數(shù)量受司機(jī)班制影響較大，但對(duì)于不同的案例，其影響差異較大。針對(duì)案例sh01，因其雙峰特征突出，不允許高峰班會(huì)使所需司機(jī)數(shù)量大幅增加；而對(duì)于案例sg07，szb12和szmr04，不允許長(zhǎng)班會(huì)使所需司機(jī)數(shù)量大幅增加。對(duì)于案例szb12，因單班次任務(wù)時(shí)間為80 m，正常班時(shí)間為7.5 h或長(zhǎng)班時(shí)間限制在10.5 h，難以提高司機(jī)的工作效率。綜上，司機(jī)工作班制設(shè)計(jì)對(duì)于公交司機(jī)調(diào)度影響顯著。一方面需要高峰班和長(zhǎng)班減少所需司機(jī)數(shù)量；另一方面，需要根據(jù)線路特征適當(dāng)修改工作時(shí)長(zhǎng)參數(shù)，有利于合理地為司機(jī)分派任務(wù)。

表6 司機(jī)班制設(shè)計(jì)對(duì)公交作業(yè)的影響Tab.6 Effects of the design of drivers'working shifts on scheduling results

3.5 計(jì)算時(shí)間

本文案例測(cè)試時(shí)間統(tǒng)計(jì)見(jiàn)表7。表7中給出了6個(gè)單線調(diào)度案例組中每個(gè)案例的平均計(jì)算時(shí)間，11個(gè)跨線調(diào)度案例的計(jì)算時(shí)間。可以看出，計(jì)算時(shí)間與案例規(guī)模相關(guān)，也受線路長(zhǎng)度、服務(wù)時(shí)長(zhǎng)、所需車輛和司機(jī)數(shù)量的影響。對(duì)于相同的案例數(shù)據(jù)，使用電動(dòng)車輛比使用燃油車輛計(jì)算時(shí)間大幅增加，因需要檢測(cè)電池續(xù)航能力，并設(shè)置充電時(shí)間和地點(diǎn)。對(duì)于跨線調(diào)度案例，計(jì)算時(shí)間大幅增加，因部分搜索算子計(jì)算復(fù)雜度為O（n2），隨案例規(guī)模增大，所需計(jì)算時(shí)間大幅增加?？紤]到公交作業(yè)計(jì)劃編制不是日常性工作，本文算法計(jì)算時(shí)間可以接受。

表7 案例計(jì)算時(shí)間Tab.7 Statistics of computing times on cases s

4 結(jié)束語(yǔ)

筆者設(shè)計(jì)了1個(gè)公交車輛與司機(jī)調(diào)度問(wèn)題的元啟發(fā)算法。算法顧及車輛停車時(shí)間、電池充電、司機(jī)休息與就餐等約束條件，優(yōu)化目標(biāo)包括車輛固定成本、車輛行駛成本、司機(jī)固定成本和司機(jī)津貼成本。算法首先生成初始解、再迭代使用班次鏈算子改進(jìn)當(dāng)前解，并通過(guò)群解、擾動(dòng)和可變鄰域下降等策略改進(jìn)解的質(zhì)量。算法支持燃油車輛或電動(dòng)車輛調(diào)度，適用于單線或跨線運(yùn)營(yíng)管理，滿足人車固定或人車分離模式的作業(yè)計(jì)劃編制，也支持靈活的問(wèn)題參數(shù)設(shè)置和算法參數(shù)設(shè)置，具有良好的通用性。

本文使用62個(gè)單線案例和11個(gè)跨線案例進(jìn)行算法測(cè)試，并比較了不同運(yùn)營(yíng)模式下生產(chǎn)作業(yè)方案的差異。測(cè)試結(jié)果驗(yàn)證了算法的功能和性能，單線案例平均計(jì)算時(shí)間為163 s，跨線案例平均為936 s，運(yùn)行時(shí)間可以接受。針對(duì)車輛與司機(jī)調(diào)度模式比較發(fā)現(xiàn)：案例中大多數(shù)公交線路能夠以1∶1的比例使用電動(dòng)車輛取代燃油車輛；部分公交線路采用跨線運(yùn)營(yíng)后，車輛和司機(jī)效率提高顯著；車輛執(zhí)行任務(wù)間隔時(shí)間設(shè)置對(duì)于車輛利用率影響顯著；工作班制設(shè)計(jì)對(duì)于公交司機(jī)調(diào)度影響顯著，多班制組合及根據(jù)線路特征設(shè)置班制參數(shù)，有利于提升司機(jī)工作效率；與人車固定模式相比，人車分離運(yùn)營(yíng)能提升車輛和司機(jī)的效率，但司機(jī)日均2次的換車作業(yè)增加了管理難度。

與國(guó)際公交車輛與司機(jī)調(diào)度算法相比，本文算法支持人車固定調(diào)度模式，滿足國(guó)內(nèi)公交企業(yè)的現(xiàn)實(shí)需求。與國(guó)內(nèi)研究相比，本文算法具有明顯的優(yōu)勢(shì)：充分考慮車輛和司機(jī)相關(guān)的成本；支持多種調(diào)度模式，具有通用性；案例測(cè)試充分，特別是測(cè)試了大規(guī)模跨線調(diào)度案例，驗(yàn)證了算法的性能。另外，案例測(cè)試結(jié)果對(duì)于國(guó)內(nèi)公交企業(yè)運(yùn)營(yíng)決策具有借鑒價(jià)值。

本文提出的公交車輛與司機(jī)調(diào)度問(wèn)題的通用算法尚需進(jìn)一步發(fā)展：①針對(duì)人車分離模式，司機(jī)換車次數(shù)偏多，因此有必要在算法中增加司機(jī)換車次數(shù)約束及相關(guān)的搜索策略；②算法的計(jì)算效率有待進(jìn)一步提高，特別是針對(duì)跨線調(diào)度運(yùn)營(yíng)模式；③本文算法應(yīng)當(dāng)在應(yīng)用中進(jìn)一步發(fā)展和改進(jìn)。