孫　博　魏　明

(南通大學(xué)交通學(xué)院　江蘇 南通 226019)

?

考慮駕駛員對(duì)線(xiàn)路熟悉程度的區(qū)域公交乘務(wù)排班模型*

孫博魏明▲

(南通大學(xué)交通學(xué)院江蘇 南通 226019)

摘要在允許駕駛員跨線(xiàn)調(diào)度情形下，提出了一種考慮駕駛員對(duì)線(xiàn)路熟悉程度的區(qū)域公交乘務(wù)排班優(yōu)化模型，滿(mǎn)足駕駛員的工作時(shí)間窗、中途休息、用餐時(shí)間等現(xiàn)實(shí)因素，以最小化駕駛員成本、正常班及加班費(fèi)用為目標(biāo)函數(shù)，編制一個(gè)最佳公交乘務(wù)排班方案。根據(jù)問(wèn)題特征，設(shè)計(jì)求解該問(wèn)題的人工免疫算法，定義了抗體、啟發(fā)式種群算法、適應(yīng)度函數(shù)、免疫操作等。最后，結(jié)合算例分析，比較任意駕駛員對(duì)不同線(xiàn)路的偏好如何影響調(diào)度結(jié)果，仿真表明：隨著駕駛員的熟悉線(xiàn)路程度增加，乘務(wù)排班的費(fèi)用逐漸減少，雖然其調(diào)度成本比現(xiàn)有模型的高很多，但是該模型比較符合實(shí)際。

關(guān)鍵詞交通管理；乘務(wù)員排班；多車(chē)場(chǎng)；駕駛員對(duì)線(xiàn)路的熟悉程度；人工免疫算法

0引言

在給定時(shí)刻表基礎(chǔ)上，公交乘務(wù)排班(crew scheduling problem, CSP)主要解決在考慮工作制、中途休息及中午晚上用餐等因素，如何合理安排司機(jī)駕駛不同車(chē)輛去執(zhí)行班次任務(wù)，是企業(yè)日常管理最關(guān)注工作之一，其方案的好壞直接決定了公交運(yùn)營(yíng)成本。CSP是一個(gè)NP難題[1]，在允許駕駛員跨線(xiàn)調(diào)度情形下，該問(wèn)題可劃分為單車(chē)場(chǎng)CSP(single depot crew scheduling problem，SDCSP)和多車(chē)場(chǎng)CSP(multiple depot crew scheduling problem，MDCSP)，考慮不同線(xiàn)路在各時(shí)段的發(fā)車(chē)不均衡性，后者比前者更容易節(jié)省運(yùn)營(yíng)成本，已經(jīng)吸引了國(guó)內(nèi)外眾多專(zhuān)家學(xué)者、交通工程師的廣泛關(guān)注。

目前， SDCSP的研究相對(duì)成熟[2-5]，MDCSP的研究相對(duì)較少，主要研究成果歸納如下：Gaffi和Nonato[6]采用近似算法首次研究一類(lèi)多車(chē)場(chǎng)BCSP；陳明明等[7]建立了多車(chē)場(chǎng)乘務(wù)排班問(wèn)題的數(shù)學(xué)模型；Huisman等[8]研究了多車(chē)場(chǎng)的車(chē)輛和人員集成調(diào)度模型；Leone等[9]提出一種融合領(lǐng)域搜索方法和路徑構(gòu)造方法的貪婪隨機(jī)自適應(yīng)搜索求解駕駛員排班問(wèn)題；Marta等[10]設(shè)計(jì)求解混合公交車(chē)輛和駕駛員調(diào)度模型一種啟發(fā)式算法；Christos和Efthymios[11]提出一種啟發(fā)式算法求解混合公交車(chē)輛和駕駛員調(diào)度問(wèn)題；沈吟東[12]研究探討一類(lèi)公交車(chē)輛和駕駛員的集成調(diào)度0-1整數(shù)規(guī)劃模型；劉波濤和李會(huì)凱[13]研究一種基于免疫算法的公交車(chē)及駕駛員調(diào)度優(yōu)化問(wèn)題。由上可知，現(xiàn)有MDCSP研究均未涉及駕駛員在不同車(chē)輛之間切換，也沒(méi)有考慮駕駛員對(duì)不同線(xiàn)路熟悉程度制約駕駛員執(zhí)行相應(yīng)班次，進(jìn)而影響乘務(wù)排班結(jié)果，與實(shí)際應(yīng)用有一定差距。

