錢(qián) 程，徐小明，彭飛

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

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

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

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

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

1 司機(jī)排班問(wèn)題

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

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

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

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

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

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

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

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

5)司機(jī)的連續(xù)工作時(shí)間不應(yīng)該超過(guò)法定最大連續(xù)工作時(shí)長(zhǎng)。連續(xù)工作時(shí)間是指司機(jī)連續(xù)執(zhí)行車(chē)次任務(wù)的時(shí)間，包括間休時(shí)間和兩個(gè)連續(xù)車(chē)次間的等待時(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。由于存在跨班型的車(chē)次任務(wù)，在早班添加一段冗余時(shí)間t，t最大為一個(gè)車(chē)次任務(wù)時(shí)長(zhǎng)，即早班時(shí)間為(06:00—14：00)+t，晚班時(shí)間為14:00—22:00。而司機(jī)班次的開(kāi)始時(shí)間和結(jié)束時(shí)間由所在班型決定，如早班工作的司機(jī)從06：00開(kāi)始工作，若司機(jī)執(zhí)行的最后一個(gè)車(chē)次任務(wù)的結(jié)束時(shí)間在14:00前，則司機(jī)在14:00簽退并結(jié)束工作，否則該司機(jī)在14：00+t時(shí)刻結(jié)束車(chē)次任務(wù)并簽退；晚班工作的司機(jī)從14:00開(kāi)始工作，在22:00簽退并結(jié)束工作。

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

2 問(wèn)題模型

文中所考慮的問(wèn)題表述為帶有約束的最小成本多商品網(wǎng)絡(luò)流問(wèn)題，其中每個(gè)商品代表一個(gè)司機(jī)，建立一個(gè)有向無(wú)環(huán)的時(shí)空網(wǎng)絡(luò)G=(V,A)。接下來(lái)首先介紹時(shí)空網(wǎng)絡(luò)的構(gòu)建，然后針對(duì)問(wèn)題建立網(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ī)的工作過(guò)程，首先分析公交司機(jī)的時(shí)空狀態(tài)，每個(gè)狀態(tài)轉(zhuǎn)換定義為一個(gè)離散事件。一串連續(xù)的離散事件能夠描述一個(gè)司機(jī)一天的工作過(guò)程，也是一個(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ì)劃的過(guò)程中，需要更新每個(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é)將介紹初始解生成的算法，該算法通過(guò)離散事件模型模擬司機(jī)調(diào)度問(wèn)題中司機(jī)的工作過(guò)程來(lái)獲得初始解，初始解生成算法如下所述。

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

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

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

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

Step 5：若當(dāng)前事件為司機(jī)開(kāi)始用餐事件，則生成司機(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)度問(wèn)題的可行解。

3.3 變鄰域搜索

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

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

Step 2：設(shè)i=0，k=1,其中i表示解連續(xù)i次迭代沒(mé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í)行車(chē)次任務(wù)的司機(jī)，各自挑選一個(gè)司機(jī)執(zhí)行的車(chē)次任務(wù)，將兩個(gè)車(chē)次任務(wù)互換司機(jī)執(zhí)行。

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

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

4 算例分析

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

表3展示了在小規(guī)模算例中VNS的解，初始解和求解器CPLEX 12.5所得的精確解結(jié)果。其中：列“H”表示發(fā)車(chē)間隔；列“|K|”表示車(chē)次任務(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ì)算方式見(jiàn)式(11)～(13))；“-”表示CPLEX在2 h內(nèi)得不到可行解。由表3可看出，當(dāng)車(chē)次任務(wù)數(shù)量增大到一定程度時(shí)，CPLEX的求解時(shí)間過(guò)長(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%)，以上說(shuō)明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%，說(shuō)明基于離散事件的仿真算法可以在極快的時(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ī)排班問(wèn)題也有著極高的求解效率。同時(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ù)同樣有效。以上分析說(shuō)明文中提出的基于離散事件的變鄰域搜索算法是一種求解司機(jī)排班問(wèn)題的最有效算法。

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

5 結(jié) 論

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

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

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

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