帶中式用餐約束的乘務(wù)調(diào)度問題

陳仕軍,沈吟東,蘇 璇,陳賀命

(華中科技大學(xué)控制科學(xué)與工程系,武漢430074)

帶中式用餐約束的乘務(wù)調(diào)度問題

陳仕軍,沈吟東*,蘇 璇,陳賀命

(華中科技大學(xué)控制科學(xué)與工程系,武漢430074)

有效的乘務(wù)調(diào)度能夠為公交企業(yè)帶來巨大的成本節(jié)約,但是,公交乘務(wù)調(diào)度問題因受制于一系列勞動法規(guī)的約束變得十分復(fù)雜.我國公交普遍存在“中式用餐”約束,進(jìn)一步加大了問題的復(fù)雜性,使西方主流調(diào)度系統(tǒng)在國內(nèi)實(shí)施面臨困難.本文基于“生成與選擇”方法解決乘務(wù)調(diào)度問題,關(guān)鍵在于“生成”階段處理“中式用餐”難題;利用“中式用餐”約束和乘務(wù)問題特點(diǎn),設(shè)計一種基于啟發(fā)式規(guī)則的換班機(jī)會篩選方法;在所選換班機(jī)會集合的基礎(chǔ)上構(gòu)造能滿足“中式用餐”約束的潛在乘務(wù)班次集合.對實(shí)際公交乘務(wù)調(diào)度問題中的12組實(shí)例進(jìn)行測試,表明本文方法不僅能處理 “中式用餐”約束,而且能極大減少所求問題的規(guī)模,因此適用于解決大規(guī)模的帶有“中式用餐”約束的乘務(wù)調(diào)度問題.

城市交通;乘務(wù)調(diào)度;中式用餐;啟發(fā)式;班次生成

1 引 言

乘務(wù)調(diào)度問題是公共交通領(lǐng)域中研究的重要難題之一,屬于世界公認(rèn)的NP難題[1].編制優(yōu)化的乘務(wù)調(diào)度方案,可以幫助公交企業(yè)節(jié)約成本、提高乘務(wù)資源效益.因此,自上世紀(jì)六十年代起,西方發(fā)達(dá)國家就開始利用計算機(jī)進(jìn)行公共交通乘務(wù)調(diào)度問題的研究,至今已有許多解決方法和技術(shù)問世[2],并取得成功應(yīng)用.其中,基于整數(shù)線性規(guī)劃(ILP)的方法仍占主導(dǎo)地位,其應(yīng)用也最為廣泛[3].

經(jīng)典的ILP方法包括一個“生成班次”和一個“選擇班次”的過程,因此,又被歸為“生成與選擇”方法[4].該類方法首先要根據(jù)勞動法規(guī)等約束生成一個大的乘務(wù)班次(簡稱“候選班次”)集合;然后基于ILP方法從中選擇一個最優(yōu)的班次子集覆蓋全部車輛工作.盡管該方法已有許多成功應(yīng)用[4],但面對一些特殊問題時有如下困難:一方面,當(dāng)乘務(wù)調(diào)度問題具有復(fù)雜的勞動法規(guī)和約束(如本文的“中式用餐”)時,生成滿足勞動法規(guī)和約束的全部候選班次會很耗時;另一方面,當(dāng)乘務(wù)調(diào)度問題規(guī)模較大(現(xiàn)實(shí)問題基本都屬于大規(guī)模問題)時,全部候選班次的數(shù)量通常很大(可能是天文數(shù)字),使得“選擇”階段超出ILP的求解能力.目前,大多數(shù)研究側(cè)重于解決后一問題,即擴(kuò)大ILP的求解能力,例如典型的方法有列生成法[5]、元啟發(fā)式方法[6]等.然而,對于如何生成潛在班次集合,一般描述比較簡單或假定其已經(jīng)存在.實(shí)際上,潛在班次的構(gòu)造過程依賴于具體的勞動法規(guī)和約束,特別是在求解具有復(fù)雜法規(guī)和約束的乘務(wù)調(diào)度問題時,生成全部潛在班次往往非常費(fèi)時,有時甚至占據(jù)總求解時間的85%以上[7].因此,研究有效構(gòu)造潛在班次集合的方法,使其滿足各種勞動法規(guī)和約束(尤其是復(fù)雜約束),是應(yīng)用ILP方法解決乘務(wù)調(diào)度問題的首要工作和基礎(chǔ).

