基于集合覆蓋理論的公交線路駕駛員排班優(yōu)化方法

魏金麗，郭亞娟，張萌萌

(1.青島理工大學(xué)　汽車與交通學(xué)院，山東　青島　266520；2.吉林大學(xué)　交通學(xué)院，吉林　長春　130022；3.山東交通學(xué)院　交通與物流工程學(xué)院，山東　濟(jì)南　250023)

?

基于集合覆蓋理論的公交線路駕駛員排班優(yōu)化方法

魏金麗1，郭亞娟2，張萌萌3

(1.青島理工大學(xué)汽車與交通學(xué)院，山東青島266520；2.吉林大學(xué)交通學(xué)院，吉林長春130022；3.山東交通學(xué)院交通與物流工程學(xué)院，山東濟(jì)南250023)

為解決公交駕駛員調(diào)度優(yōu)化問題，提出了一種基于人員成本最小化的公交線路駕駛員排班優(yōu)化模型。在運(yùn)營公交車輛最少的前提下，以單條公交線路的車次鏈為研究對(duì)象，考慮車輛運(yùn)營任務(wù)、換班時(shí)間、勞動(dòng)規(guī)則要求等約束，借助集合覆蓋理論進(jìn)行數(shù)學(xué)建模，并提出了一種基于啟發(fā)式的0-1整數(shù)規(guī)劃算法進(jìn)行模型求解。最后，結(jié)合濟(jì)南市公交調(diào)查的實(shí)際數(shù)據(jù)，以MATLAB為平臺(tái)，實(shí)現(xiàn)了上述算法，求出公交駕駛員的排班方案。試驗(yàn)結(jié)果表明：與其他算法相比，該算法可減少駕駛員候車時(shí)間消耗，降低班次總工作時(shí)間和人員成本，進(jìn)而降低公交公司運(yùn)營成本；該算法在提高駕駛員工作效率的基礎(chǔ)上，有效保障了駕駛員的工作時(shí)間，為公交線路駕駛員排班組合優(yōu)化問題提供了合理方案。

交通工程；駕駛員排班；啟發(fā)式方法；集合覆蓋；0-1整數(shù)規(guī)劃

0　引言

隨著城市交通擁堵問題的日益嚴(yán)重，城市公共交通的主體地位也逐漸凸顯。目前，為了進(jìn)一步提升公交服務(wù)水平，政府投入了大量資金建設(shè)智能公共交通系統(tǒng)。其中，行車計(jì)劃編制和公交線路駕駛員排班優(yōu)化是公交系統(tǒng)實(shí)現(xiàn)智能調(diào)度的重要組成部分，直接影響到公交運(yùn)營效率。

國外有關(guān)公交駕駛員排班問題的理論研究與實(shí)踐探索已有50多年的歷史[1-3]；而國內(nèi)的相關(guān)研究工作最近幾年才逐漸開展，已取得一定研究成果[4-5]?？傮w來看，國內(nèi)外的研究主要可以分為兩大主流：(1)駕駛員與公交車的集中調(diào)度[6-8]；(2)將駕駛員調(diào)度當(dāng)成一個(gè)孤立的問題看待。前者有利于降低公交運(yùn)營的總成本，后者方便公交企業(yè)的靈活運(yùn)營。獨(dú)立的公交線路駕駛員排班模型算法主要集中于遺傳算法[9-10]、螞蟻算法[11]、禁忌算法[12]和分支定界法[13]等。但這些算法都比較繁雜，不利于實(shí)現(xiàn)。

從公交公司運(yùn)營管理角度出發(fā)，在公交運(yùn)營車輛最少的前提下，公交駕駛員的成本最小即可滿足公交公司利益最大化。因此本文以公交駕駛員成本最小為目標(biāo)，將公交駕駛員排班問題抽象為一個(gè)集合覆蓋問題，并設(shè)計(jì)啟發(fā)式方法與0-1整數(shù)規(guī)劃相結(jié)合的算法，最后采用MATLAB實(shí)現(xiàn)問題的求解。

1　公交線路駕駛員排班問題的分析