綜上所述，筆者提出了一種考慮駕駛員對(duì)線(xiàn)路熟悉程度的公交乘務(wù)排班優(yōu)化模型，設(shè)計(jì)求解該問(wèn)題的人工免疫算法，在滿(mǎn)足駕駛員的工作時(shí)間窗、用餐時(shí)間等實(shí)現(xiàn)約束情形下，編制了一個(gè)最佳公交乘務(wù)排班方案，并比較駕駛員偏好線(xiàn)路程度對(duì)調(diào)度方案的影響。

1問(wèn)題描述及數(shù)學(xué)模型

綜上所述，數(shù)學(xué)模型如下

(1)

st.Cp∩Cq=??p,q∈D

(2)

(3)

(4)

(5)

(6)

(7)

etxi-1+RT+zxi·ETstxi?

(8)

在上述模型中，式(1)為問(wèn)題的目標(biāo)函數(shù)，表示公交乘務(wù)排班優(yōu)化方案的營(yíng)運(yùn)成本極小化，包括總的駕駛員成本、正常班及加班費(fèi)用；式(2)～(8)為問(wèn)題的約束條件，其中：式(2)表示一個(gè)駕駛員僅屬于一個(gè)車(chē)場(chǎng)，式(3)表示所有班次任務(wù)必須被駕駛員執(zhí)行，式(4)表示每駕駛員同時(shí)只能完成一個(gè)班次任務(wù)，一個(gè)班次任務(wù)只能被一個(gè)駕駛員完成，式(5) 表示駕駛員僅執(zhí)行熟悉線(xiàn)路的班次任務(wù)，式(6) 表示駕駛員的上班時(shí)間小于某值，式(7)表示駕駛員的在車(chē)時(shí)間低于某值，式(8)表示任意駕駛員按次序執(zhí)行相鄰班次任務(wù)的必備條件。

2求解SDCSP的人工免疫算法

人工免疫算法是借鑒自然免疫系統(tǒng)的一種智能算法，將抗原和抗體抽象為優(yōu)化問(wèn)題的目標(biāo)函數(shù)與解，利用抗體的免疫操作機(jī)制快速收斂至全局最優(yōu)解，在旅行商、物流配送、車(chē)間作業(yè)調(diào)度等組合優(yōu)化領(lǐng)域已經(jīng)廣泛應(yīng)用[14-15]。

目前，人工免疫算法在求解CSP方面尚不多見(jiàn)，本文設(shè)計(jì)求解SDCSP的人工免疫算法，根據(jù)問(wèn)題特征，定義了抗體、啟發(fā)式種群算法等，并描述了具體算法的求解流程。

2.1解的抗體表示

用向量X=(x1,x2,···,x|CT|)表示SDCSP的一個(gè)解，元素?xi∈X為班次任務(wù)的編號(hào)(為1～|CT|之間的互不相同整數(shù))，若遵循(8)式，班次任務(wù)xi-1和xi被某駕駛員按順序執(zhí)行；否則，它們被不同駕駛員完成，其中x1的前一個(gè)班次任務(wù)可能是x|CT|。顯然，將X均解析為不同駕駛員的一系列班次任務(wù)序列，若它們滿(mǎn)足約束式(5)～( 7)，它是一個(gè)可行解。

2.2產(chǎn)生抗體群

SDCSP涉及眾多因素均是強(qiáng)約束的，隨機(jī)產(chǎn)生的個(gè)體很難是可行解，設(shè)計(jì)啟發(fā)式算法生成求解該問(wèn)題的初始抗體種群。

步驟2。令可執(zhí)行CT'的駕駛員集合記為C=?，設(shè)置i=1。

