基于列生成啟發(fā)式的單線電動公交車與司機整合調(diào)度優(yōu)化

劉昊翔，吳啊峰，龍建成*,b，周玨

(合肥工業(yè)大學，a.汽車與交通工程學院；b.工業(yè)安全與應(yīng)急技術(shù)安徽省重點實驗室，合肥230009)

0 引言

隨著我國城市化水平的不斷提升和經(jīng)濟迅速發(fā)展，交通擁堵等城市問題隨之衍生。大力發(fā)展公共交通，對緩解交通擁堵有重要意義[1]。城市公交出行研究領(lǐng)域中，公交車調(diào)度問題和司機排班問題一直是公交系統(tǒng)運營過程中的熱點研究問題。如何科學、合理地安排車輛運營計劃和司機排班，對城市交通資源的優(yōu)化和公交企業(yè)的有效運營具有重要意義。

公交系統(tǒng)運營調(diào)度的優(yōu)化方法主要有順序調(diào)度模式和整合調(diào)度模式。順序調(diào)度模式是先進行車輛調(diào)度，生成車輛運營計劃，再基于車輛運用計劃進行司機排班計劃，順序調(diào)度模式下進行車輛調(diào)度時，不需要考慮司機的約束。而整合調(diào)度模式下，車輛調(diào)度問題和司機排班問題相互制約，需要同時生成車輛運用計劃和司機排班計劃。整合調(diào)度方法是將車輛調(diào)度問題和司機排班問題作為子問題，因此，傳統(tǒng)順序調(diào)度問題的研究方法為整合調(diào)度問題的研究提供了重要參考。FRELING 等[2]首次提出公交車和司機整合調(diào)度問題，并給出整合調(diào)度的原因。在模型的構(gòu)建方面主要有集合分割模型與網(wǎng)絡(luò)流模型結(jié)合[2-4]，優(yōu)化算法方面主要有基于拉格朗日松弛的列生成啟發(fā)式算法[2]、分支定價算法[3-4]等。HUISMAN 等[3]和STEINZEN 等[4]將整合調(diào)度模式分別運用于公交系統(tǒng)運營，并與傳統(tǒng)的順序調(diào)度模型進行對比，結(jié)果表明，整合調(diào)度方法能有效降低公司的運營成本。

電動公交車有零排放、噪聲小等優(yōu)點，為緩解交通環(huán)境污染問題，各地政府大力發(fā)展電動公交車。然而，由于電動車續(xù)駛里程短，需要充電才能完成更多的車次任務(wù)。電動公交車調(diào)度問題近年成為國內(nèi)外的熱點研究方向。唐春艷等[5]以最小化車輛數(shù)為目標，構(gòu)建電動公交車調(diào)度模型，并設(shè)計遺傳算法求解。LI[6]和楊揚等[7]設(shè)計基于列生成的方法求解電動公交車調(diào)度問題，對本文有重要的啟發(fā)。司機排班問題與車輛調(diào)度問題相似，關(guān)于司機排班問題的研究非常多，一般都是構(gòu)建集合分割或者集合覆蓋模型，并設(shè)計基于列生成的方法進行求解[8-9]。近年來，我國在公交司機排班問題上有很多優(yōu)秀的研究成果，陳明明等[10]設(shè)計禁忌搜索算法進行求解，侯彥娥[11]考慮“人車綁定”的管理模式，并設(shè)計混合元啟發(fā)式算法求解司機排班問題，與“人車綁定”的模式不同，本文允許車輛和司機在多條線路之間進行聯(lián)合調(diào)度，更加靈活，有利于減少司機和車輛的數(shù)量。

研究表明，傳統(tǒng)燃油公交車與司機整合調(diào)度能有效降低公交企業(yè)的運營成本。近年來，電動公交車發(fā)展迅速，據(jù)查閱，鮮有電動公交車與司機整合調(diào)度的研究內(nèi)容，故本文旨在提出電動公交車與司機整合調(diào)度問題及其求解算法。本文考慮司機連續(xù)工作時間和總工作時間約束以及電動公交車里程約束，結(jié)合現(xiàn)有公交車和司機整合調(diào)度模式，研究電動公交車和司機整合調(diào)度問題，并提出列生成啟發(fā)式算法求解。列生成算法將問題分解為一個主問題和兩個子問題，設(shè)計時空網(wǎng)絡(luò)結(jié)合標號法求解子問題。在列生成算法得到線性松弛解后，設(shè)計深淺算法(Pure Diving)得到整數(shù)可行解，在有限時間內(nèi)得到質(zhì)量較高的解[12]。使用合肥市3條公交線路的基本信息生成算例，測試列生成啟發(fā)式算法的有效性，并對比整合調(diào)度模式下和順序調(diào)度模式下公交企業(yè)運營的成本變化。