公交線路駕駛員排班是根據(jù)編制的行車作業(yè)計(jì)劃安排駕駛員的工作。在安排駕駛員工作時(shí)應(yīng)該同時(shí)滿足以下條件：(1)駕駛員每天的工作一般是由一輛車或兩輛車的幾段工作組成的；(2)運(yùn)營的公交車輛所有的工作必須包含到駕駛員的工作中，所有駕駛員的工作集合必須覆蓋運(yùn)營車輛的任務(wù)。由此可以看出，公交線路駕駛員排班是一個(gè)極其復(fù)雜的組合優(yōu)化問題。

在公交實(shí)際運(yùn)營中，駕駛員排班首先將車輛的運(yùn)營工作按照換班時(shí)間點(diǎn)劃分成一個(gè)小駕駛段集合，然后在滿足一系列目標(biāo)和約束的基礎(chǔ)上將這個(gè)小駕駛段集合重新整合、連接形成一個(gè)連續(xù)駕駛段集合，最后將幾個(gè)連續(xù)駕駛段連接并將其分配給一個(gè)公交駕駛員完成，即形成一個(gè)班次?？梢钥闯?公交駕駛員排班本質(zhì)上是一個(gè)組合優(yōu)化問題，而這個(gè)組合優(yōu)化問題是很復(fù)雜的，其復(fù)雜性主要表現(xiàn)在目標(biāo)多、規(guī)模大、約束條件復(fù)雜多樣。

為消除公交駕駛員排班問題的復(fù)雜性，文獻(xiàn)[13]中提出了一種列生成算法來解決集合覆蓋問題，其難點(diǎn)在于求解初始可行解。在構(gòu)建初始可行解時(shí)利用的貪婪算法和駕駛段配對(duì)方法較為復(fù)雜，初始排班方案會(huì)直接影響受限主問題的求解規(guī)模以及整個(gè)算法的循環(huán)迭代次數(shù)。本文在其基礎(chǔ)上，設(shè)計(jì)了一種較為簡單便捷的啟發(fā)式算法得到可行班次集合，增加了算法的適用性。

2　公交線路駕駛員排班模型

2.1模型原理

公交線路駕駛員排班是一個(gè)將連續(xù)駕駛段予以集合，并在滿足一系列目標(biāo)和約束條件的基礎(chǔ)上重新整合、連接的過程。首先將車輛調(diào)度所得的車次鏈按換班點(diǎn)分割成若干小駕駛段，考慮勞動(dòng)法規(guī)約束，把小駕駛段合并成一些可行的連續(xù)駕駛段，然后對(duì)連續(xù)駕駛段進(jìn)行任意組合篩選得出可行的班次集合，最后基于公交駕駛員成本最小化對(duì)可行的班次集合進(jìn)行選擇和再優(yōu)化，即得到最終的勞動(dòng)班次。

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

本文結(jié)合啟發(fā)式方法和0-1整數(shù)規(guī)劃，設(shè)計(jì)了解決公交線路駕駛員排班問題相應(yīng)的算法。該算法可分為4個(gè)模塊：連續(xù)駕駛段確定模塊、可行班次集合產(chǎn)生模塊、班次選擇模塊和班次優(yōu)化模塊。

(1)連續(xù)駕駛段確定模塊

確定每個(gè)連續(xù)駕駛段即確定駕駛員每個(gè)工作時(shí)間段的長短。該模塊為了保證駕駛員勞動(dòng)法則的約束，采用有效工時(shí)不超過8 h來實(shí)現(xiàn)。為了保證駕駛員在連續(xù)駕駛段內(nèi)較高的工作效率，采用小駕駛段之間的最小時(shí)間間隔來約束。具體的模塊算法如下。

該模塊已知每條車次鏈中每個(gè)小駕駛段的起始時(shí)間和起始地點(diǎn)。其中定義第p個(gè)車次鏈(班次)中第k個(gè)小駕駛段的起始時(shí)間為tpks和結(jié)束時(shí)間為tpke，第p個(gè)車次鏈中第k個(gè)小駕駛段的起始地點(diǎn)為zpks和結(jié)束地點(diǎn)為zpke。

求解每條車次鏈分割成的連續(xù)駕駛段的起始時(shí)間、起始地點(diǎn)以及所在車次鏈編號(hào)。

該模塊的約束條件有兩個(gè)。

