陳明明,?；菝?/p>

(蘭州交通大學(xué)交通運(yùn)輸學(xué)院,蘭州730070)

多車場(chǎng)公交乘務(wù)排班問(wèn)題優(yōu)化

陳明明,牛惠民*

(蘭州交通大學(xué)交通運(yùn)輸學(xué)院,蘭州730070)

公交乘務(wù)排班是公交智能化調(diào)度的重要研究?jī)?nèi)容.目前我國(guó)大多數(shù)城市排班主要采用人工經(jīng)驗(yàn),具有很大盲目性和繁瑣性,且排班結(jié)果多為單車場(chǎng)的乘務(wù)組排班方案.本文以班次時(shí)間接續(xù)、乘務(wù)組勞動(dòng)強(qiáng)度、車場(chǎng)能力等為約束條件,以最小化乘務(wù)組的車場(chǎng)駛?cè)?駛出成本、停留等待成本和空駛成本為目標(biāo)函數(shù),建立了多車場(chǎng)公交乘務(wù)排班問(wèn)題的數(shù)學(xué)模型.采用禁忌搜索算法求解模型,設(shè)計(jì)了初始生成解的啟發(fā)式方法,提出了基于有序序列的班次交換和插入策略進(jìn)行鄰域搜索.選取兩個(gè)車場(chǎng)范圍內(nèi)的四條公交線路為實(shí)例,進(jìn)行仿真測(cè)算和數(shù)據(jù)分析.結(jié)果表明,利用本文模型得到的乘務(wù)排班結(jié)果能有效地處理多車場(chǎng)公交乘務(wù)組跨線排班問(wèn)題.

城市交通;乘務(wù)排班;禁忌搜索算法;班次;多車場(chǎng)

1 引 言

乘務(wù)排班問(wèn)題作為城市公交調(diào)度問(wèn)題中的重要內(nèi)容,主要是對(duì)乘務(wù)組一天內(nèi)公交運(yùn)營(yíng)工作的安排.合理安排乘務(wù)排班計(jì)劃,不僅能夠有效利用人力資源,提高乘務(wù)工作效率,而且可以降低公交運(yùn)營(yíng)成本,提高公交管理水平,從而為公交管理部門決策提供科學(xué)依據(jù).

公交乘務(wù)排班問(wèn)題有較為廣泛的研究,出現(xiàn)了許多模型和求解方法.Simth等提出了基于集覆蓋問(wèn)題的乘務(wù)排班模型,并用整數(shù)線性規(guī)劃進(jìn)行求解[1].Ceder將乘務(wù)排班方法歸結(jié)為集分割問(wèn)題,使用最短路徑及匹配算法進(jìn)行求解[2].Lourenco等提出了一種多目標(biāo)的乘務(wù)排班模型,分別利用禁忌搜索和遺傳算法進(jìn)行求解[3].沈吟東等以乘務(wù)組數(shù)量最少和成本最低為目標(biāo)建立了優(yōu)化模型,設(shè)計(jì)了帶時(shí)間窗的多鄰域結(jié)構(gòu)及禁忌搜索算法[4].陳明明等以乘務(wù)組總空閑時(shí)間最小為目標(biāo),建立了多班型的乘務(wù)排班模型[5].上述研究大多考慮單車場(chǎng)的公交乘務(wù)排班問(wèn)題,較少對(duì)多車場(chǎng)公交乘務(wù)排班問(wèn)題進(jìn)行研究.

Boschetti等將多車場(chǎng)的車輛調(diào)度問(wèn)題和單車場(chǎng)的乘務(wù)排班問(wèn)題相結(jié)合,建立了基于集分割問(wèn)題的數(shù)學(xué)模型,但目標(biāo)函數(shù)中未考慮乘務(wù)組的空閑時(shí)間成本[6];Huisman等研究了多車場(chǎng)的車輛和人員統(tǒng)一調(diào)度模型,其中假定乘務(wù)組在執(zhí)行連續(xù)班次間,若有充足時(shí)間將返回車場(chǎng)[7],這一假設(shè)有悖于我國(guó)目前公交調(diào)度實(shí)際情況;Kliewer等人建立了帶有時(shí)間窗的多車場(chǎng)乘務(wù)調(diào)度模型[8],但模型未充分考慮公交車場(chǎng)的能力約束;鐘石泉等分析了多車場(chǎng)車輛調(diào)度中能力、時(shí)間窗、多車型等約束的處理方法[9],但沒(méi)有研究乘務(wù)組排班問(wèn)題對(duì)多車場(chǎng)公交調(diào)度的影響.

