孔云峰

（河南大學(xué)黃河中下游地理信息技術(shù)教育部重點實驗室 河南 開封475000）

0 引 言

我國城市公共交通事業(yè)近年發(fā)展快速。①城市道路、公交專道、停車場、充電設(shè)施、公交站臺等基礎(chǔ)設(shè)施不斷完善；②運營公交車輛數(shù)量保持增長，車輛性能和舒適度得到明顯提升，且環(huán)保清潔的電動車輛占比越來越高；③公交信息化日益普及，大多數(shù)公交企業(yè)已建成信息化平臺，提供車輛與司機(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個過程：公交網(wǎng)絡(luò)設(shè)計、發(fā)車頻率設(shè)置、時刻表確定、車輛調(diào)度和司機(jī)排班等過程。K.Kepaptsoglou等[2]詳細(xì)地歸納了公交線網(wǎng)設(shè)計問題的模型定義、主要特征和求解方法。針對發(fā)達(dá)國家公交企業(yè)車輛與司機(jī)調(diào)度問題，R.Pine等[3]完成的專題報告及后續(xù)更新報告[4]提供了1套解決方案，基本步驟如下：①車輛調(diào)度（blocking）：根據(jù)公交班次任務(wù)進(jìn)行車輛調(diào)度，最小化車輛數(shù)量及行駛成本，形成若干班次鏈（block）；②司機(jī)調(diào)度（runcutting）：劃分班次鏈為若干任務(wù)段，分段點作為潛在的司機(jī)交接班時間和地點；根據(jù)司機(jī)工作時間、休息、就餐、報酬制度等，為司機(jī)分派任務(wù)，目標(biāo)是降低所需司機(jī)數(shù)量和薪酬成本；③司機(jī)輪班（rostering）：根據(jù)司機(jī)休假時間規(guī)定，按月安排司機(jī)輪班工作和休息。其中，司機(jī)調(diào)度問題最為困難，原因在于任務(wù)段組合空間巨大，且司機(jī)工作規(guī)范及薪酬規(guī)定企業(yè)間差異很大。通常采用“生成與選擇”方法求解司機(jī)調(diào)度問題：生成是根據(jù)調(diào)度經(jīng)驗生成數(shù)以十萬計的班次鏈，選擇是求解1個覆蓋集問題模型，從候選班次鏈中選擇1個成本較低的方案。除了使用遺傳算法求解覆蓋集問題，學(xué)者也提出了其他優(yōu)化方法，如基于禁忌搜索與遺傳算法的混合元啟發(fā)算法［5］、貪婪隨機(jī)自適應(yīng)搜索（GRASP）算法［6］、列生成算法［7］等。另外，C.Valouxis等[8]提出使用混合算法進(jìn)行車輛與司機(jī)一體化調(diào)度。

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

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

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

1 問題定義

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

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

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

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

與班次鏈B k相關(guān)的成本如下：①車輛固定成本cbf，包括車輛的年折舊成本、維護(hù)費用和保險費用；②車輛運行成本f1(B k)，包括行駛成本、空駛懲罰成本、充電成本等。給定班次鏈B k，車輛行駛時間、空駛時間、充電時間和時長均已知，可通過定義單位成本計算運行成本：車輛每分鐘行駛成本cbd、車輛空駛每分鐘懲罰成本c be、電池充電1次折舊成本c ec及浮動電價c0，c1，…，c23（代表0時，1時，…，23時的電價）；③司機(jī)固定成本f2(B k)。為班次鏈B k分派司機(jī)，一般有4種可能：1名正常班司機(jī)、1名高峰班司機(jī)、1名長班司機(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è)對于司機(jī)的津貼政策可能差異很大，根據(jù)實際需要計算司機(jī)津貼成本。

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

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

2 算法設(shè)計

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

與基于單解的鄰域搜索算法相比，本文算法維護(hù)1組精英解。首先，算法步驟1生成1組初始解；其次，在每1次迭代搜索中，從群解中隨機(jī)選擇1個解進(jìn)行搜索（步驟2）進(jìn)行擾動（步驟3）和搜索（步驟4）；再次，搜索完成后，使用新解更新群解（步驟5）。群解更新時，優(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)前解不是局部最優(yōu)，下輪搜索中很容易被破壞，減少了到達(dá)局部最優(yōu)的機(jī)會。因此，VND搜索用于ILS算法，有利于提成算法求解質(zhì)量。

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

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

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

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

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

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

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

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

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

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

3 案例測試

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

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

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

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

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

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

實驗設(shè)計的主要參數(shù)如下：車輛固定成本cbf=200 000元，車輛每分鐘行駛成本cbd=1元，車輛空駛每分鐘懲罰成本cbe=1 000元；電動車輛電池有效電量G=150或120 kW·h、行駛平均每分鐘耗電g1=0.3 kW·h、每分鐘可充電g2=2.0 kW·h；電池1次充電折舊成本cec=30，浮動電價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；長班tdl1=10.5 h和tdl2=13 h；司機(jī)休息規(guī)定參數(shù)tlt=4 h和tlb=0.5 h，就餐時間t m=0.5 h。車輛或司機(jī)班次鏈中，2個連續(xù)任務(wù)的停車間隔不小于前1個任務(wù)時長的10%，即gap=10%。另外，要求車輛完成班次任務(wù)后，必須回到出發(fā)地。

本文算法使用Python語言編程實現(xiàn)，測試環(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)境中運行算法。

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

針對62條單線案例，進(jìn)行車輛與司機(jī)調(diào)度。每個案例設(shè)置調(diào)度場景如下：采用燃油車輛、配置150 kWh電池的電動車輛（“電動1”）和配置120 kWh電池的電動車輛（“電動2”），并分別按人車固定和人車分離模式進(jìn)行調(diào)度。這樣，每個案例獲得6個調(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è)計劃統(tǒng)計Tab.3 Scheduling results from the single-route instances

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

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

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

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

3.4 參數(shù)分析

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

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

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

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

3.5 計算時間

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

表7 案例計算時間Tab.7 Statistics of computing times on cases s

4 結(jié)束語

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

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

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

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