錢 程，徐小明，彭飛

(1.合肥工業(yè)大學(xué) 汽車與交通工程學(xué)院，合肥 230009；2.北京電子科技職業(yè)學(xué)院 汽車工程學(xué)院，北京 100176)

在公交運(yùn)營(yíng)管理中，運(yùn)營(yíng)組織與調(diào)度是公交企業(yè)工作的核心。公交運(yùn)營(yíng)組織和調(diào)度的首要任務(wù)，是有效管理和合理分配有限的車輛和人力資源，調(diào)整供需平衡，爭(zhēng)取以最小的人力、物力及財(cái)力投入來(lái)保障日益增加的客流需求[1]。司機(jī)排班問題是公交運(yùn)營(yíng)規(guī)劃的重要組成部分，用于司機(jī)的費(fèi)用大約占整個(gè)公交公司運(yùn)營(yíng)成本的60%[2]，一個(gè)高質(zhì)量的司機(jī)排班計(jì)劃可以為公交公司節(jié)省很多成本。乘務(wù)調(diào)度問題(CSP)的目標(biāo)是在滿足一系列復(fù)雜勞動(dòng)法規(guī)的條件下，合理安排一組乘務(wù)人員完成一天內(nèi)的全部車輛運(yùn)行任務(wù)，公交系統(tǒng)中的乘務(wù)調(diào)度問題又可稱為司機(jī)排班問題(DSP)。

司機(jī)排班問題自20世紀(jì)60年代以來(lái)一直受到廣泛的關(guān)注和研究，班制和用餐約束在司機(jī)排班問題中被廣泛考慮。在實(shí)際的公交系統(tǒng)中，常規(guī)班制和早晚班制是兩種常見的司機(jī)工作班制[3]。在公交司機(jī)排班問題中，設(shè)置司機(jī)用餐休息也有兩種常見的方式：一種是在司機(jī)達(dá)到最大連續(xù)工作時(shí)間后設(shè)置一段長(zhǎng)休息作為司機(jī)的用餐時(shí)間；另一種是更符合人們飲食習(xí)慣的“中式用餐”[4]，即設(shè)置司機(jī)的用餐時(shí)間窗，規(guī)定司機(jī)在用餐時(shí)間窗內(nèi)用餐。

司機(jī)排班問題為NP-hard問題，這一點(diǎn)已被許多研究所證實(shí)[5]，對(duì)于此類問題，通常結(jié)合集合覆蓋或集合劃分模型進(jìn)行建模[6]。乘務(wù)排班問題的主要求解方法包括列生成和啟發(fā)式兩種，Desrochers等[7]較早開始研究列生成算法求解公交司機(jī)排班問題，為加快列生成算法的收斂速度，一些學(xué)者開始在使用列生成算法時(shí)引入一些啟發(fā)式策略和方法：Mauri等[8]提出了種群訓(xùn)練啟發(fā)式算法，并結(jié)合列生成求解司機(jī)排班問題；Li等[9]設(shè)計(jì)了一種基于超啟發(fā)式的列生成算法來(lái)加快列生成的速度；Gamache等[10]采用集合劃分模型設(shè)計(jì)了在列生成中加入啟發(fā)式算法應(yīng)用于航空乘務(wù)調(diào)度。隨著算例規(guī)模的增大，商業(yè)求解器和精確算法在求解大規(guī)模司機(jī)排班問題時(shí)可能出現(xiàn)難以接受的計(jì)算時(shí)間，一些學(xué)者提出了啟發(fā)式算法來(lái)求解司機(jī)排班問題，其中主要有遺傳算法、禁忌搜索算法和變鄰域搜索算法(VNS)。針對(duì)司機(jī)常規(guī)班制和無(wú)固定司機(jī)用餐時(shí)間窗的司機(jī)排班問題，Shen等[11]對(duì)混合遺傳算法進(jìn)行改進(jìn)，采用一種自適應(yīng)進(jìn)化的混合遺傳算法求解該問題。針對(duì)常規(guī)班制和不帶用餐時(shí)間窗的公交司機(jī)排班問題：Ma等[12]將變鄰域搜索算法應(yīng)用在北京公交排班問題中；彭琨琨等[13]在變鄰域搜索算法中設(shè)計(jì)了一種班次評(píng)價(jià)方法對(duì)解進(jìn)行評(píng)價(jià)；Shen等[14]將禁忌搜索算法應(yīng)用于司機(jī)排班問題；Ma等[15]考慮了排班的公平性；De Leone等[16]設(shè)計(jì)一種貪婪隨機(jī)自適應(yīng)搜索啟發(fā)式算法求解該問題。