① 每條車次鏈中任意相鄰的兩個(gè)小駕駛段之間的空閑時(shí)間不得大于0.5 h，即:

(1)

② 由每條車次鏈中a個(gè)連續(xù)小駕駛段合并得到的連續(xù)駕駛段有效工時(shí)不得大于8 h，即:

(2)

(2)可行班次集合產(chǎn)生模塊

在實(shí)際運(yùn)營中，一個(gè)公交線路駕駛員排班問題的規(guī)模是由連續(xù)駕駛段個(gè)數(shù)或者換班點(diǎn)個(gè)數(shù)所決定的。為了解決駕駛員實(shí)際換班時(shí)換車?yán)щy的問題，該模塊對(duì)上一個(gè)模塊所獲得的連續(xù)駕駛段任意組合后，利用啟發(fā)式方法篩選掉部分換班點(diǎn)來縮小問題規(guī)模，通過限制最小換車次數(shù)、確保組合中任意兩個(gè)相鄰連續(xù)駕駛段之間換班時(shí)間協(xié)調(diào)且換班地點(diǎn)一致，從而產(chǎn)生可行班次集合S。具體的模塊算法如下。

已知連續(xù)駕駛段集合中元素對(duì)應(yīng)的起始時(shí)間Tpks、結(jié)束時(shí)間Tpke、起始地點(diǎn)Zpks、結(jié)束地點(diǎn)Tpke以及所屬的車次鏈編號(hào)。

其中約束條件如下。

①每個(gè)班次j覆蓋的連續(xù)駕駛段個(gè)數(shù)最多為4，即1≤N≤4。

②每個(gè)班次j覆蓋的連續(xù)駕駛段最多跨越兩個(gè)車次鏈，且必須滿足每個(gè)班次只能從一個(gè)車次鏈到另一個(gè)車次鏈跨越1次。

③連續(xù)駕駛段換班時(shí)間的限制，即每個(gè)班次j中相鄰的兩個(gè)連續(xù)駕駛段必須滿足：前一個(gè)連續(xù)駕駛段i的結(jié)束時(shí)間必須早于下一個(gè)連續(xù)駕駛段i+1的起始時(shí)間，滿足：

(3)

④ 連續(xù)駕駛段換班地點(diǎn)的限制，即在一個(gè)班次j中，相連接的兩個(gè)連續(xù)駕駛的結(jié)束與起始時(shí)間間隔小于Tsingle時(shí)，前一個(gè)連續(xù)駕駛段i的結(jié)束地點(diǎn)是后一個(gè)連續(xù)駕駛段i+1的起始地點(diǎn)，即滿足：

(4)

式中Tsingle為公交車輛從首站(末站)到末站(首站)的工作時(shí)間。

(3)班次選擇模塊

為了保證人員排班的合理性和公平性，單個(gè)班次的運(yùn)營成本計(jì)算應(yīng)該是有效工時(shí)成本與超過勞動(dòng)法則規(guī)定工作時(shí)間T的加班工資成本之和。在此基礎(chǔ)上，基于集合覆蓋思想進(jìn)行建模。通過求解該模塊中0-1整數(shù)規(guī)劃問題，從可行班次集合S中選出基于人員成本最小化的可行班次集合Q，使集合Q中的全部元素結(jié)合起來能夠覆蓋全部的車輛運(yùn)營工作。

此0-1整數(shù)規(guī)劃問題具體為：

①所求的變量

(5)

式中xj表示班次j是否被選中，j=1,2,…,n。

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

(6)

式中cj為班次j的人員成本。

(7)

③ 約束條件

每個(gè)連續(xù)駕駛段都會(huì)被唯一的班次覆蓋，即保證：

(8)

(4)班次優(yōu)化模塊

該模塊利用啟發(fā)式方法進(jìn)一步篩選掉已生成的但不太“好”的班次，即對(duì)以上所得的基于人員成本最小化的可行班次集合Q，進(jìn)行班次的最后優(yōu)化，得到最終的班次集合O。

其中進(jìn)行優(yōu)化的約束條件為：

可行班次集合Q中在班時(shí)間小于5 h的班次為需要優(yōu)化的班次，而需要優(yōu)化的班次中任意兩個(gè)班次c與d之間的空閑時(shí)間大于等于5 h可合并優(yōu)化為一個(gè)新的班次，即滿足：