1 問題描述

電動公交車和司機整合調(diào)度問題定義為：已知所有車次的信息、場站和所有終點站之間的行駛時間及距離，選擇可行的司機車次鏈和電動公交車行車路徑，使司機排班計劃和電動公交車車輛運用計劃覆蓋所有車次，并保證司機排班計劃覆蓋電動公交車車輛運營計劃產(chǎn)生的所有空駛。本文有兩種空駛情況：車輛或者司機從場站出發(fā)或者回到場站；車次任務(wù)可能被覆蓋多次，一次為執(zhí)行任務(wù)，其余為空駛。根據(jù)公交系統(tǒng)實際運營情況，作如下假設(shè)：

(1)車輛從場站出發(fā)，完成1 d工作之后回到場站，駕駛車輛從場站出發(fā)的司機完成1 d 工作后沒有必要一定返回場站，可由其他司機駕駛返回，保證所有車輛均回到場站。

(2)車輛從場站出發(fā)時電量是滿的。車輛可以在公交線路終點站充電，假設(shè)充電時間固定，且每次都充滿。

(3)為簡化問題復雜度，將用餐時間考慮在司機休息時間內(nèi)，司機連續(xù)工作4 h，必須休息0.5 h以上，1 d總工作時間不能大于8 h。

該問題決策如何安排電動公交車的用車計劃及司機排班計劃，目標函數(shù)是司機和電動公交車產(chǎn)生的總費用最小。電動公交車的費用包括：固定費用、每公里行駛費用、每次充電費用。本文假設(shè)充電時間固定，故每次充電成本相同，即充電成本與充電次數(shù)成正比。司機的費用由司機出勤的固定費用和司機工作單位時間產(chǎn)生的費用組成。需要考慮的約束包括：電動公交車里程、司機總工作時間和連續(xù)工作時間。

2 時空網(wǎng)絡(luò)和數(shù)學模型

2.1 時空網(wǎng)絡(luò)的構(gòu)建

KLIEWER等[13]首次將時空網(wǎng)絡(luò)應(yīng)用于公交車調(diào)度問題，本文構(gòu)建時空網(wǎng)絡(luò)求解子問題，用于生成可行的司機車次鏈和電動公交車行車路徑。

(1)車次弧

已知每個車次i∈I的起點站點li，其中，I為車次集合，終點站點，開始時間si，結(jié)束時間ei，為車次i起點站點li對應(yīng)的虛擬出發(fā)節(jié)點，為車次i終點站點對應(yīng)的虛擬到達節(jié)點。車次i對應(yīng)的車次弧的起點為，終點為，對應(yīng)的時刻分別為si和ei。

(2)出場弧

假設(shè)司機和車輛可以在任何時刻從場站出發(fā)。出場弧對應(yīng)的起點是虛擬起點，終點是虛擬出發(fā)節(jié)點。

(3)入場弧

假設(shè)司機和車輛可以在任何時刻回到場站。入場弧對應(yīng)的起點是車次弧的終點，終點是虛擬終點。

(4)充電弧

ε為車輛每次充電時間，假設(shè)充電時間固定，車輛可以在任意終點站s∈S充電，假設(shè)車輛在t∈T時刻在終點站s充電，則對應(yīng)充電弧的起點為，終點為，對應(yīng)的時間分別是t和t+ε，并且只有車輛行車路徑才能覆蓋充電弧。

(5)等待弧

司機和車輛可以在任意虛擬到達站點和虛擬出發(fā)站點s∈S1?S2等待。每條等待弧的長度為1個時間單位，假設(shè)司機在t∈T時刻在虛擬終點站s∈S1?S2等待，則對應(yīng)等待弧的起、終點均為s，對應(yīng)的時間分別為t和t+1。

(6)緩沖弧