步驟3.1。設(shè)置uC=?，對(duì)任意駕駛員?k∈C，搜索他們的當(dāng)前最后任務(wù)lT(k)。

2.3計(jì)算抗體適應(yīng)值

值得注意的是，如果用紅薯、白薯來(lái)替代主食，那么要額外增加一個(gè)蛋，或者幾口魚(yú)肉豆腐。因?yàn)楦适淼牡鞍踪|(zhì)含量低于大米和白面，如果長(zhǎng)期吃甘薯而不搭配其他食物，則容易引起蛋白質(zhì)缺乏。

抗體的適應(yīng)度刻畫(huà)候選解對(duì)最優(yōu)解的貼近能力，可直接采用優(yōu)化問(wèn)題的目標(biāo)函數(shù)變換得到，如下所示。

(9)

式中：C是常數(shù)，Qu是抗體u的適應(yīng)度函數(shù)，f是該抗體映射問(wèn)題的目標(biāo)函數(shù)，C+f≥0。

2.4免疫操作

免疫進(jìn)化操作的主要思想：計(jì)算抗體群的信息熵，據(jù)此選擇較優(yōu)的抗體，利用交叉和變異操作從中生成一些較好的抗體，維持抗體群的多樣性。具體步驟描述如下：

步驟1。計(jì)算父代抗體群的每個(gè)抗體期望生存率pu，與抗體濃度Lu、適應(yīng)值Qu相關(guān)。如式(10)所示，當(dāng)抗體的Lu和Qu分別較低和較大時(shí)，其pu也越大，從而保護(hù)較好抗體和促進(jìn)濃度較低個(gè)體進(jìn)化，維持抗體群在進(jìn)化中的多樣性。

(10)

步驟2。根據(jù)式(10)，利用輪盤(pán)法，隨機(jī)選擇較好的抗體。

此外，引入免疫記憶細(xì)胞，將較好抗體直接保留到新群體中，避免其被舍棄。

2.5算法步驟

算法步驟見(jiàn)圖1。

圖1　基于人工免疫算法求解SDCSP的算法流程圖Fig.1　Flowchart of SDCSP algorithm

3算例分析

某公交公司對(duì)6條線(xiàn)路進(jìn)行區(qū)域乘務(wù)排班，共有3種類(lèi)型駕駛員C1、C2和C3，其基本信息及所蘊(yùn)含的時(shí)刻表如表1和2所示，其它運(yùn)營(yíng)參數(shù)為c1=126.4 元/人，c2=8.6 元/小時(shí)，c3=15 元/小時(shí)，RT=5 min，ET=15 min，LT=540 min和WT=480 min, 據(jù)此計(jì)算不同駕駛員熟悉線(xiàn)路情況下的最佳調(diào)度方案。

表1　公交線(xiàn)路信息

表2　行車(chē)時(shí)刻表

利用Matlab編寫(xiě)求解問(wèn)題模型的免疫算法程序，設(shè)置相關(guān)參數(shù)為抗體數(shù)100，進(jìn)化次數(shù)200，交叉率 0.2，變異率 0.02，淘汰率 0.2，濃度罰值 0.5，記憶細(xì)胞數(shù)30，計(jì)算3種駕駛員熟悉線(xiàn)路情況下的最佳調(diào)度方案，結(jié)果如表3所示，從中可知：隨著駕駛員的熟悉線(xiàn)路數(shù)減少，需要更多的駕駛員，這引起他們的空閑時(shí)間增多和加班時(shí)間減少，由于人員費(fèi)用的增加幅度大于加班費(fèi)用的減少程度(正常班費(fèi)用相差不大)，所以乘務(wù)排班的費(fèi)用逐漸變大。由上可知，方案1和3分別是單和多車(chē)場(chǎng)CSP，而方案2是多車(chē)場(chǎng)CSP的改進(jìn)模型，雖然其調(diào)度成本比現(xiàn)有多車(chē)場(chǎng)CSP的高很多，但是該模型比較符合實(shí)際。

表3　不同方案的計(jì)算結(jié)果分析