我國的乘務(wù)調(diào)度問題除了具有一般乘務(wù)調(diào)度問題的常見勞動法規(guī)和約束外(例如總工時、連續(xù)工時等的限制),還有一些具有普遍性的特色約束.其中,要求有“中國式”的固定時間段用餐(簡稱“中式用餐”)這一特色約束[8],使其比已有的乘務(wù)調(diào)度問題更加復(fù)雜,進(jìn)而,使得在西方國家得到成功應(yīng)用的各種乘務(wù)調(diào)度方法在國內(nèi)實(shí)施面臨求解困難.本文將采取“生成與選擇”的方法解決我國的具有“中式用餐”約束的乘務(wù)調(diào)度問題,主要是在“生成班次”階段來處理復(fù)雜的“中式用餐”約束.先通過分析“中式用餐”的特點(diǎn),結(jié)合相關(guān)的勞動法規(guī)等約束和乘務(wù)問題特征,設(shè)計出基于啟發(fā)式規(guī)則的換班機(jī)會篩選方法;再利用篩選出的換班機(jī)會集合生成所有潛在班次.本文方法不僅能滿足“中式用餐”的約束要求,而且能極大減小所求問題的規(guī)模,有利于解決大規(guī)模的“中式用餐”乘務(wù)調(diào)度問題.

2 乘務(wù)調(diào)度問題

公共交通乘務(wù)調(diào)度問題就是合理安排一組乘務(wù)班次來完成一日內(nèi)的全部車輛運(yùn)營任務(wù).單個車輛的運(yùn)營任務(wù)通常是從車場出發(fā),歷經(jīng)若干趟在線路上的運(yùn)營,最終返回車場,稱為一個車輛運(yùn)營任務(wù)塊(Block).在每輛車的運(yùn)營線路上一般會有一個或多個指定的可供乘務(wù)員換班的地點(diǎn),稱為“換班點(diǎn)”;換班點(diǎn)與車輛到達(dá)該地點(diǎn)的時間結(jié)合起來就構(gòu)成一個“換班機(jī)會(RO)”;在任意一個換班機(jī)會,乘務(wù)員都可以(但不一定)換班;在兩個連續(xù)的“換班機(jī)會”之間,乘務(wù)員通常是不允許換班的,這段連續(xù)的工作被稱為“最小值乘段(Piece)”;一個或幾個連續(xù)的“最小值乘段”可以構(gòu)成“連續(xù)值乘段(Spell)”.一個或者多個“連續(xù)值乘段”進(jìn)行合理組合,可構(gòu)成一個乘務(wù)班次,簡稱“班次(Shift)”,也就是乘務(wù)員一天的工作安排,通常從場站簽到開始到場站簽退結(jié)束[4,9].根據(jù)“班次”的特點(diǎn),一般可以將其劃分成整班、大單班、單班3種類型.整班(又稱連續(xù)班),期間有一個短暫的時間供乘務(wù)員用餐和休息;大單班的乘務(wù)員上班時間跨度(從簽到至簽退)比較長,兩個連續(xù)值乘段間有一段較長休息時間;單班只包含一個連續(xù)乘務(wù)段的班次.圖1描述了部分與乘務(wù)調(diào)度相關(guān)的概念.

乘務(wù)調(diào)度是一個極為復(fù)雜的組合優(yōu)化問題,其目標(biāo)是采用最少數(shù)量和最小運(yùn)營成本的乘務(wù)班次集合去執(zhí)行完所有車輛任務(wù),且所有乘務(wù)班次需要同時滿足運(yùn)營企業(yè)和國家規(guī)定的相關(guān)勞動法規(guī)和約束.對于一般的乘務(wù)調(diào)度問題,其乘務(wù)班次需要滿足如下約束[9-11]:

(1)乘務(wù)員連續(xù)值乘時長不可超過規(guī)定的最長時長Tmax和最短時長Tmin;

(2)班次的總工時不可超過相應(yīng)班型所規(guī)定的最長總工時TSmax與最短總工時TSmin;

(3)班次的有效工時不可超過相應(yīng)班型所規(guī)定的最長有效工時TWmax與最短有效工時TWmin;

(4)整班型班次的用餐時間不得超出規(guī)定的用餐最長時間TBmax與最短時間TBmin;

(5)大單班型班次中兩個連續(xù)值乘段間的休息時間不得少于規(guī)定的最短休息時間TBSmin.

圖1 車輛任務(wù)和乘務(wù)班次Fig.1 Vehicle work and crew shift

式中 xj為決策變量,cj是班次j的成本;式(1)是目標(biāo)函數(shù);式(2)表示任意最小值乘段至少被一個被選擇班次所覆蓋.

由模型可以看出,乘務(wù)調(diào)度問題的規(guī)模與n(即候選班次的數(shù)量)的大小直接相關(guān),而生成候選班次的數(shù)量直接由RO數(shù)量決定.假設(shè)有p輛車的運(yùn)營計劃,平均每輛車的運(yùn)營計劃中含有r個RO(含有r-1個最小值乘段).若暫不考慮班次的合法性約束,則所有車輛運(yùn)行計劃可以生成p×r× ( r-1 )/2個連續(xù)值乘段.當(dāng)考慮生成最多包含k個連續(xù)值乘段的班次時,理論上我們可以算出可能的候選班次數(shù)量

當(dāng)k較大時,候選班次的數(shù)量n以RO的數(shù)量r呈高次多項式級增長,給ILP模型求解帶來極大困難.因此,在不損失最優(yōu)解前提下盡可能減小候選RO數(shù)量r是解決該問題的關(guān)鍵.下文將基于“中式用餐”約束和乘務(wù)問題特點(diǎn)設(shè)計一些啟發(fā)式策略,篩選出一些“好”的RO作為候選換班機(jī)會集合,從而縮小候選乘務(wù)班次集J的規(guī)模.

3 “中式用餐”約束下的乘務(wù)班次集生成

3.1 換班機(jī)會的選擇

由于“中式用餐”約束要求用餐時間在規(guī)定時間段[tstart,tend]內(nèi)進(jìn)行,故規(guī)定[tstart,tend]內(nèi)的任何RO都可能被用作換班,所以應(yīng)保留這些RO;另一方面,因為用餐必須要換班,且在[tstart,tend]內(nèi)進(jìn)行,故用[tstart,tend]外的大部分換班機(jī)會可能不會被使用,因此可以剔除其中一些“不好”或“不合理”的RO,以縮小問題的規(guī)模.本文在用餐規(guī)定的時間段[tstart,tend]外,根據(jù)乘務(wù)調(diào)度問題的本身特點(diǎn)選擇出一些“好”或“合理”的RO,剔除剩余的RO,使得生成的班次既能滿足“中式用餐”約束,且不會損失關(guān)鍵的RO.選擇一些“好”的RO時,主要基于乘務(wù)問題的如下特點(diǎn):乘務(wù)人員在執(zhí)行車輛運(yùn)營任務(wù)時,一般應(yīng)盡可能持續(xù)較長的工作,以免造成多次換班,從而影響值乘效率;特別,車輛出車場后的工作,一般由同一乘務(wù)員執(zhí)行盡可能長的任務(wù)后,才考慮換班;同理,返回車場的最后一段值乘任務(wù)也盡可能長,以提高工作效率.

首先,對給定時間區(qū)間[t1,t2]內(nèi)的車輛任務(wù),給出一個簡單啟發(fā)式RO選擇方法(SHA),使所生成連續(xù)值乘段盡可能長.記[t1,t2]內(nèi)最早的換班機(jī)會為rc(對應(yīng)時間tc),SHA如下:

Step 1 若t2-tc≤Tmax,則停止;

Step 2 從rc開始,向前尋找新的換班機(jī)會rf(對應(yīng)時間tr),使得rc與rf連接構(gòu)成的連續(xù)值乘段盡可能長,且滿足tr-tc≤Tmax;

Step 3 選擇rf,記當(dāng)前換班機(jī)會(rf)為rc,返回Step1.

現(xiàn)對各個車輛任務(wù)分別選擇出一些RO,以用作生成潛在班次集J.記車輛從車場出發(fā)時間ts,返回車場的時間t,中餐時間段[t1,t1],晚餐時

estartend間段[t2start,t2end],具體的篩選RO策略如下.

(1)選擇車輛從車場出發(fā)和返回車場的RO (必用換班機(jī)會,即班次開始和結(jié)束RO),如圖2所示.圖2中,黑色圓點(diǎn),表示選擇的RO;白色圓點(diǎn)表示沒有被選擇的RO;虛線表示未畫出的車輛運(yùn)營任務(wù)段.

圖2 選擇車輛運(yùn)營任務(wù)的始末ROFig.2 Selecting the start RO and the end RO

(2)選擇規(guī)定用中餐時間段[t1,t1]和晚餐

startend時間段[t2,t2]內(nèi)的所有RO,如圖3所示.圖3

startend中的黑圓點(diǎn)表示被選擇的RO,白圓點(diǎn)表示未被選擇RO.

圖3 選擇用餐時間段內(nèi)的所有ROFig.3 Selecting all the ROs in meal-break time

由于只依賴策略(1)、策略(2)所選擇的RO集合,無法保證所有車輛任務(wù)被分割成合法的連續(xù)值乘段,因此還需根據(jù)策略(3)選擇一些其他RO.

(3)選擇用餐時間段[t1,t1]、[t2,t2]以

startendstartend外的其他RO,確保所有車輛任務(wù)能形成連續(xù)值乘段(根據(jù)參數(shù)Tmax).

不妨假定車輛運(yùn)營任務(wù)包含中餐和晚餐時間段(只包含1個中餐或晚餐時間段的方法類似),記[t1start,t1

end]內(nèi)最早和最晚RO的時間分別為t1f, t1

l;[t2start,t2

end]內(nèi)最早和最晚RO的時間分別為t2f, t2.分以下三種情況,依次選擇RO

l

① 當(dāng)t1f-ts＞Tmax時,則從 t1f向后逐個尋找新RO(對應(yīng)時間tr),直到tr-ts≤Tmax;選擇時間段[tr,t1start]內(nèi)的所有RO,如圖4所示.

圖4 向后逐個尋找選擇ROFig.4 Selecting the ROs backward

② 當(dāng)te-t2l＞Tmax時,則從t2l向前逐個尋找新RO(對應(yīng)時間tr),直到te-tr≤Tmax;選擇時間段[t2end,tr]內(nèi)的所有RO,如圖5所示.

③ 當(dāng)t2f-t1l＞Tmax時,則對[t1l,t2f]內(nèi)的車輛任務(wù)利用SHA選擇RO,如圖6所示.

圖6 利用SHA選擇ROFig.6 Selecting the ROs by using SHA

(4)若車輛任務(wù)計劃不包含用餐時間段,則在[ts,te]時間段內(nèi)應(yīng)用SHA選擇RO.

通過以上RO的選擇過程,形成可能用到的RO集合R.

3.2 候選班次集J的生成

基于3.1節(jié)篩選出的RO集合R,根據(jù)如下步驟形成候選班次集J0:

Step 1 根據(jù)R中的換班機(jī)會,對所有車輛任務(wù)集進(jìn)行切割劃分,以形成最小值乘段集(Piece集);

Step 2 對多個相鄰的最小值乘段進(jìn)行連接(要求相連的總長度不超過Tmax),形成所有可行連續(xù)值乘段集(Spell集);

Step 3 對所有連續(xù)值乘段按起始時間排序;