司機和車輛完成一個車次之后需要一定的緩沖時間才能運行下個車次(司機需要休息，車輛出發(fā)之前需要檢查)。設(shè)車輛運行完車次i∈I到達虛擬到達站點之后，需要進行βmin緩沖，對應(yīng)緩沖弧的起點為，終點為，對應(yīng)的時間分別為ei和ei+β。

為清楚了解時空網(wǎng)絡(luò)的構(gòu)建，根據(jù)表1車次信息，構(gòu)建時空網(wǎng)絡(luò)，如圖1所示，節(jié)點由虛擬起點o，虛擬終點ω，兩個虛擬到達站點，兩個虛擬出發(fā)站點組成。

圖1 時空網(wǎng)絡(luò)生成案例Fig.1 Example of time-space network

表1 車次信息Table 1 Trip information

(1)車輛可以從場站出發(fā)依次完成車次1、車次2、車次3，或者車次2、車次3。但是車輛完成車次1之后不能去運行車次3，因為車次1 的終點站和車次3 的起點站不同。車輛完成每個車次都可以在終點站進行充電或者回到場站。

(2)司機車次鏈的起點不一定是場站，例如司機1駕駛車輛從o出發(fā)完成車次1，由司機2繼續(xù)從出發(fā)駕駛車輛依次完成車次2、車次3，然后回到d。

2.2 數(shù)學模型

列生成算法將問題分解為一個主問題和兩個子問題，將復雜的電動公交車里程約束以及司機連續(xù)工作時間和總工作時間約束放到兩個子問題中。主問題數(shù)學模型將公交車調(diào)度和司機排班的集合覆蓋模型結(jié)合，以司機和電動公交車總成本最小為目標，在電動公交車行車路徑集合和司機車次鏈集合中選擇車輛運營計劃和司機排班計劃，保證司機和電動公交車運用計劃覆蓋所有車次弧，并且保證司機排班計劃覆蓋電動公交車輛運營計劃產(chǎn)生的空駛弧。兩個子問題分別生成從虛擬起點o到虛擬終點d的可行電動公交車行車路徑和可行司機車次鏈，是資源約束最短路問題。本文主問題模型使用的變量及集合符號如表2所示。

表2 變量及符號定義Table 2 Definition of variables and symbols

電動公交車和司機整合調(diào)度問題描述為整數(shù)線性規(guī)劃問題，即

式(1)為最小化電動公交車和司機的總運營成本。式(2)和式(3)分別表示電動公交車車輛運用計劃和司機排班計劃覆蓋所有車次弧，允許車次被覆蓋多次，一次為執(zhí)行任務(wù)，其余視為空駛，本文假設(shè)車次的成本固定，未考慮車次作為空駛時對系統(tǒng)總成本產(chǎn)生的影響。如果車次任務(wù)允許被車次鏈覆蓋多次，如圖2所示，矩形框表示車次，圓表示場站，虛線表示出入場或者等待，車次5 被覆蓋2 次，需要兩個車次鏈將所有車次覆蓋。如果車次任務(wù)不允許被車次鏈覆蓋多次，如圖3所示，所有車次只允許被覆蓋一次，需要3條車次鏈才能將所有車次任務(wù)覆蓋。

圖2 車次允許被覆蓋多次Fig.2 Trips that allowed to be covered multiple times

圖3 車次不允許被覆蓋多次Fig.3 Trips that not allowed to be covered multiple times

由式(4)～式(6)可知，整合調(diào)度模式下電動公交車車輛運用計劃和司機排班計劃相互影響、相互制約，需要保證車輛運用計劃覆蓋的車次被司機排班計劃覆蓋，同時，保證車輛運用計劃覆蓋的空駛被司機排班計劃覆蓋。

3 列生成啟發(fā)式求解算法

3.1 列生成算法

列生成算法將問題分為兩部分。第1 部分是求解限制線性主問題，對式(7)和式(8)進行線性松弛，構(gòu)成限制線性主問題模型，運用Cplex求解器得到線性松弛問題最優(yōu)解，設(shè)P′和D′分別為當前電動公交車行車路徑集合和司機車次鏈集合。

第2部分是求解定價子問題，生成當前最優(yōu)的電動公交車行車路徑p和司機車次鏈d，分別加入P′和D′，繼續(xù)求解限制線性松弛主問題。如果電動公交車行車路徑及司機車次鏈的檢驗數(shù)大于等于零，則列生成算法終止，輸出線性松弛問題最優(yōu)解。

3.1.1 定價子問題