綜上，當(dāng)前研究主要側(cè)重于常規(guī)班制研究，極少有人在考慮早晚班制的同時(shí)結(jié)合固定用餐時(shí)間約束。針對(duì)當(dāng)前研究中的不足,文中考慮早晚班制和固定司機(jī)用餐時(shí)間窗的公交司機(jī)排班問題，結(jié)合勞動(dòng)法規(guī)等相關(guān)約束，構(gòu)建整數(shù)規(guī)劃模型，并設(shè)計(jì)基于離散事件的變鄰域搜索算法求解，為司機(jī)調(diào)度計(jì)劃的編制與優(yōu)化提供依據(jù)。

1 司機(jī)排班問題

公交司機(jī)排班問題的目的是降低運(yùn)營(yíng)成本，安排公交司機(jī)執(zhí)行車次任務(wù)，同時(shí)確定公交司機(jī)的班次。為了更加準(zhǔn)確的描述問題，介紹以下術(shù)語(yǔ)。

1)班型是指由早晚班制確定的一段工作時(shí)間，司機(jī)在一天中可以選擇在早班時(shí)間工作或在晚班時(shí)間工作。

2)班次是司機(jī)從場(chǎng)站簽到開始直到場(chǎng)站簽退結(jié)束，一整天完成的所有工作集合，包括簽到、簽退、執(zhí)行車次任務(wù)、間休、等待和用餐。

一個(gè)完整的司機(jī)排班計(jì)劃是司機(jī)排班問題的一個(gè)解決方案，它包括一組共同覆蓋所有車次任務(wù)的可行班次。表1列出了問題涉及的各種參數(shù)，其中與時(shí)間相關(guān)的參數(shù)都是整數(shù)。文中研究的司機(jī)排班問題有以下特點(diǎn)。

1)文中考慮的場(chǎng)景是包括s1和s2兩個(gè)場(chǎng)站的單條雙向公交線路。場(chǎng)站作為公交車的起終點(diǎn)，司機(jī)可以在場(chǎng)站進(jìn)行簽到、簽退、用餐、休息和等待。

2)車次時(shí)刻表為確定的輸入數(shù)據(jù)。

3)所有的車次任務(wù)都要被執(zhí)行，并且每個(gè)車次任務(wù)只能由一名司機(jī)執(zhí)行一次，一個(gè)司機(jī)在同一時(shí)間只能執(zhí)行一個(gè)車次任務(wù)。

4)司機(jī)在一天內(nèi)的總工作時(shí)間不應(yīng)該超過法定最大工作時(shí)長(zhǎng)。司機(jī)總工作時(shí)間是指司機(jī)一天中從簽到時(shí)間到簽退時(shí)間之間的總時(shí)間，包括執(zhí)行車次任務(wù)時(shí)間、間休時(shí)間、用餐時(shí)間和等待時(shí)間。

5)司機(jī)的連續(xù)工作時(shí)間不應(yīng)該超過法定最大連續(xù)工作時(shí)長(zhǎng)。連續(xù)工作時(shí)間是指司機(jī)連續(xù)執(zhí)行車次任務(wù)的時(shí)間，包括間休時(shí)間和兩個(gè)連續(xù)車次間的等待時(shí)間。

6)若司機(jī)的工作時(shí)間內(nèi)包含用餐時(shí)間窗，司機(jī)應(yīng)在用餐時(shí)間窗內(nèi)進(jìn)行用餐。用餐時(shí)間也被當(dāng)作休息時(shí)間。

7)將計(jì)劃周期[0,T]進(jìn)行離散化，每個(gè)時(shí)間單元都表示為整數(shù)，比如，若計(jì)劃周期為24 h，每個(gè)時(shí)間單元為1 min，T=1 440 min。

