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

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

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

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

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

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

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

1 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

l;[t2start,t2

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

l

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

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

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

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

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

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

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

3.2 候選班次集J的生成

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

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

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

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

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

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

4 案例計(jì)算

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

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

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

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

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

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

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

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

5 研究結(jié)論

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

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

[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]沈吟東,倪郁東.含時(shí)間窗的司售員調(diào)度問(wèn)題建模及多鄰域結(jié)構(gòu)設(shè)計(jì)[J].華中科技大學(xué)學(xué)報(bào),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

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

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

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

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