限制線性主問題對偶問題的數(shù)學規(guī)劃模型為

電動公交車行車路徑p的檢驗數(shù)ξp和司機車次鏈d的檢驗數(shù)為

子問題是兩個資源約束最短路問題，分別生成從虛擬起點o到虛擬終點d的可行電動公交車行車路徑和可行司機車次鏈。對于電動公交車行車路徑，主要考慮電動公交車里程約束，本文假設(shè)電動公交車從虛擬起點出發(fā)時是滿電狀態(tài)，可以在公交線路終點站充電，每次充電都充滿。對于司機車次鏈，主要考慮司機連續(xù)工作時間和總工作時間約束，本文假設(shè)司機只能在公交線路終點站或者場站休息，如果休息時間滿30 min，連續(xù)工作時間歸零，且休息時間不計入總工作時間。

標號法在求解資源約束最短路問題具有廣泛應(yīng)用[14]?？紤]到電動公交車里程約束和可充電的性質(zhì)，設(shè)計相應(yīng)的標簽策略，為生成車輛行車路徑時空網(wǎng)絡(luò)中節(jié)點v∈V的標簽，g為車輛從場站o行駛到節(jié)點v的累計行駛距離，設(shè)為車輛從場站o行駛到節(jié)點v的累計成本。假設(shè)標簽向外拓展到，如果節(jié)點v1和節(jié)點v2對應(yīng)的弧是充電弧，則g2=0，否則，為節(jié)點v1到v2之間的距離)，如果g2＞γ，該標簽不可行，將該標簽刪除，其中γ表示車輛的里程約束。假設(shè)標簽和標簽都是節(jié)點v3對應(yīng)的標簽，如果滿足，且，表示標簽被支配，則將標簽從v3對應(yīng)的標簽集合中刪除，否則，將兩個標簽都加入v3對應(yīng)的標簽集合中。最后，在終點d對應(yīng)的標簽集合中選擇累計成本最小的標簽，回溯找到最短路徑。標號法求解電動公交車資源約束最短路子問題的步驟如下。

Step 1 初始化。

Step 1.1 將時空網(wǎng)絡(luò)中所有節(jié)點進行拓撲排序。

Step 1.4 給虛擬起點添加標簽。Δot=，其中，p記錄前接節(jié)點及前接標簽的信息，起點o沒有前接節(jié)點，所以為。

Step 2 向后接節(jié)點拓展。

從時空網(wǎng)絡(luò)拓撲排序第1 個節(jié)點開始向后接節(jié)點拓展，并根據(jù)支配規(guī)則判斷拓展后的標簽是否被支配。如果該標簽被支配或者不可行，則將該標簽刪除。

Step 3 回溯找到最短路徑。

Step 3.1 在虛擬終點d的標簽集合中找到成本c最小的標簽。遍歷所有中的標簽，找到所有累計成本最小的標簽。

Step 3.2 根據(jù)前接標簽信息找到最短路徑。如果前接標簽是虛擬起點o的標簽，記錄最短路徑，算法結(jié)束，生成可行的電動公交車行車路徑。

生成可行司機車次鏈時，求解步驟與生成電動公交車行車路徑相似，但是在設(shè)計標簽時需要同時考慮司機的連續(xù)工作時間和總工作時間，設(shè)為生成司機車次鏈時時空網(wǎng)絡(luò)中節(jié)點v∈V的標簽，其中，t為司機連續(xù)工作時間，t′為司機從開始工作到節(jié)點v總工作時間，為司機從開始工作到節(jié)點v的累計成本。司機在完成一個車次之后開始記錄其休息時間，如果休息時間大于等于30 min則司機的連續(xù)工作時間清零，休息時間不算司機的總工作時間；如果司機的連續(xù)工作時間大于α1(α1表示司機的連續(xù)工作時間約束)或者總工作時間大于α2(α2表示司機的總工作時間約束)，則表示該標簽不可行，將該標簽刪除。假設(shè)標簽和都是節(jié)點v1對應(yīng)的標簽，如果滿足且，則表示標簽被支配，將標簽從v1對應(yīng)的標簽集合中刪除，否則，將兩個標簽都加入v1對應(yīng)的標簽集合中。