基于以上考慮,本文將車場(chǎng)、乘務(wù)組和班次相結(jié)合,對(duì)多車場(chǎng)下的公交乘務(wù)排班過(guò)程進(jìn)行闡述,提出相應(yīng)的乘務(wù)排班優(yōu)化模型和算法,求得最優(yōu)排班方案,從而為多車場(chǎng)公交乘務(wù)跨線排班問(wèn)題提供理論依據(jù).

2 問(wèn)題分析

本文以多條城市公交線路為研究對(duì)象,在公交運(yùn)營(yíng)時(shí)間內(nèi),每條線路一天所發(fā)班次的數(shù)量及每個(gè)班次在起始點(diǎn)的開(kāi)始時(shí)刻和終點(diǎn)站的結(jié)束時(shí)刻均已確定.所有班次的時(shí)間安排構(gòu)成了一天的公交運(yùn)行時(shí)刻表.乘務(wù)組人員和車輛固定,中途不更換車輛.乘務(wù)組可選擇從多個(gè)車場(chǎng)中的某一車場(chǎng)簽到出發(fā),執(zhí)行一系列班次任務(wù),最后返回同一車場(chǎng)進(jìn)行簽退,從而完成一天的運(yùn)營(yíng)工作任務(wù),如圖1所示.

圖1 乘務(wù)組運(yùn)營(yíng)工作示意圖Fig.1 The operation diagram of crew

多車場(chǎng)乘務(wù)組排班問(wèn)題就是根據(jù)一天給定的公交運(yùn)行時(shí)刻表和乘務(wù)規(guī)則等,考慮一定的優(yōu)化目標(biāo)和約束條件,對(duì)乘務(wù)組的駛?cè)腭偝鲕噲?chǎng)和執(zhí)行班次鏈等做出具體的安排,以確保有效地完成所有的班次任務(wù).

3 數(shù)學(xué)模型

3.1 符號(hào)及參數(shù)

定義建模所需的符號(hào)及參數(shù)如下:M為公交車場(chǎng)總數(shù)量;m為車場(chǎng)標(biāo)記;N為公交時(shí)刻表規(guī)定的一天班次數(shù)量;i為班次標(biāo)記;di為班次i在起始站的開(kāi)始時(shí)刻;ai為班次i在終點(diǎn)站的結(jié)束時(shí)刻;k為乘務(wù)組標(biāo)記;xim,k為0-1決策變量,若班次i由車場(chǎng)為m的乘務(wù)組k執(zhí)行,取值為1,否則為0;為0-1變量,若車場(chǎng)為m的乘務(wù)組k執(zhí)行班次任務(wù)i后,下一個(gè)執(zhí)行任務(wù)為班次j,取值為1,否則為0.

為研究方便,本文采用將車場(chǎng)序號(hào)與班次序號(hào)相對(duì)應(yīng)的方法,例如車場(chǎng)m的序號(hào)用N+m來(lái)表示。定義ti,j為乘務(wù)組從節(jié)點(diǎn)i到節(jié)點(diǎn)j的空駛時(shí)間,這里的節(jié)點(diǎn)可表示車場(chǎng)或班次的起訖點(diǎn),例如tN+2,3表示乘務(wù)組從車場(chǎng)2到班次3起始站A的空駛時(shí)間;t3,5為乘務(wù)組在執(zhí)行班次3和班次5之間的空駛時(shí)間;t5,N+2表示乘務(wù)組執(zhí)行完班次5后返回車場(chǎng)2的空駛時(shí)間,如圖2所示.