Step 4 對排序后的連續(xù)值乘段集,通過完全枚舉法進(jìn)行連接,并判斷是否滿足第2節(jié)中的乘務(wù)約束(2)-(5),得到候選班次集J0.

Step 5 對J0剔除不滿足中式用餐約束的班次,即刪除不滿足約束(6)的班次,得到班次集J.

4 案例計算

生成候選班次集J之后,若|J|不大(例如小于2 000),則可以利用著名數(shù)學(xué)優(yōu)化軟件ILOG Cplex求解式(1)、式(2)對應(yīng)的ILP模型[12];但當(dāng)候選班次集規(guī)模|J|較大時,還需要利用列生成法[10]、元啟發(fā)式方法[6]等大規(guī)模優(yōu)化方法求解.主要測試在生成班次滿足“中式用餐”約束條件下,篩選換班機(jī)會方法對生成乘務(wù)班次集規(guī)模|J|的影響.

通過測試12組實(shí)際數(shù)據(jù)來說明本文方法的有效性,測試數(shù)據(jù)主要來自海口市、武漢市和十堰市的部分公交線路行車方案.相關(guān)乘務(wù)約束所采用的參數(shù)設(shè)置如下:乘務(wù)員的連續(xù)值乘時間不得低于2 h且不超過5 h;乘務(wù)員的實(shí)際值乘時間不得少于6.5 h且不超過8 h,其中單班的值乘時間不低于2 h且不超過5 h;中餐時間段:11:00-13:00,晚餐時間段:18:00-20:00;整班用餐時間不得低于30 min,大單班的休息時間不得低于4 h.

主要考慮和比較兩類潛在班次集生成方法:

(1)傳統(tǒng)的考慮所有換班機(jī)會的方法(一般方法);

(2)本文篩選換班機(jī)會的方法(本文方法).

計算和測試兩類不同方法下 Piece、Spell及Shift的數(shù)量變化.特別是Shift數(shù)量直接影響到求解乘務(wù)調(diào)度集覆蓋模型的求解難度.相關(guān)的實(shí)驗結(jié)果如表1所示.在表1中,12個測試案例按Block數(shù)量從小到大排列;ro、piece、spell和shift,各自表示該方法下ro、piece、spell和最終生成潛在班次的數(shù)量.RPD表示利用本文方法后潛在班次數(shù)量相對于一般方法班次數(shù)量減少的百分比,計算為

表1 潛在班次集生成實(shí)驗結(jié)果Table 1 Experimental results for generation of potential shift set

從表1可知,應(yīng)用本文所提篩選換班點(diǎn)方法后,很大程度地減少了ro、piece、spell及候選班次的數(shù)量.特別是,篩選換班機(jī)會后,候選班次數(shù)量平均減少了63.9%.因此,有利于求解更大規(guī)模的問題.

5 研究結(jié)論

本文提出了一種能夠有效處理“中式用餐”約束且能極大縮小問題規(guī)模的乘務(wù)候選班次集的生成方法.“中式用餐”約束與西方國家的用餐約束存在很大差異,因此,使得現(xiàn)有的基于ILP的方法無法直接求解.本文通過在“生成”階段預(yù)先生成滿足“中式用餐”約束的候選班次集合,不僅使得傳統(tǒng)的ILP方法可以用以求解具有中國特色的乘務(wù)調(diào)度問題,而且,還能有效利用“中式用餐”約束,達(dá)到降低候選班次集規(guī)模的目的.總之,本文所提的乘務(wù)班次生成方法不僅有助于解決帶有“中式用餐”的乘務(wù)調(diào)度問題,而且有助于擴(kuò)大基于ILP的乘務(wù)調(diào)度方法的求解規(guī)模.

雖然本文方法能夠有效降低問題的規(guī)模,但對于大規(guī)模的乘務(wù)調(diào)度問題(如本文所測試的多數(shù)案例),潛在班次數(shù)量仍然很大,直接利用整數(shù)規(guī)劃軟件(如ILOG Cplex)求解ILP模型仍然存在時間上的困難.因此,需要進(jìn)一步研究智能優(yōu)化方法或列生成技術(shù)以解決更大規(guī)模的乘務(wù)調(diào)度問題.