培育社區(qū)文化陣地。完善社區(qū)文化設(shè)施。普遍建立綜合文化服務(wù)中心，打通公共文化服務(wù)“最后一公里”。市級“文化指導員”隊伍深入社區(qū)幫助指導開展群眾文化活動，輔導、帶動基層文藝骨干和團隊，提高社區(qū)文化創(chuàng)作、展演水平。豐富社區(qū)文化活動。立足根植群眾的主體定位和雅俗共享的藝術(shù)定位，借助“靖江文藝節(jié)”“驥江大舞臺”“馬洲大舞臺”“靖江大明星”等平臺，多側(cè)面、全方位、大視角地開展社區(qū)文化活動。擦亮社區(qū)文化品牌。結(jié)合各自地理位置、歷史淵源、人文底蘊，積極打造社區(qū)文化品牌，使具有鮮明社區(qū)特色的文化活動、精品節(jié)目成為社區(qū)的名片，真正使社區(qū)文化成為居民交流溝通的橋梁、社會穩(wěn)定和諧的基石。

3.1.2 列生成算法流程

在開始列生成算法之前，需要加入初始變量xp(p∈P′)、yd(d∈D′)，構(gòu)建初始限制線性松弛主問題模型，保證電動公交車運用計劃和司機排班計劃覆蓋所有車次，并且保證司機排班計劃覆蓋所有電動公交車運用計劃產(chǎn)生的空駛弧。在初始解生成及定價子問題的求解中，都應(yīng)用標號法，并生成同時滿足司機連續(xù)工作時間、總工作時間及車輛里程約束的車次鏈。將生成的車次鏈分別加入車輛行車路徑集合和司機車次鏈集合中，同時，將生成車次鏈中的所有車次在時空網(wǎng)絡(luò)中對應(yīng)車次弧的成本設(shè)為無窮大。然后，繼續(xù)使用標號法生成同時滿足司機連續(xù)工作、總工作時間及車輛里程約束的車次鏈，直到所有車次都被初始車輛行車路徑和司機車次鏈覆蓋。標號法生成初始解的思想與標號法生成車輛行車路徑相似，操作步驟如下。

Step 2 標號法求解資源約束最短路問題。生成一條同時滿足車輛里程約束、司機連續(xù)工作時間約束、總工作時間約束車次鏈。將車次鏈分別加入車輛行車路徑集合P′以及司機車次鏈集合D′中。

Step 3 更新時空網(wǎng)絡(luò)車次弧的成本。將Step 2中標號法得到的車次鏈在時空網(wǎng)絡(luò)對應(yīng)車次弧的成本設(shè)為無窮大。

Step 4 終止條件。如果時空網(wǎng)絡(luò)中所有車次弧的成本都為無窮大，則算法終止，輸出初始車輛行車路徑集合P′以及初始司機排班集合D′；否則，轉(zhuǎn)到Step 2繼續(xù)求解資源約束最短路問題。

生成的車輛行車路徑集合P′和司機車次鏈集合D′作為初始可行解構(gòu)建初始限制線性主問題模型。列生成算法的主要流程如下。

Step 1 構(gòu)建初始限制線性主問題模型。采用貪婪算法得到初始行車路徑集合P和司機車次鏈集合D，構(gòu)建初始線性限制主問題。

Step 2 求解限制線性主問題。使用Cplex求解限制線性主問題。得到對偶變量，。

Step 3 求解定價子問題。

Step 3.1 子問題1，生成電動公交車行車路徑p。更新車次弧u∈U的成本，更新出場弧u∈U1的成本，更新入場弧u∈U2的成本。使用標號法生成電動公交車行車路徑p。

Step 3.2 子問題2，生成司機車次鏈d。更新車次弧u∈U的成本，更新出場弧的成本，更新入場弧的成本，使用標號法生成司機車次鏈d。

Step 4 列生成終止條件。如果電動公交車路徑p的檢驗數(shù)ξp以及司機車次鏈d的檢驗數(shù)都大于等于零，算法迭代終止；否則，P=P?p，D=D?d，轉(zhuǎn)到Step 3。

兩個子問題分別用于生成電動公交車行車路徑和司機車次鏈，將生成的車輛行車路徑和司機車次鏈分別加入車輛行車路徑集合和司機車次鏈集合中，由限制線性主問題模型可以看出，在求解限制線性主問題時，兩個子問題相互影響、相互制約。最后，同時輸出電動公交車線性松弛最優(yōu)解及司機排班線性松弛最優(yōu)解。

3.2 列生成啟發(fā)式求解算法