圖2 乘務(wù)組空駛時(shí)間的表示Fig.2 The expression of deadheading

3.2 約束條件

(1)班次唯一性約束.

對(duì)于任意一個(gè)班次,僅能由唯一車場(chǎng)的乘務(wù)組執(zhí)行且只執(zhí)行一次.

對(duì)于兩個(gè)接續(xù)班次,必須保證由同一乘務(wù)組執(zhí)行,故有

(2)班次時(shí)間接續(xù)約束.

在乘務(wù)組執(zhí)行的連續(xù)班次中,當(dāng)前班次的終點(diǎn)站與后一班次的起始站處于相同站點(diǎn)時(shí),該班次間不存在空駛;否則產(chǎn)生空駛.定義δi,j為0-1輔助變量,當(dāng)班次i與j之間有空駛,其值為1;否則其值為0.

式中 Start(i)表示班次i的起始站;End(i)表示班次i的終點(diǎn)站.

班次時(shí)間接續(xù)約束,即乘務(wù)組執(zhí)行的相鄰兩個(gè)班次中,后一班次的開(kāi)始時(shí)刻和前一班次的結(jié)束時(shí)刻相差應(yīng)不小于最小停留時(shí)間T0.對(duì)于有空駛現(xiàn)象的連續(xù)班次,還應(yīng)考慮空駛時(shí)間約束,則有

(3)乘務(wù)組勞動(dòng)強(qiáng)度約束.

乘務(wù)組勞動(dòng)強(qiáng)度約束,即每個(gè)乘務(wù)組一天的累計(jì)工作時(shí)間不應(yīng)超過(guò)規(guī)定的最長(zhǎng)工作時(shí)間T1,故有

(4)車場(chǎng)能力約束.

對(duì)于車場(chǎng)m,一天實(shí)際的乘務(wù)組數(shù)量取決于從該車場(chǎng)駛出的乘務(wù)組數(shù)量,計(jì)算如下

由于假設(shè)每個(gè)乘務(wù)組與車輛相對(duì)應(yīng),中途不更換車輛,因此,車場(chǎng)對(duì)公交車輛的能力約束也就轉(zhuǎn)換為對(duì)乘務(wù)組的能力約束,即

式中 ψm為車場(chǎng)m一天能安排的最大乘務(wù)組數(shù)量.

3.3 目標(biāo)函數(shù)

乘務(wù)組的成本包括班次運(yùn)營(yíng)成本、駛?cè)?駛出車場(chǎng)成本、班次間空駛成本和停留等待成本.乘務(wù)排班的優(yōu)化目標(biāo)是使乘務(wù)組的總成本最小.由于每個(gè)班次的運(yùn)營(yíng)時(shí)間固定,不同乘務(wù)排班方案中班次運(yùn)營(yíng)成本均相同,在優(yōu)化目標(biāo)中可忽略該成本因素.駛?cè)?駛出車場(chǎng)成本取決于乘務(wù)組從車場(chǎng)駛出到第一個(gè)班次起始站的空駛時(shí)間,以及從最后一個(gè)班次的終點(diǎn)站至駛?cè)胲噲?chǎng)的空駛時(shí)間.則對(duì)于車場(chǎng)m的第k個(gè)乘務(wù)組,其駛?cè)?駛出車場(chǎng)的空駛成本為

式中 ωd為乘務(wù)組的單位空駛成本;

對(duì)于車場(chǎng)m的第k個(gè)乘務(wù)組,班次間的總空駛成本為

停留等待時(shí)間是指乘務(wù)組執(zhí)行下一班次的開(kāi)始時(shí)刻與上一班次結(jié)束時(shí)刻的時(shí)間差。當(dāng)班次間存在空駛,應(yīng)減去空駛時(shí)間.則對(duì)于車場(chǎng)m的第k個(gè)乘務(wù)組,停留等待總成本為

式中 ωw為乘務(wù)組的單位停留等待成本.

基于以上分析,該數(shù)學(xué)模型的目標(biāo)函數(shù)為

4 算法設(shè)計(jì)