(9)

(10)

2.3算法流程

該模型具體的優(yōu)化流程如圖1所示。

圖1　基于集合覆蓋理論的公交線路駕駛員排班優(yōu)化流程圖Fig.1　Flowchart of optimizing work schedule of bus drivers based on set covering theory

3　實(shí)例應(yīng)用

根據(jù)濟(jì)南市某公交線路的行車作業(yè)計(jì)劃表，以公交線路的換班點(diǎn)為分界，將該公交線路的3條車次鏈劃分成若干小駕駛段，得到小駕駛段的到發(fā)時(shí)刻表，如表1所示。

利用上述算法步驟，編制相應(yīng)的MATLAB程序?qū)崿F(xiàn)該問題的求解。其過程中可得到連續(xù)駕駛段的到發(fā)時(shí)刻表，如表2所示。

將以上所得的連續(xù)駕駛段代入模型求解，并進(jìn)行再次優(yōu)化，得最終班次表，如表3所示。

從計(jì)算結(jié)果可以看出，該方法體現(xiàn)了兩個(gè)方面的優(yōu)點(diǎn)：(1)能夠有效提高駕駛員的工作效率，減少候車時(shí)間消耗，例如班次1、班次3、班次4；(2)如果駕駛員在一天內(nèi)需要分時(shí)段行駛，則需要為其在換班點(diǎn)留夠足夠的休息時(shí)間，例如班次2、班次5。

為了驗(yàn)證本文算法的性能，選取實(shí)際人工編制和遺傳算法[9]得出其他兩種不同的排班方案，以此進(jìn)行對(duì)比分析。各個(gè)調(diào)度方案的相關(guān)性能數(shù)據(jù)分析如表4所示?？梢钥闯?，本文算法的班次個(gè)數(shù)最少，且相應(yīng)的班次總工作時(shí)間和人員成本也都最小，同時(shí)能夠保證較快的優(yōu)化速度，即MATLAB優(yōu)化實(shí)現(xiàn)時(shí)間。因此可驗(yàn)證本文算法得出的排班方案最優(yōu)，既能有效減少人員成本支出，又能提高排班速度。

表1　小駕駛段的到發(fā)時(shí)刻表

表2　連續(xù)駕駛段的到發(fā)時(shí)刻表

表3　班次表

表4　排班方案的對(duì)比分析

4　結(jié)論

在分析公交駕駛員排班問題復(fù)雜性的基礎(chǔ)上，以人員總成本最小化為目標(biāo)，考慮公交駕駛員排班問題的車輛運(yùn)營任務(wù)、換班時(shí)間、勞動(dòng)規(guī)則要求等約束，借助集合覆蓋問題進(jìn)行數(shù)學(xué)建模，并融合啟發(fā)式方法和0-1整數(shù)規(guī)劃設(shè)計(jì)算法進(jìn)行了模型的求解。最后，結(jié)合濟(jì)南市公交公司的實(shí)際數(shù)據(jù)，以MATLAB為平臺(tái)，實(shí)現(xiàn)了以上算法，求出了公交駕駛員排班方案。該方案很好地解決了提高駕駛員工作連續(xù)性的問題。

本文研究的重點(diǎn)是單條公交線路的排班問題，只能滿足對(duì)單條線路的求解要求，但相對(duì)于大規(guī)模的多場(chǎng)站跨線路的駕駛員排班問題，這種模型和算法仍有待改進(jìn)。

[1]XIE L,NAUMANN M,SUHL L.A Stochastic Model for Rota Scheduling in Public Bus Transport[R].Paderborn,Germany:University of Paderborn,2012.

[2]徐群嶺.基于免疫優(yōu)化的公交駕駛員調(diào)度問題[J].計(jì)算機(jī)工程，2010,36(24):164-166.

XU Qun-ling.Schedule Problem of City Bus Drivers Based on Immune Optimization[J].Computer Engineering，2010,36(24):164-166.

[3]LOUREN?O H R，PORTUGAL R.Multiobjective Metaheuristics for the Bus Driver Scheduling Problem[J].Transportation Science,2001,35(3):331-343.

[4]CEDER A.公共交通規(guī)劃與運(yùn)營：理論、建模及應(yīng)用[M].北京:清華大學(xué)出版社，2010.