文中設(shè)置早晚兩種班型，班型設(shè)置時(shí)考慮司機(jī)最大工作時(shí)長(zhǎng)，如工作時(shí)間為06:00—22:00, 共16 h，而司機(jī)最大工作時(shí)長(zhǎng)為8 h，則早班和晚班的工作時(shí)長(zhǎng)都為8 h。由于存在跨班型的車次任務(wù)，在早班添加一段冗余時(shí)間t，t最大為一個(gè)車次任務(wù)時(shí)長(zhǎng)，即早班時(shí)間為(06:00—14：00)+t，晚班時(shí)間為14:00—22:00。而司機(jī)班次的開始時(shí)間和結(jié)束時(shí)間由所在班型決定，如早班工作的司機(jī)從06：00開始工作，若司機(jī)執(zhí)行的最后一個(gè)車次任務(wù)的結(jié)束時(shí)間在14:00前，則司機(jī)在14:00簽退并結(jié)束工作，否則該司機(jī)在14：00+t時(shí)刻結(jié)束車次任務(wù)并簽退；晚班工作的司機(jī)從14:00開始工作，在22:00簽退并結(jié)束工作。

表1 數(shù)學(xué)符號(hào)及定義

2 問題模型

文中所考慮的問題表述為帶有約束的最小成本多商品網(wǎng)絡(luò)流問題，其中每個(gè)商品代表一個(gè)司機(jī)，建立一個(gè)有向無(wú)環(huán)的時(shí)空網(wǎng)絡(luò)G=(V,A)。接下來(lái)首先介紹時(shí)空網(wǎng)絡(luò)的構(gòu)建，然后針對(duì)問題建立網(wǎng)絡(luò)流模型。

2.1 時(shí)空網(wǎng)絡(luò)

圖1 司機(jī)r在時(shí)空網(wǎng)絡(luò)上的一條路徑

2.2 整數(shù)規(guī)劃模型

(1)

(2)

(3)

(4)

(5)

?u′→v′∈Asignj,r∈R,j∈J

(6)

(7)

?u′→v′∈Asignj,r∈R,j∈J,m∈Mj

(8)

(9)

(10)

3 求解算法

文中提出了一種基于離散事件模型和變鄰域搜索的快速求解算法，可以在可接受的計(jì)算時(shí)間內(nèi)得到高質(zhì)量的公交司機(jī)調(diào)度計(jì)劃。為了模擬司機(jī)的工作過程，首先分析公交司機(jī)的時(shí)空狀態(tài)，每個(gè)狀態(tài)轉(zhuǎn)換定義為一個(gè)離散事件。一串連續(xù)的離散事件能夠描述一個(gè)司機(jī)一天的工作過程，也是一個(gè)司機(jī)班次。該算法第一階段設(shè)計(jì)基于離散事件的啟發(fā)式算法求得初始解，第二階段對(duì)初始解進(jìn)行變領(lǐng)域搜索，對(duì)解進(jìn)行優(yōu)化。

3.1 司機(jī)狀態(tài)轉(zhuǎn)換定義

圖2 司機(jī)狀態(tài)轉(zhuǎn)移

在給定當(dāng)前系統(tǒng)時(shí)間t下，給出文中所提出的司機(jī)調(diào)度系統(tǒng)狀態(tài)轉(zhuǎn)換的3個(gè)定義：

定義1(事件)：在司機(jī)狀態(tài)改變時(shí)產(chǎn)生事件。

在生成調(diào)度計(jì)劃的過程中，需要更新每個(gè)執(zhí)行的離散事件對(duì)應(yīng)的司機(jī)位置、狀態(tài)和系統(tǒng)時(shí)間，直到最后一個(gè)離散事件被執(zhí)行，即計(jì)劃周期結(jié)束。司機(jī)調(diào)度仿真啟發(fā)式算法由3部分組成，即初始化系統(tǒng)、確定系統(tǒng)更新步驟和更新系統(tǒng)信息。由于啟發(fā)式算法是基于司機(jī)狀態(tài)轉(zhuǎn)移設(shè)計(jì)，狀態(tài)轉(zhuǎn)移在本質(zhì)上是離散事件的產(chǎn)生。

3.2 初始解生成

本節(jié)將介紹初始解生成的算法，該算法通過離散事件模型模擬司機(jī)調(diào)度問題中司機(jī)的工作過程來(lái)獲得初始解，初始解生成算法如下所述。