禁忌搜索算法是一種基于鄰域搜索的算法,通過(guò)引入一個(gè)靈活的存儲(chǔ)結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則來(lái)避免迂回搜索,并通過(guò)藐視準(zhǔn)則來(lái)赦免一些被禁忌的優(yōu)良狀態(tài),進(jìn)而保證多樣化的有效搜索以最終實(shí)現(xiàn)全局優(yōu)化.本文所構(gòu)建的多車場(chǎng)乘務(wù)排班模型是一個(gè)復(fù)雜的0-1規(guī)劃問(wèn)題,可用禁忌搜索算法進(jìn)行求解.算法的主要參數(shù)設(shè)計(jì)如下.

4.1 解的表示形式

乘務(wù)排班問(wèn)題的解,可采用二維整數(shù)型數(shù)組進(jìn)行編碼,其中行表示乘務(wù)組,第一列元素的值表示乘務(wù)組所屬車場(chǎng)編號(hào),其余列元素的值為乘務(wù)組的執(zhí)行班次,班次按自然數(shù)列升序排列.假定5個(gè)乘務(wù)組執(zhí)行18個(gè)班次,問(wèn)題解的表示形式如圖3所示.

圖3 解的表示形式Fig.3 The expression of solution

解碼是根據(jù)二維數(shù)組中數(shù)值對(duì)問(wèn)題的解進(jìn)行操作.以圖3中數(shù)據(jù)為例,由于所有乘務(wù)組共從兩個(gè)車場(chǎng)駛?cè)?駛出,第一個(gè)車場(chǎng)的乘務(wù)組數(shù)量為2,由序號(hào)為1和2的乘務(wù)組執(zhí)行,執(zhí)行班次分別為1-1-4-8-12和1-2-5-9,則變量.第二個(gè)車場(chǎng)乘務(wù)組的解碼方法同理可得,如圖4所示.

圖4 解碼示意圖Fig.4 The decoding of solution

4.2 初始解的生成

初始解決定算法搜索的起始點(diǎn),質(zhì)量?jī)?yōu)的初始解能使算法快速收斂到最優(yōu)解.在初始解生成過(guò)程中,考慮班次時(shí)間接續(xù)和乘務(wù)組勞動(dòng)強(qiáng)度約束,設(shè)計(jì)如下貪婪啟發(fā)式算法。

Step 1 初始化,令車場(chǎng)m的第k個(gè)乘務(wù)組所完成的班次集合

Step 2 確定執(zhí)行班次i的乘務(wù)組所對(duì)應(yīng)的車場(chǎng)序號(hào)

Step 3 確定執(zhí)行班次i的乘務(wù)組編號(hào)k和最大班次序號(hào).若sm＞ 0,則,轉(zhuǎn)Step 4;否則轉(zhuǎn)Step 6.

Step 4 班次時(shí)間接續(xù)檢驗(yàn),若di-ai′-δi′,i·,則轉(zhuǎn)Step 5;否則轉(zhuǎn)Step 6.

Step 5 乘務(wù)組勞動(dòng)強(qiáng)度檢驗(yàn),令車場(chǎng)m的第k個(gè)乘務(wù)組的總工作時(shí)間+ai-di,若Zm,k≤T1,則轉(zhuǎn)Step 7;否則轉(zhuǎn)Step 6.

Step 6 令sm←sm+1,k←sm,轉(zhuǎn)Step 7.

Step 8 若i＞N,算法終止,輸出結(jié)果;否則轉(zhuǎn)Step 2.

4.3 鄰域結(jié)構(gòu)

采用乘務(wù)組間班次的交換與插入策略.班次交換策略,即從乘務(wù)組1和乘務(wù)組2中各選一個(gè)班次進(jìn)行交換.例如將乘務(wù)組1:1-1-4-8-12的班次4和乘務(wù)組2:1-2-5-9的班次5進(jìn)行交換,可得到新解:乘務(wù)組1:1-1-5-8-12和乘務(wù)組2:1-2-4-9,如圖5所示.

