單線公交司機排班計劃網(wǎng)絡流模型與求解算法

錢 程，徐小明，彭飛

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

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

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

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

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

1 司機排班問題

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

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

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

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

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

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

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

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

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

6)若司機的工作時間內(nèi)包含用餐時間窗，司機應在用餐時間窗內(nèi)進行用餐。用餐時間也被當作休息時間。

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

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

表1 數(shù)學符號及定義

2 問題模型

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

2.1 時空網(wǎng)絡

圖1 司機r在時空網(wǎng)絡上的一條路徑

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 求解算法

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

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

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

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

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

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

3.2 初始解生成

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

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

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

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

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

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

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

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

3.3 變鄰域搜索

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

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

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

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

Step 4：令k=k+1，重復step 3，若k>2，進行step 5；

Step 5：若scurr

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

設計兩種不同的鄰域NS1,NS2。

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

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

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

4 算例分析

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

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

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

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

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

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

5 結(jié) 論

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

1)文中研究成果適用于單線公交司機排班問題，未來研究還應進一步將問題擴展為多線路公交司機排班。

2)在實際公交公司運營時，也存在多種班制混合存在的情形，多種班制混合司機排班問題也將是一個值得研究的方向。

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