SADYKOV 等[12]研究精確算法和啟發(fā)式策略的結(jié)合，提出深淺算法(Pure Diving)。深淺算法是運用深度優(yōu)先搜索策略處理線性松弛主問題最優(yōu)解的啟發(fā)式策略。本文在列生成算法得到線性松弛最優(yōu)解之后，每次選擇1 個小數(shù)解xp或者yd固定為1(每次選擇小數(shù)解1 的差的絕對值最小)，然后，使用列生成算法繼續(xù)求解線性松弛主問題，直到所有的解都為整數(shù)，算法結(jié)束。基于列生成啟發(fā)式的電動公交車與司機整合調(diào)度問題求解過程如下。

Step 1 初始化。設(shè)P=?，D=?，小數(shù)變量的集合F=?。

貪婪算法生成初始電動公交車行車路徑P和司機車次鏈集合D，保證所有車次被司機和電動公交車覆蓋。設(shè)。

Step 2 深淺算法。

Step 2.1 列生成算法，求解線性松弛問題。

Step 2.2 終止條件。如果小數(shù)變量集合F=?，轉(zhuǎn)到Step 4；如果線性松弛主問題不可行，算法終止。

Step 2.3 更新小數(shù)變量的上、下界。選擇最接近1的小數(shù)變量fc∈F，令fc=1。

Step 2.4 遞歸深淺算法。

4 算例與效果分析

將合肥3 條公交線路的基本信息隨機生成車次數(shù)據(jù)，測試列生成啟發(fā)式算法的有效性，并對比順序調(diào)度和整合調(diào)度兩種調(diào)度模式的求解結(jié)果。所有算例在配置Intel Core i7-9700k 3.20 GHz 處理器和16 GB 內(nèi)存的計算機上運行，使用Visual Studio C#編譯列生成啟發(fā)式算法程序，涉及的線性規(guī)劃問題借助數(shù)學規(guī)劃求解軟件CPLEX 12.6。

4.1 算例設(shè)置

3 條線路行駛距離，上、下行線路運營時間如表3所示。

表3 3條公交車線路運營情況Table 3 Information of three bus lines

本文假設(shè)每條線路高峰時間段發(fā)出車次的運營時間相同，平峰時間段發(fā)出車次的運營時間相同。不同線路在不同時間段發(fā)車車次的運營時間如表4所示，場站距離各線路終點站的距離及時間如表5所示，其余參數(shù)如表6所示。

表4 不同時間段、不同線路車次的單程運行時間及發(fā)車間隔Table 4 One-way time,departure time interval of different lines in different time periods

表5 場站到每條線路終點站的距離及時間Table 5 Distance and time from depot to terminals of each line

表6 參數(shù)設(shè)置Table 6 Parameter settings

4.2 線性松弛問題算例測試

根據(jù)合肥市1條公交線路的基本信息，隨機生成146 個車次數(shù)據(jù)，并使用列生成啟發(fā)式算法求解。最終，電動公交車行車路徑集合中有1435 條可行行車路徑，司機車次鏈集合中有2069 個司機車次鏈。求解得到的電動公交車輛運用計劃中有17 條車輛行車路徑，司機排班計劃中有26 個司機車次鏈。線性松弛最優(yōu)解隨迭代次數(shù)的變化情況如圖4所示，Cplex 求解器共求解限制線性主問題2070次。

圖4 線性松弛最優(yōu)解在迭代過程中的收斂情況Fig.4 Convergence of optimal solution of linear relaxed problems in iterations

4.3 算法求解效果對比分析

根據(jù)3條線路的運營情況，高峰時發(fā)車間隔時間設(shè)為8～10 min，平峰時發(fā)車間隔時間設(shè)為10～15 min，隨機生成3個算例，對列生成啟發(fā)式算法進行測試。每個算例測試的線路編號，上、下行運營時間及每個算例的車次數(shù)量如表7所示。

表7 算例設(shè)置Table 7 Data settings of numerical examples