班次插入策略,即將乘務(wù)組1的一個(gè)班次插入到乘務(wù)組2,插入位置依據(jù)乘務(wù)組2中班次序號(hào)升序排列.例如將乘務(wù)組1:1-1-4-8-12中的班次4插入到乘務(wù)組2:1-2-5-9中,可得新解:乘務(wù)組1:1-1-8-12和乘務(wù)組2:1-2-4-5-9,如圖6所示.交換或插入后的乘務(wù)排班結(jié)果若不滿足時(shí)間接續(xù)和勞動(dòng)強(qiáng)度約束,則不進(jìn)行該操作.

4.4 禁忌表、禁忌長(zhǎng)度、藐視準(zhǔn)則及終止條件

禁忌表中記錄的是變換(交換和插入)的節(jié)點(diǎn),禁忌長(zhǎng)度采用固定長(zhǎng)度.選取基于評(píng)價(jià)值的規(guī)則作為藐視準(zhǔn)則,即若出現(xiàn)一個(gè)解的目標(biāo)值好于前面任何一個(gè)最佳候選解,可特赦.終止準(zhǔn)則采用目標(biāo)控制原則,如果在一個(gè)給定步數(shù)內(nèi),當(dāng)前最優(yōu)值

沒(méi)有變換,終止計(jì)算.

圖5 班次交換策略Fig.5 Trips exchange strategy

圖6 班次插入策略Fig.6 Trips insert strategy

4.5 解的評(píng)價(jià)

為使算法在迭代過(guò)程中不斷搜索到更優(yōu)解,需進(jìn)行解的評(píng)價(jià).在評(píng)價(jià)中既要計(jì)算目標(biāo)函數(shù)值,又要考慮約束條件.由于初始解已滿足時(shí)間接續(xù)、勞動(dòng)強(qiáng)度約束,且在鄰域搜索過(guò)程中生成的新解也都滿足該約束,故在解的評(píng)價(jià)中僅需考慮車場(chǎng)能力約束.在計(jì)算適應(yīng)值時(shí),需對(duì)不滿足車場(chǎng)能力約束的解進(jìn)行懲罰,采用的適應(yīng)值函數(shù)為

5 算例研究

為研究方便,本文將一條公交線路按上下行方向劃分為兩條不同的公交線路,則起訖點(diǎn)A、B和B、C之間共有四條公交線路(L1、L2、L3、L4),如圖7所示.乘務(wù)組可從兩個(gè)車場(chǎng)中任一車場(chǎng)駛出至首發(fā)班次的起始站,從結(jié)束班次的終點(diǎn)站返回至出發(fā)車場(chǎng).四條公交線路一天共337個(gè)班次,每個(gè)班次所屬線路及開(kāi)始時(shí)刻已知,如表1所示.L1、L2線路的運(yùn)行時(shí)間均為25 min,L3、L4線路間的運(yùn)行時(shí)間均為30 min.站點(diǎn)A與站點(diǎn)B、站點(diǎn)C、車場(chǎng)1、車場(chǎng)2之間的空駛時(shí)間分別為10 min、16 min、 8 min、15 min;站點(diǎn)B與站點(diǎn)C、車場(chǎng)1、車場(chǎng)2之間的空駛時(shí)間分別為20 min、15 min、10 min;站點(diǎn)C與車場(chǎng)1、車場(chǎng)2之間的空駛時(shí)間分別為18 min、12 min.

圖7 多車場(chǎng)公交線路運(yùn)行示意圖Fig.7 Bus lines with multiple depots

從表1可以看出,不同線路一天所發(fā)班次總數(shù)差異較大,線路L1全天共有107個(gè)班次,且在早高峰(7:00-9:00)平均發(fā)車間隔為5 min;線路L2共有108個(gè)班次,在晚高峰(18:00-20:00)平均發(fā)車間隔為5 min;線路L3和L4全天分別有59和63個(gè)班次,平均發(fā)車間隔分別為15 min和14 min.