Step 1：初始化離散事件集合，集合中只包含各車次任務(wù)的開始事件和結(jié)束事件；初始化司機(jī)集合。

Step 2：遍歷離散事件集合，挑選司機(jī)來(lái)執(zhí)行各離散事件。

Step 3：若當(dāng)前事件為車次開始事件，依次對(duì)司機(jī)的時(shí)間、位置、狀態(tài)進(jìn)行判斷，若滿足上述條件，則該司機(jī)執(zhí)行該車次開始事件，該車次的到達(dá)事件也由同一司機(jī)執(zhí)行，更新司機(jī)狀態(tài)；否則，重新挑選司機(jī)。

Step 4：若當(dāng)前事件為車次結(jié)束事件，則生成一個(gè)司機(jī)間休事件；若當(dāng)前系統(tǒng)時(shí)間在用餐時(shí)間窗內(nèi)，則生成一個(gè)司機(jī)開始用餐事件；更新司機(jī)狀態(tài)，離散事件集合。

Step 5：若當(dāng)前事件為司機(jī)開始用餐事件，則生成司機(jī)結(jié)束用餐事件；更新司機(jī)狀態(tài)，離散事件集合。

Step 6：若當(dāng)前事件為司機(jī)間休事件或司機(jī)用餐結(jié)束事件，更新系統(tǒng)信息。

Step 7：當(dāng)最后一個(gè)離散事件被執(zhí)行時(shí)，終止程序，得到一組司機(jī)執(zhí)行的離散事件集合，即司機(jī)調(diào)度問題的可行解。

3.3 變鄰域搜索

變鄰域搜索算法是一種求解最優(yōu)化問題的啟發(fā)式算法，其主體為設(shè)計(jì)多個(gè)鄰域，在搜索解時(shí)規(guī)律地改變當(dāng)前的鄰域，不斷迭代地尋找更優(yōu)解。文中采用的算法框架如下：

Step 1：通過3.2節(jié)所述的仿真啟發(fā)式算法得到初始解s，令sbest=s，scurr=s；

Step 2：設(shè)i=0，k=1,其中i表示解連續(xù)i次迭代沒有改進(jìn)，k表示第k個(gè)鄰域操作；

Step 3：對(duì)scurr在鄰域NSk中進(jìn)行局部搜索，得到s，s←NSk(scurr)；若s

Step 4：令k=k+1，重復(fù)step 3，若k>2，進(jìn)行step 5；

Step 5：若scurr

Step 6：達(dá)到終止條件，即i=MaxIter，結(jié)束循環(huán)，輸出最優(yōu)解sbest，否則轉(zhuǎn)到step 3。

設(shè)計(jì)兩種不同的鄰域NS1,NS2。

1)第一種鄰域操作是為了避免解陷入局部最優(yōu)。選擇兩個(gè)班次相同且執(zhí)行車次任務(wù)的司機(jī)，各自挑選一個(gè)司機(jī)執(zhí)行的車次任務(wù)，將兩個(gè)車次任務(wù)互換司機(jī)執(zhí)行。

2)第二種鄰域操作是為了減少所用的司機(jī)數(shù)量。選擇一個(gè)執(zhí)行車次任務(wù)的司機(jī)刪除，將該司機(jī)執(zhí)行的任務(wù)插入其他至少執(zhí)行一個(gè)車次任務(wù)的司機(jī)班次中。

需要注意的是，在進(jìn)行鄰域操作過程中，要保證解的可行性。

4 算例分析

表2 算例參數(shù)設(shè)置 min