方案2的最佳調(diào)度方案如表4所示，總共需要40個(gè)駕駛員花費(fèi)8 013.9元才能完成215個(gè)班次，3類(lèi)駕駛員C1，C2和C3的數(shù)量分別為13，14和13，所有乘務(wù)員在3個(gè)車(chē)場(chǎng)A，B和C的初始分布數(shù)量為3，5 和32，他們的總工作、空閑和加班時(shí)間分別為7 985 min、4 705 min和12 430 min。由于各線(xiàn)路的發(fā)車(chē)頻率不均衡性，考慮駕駛員對(duì)各條線(xiàn)路的熟悉程度偏好，可能出現(xiàn)部分駕駛員僅執(zhí)行一個(gè)或少數(shù)班次任務(wù)，計(jì)算結(jié)果符合直觀分析。

表4　最佳駕駛員排班方案

4結(jié)論

遵從“一車(chē)多司機(jī)”制，與單線(xiàn)公交乘務(wù)排班相比，區(qū)域調(diào)度模式可以有效減少運(yùn)營(yíng)成本。然而，若該調(diào)度模式忽略駕駛員對(duì)不同線(xiàn)路的熟悉程度，不僅影響調(diào)度成本，而且容易造成交通隱患。針對(duì)現(xiàn)有研究較少關(guān)注此類(lèi)問(wèn)題，文中研究一類(lèi)考慮駕駛員對(duì)線(xiàn)路熟悉程度的區(qū)域公交乘務(wù)排班優(yōu)化模型及其求解算法，在滿(mǎn)足駕駛員的工作時(shí)間窗、用餐時(shí)間、加班費(fèi)用等現(xiàn)實(shí)約束情形下，合理安排駕駛員完成一系列班次任務(wù)。仿真表明：隨著駕駛員的熟悉線(xiàn)路程度增加，乘務(wù)排班的費(fèi)用逐漸減少，雖然其調(diào)度成本比現(xiàn)有模型的高很多，但是該模型比較符合實(shí)際。

然而文中模型未考慮不確定因素對(duì)乘務(wù)排班的影響，當(dāng)交通擁堵等隨機(jī)干擾引起車(chē)輛延誤完成某個(gè)班次，這容易導(dǎo)致當(dāng)前乘務(wù)排班方案失效，故亟待尋求編制一個(gè)高可靠、低成本的乘務(wù)排班方案以適應(yīng)不斷變化環(huán)境，將是今后進(jìn)一步研究的方向。

參考文獻(xiàn)

[1]CEDER A. Public Transit Planning and Operation Theory,Modeling and Practicce[M].Atlanta, USA:Elsevier，2007.

[2]LOURENCO H R, PAIXAO J P, PORTUGALL R. Multiobjective metaheuristics for the bus-driver scheduling problem[J]. Transportation Science, 2001, 35(3): 331-343.

[3]沈吟東,倪郁東. 含時(shí)間窗的司售員調(diào)度模型及多鄰域結(jié)構(gòu)設(shè)計(jì)[J]. 華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版, 2008,36 (12):31-34.

SHEN Yindong, NI Yudong. Model for crew scheduling with time windows and multi-neighborhood structure[J]. Journal of Huazhong University of Science and Technology：Natural Science Edition, 2008,36(12):31-34.

[4]CHEN Mingming, NIU Huimin. A model for bus crew scheduling problem with multiple duty types[J]. Discrete Dynamics in Nature and Society, 2012, 2012(2):407-432.

[5]FRELING R, HUISMAN D, WAGELMANS A. Models and algorithms for integration of vehicle and crew scheduling[J].Journal of Scheduling, 2003,6(1), 63-85.

[6]GAFFI A, NONATO M.Computer-aided transit scheduling[M]. Berlin:,Springer-Verlag, 1999.

[7]陳明明,?；菝? 多車(chē)場(chǎng)公交乘務(wù)排班問(wèn)題優(yōu)化[J]. 交通運(yùn)輸系統(tǒng)工程與信息, 2013, 13(5): 159-166.