車場(chǎng)1和車場(chǎng)2一天能安排的最大乘務(wù)組數(shù)量分別為10和25,乘務(wù)組的單位空駛成本和單位停留等待成本分別為2元/min和0.4元/min.乘務(wù)組班次間的最小停留時(shí)間為3 min,累計(jì)工作時(shí)間不超過(guò)480 min.禁忌搜索算法的參數(shù)設(shè)置為:禁忌長(zhǎng)度為6,最大迭代次數(shù)為800,懲罰因子取值為10 000.應(yīng)用VC++編程得到最優(yōu)解如表2所示.

表1 班次開(kāi)始時(shí)刻表及所屬線路Table 1 Departure time and line number of trips

表2 乘務(wù)排班優(yōu)化方案Table 2 The optimal result of crew scheduling

表3 高峰時(shí)段乘務(wù)組空駛結(jié)果Table 3 The deadheading trips during peak hours

根據(jù)表2中的乘務(wù)排班優(yōu)化方案,可推算出早晚高峰時(shí)段乘務(wù)組空駛班次結(jié)果,如表3所示.在早高峰時(shí)段,L1線路(A→B)發(fā)車間隔較小,在乘務(wù)組數(shù)量有限的情況下,勢(shì)必需要其余線路乘務(wù)組空駛到L1線路的起始站A,本例中共有5個(gè)空駛班次分別從站點(diǎn)B和站點(diǎn)C到達(dá)站點(diǎn)A,從而在不需增加乘務(wù)組總數(shù)的前提下,解決了L1線路早高峰的運(yùn)力緊張問(wèn)題;在晚高峰時(shí)段,L2線路(B→A)發(fā)車頻率較大,則需其余線路乘務(wù)組空駛到L2線路的起始站B,而此時(shí)L1線路(A→B)發(fā)車間隔較大,通過(guò)7個(gè)空駛班次從L1線路的始發(fā)站A到達(dá)站點(diǎn)B,有效地解決了L2線路晚高峰的供需不平衡問(wèn)題.

表4 禁忌搜索算法與貪婪算法計(jì)算結(jié)果對(duì)比Table 4 Comparison of computing results using tabu

表4對(duì)比了運(yùn)用禁忌搜索算法和貪婪算法計(jì)算得到的乘務(wù)排班方案成本,顯然禁忌搜索算法得到的總成本要遠(yuǎn)低于貪婪算法的總成本.貪婪算法結(jié)果中班次間空駛成本占總成本的62.7%,這是由于排班方案僅考慮了班次接續(xù)約束和乘務(wù)組勞動(dòng)強(qiáng)度約束,未考慮不同成本類型對(duì)目標(biāo)值的影響.禁忌搜索算法得到的排班優(yōu)化方案,停留等待成本占乘務(wù)組總成本的70.2%,空駛成本僅占9.8%.該算法通過(guò)班次交換策略改變了乘務(wù)組所執(zhí)行班次鏈的結(jié)構(gòu),使乘務(wù)組班次間的空駛數(shù)量減少,從而有效降低了班次間的總空駛成本;班次插入策略改變了乘務(wù)組所執(zhí)行班次數(shù)量,優(yōu)化了乘務(wù)組駛?cè)?駛出車場(chǎng)成本和停留等待成本,避免算法陷入局部最優(yōu).因此通過(guò)禁忌搜索算法可以進(jìn)一步優(yōu)化排班方案,提高解的質(zhì)量,驗(yàn)證了該算法的有效性.

6 研究結(jié)論

本文以公交區(qū)域調(diào)度中的車場(chǎng)、乘務(wù)組和班次為研究對(duì)象,考慮了車場(chǎng)能力、乘務(wù)組勞動(dòng)強(qiáng)度、班次時(shí)間接續(xù)等約束,以最小化乘務(wù)組的駛?cè)?駛出成本、空駛成本、停留等待成本為目標(biāo)函數(shù),建立了多車場(chǎng)下公交乘務(wù)排班模型及相應(yīng)的禁忌搜索算法,并運(yùn)用實(shí)例進(jìn)行仿真計(jì)算.結(jié)果表明,該模型適用于客流具有明顯潮汐特性的公交線路,可以有效地解決多車場(chǎng)約束下乘務(wù)組跨線排班問(wèn)題.此外,模型通過(guò)整合不同車場(chǎng)的車輛和乘務(wù)組資源,在一定區(qū)域范圍內(nèi)將多個(gè)車場(chǎng)的車輛和乘務(wù)組人員相協(xié)調(diào),高效地完成多條公交線路的所有班次任務(wù),實(shí)現(xiàn)資源的有效配置和充分利用.考慮帶有時(shí)間窗和不同班型條件下的多車場(chǎng)公交乘務(wù)組排班問(wèn)題,將是下一步研究的方向.

