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

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

0 引言

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

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

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

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

1 問題描述

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

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

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

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

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

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

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

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

(1)車次弧

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

(2)出場(chǎng)弧

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

(3)入場(chǎng)弧

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

(4)充電弧

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

(5)等待弧

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

(6)緩沖弧

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

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

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

表1 車次信息Table 1 Trip information

(1)車輛可以從場(chǎng)站出發(fā)依次完成車次1、車次2、車次3，或者車次2、車次3。但是車輛完成車次1之后不能去運(yùn)行車次3，因?yàn)檐嚧? 的終點(diǎn)站和車次3 的起點(diǎn)站不同。車輛完成每個(gè)車次都可以在終點(diǎn)站進(jìn)行充電或者回到場(chǎng)站。

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

2.2 數(shù)學(xué)模型

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

表2 變量及符號(hào)定義Table 2 Definition of variables and symbols

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

式(1)為最小化電動(dòng)公交車和司機(jī)的總運(yùn)營(yíng)成本。式(2)和式(3)分別表示電動(dòng)公交車車輛運(yùn)用計(jì)劃和司機(jī)排班計(jì)劃覆蓋所有車次弧，允許車次被覆蓋多次，一次為執(zhí)行任務(wù)，其余視為空駛，本文假設(shè)車次的成本固定，未考慮車次作為空駛時(shí)對(duì)系統(tǒng)總成本產(chǎn)生的影響。如果車次任務(wù)允許被車次鏈覆蓋多次，如圖2所示，矩形框表示車次，圓表示場(chǎng)站，虛線表示出入場(chǎng)或者等待，車次5 被覆蓋2 次，需要兩個(gè)車次鏈將所有車次覆蓋。如果車次任務(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)度模式下電動(dòng)公交車車輛運(yùn)用計(jì)劃和司機(jī)排班計(jì)劃相互影響、相互制約，需要保證車輛運(yùn)用計(jì)劃覆蓋的車次被司機(jī)排班計(jì)劃覆蓋，同時(shí)，保證車輛運(yùn)用計(jì)劃覆蓋的空駛被司機(jī)排班計(jì)劃覆蓋。

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

3.1 列生成算法

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

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

3.1.1 定價(jià)子問題

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

電動(dòng)公交車行車路徑p的檢驗(yàn)數(shù)ξp和司機(jī)車次鏈d的檢驗(yàn)數(shù)為

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

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

Step 1 初始化。

Step 1.1 將時(shí)空網(wǎng)絡(luò)中所有節(jié)點(diǎn)進(jìn)行拓?fù)渑判颉?/p>

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

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

從時(shí)空網(wǎng)絡(luò)拓?fù)渑判虻? 個(gè)節(jié)點(diǎn)開始向后接節(jié)點(diǎn)拓展，并根據(jù)支配規(guī)則判斷拓展后的標(biāo)簽是否被支配。如果該標(biāo)簽被支配或者不可行，則將該標(biāo)簽刪除。

Step 3 回溯找到最短路徑。

Step 3.1 在虛擬終點(diǎn)d的標(biāo)簽集合中找到成本c最小的標(biāo)簽。遍歷所有中的標(biāo)簽，找到所有累計(jì)成本最小的標(biāo)簽。

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

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

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

3.1.2 列生成算法流程

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

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

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

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

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

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

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

Step 3 求解定價(jià)子問題。

Step 3.1 子問題1，生成電動(dòng)公交車行車路徑p。更新車次弧u∈U的成本，更新出場(chǎng)弧u∈U1的成本，更新入場(chǎng)弧u∈U2的成本。使用標(biāo)號(hào)法生成電動(dòng)公交車行車路徑p。

Step 3.2 子問題2，生成司機(jī)車次鏈d。更新車次弧u∈U的成本，更新出場(chǎng)弧的成本，更新入場(chǎng)弧的成本，使用標(biāo)號(hào)法生成司機(jī)車次鏈d。

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

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

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

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

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

貪婪算法生成初始電動(dòng)公交車行車路徑P和司機(jī)車次鏈集合D，保證所有車次被司機(jī)和電動(dòng)公交車覆蓋。設(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 條公交線路的基本信息隨機(jī)生成車次數(shù)據(jù)，測(cè)試列生成啟發(fā)式算法的有效性，并對(duì)比順序調(diào)度和整合調(diào)度兩種調(diào)度模式的求解結(jié)果。所有算例在配置Intel Core i7-9700k 3.20 GHz 處理器和16 GB 內(nèi)存的計(jì)算機(jī)上運(yùn)行，使用Visual Studio C#編譯列生成啟發(fā)式算法程序，涉及的線性規(guī)劃問題借助數(shù)學(xué)規(guī)劃求解軟件CPLEX 12.6。

4.1 算例設(shè)置

3 條線路行駛距離，上、下行線路運(yùn)營(yíng)時(shí)間如表3所示。

表3 3條公交車線路運(yùn)營(yíng)情況Table 3 Information of three bus lines

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

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

表5 場(chǎng)站到每條線路終點(diǎn)站的距離及時(shí)間Table 5 Distance and time from depot to terminals of each line

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

4.2 線性松弛問題算例測(cè)試

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

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

4.3 算法求解效果對(duì)比分析

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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