CEDER A.Public Transit Planning and Operation:Theory,Modeling and Practice[M].Beijing:Tsinghua University Press,2010.

[5]毛霖，李文權(quán).公交線路車輛排班模型及算法研究[J].交通運(yùn)輸工程與信息學(xué)報(bào)，2009，7(3):64-67.MAO Lin,LI Wen-quan.Research on Transit Vehicle Scheduling Model and Its Algorithm [J].Journal of Transportation Engineering and Information,2009,7(3):64-67.

[6]MESQUITA M,MOZ M,PAIAS A,et al.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.

[7]LIN X,KLIEWER N,SUHL L.Integrated Driver Rostering Problem in Public Bus Transit[J].Procedia-Social and Behavioral Sciences,2012,54:656-665.

[8]MESQUITA M,MOZ M,PAIAS A,et al.A New Model for the Integrated Vehicle-crew-rostering Problem and a Computational Study on Rosters[J].Journal of Scheduling,2011,14(4):319-334.

[10]楊英俊，王軼萍，趙祥模.基于遺傳算法的城市客運(yùn)出租汽車調(diào)度中心人員排班研究[J].公路交通科技，2010，27(7):142-146.

YANG Ying-jun,WANG Yi-ping,ZHAO Xiang-mo.Research on Staff Scheduling of Urban Passenger Taxi Dispatching Center Based on Genetic Algorithm[J].Journal of Highway and Transportation Research and Development,2010,27(7):142-146.

[11]楊尚.基于螞蟻算法的公交駕駛員調(diào)度問題研究[D].武漢：華中科技大學(xué)，2009.

YANG Shang.Study on Bus Driver Scheduling Problem Based on Ant Algorithm[D].Wuhan:Huazhong University of Science and Technology,2009.

[12]翟東偉.基于GATS的公交駕駛員調(diào)度算法研究[D].北京：北京交通大學(xué)，2007.

ZHAI Dong-wei.Study on Bus Driver Scheduling Algorithm Based on GATS[D].Beijing:Beijing Jiaotong University，2007.

[13]王健.公交司售人員排班集合覆蓋問題的求解算法研究與實(shí)現(xiàn)[D].北京：北京交通大學(xué)，2011.

WANG Jian.Research and Implementation of Bus Crew-scheduling Algorithm Based on Set-covering Problem[D].Beijing:Beijing Jiaotong University，2011.

A Method of Optimizing Work Schedule of Bus Drivers Based on Set Covering Theory

WEI Jin-li1，GUO Ya-juan2，ZHANG Meng-meng3

(1.School of Automobile and Traffic,Qingdao Technological University,Qingdao Shandong 266520,China; 2.School of Traffic,Jilin University,Changchun Jilin 130022,China; 3.School of Traffic and Logistics Engineering,Shandong Jiaotong University,Jinan Shandong 250023,China)

To optimize the work schedule of bus drivers,a work schedule optimization model of bus route based on minimizing labor cost is proposed.In the premise of minimizing the number of operating buses,taking the bus schedule chain of single bus line as the research subject,considering the constraints of vehicle operation task,shift time,labor rules,etc.,the mathematic model is constructed by set covering theory,and a 0-1 integer programming algorithm based on heuristic method is designed to solve the model.Finally,according to the real investigation data of Jinan public transit,the above algorithm is realized and the schedule scheme is worked out based on the platform of MATLAB.The experiment result shows that (1) compared with other algorithms,this algorithm can reduce the drivers’ waiting consumption and reduce the total work time and personnel cost to achieve the purpose of reducing the bus company operating costs;(2) the method can protect the drivers’ working hours based on improving the efficiency,which provided a reasonable solution for optimizing work schedule of bus drivers.

traffic engineering;work schedule of bus drivers;heuristic method;set covering;0-1 integer programming

2014-09-22

國家自然科學(xué)基金項(xiàng)目(61174175，51178231)；山東省自然科學(xué)基金項(xiàng)目(ZR2014EEP023)

魏金麗(1982-)，女，山東濱州人，碩士.(wjl827025@163.com)

10.3969/j.issn.1002-0268.2016.01.019

U492.4+12

A

1002-0268(2016)01-0125-05