表3展示了在小規(guī)模算例中VNS的解，初始解和求解器CPLEX 12.5所得的精確解結(jié)果。其中：列“H”表示發(fā)車間隔；列“|K|”表示車次任務(wù)數(shù)量；列“Cost”表示目標(biāo)函數(shù)值；列“r”表示解的司機(jī)數(shù)量；列“t”表示算法運(yùn)行時(shí)間；列“Gap1”表示初始解與CPLEX所得精確解之間總成本的相對(duì)差值，列“Gap2”表示VNS解與CPLEX所得精確解之間總成本的相對(duì)差值，列“Gap3”表示初始解與VNS解之間的相對(duì)差值(Gap1、Gap2、Gap3的計(jì)算方式見式(11)～(13))；“-”表示CPLEX在2 h內(nèi)得不到可行解。由表3可看出，當(dāng)車次任務(wù)數(shù)量增大到一定程度時(shí)，CPLEX的求解時(shí)間過長(zhǎng)，甚至在2 h內(nèi)無(wú)法求得可行解(如Inst5)，而VNS幾乎都能在70 s內(nèi)得到最優(yōu)解，所以從整體看來(lái)，VNS的求解效率相比CPLEX的求解效率有顯著提高。在算例Inst 1、Inst 4中采用VNS可得到與CPLEX相同的解，在算例Inst 2和Inst 3中結(jié)果會(huì)有少許誤差(算例Inst 2中VNS的Gap為1.02%，算例Inst 3中VNS的Gap為0.73%)，以上說明VNS相比于CPLEX可以在顯著提高求解效率的同時(shí)獲得近似解。

表3 小規(guī)模算例計(jì)算結(jié)果

從表3還可以看出，基于離散事件的仿真算法可在0.01 s內(nèi)求得可行解。與CPLEX所得精確解相比，仿真算法在Inst 1中可以得到與CPLEX相同的解，在其余3組CPLEX能夠在2 h內(nèi)求得解的算例中，初始解的最大Gap為10.19%，最小Gap為2.82%，說明基于離散事件的仿真算法可以在極快的時(shí)間內(nèi)求得較高質(zhì)量的解，甚至直接得到最優(yōu)解，如Inst 1。

表4展示了大規(guī)模算例所得VNS的初始解。由于計(jì)劃周期和算例規(guī)模較大，算例Inst 6-Inst 11 用CPLEX均無(wú)法在2 h內(nèi)得到可行解；對(duì)于CPLEX難以求解的大規(guī)模算例，VNS能在70 s內(nèi)得到解，所以VNS對(duì)于求解大規(guī)模網(wǎng)絡(luò)的司機(jī)排班問題也有著極高的求解效率。同時(shí)，針對(duì)大規(guī)模網(wǎng)絡(luò)的初始解求解，所提出的基于離散事件的仿真算法都能在極短時(shí)間內(nèi)求得較好的初始解。根據(jù)表3、表4中的Gap3可得，VNS求得的最優(yōu)解和初始解之間相差均不足10%。在Inst 1、Inst 7和Inst 11 中，初始解即最優(yōu)解，所以基于離散事件的仿真算法可以求得高質(zhì)量的初始解。Inst 11結(jié)果表明，該算法對(duì)于真實(shí)的數(shù)據(jù)同樣有效。以上分析說明文中提出的基于離散事件的變鄰域搜索算法是一種求解司機(jī)排班問題的最有效算法。

表4 大規(guī)模算例計(jì)算結(jié)果

5 結(jié) 論

文中探討了考慮早晚班制和固定司機(jī)用餐時(shí)間的單線路公交司機(jī)排班問題，以公交司機(jī)三餐的用餐時(shí)間窗和相關(guān)司機(jī)休息法規(guī)及覆蓋車次時(shí)刻表為約束，以最小化系統(tǒng)總成本為目標(biāo)，將公交司機(jī)排班問題構(gòu)建為0～1整數(shù)規(guī)劃模型，設(shè)計(jì)基于離散事件的變鄰域搜索啟發(fā)式算法。通過案例研究，在小規(guī)模算例中該算法能夠快速得到與CPLEX近似的解,在大規(guī)模算例中，該算法能夠快速得到可行的司機(jī)調(diào)度方案。還有許多問題有待進(jìn)一步解決，主要有以下幾方面：

1)文中研究成果適用于單線公交司機(jī)排班問題，未來(lái)研究還應(yīng)進(jìn)一步將問題擴(kuò)展為多線路公交司機(jī)排班。

2)在實(shí)際公交公司運(yùn)營(yíng)時(shí)，也存在多種班制混合存在的情形，多種班制混合司機(jī)排班問題也將是一個(gè)值得研究的方向。

3)文中僅考慮常規(guī)公交的司機(jī)排班問題，實(shí)際中的電動(dòng)公交車司機(jī)排班問題將存在不同于常規(guī)公交的問題特點(diǎn)，這也是今后需要進(jìn)一步探討的課題。