CHEN Mingming，NIU Huimin. An optimization model for bus crew scheduling with multiple depots[J]. Journal of Transportation Systems Engineering and Information Technology, 2013, 13(5): 159-166.

[8]HUISMAN D, FRELING R, WAGELMANS A. Multipledepot integrated vehicle and crew scheduling[R].Washington D.C. USA:Economic Institute, 2003.

[9]LEONE R, FESTA P, MARCHITTO E. Solving a bus driver scheduling problem with randomized multistart heuristics[J]. International Transactions in Operational Research, 2011,18(6): 707-727.

[10]MARTA M, MARGARIDA M, ANA P. A decomposition approach for the integrated vehicle-crew-roster problem with days-off pattern[J]. European Journal of Operational Research, 2013, 229(2): 318-331.

[11]CHRISTOS V, EFTHYMIOS H. Combined bus and driver scheduling[J]. Computers and Operations Research, 2002, 29(3):243-259.

[12]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.

[13]劉波濤,李會(huì)凱.公交車(chē)和駕駛員集成調(diào)度算法研究[J].計(jì)算機(jī)工程與科學(xué), 2011,33(4):150-153.

LIU Botao, LI Huikai. Research on the scheduling algorithm of city buses and drivers[J]. Computer Engineering& Science, 2011,33(4):150-153.

[14]王 冰,李巧云,尹 磊.基于人工免疫算法的魯棒滿(mǎn)意項(xiàng)目調(diào)度[J].計(jì)算機(jī)集成制造系統(tǒng),2011,17(5): 1089-1094.

WANG Bing, LI Qiaoyun, YIN Lei. Robustsatisfying project scheduling based on artificial immune algorithm[J].Computer Integrated Manufacturing Systems,2011,17(5): 1089-1094.

[15]KIM J W. Integrating artificial immune algorithms for intrusion detection[D]. London: University College London, 2002.

An Optimization Model for Regional Crew Scheduling

Problem Considering the Driver′s Familiarity to Bus Lines

Bo SunWei Ming▲

(SchoolofTransportation,NantongUniversity,Nantong226019,Jiangsu,China)

Abstract：In the case of allowing drivers to cover tasks belonged to different bus lines, a model for regional crew scheduling is proposed by considering each driver′s familiarity to different bus lines. The model meets the following constraints such as working time, halfway rest, and mealtime. The objective is to identify the best crew scheme to minimize operating costs, and salary costs of bus drivers by taking regular and overtime work into consideration. The solutions are obtained using a tailored artificial immune algorithm which redesigned a solution code, heuristic procedure to initialize chromosomes randomly, fitness function, immune operation, etc. Finally, a numerical example is presented to calculate the best scheme and the impacts of drivers' preference for different lines on the scheduling scheme, which in turn demonstrates the effectiveness of the model and algorithm. Simulation results show that the costs of crew scheduling decrease with the increasing drivers′ familiarity with one bus line. Although its scheduling cost of proposed model is much higher than the existing models, the one proposed in this paper is more realistic.

Key words：traffic management; crew scheduling; multiple depots; driver′s familiarity with different bus lines; artificial immune algorithm

通信作者：▲魏明(1984-)，博士.研究方向：公交調(diào)度.E-mail: mingtian911@163.com

作者簡(jiǎn)介：第一孫博(1986-)，碩士.研究方向：交通規(guī)劃與管理.E-mail: bowensunny@163.com

基金項(xiàng)目*國(guó)家自然科學(xué)(批準(zhǔn)號(hào)：61503201)、中國(guó)博士后科學(xué)基金面上項(xiàng)目(批準(zhǔn)號(hào)：2013M540408)、江蘇省高校自然科學(xué)研究面上項(xiàng)目(批準(zhǔn)號(hào)：13KJB580008，15KJB580011)、南通科技計(jì)劃項(xiàng)目(批準(zhǔn)號(hào)：BK2014059)資助

收稿日期：2015-09-25修回日期：2015-11-23

中圖分類(lèi)號(hào)：U491

文獻(xiàn)標(biāo)志碼：A

doi：10.3963/j.issn 1674-4861.2015.06.020