[1]Wren A,Fores S,Kwan A S K,et al.A flexible system for scheduling drivers[J].Journal of Scheduling, 2003,6(5):437-55.

[2]Hickman M,Mirchandani P.Computer-aided systems in public transport[C]//Lecture Notes in Economics and Mathematical Systems.Berlin:Springer,2008.

[3]JütteS, Thonemann U W. Divide-and-price: A decomposition algorithm for solving large railway crew scheduling problems[J]. European Journal of Operational Research,2012,219(2):214-223.

[4]Shen Y,Kwan R S K.Tabu search for driver scheduling [C].Lecture Notes in Economics and Mathematical Systems,Berlin:Springer,2001(505):121-135.

[5]Fores S.Column generation approaches to bus driver scheduling[D].University of Leeds,1996.

[6]Li J,Kwan R S K.A fuzzy genetic algorithm for driver scheduling[J]. European JournalofOperational Research,2003,147(2):334-344.

[7]Shen Y.Tabu search for bus and train driver scheduling with time windows[D].University of Leeds,2001.

[8]Shen Y,Xia J.Integrated bus transit scheduling for the Beijing bus group based on a unified mode of operation[J].International Transactions in Operational Research,2009,16(2):227-242.

[9]沈吟東,倪郁東.含時間窗的司售員調(diào)度問題建模及多鄰域結(jié)構(gòu)設(shè)計[J].華中科技大學(xué)學(xué)報,2008, 36(12):31-34.[SHEN Y D,NI Y D.Model for crew scheduling with time windows and multineighborhood structures[J].Journal of Huazhong University of Science and Technology(Natural Science Edition),2008,36(12):31-34.]

[10]Mesquita M,Paias A.Set partitioning and coveringbased approaches for the integrated vehicle and crew scheduling problem[J].Computers& Operations Research,2008,35(5):1562-1575.

[11]Shen Yindong.Two neighbourhood search approaches: 2-opt heuristics and tabu search for bus and train driver scheduling[M].Beijing:Science Press,2003.

[12]Shen Y,Chen S,Su X.Rail crew scheduling based on a pooling mode for high speed passenger lines[C]// Proceedingsof2010 InternationalConference on Logistics Engineering and Intelligent Transportation Systems,2010.

A Crew Scheduling with Chinese Meal Break Rules

CHEN Shi-jun,SHEN Yin-dong,SU Xuan,CHEN He-ming
(Department of Control Science and Engineering,Huazhong University of Science and Technology,Wuhan 430074,China)

An efficient crew scheduling can significantly reduce the operational cost for transit enterprises. However,the crew scheduling problem,known to be NP-hard,is complicated by the fact that there are many restrictions on the shift generation.Moreover,there are some special requirements in China,for example, meal break is normally required to be taken during the conventional time ranges for lunch or dinner,which is called a Chinese meal break rule to distinguish from the western ones.It also makes the existing crew scheduling approaches encountering difficulties.On the basis of the“generate and select”approach to solve the crew scheduling problem,this paper proposes an approach to handling the Chinese meal break rule in the phase of“generate”.Taking advantages of the characteristics of Chinese meal break rule and problem domain knowledge,a heuristic-based approach is proposed to select some promising relief opportunities (ROs).A shift generation approach is then devised to generate a large set of potential shifts that satisfy the Chinese meal break rule.Experimental results from 12 groups of real-world problem instances demonstrate the success of the proposed approach,which can greatly reduce the number of potential shifts generated. Therefore,it is suggested that the proposed approach be used to solve the large scale crew scheduling problems with Chinese meal break rule.

U268.6

A

U268.6

A

1009-6744(2013)02-0090-06

2012-10-11

2012-11-20錄用日期:2012-12-07

國家自然科學(xué)基金(70971044,71171087).

陳仕軍(1980-),男,湖北襄陽人,博士生.

*通訊作者:yindong@hust.edu.cn.

Key words:urban transportation;crew scheduling;Chinese meal break;heuristics;shift generation