[1] Smith B M,Wren A.A bus crew scheduling system using a set covering formulation[J].Transportation Research,1988(22A):97-108.

[2] Avishai Ceder.Public transit planning and operation——Theory,modelingandpractice[M].London: Butterworth-Heinemann,2007.

[3] Lourenco H R,Paixao J P,Portugall R.Multiobjective metaheuristics for the bus-driver scheduling problem [J].Transportation Science,2001,35(3):331-343.

[4] 沈吟東,倪郁東.含時(shí)間窗的司售員調(diào)度模型及多鄰域結(jié)構(gòu)設(shè)計(jì)[J].華中科技大學(xué)學(xué)報(bào),2008(12): 31-34.[SHEN Y D,NI Y D.Model for crew scheduling with time windows and multi-neighborhood structures[J].Journal of Huazhong Univ.of Sci.& Tech.,2008(12):31-34.]

[5] Mingming Chen,Huimin Niu.A model for bus crew scheduling problem with multiple duty types[J]. Discrete Dynamics in Nature and Society,2012:1-12.

[6] Boschetti M A,Mingozzi A.An exact algorithm for the simplified multiple depot crew scheduling problem[J]. Annals of Operations Research,2004(127):177-201.

[7] Dennis Huisman,Richard Freling,P M Wagelmans. Multiple-depot integrated vehicle and crew scheduling [J].Transportation Science,2005(39):491-502.

[8] Natalia Kliewer,Bastian Amberg,Boris Amberg. Multiple depot vehicle and crew scheduling with time windows for scheduled trips[J].Public Transport, 2012,3(3):213-244.

[9] 鐘石泉,賀國(guó)光.多車場(chǎng)有時(shí)間窗的多車型車輛調(diào)度及其禁忌算法研究[J].運(yùn)籌學(xué)學(xué)報(bào),2005(4): 67-73.[ZHONG S Q,HE G G.Study on multi-depot vehicle scheduling problem with time windows and multi-type vehicle limits and its tabu search algorithm [J].OR Transactions,2005(4):67-73.]

An Optimization Model for Bus Crew Scheduling with Multiple Depots

CHEN Ming-ming,NIU Hui-min
(School of Traffic and Transportation,Lanzhou Jiaotong University,Lanzhou 730070,China)

Crew scheduling is an important element of intelligent transit dispatching.The scheduling methods of many cities in China are mainly based on artificial experience with great blindness and tediousness.Moreover,the scheduling results are mostly focused on the field of crew scheduling with a single depot.A mathematical model of multiple depots crew scheduling is formulated with the time shift of trips, work intensity for crew,capacity of depots as constrains,and with the minimum cost of pull-in/pull-out time,waiting time and deadheading as the objective function.The tabu search algorithm is used to solve the proposed model,and a heuristic algorithm is designed to generate the initial solution.A neighborhood search method with trip exchange and insert strategy is also presented based on the ordered sequence.Taking four bus lines with two depots as examples,the proposed model can effectively solve the crew scheduling problem with multiple depots which allows vehicles and crew running at the cross-lines.

urban traffic;crew scheduling;tabu search algorithm;trips;multiple depots

U491

: A

U491

A

1009-6744(2013)05-0159-08

2013-04-10

2013-05-09錄用日期:2013-05-20

國(guó)家自然科學(xué)基金項(xiàng)目(71261014).

陳明明(1982-),男,山西霍州人,博士生.

*通訊作者:hmniu@mail.lzjtu.cn