表8為列生成啟發(fā)式算法對3個算例的求解結(jié)果。第2 列Z是貪婪算法初始解目標函數(shù)值，第3列Zl是Cplex 求解限制線性主問題模型的線性松弛最優(yōu)解目標函數(shù)值，第4列Zu是深淺算法得到整數(shù)解之后的目標函數(shù)值，第7列是求解時間，第8列表示初始可行解的生成時間，第9列表示電動公交車的充電次數(shù)，根據(jù)車輛運用計劃中所有車輛行車路徑覆蓋充電弧的次數(shù)確定充電次數(shù)，第10 列車輛數(shù)為列生成啟發(fā)式算法得到的車輛運用計劃中的車輛行車路徑的數(shù)量，第11 列司機數(shù)為列生成啟發(fā)式算法得到的司機排班計劃中的司機車次鏈的數(shù)量，第5 列E1和第6 列E2分別記錄了最優(yōu)整數(shù)解目標函數(shù)值和初始解目標函數(shù)值之間的差，以及線性松弛最優(yōu)解目標函數(shù)值和最優(yōu)整數(shù)解目標函數(shù)值之間的差，計算方法為

表8 整合調(diào)度測試結(jié)果Table 8 Results of integrated scheduling

式中：Z為貪婪算法求解初始解得到的目標函數(shù)值；Zu為整合調(diào)度模式下的最優(yōu)整數(shù)解的目標函數(shù)值；Zl為整合調(diào)度模式下的線性松弛解的目標函數(shù)值。

由第6列E2可知，列生成啟發(fā)式算法最后的線性松弛解與最優(yōu)整數(shù)解之間的差較小，說明使用深淺算法得到整數(shù)可行解的精度較高。

使用順序調(diào)度方法測試3個算例，順序調(diào)度方法首先使用列生成啟發(fā)式方法得到車輛運用計劃，保證所有車次都被車輛運用計劃覆蓋，然后，將車輛運用計劃作為輸入求解司機排班問題，保證所有車次都被司機排班計劃覆蓋，并保證車輛運用計劃產(chǎn)生的空駛弧被司機排班計劃覆蓋。順序調(diào)度與整合調(diào)度的對比結(jié)果如表9所示，其中，E3為整合調(diào)度目標函數(shù)和順序調(diào)度目標函數(shù)之間的差，計算方法為

表9 整合調(diào)度與順序調(diào)度結(jié)果對比Table 9 Comparison of results of integrated scheduling and sequential scheduling

對比表9整合調(diào)度與順序調(diào)度結(jié)果，得到如下結(jié)論：

(1)順序調(diào)度模式下的車輛數(shù)比整合調(diào)度模式下的車輛少。由于順序調(diào)度模式是先進行車輛調(diào)度，生成車輛運營計劃，再基于車輛運營計劃進行司機排班計劃。因此，順序調(diào)度模式下進行車輛調(diào)度問題研究時，只需要考慮電動公交車里程約束；整合調(diào)度模式下同時生成車輛運用計劃和司機排班計劃，生成車輛運用計劃時需要保證車輛運用計劃中的空駛被司機排班計劃覆蓋，導致順序調(diào)度模式下的車輛比整合調(diào)度模式下的車輛少。

(2)整合調(diào)度模式下的司機數(shù)量和公交企業(yè)運營總成本明顯比順序調(diào)度模式下少。由于順序調(diào)度模式是先進行車輛調(diào)度，生成車輛運營計劃，再基于車輛運營計劃進行司機排班計劃，因此，順序調(diào)度模式下進行司機排班時車輛運用計劃中的空駛信息固定，需要保證所有車次以及車輛運用計劃中的空駛被司機排班覆蓋；而整合調(diào)度下車輛運用計劃和司機排班集合相互制約、相互影響，會考慮車輛運用計劃對司機排班計劃的影響，因此，一般整合調(diào)度模式下的司機數(shù)量與公交企業(yè)運營成本都比順序調(diào)度模式下少。

5 結(jié)論

本文研究電動公交車與司機整合調(diào)度問題，考慮電動車的里程約束和司機的連續(xù)工作時間和總工作時間約束，同時生成電動公交車車輛運用計劃和司機排班計劃，并保證車輛運用計劃的空駛被司機排班計劃覆蓋，以合肥市3條公交線路的基本信息隨機生成時刻表數(shù)據(jù)進行求解測試，結(jié)果表明了本文所構(gòu)建的集合覆蓋模型和列生成啟發(fā)式算法的有效性。由E2的值可知，深淺算法在較短的時間內(nèi)能夠得到精度較高的整數(shù)解。整合調(diào)度和順序調(diào)度的對比結(jié)果表明，整合調(diào)度能有效減少公交運營成本和司機數(shù)量。