城市軌道交通乘務(wù)夜早任務(wù)搭配模型研究*

董 皓 石俊剛 周 峰 徐瑞華

(1.北京城建設(shè)計(jì)發(fā)展集團(tuán)股份有限公司,100037,北京; 2.華東交通大學(xué)軌道交通學(xué)院，330013，南昌;3.同濟(jì)大學(xué)交通運(yùn)輸工程學(xué)院,201804,上海∥第一作者，工程師)

城市軌道交通乘務(wù)夜早任務(wù)搭配模型研究*

董 皓1石俊剛2周 峰3徐瑞華3

(1.北京城建設(shè)計(jì)發(fā)展集團(tuán)股份有限公司,100037,北京; 2.華東交通大學(xué)軌道交通學(xué)院，330013，南昌;3.同濟(jì)大學(xué)交通運(yùn)輸工程學(xué)院,201804,上海∥第一作者，工程師)

乘務(wù)夜早任務(wù)連乘是我國(guó)城市軌道交通(以下簡(jiǎn)為“城軌”)乘務(wù)普遍采用的輪轉(zhuǎn)策略。編制良好的乘務(wù)夜早任務(wù)搭配方案可保證乘務(wù)員工作的均衡性和安全性。根據(jù)城軌乘務(wù)夜早任務(wù)連乘需求,建立了相應(yīng)的最優(yōu)分配模型(NMC模型),設(shè)計(jì)了夜早連乘任務(wù)綜合費(fèi)用函數(shù),并結(jié)合傳統(tǒng)的匈牙利算法對(duì)NMC模型進(jìn)行了求解。以某地鐵線路為例,進(jìn)行了算例分析。結(jié)果表明,NMC模型所編制的夜早連乘方案能夠滿足現(xiàn)場(chǎng)需求,可提高乘務(wù)夜早任務(wù)搭配的效率。

城市軌道交通; 乘務(wù)計(jì)劃編制; 夜早任務(wù)搭配; 最優(yōu)分配

First-author′s address Beijing Urban Engineering Design and Research Institute Co.,Ltd.,100037,Beijing China

1 問題的提出

乘務(wù)計(jì)劃編制是城市軌道交通(以下簡(jiǎn)為“城軌”)乘務(wù)管理的重要工作,良好的乘務(wù)計(jì)劃既能保證乘務(wù)員之間工作的均衡性,又能保證乘務(wù)員的駕車效率和安全性[1-9]。乘務(wù)計(jì)劃編制包括乘務(wù)任務(wù)配對(duì)和乘務(wù)任務(wù)輪轉(zhuǎn)[2-3]兩部分工作。乘務(wù)夜早任務(wù)搭配是乘務(wù)任務(wù)輪轉(zhuǎn)的前期工作,也是乘務(wù)計(jì)劃編制過程中出現(xiàn)的新問題。

我國(guó)城軌列車運(yùn)營(yíng)時(shí)間長(zhǎng),一般一日首班車始發(fā)時(shí)間在凌晨5∶00—6∶00,末班車收車時(shí)間超過24∶00,為降低乘務(wù)人員工作負(fù)荷和保障列車運(yùn)行的安全性,乘務(wù)管理中,將一日內(nèi)的列車駕駛?cè)蝿?wù)分為早班、白班、夜班,分三班進(jìn)行輪轉(zhuǎn)。然而，過早開始運(yùn)營(yíng)使得早班乘務(wù)員難以按時(shí)趕到出勤地點(diǎn),過晚結(jié)束運(yùn)營(yíng)使得夜班乘務(wù)員無法乘坐公共交通回家,交通補(bǔ)貼費(fèi)用高。因此,乘務(wù)輪轉(zhuǎn)中,一般安排夜班乘務(wù)員退勤后留宿在退勤地點(diǎn),次日繼續(xù)值乘早班任務(wù)(稱為夜早班連乘),由此可解決早班出勤難和夜班退勤難的問題。夜早班連乘示意圖如圖1所示,司機(jī)執(zhí)勤完夜班后留宿在出退勤點(diǎn)2,第二天繼續(xù)執(zhí)勤早班任務(wù),最后在出退勤點(diǎn)1退勤,完成夜早班連乘。

夜早班連乘是目前國(guó)內(nèi)大部分城市的城軌乘務(wù)管理普遍采用的輪換策略,如北京、上海、蘇州等。夜早班連乘過程中需要考慮以下問題:

(1) 乘務(wù)員夜間休息時(shí)間均衡。一般夜班早退勤的乘務(wù)員早班早出勤,反之亦然。

(2) 乘務(wù)員夜早連乘總?cè)蝿?wù)量不超勞。夜早連乘要求司機(jī)保持良好的值乘狀態(tài),因此夜早連乘的總工作量不宜過長(zhǎng),一般采用駕駛里程和總工作時(shí)間進(jìn)行衡量。

圖1 夜早連乘示意圖

(3) 夜早連乘地點(diǎn)一致。夜班任務(wù)退勤地點(diǎn)必須與早班任務(wù)出勤地點(diǎn)保持一致。一般要求夜班出勤地點(diǎn)與次日早班退勤地點(diǎn)盡量保持一致,方便乘務(wù)員處理一些出退勤事宜(如更換工作服等)。

一個(gè)較優(yōu)的乘務(wù)夜早班連乘方案,既能保證乘務(wù)員之間任務(wù)的均衡性,又能保證乘務(wù)員的夜間休息時(shí)間和駕車安全性。夜早班連乘方案編制即將夜班任務(wù)與早班任務(wù)按照特定要求進(jìn)行一一對(duì)應(yīng),形成夜早連乘任務(wù)集合,稱為夜早任務(wù)搭配。目前國(guó)內(nèi)乘務(wù)計(jì)劃編制過程中,夜早班搭配基本采用人工手段,工作難度大,出錯(cuò)率高,特別是當(dāng)夜早任務(wù)較多時(shí),手工編制難以將所有因素考慮齊全,因此需要進(jìn)行計(jì)算機(jī)優(yōu)化計(jì)算。

夜早任務(wù)搭配是城軌乘務(wù)計(jì)劃編制過程中的新問題,目前國(guó)內(nèi)外還沒有相關(guān)研究。本文以此為研究對(duì)象,建立相關(guān)數(shù)學(xué)模型及算法進(jìn)行求解,希望能夠提高乘務(wù)計(jì)劃編制的效率。

2 數(shù)學(xué)建模及求解

乘務(wù)任務(wù)夜早班搭配發(fā)生在乘務(wù)任務(wù)配對(duì)工作之后。乘務(wù)任務(wù)配對(duì)指將給定的列車運(yùn)行計(jì)劃(即列車運(yùn)行圖)配對(duì)形成若干乘務(wù)任務(wù)[2],乘務(wù)任務(wù)一般分早班、白班、夜班三種。乘務(wù)任務(wù)夜早班搭配指將夜班與早班按照特定要求進(jìn)行一一搭配,形成夜早連乘任務(wù)集合,即夜早任務(wù)搭配方案(見圖2,其中虛線框內(nèi)為一個(gè)夜早連乘任務(wù))。

設(shè)夜班集合為N,早班集合為M,夜班任務(wù)i與早班任務(wù)j搭配可形成夜早連乘任務(wù)(i,j),cij為連乘任務(wù)(i,j)的綜合費(fèi)用,夜早班連乘任務(wù)集合為S(即夜早任務(wù)搭配方案)。夜早任務(wù)搭配問題可歸納為尋找一個(gè)最優(yōu)的夜早任務(wù)搭配方案,使得所有的夜早連乘任務(wù)總費(fèi)用最小。

圖2 夜早任務(wù)搭配示意圖

夜早任務(wù)搭配需要保證夜班與早班任務(wù)數(shù)量嚴(yán)格一致,然而在實(shí)際乘務(wù)任務(wù)配對(duì)過程中,往往難以完全保證,此時(shí)可采用備班任務(wù)(作為預(yù)備乘務(wù)員)填充夜班或早班,使得夜早任務(wù)數(shù)一致。因此,本文僅需考慮夜早任務(wù)數(shù)一致的情況,設(shè)夜早任務(wù)數(shù)均為n。

基于以上分析,為乘務(wù)夜早任務(wù)搭配問題建立如下數(shù)學(xué)模型(以下簡(jiǎn)為NMC模型):

目標(biāo)約束:要求形成的搭配方案S中所有夜早連乘任務(wù)的總費(fèi)用最小。即:

(1)

式中：

xij——夜早連乘任務(wù)是否被采用標(biāo)識(shí),采用為1,反之則為0。

一一搭配約束：要求一個(gè)夜班只能搭配一個(gè)早班。即：

(2)

(3)

0-1約束:

(4)

上述模型最優(yōu)解需要保證夜早連乘任務(wù)之間的休息時(shí)間相對(duì)均衡,任務(wù)量不超勞,且出退勤的地點(diǎn)保持一致。為此,需要設(shè)計(jì)特殊的夜早連乘任務(wù)綜合費(fèi)用函數(shù)cij。

首先將夜班任務(wù)依次按照出勤地點(diǎn)(按車站名稱)、退勤地點(diǎn)(按車站名稱)、退勤時(shí)間(由早到晚)排序,存于N中;其次將早班任務(wù)依次按照退勤地點(diǎn)(按車站名稱)、出勤地點(diǎn)(按車站名稱)、出勤時(shí)間(由早到晚)排序,存于M中。以N為行,M為列,構(gòu)建夜早連乘任務(wù)費(fèi)用矩陣,如表1所示。

基于夜早連乘任務(wù)費(fèi)用矩陣,設(shè)計(jì)夜早連乘任務(wù)(i,j)的綜合費(fèi)用cij如下:

表1 夜早連乘任務(wù)費(fèi)用矩陣

(5)

式(5)中：

ctij為夜班任務(wù)i搭配早班任務(wù)j出退勤次序錯(cuò)亂造成的費(fèi)用,其具體形式見式(6)。當(dāng)i=j時(shí),夜班任務(wù)i搭配早班任務(wù)j為正常出退勤次序,此時(shí)將不造成費(fèi)用;當(dāng)ij時(shí),夜班任務(wù)i搭配早班任務(wù)j為提早出勤,此時(shí)乘務(wù)員夜間休息時(shí)間減少,將產(chǎn)生正費(fèi)用,b為每提早一個(gè)次序所造成的費(fèi)用值,為正值,|b|>|a|。ctij可保證夜早連乘過程中,盡量按照正常次序,從而保證乘務(wù)員休息時(shí)間均衡。

(6)

SEij表示夜班任務(wù)i出勤地點(diǎn)與早班任務(wù)j退勤地點(diǎn)是否一致,如果不一致,則SEij=1,反之SEij=0,γ為不一致的懲罰值。

ESij表示夜班任務(wù)i退勤地點(diǎn)與早班任務(wù)j出勤地點(diǎn)是否一致,如果不一致,則ESij=1,反之ESij=0,λ為不一致的懲罰值。此部分可保證夜早班搭配的出退勤地點(diǎn)保持一致。

OTij表示夜早連乘任務(wù)(i,j)工作時(shí)間是否超勞,如果超勞，則OTij=1,反之OTij=0,σ為不一致的懲罰值。即：

(8)

式中：

tij——夜早連乘任務(wù)(i,j)的總工作時(shí)間;

Tmax——允許的最大工作時(shí)間。

ODij表示夜早連乘任務(wù)(i,j)駕駛里數(shù)程是否超限，如果超限，則ODij1，反正ODij=0,ω為不一致的懲罰值。即：

(7)

式中：

dij——夜早連乘任務(wù)(i,j)的總駕駛里程；

Dmax——允許的最大駕駛里程。

NMC模型為最優(yōu)分配模型[8-9],可結(jié)合匈牙利算法[8]進(jìn)行求解。其求解步驟如下:

步驟1:構(gòu)建夜早連乘任務(wù)費(fèi)用矩陣。分別將夜班、早班進(jìn)行排序,基于式(5)構(gòu)建表1的夜早連乘任務(wù)費(fèi)用矩陣;

步驟2:基于費(fèi)用矩陣,采用匈牙利算法求解最優(yōu)矩陣(獨(dú)立零的個(gè)數(shù)為n),并獲取最優(yōu)解X;

步驟3:根據(jù)最優(yōu)解X,將夜早任務(wù)搭配形成夜早連乘任務(wù)集合,形成最優(yōu)夜早任務(wù)搭配方案。

3 算例分析

某地鐵線路基本情況如圖3所示,S為普通站,D為車場(chǎng)。其中，AHQB與TGY為終端折返站,XG為中間折返站,XS為中間站,LBC、MJP、NZL均為車場(chǎng)。該線路采用大小交路方式運(yùn)營(yíng),大交路為AHQB→TGY,小交路為AHQB→XG。

圖3 線路示意圖

夜班出勤地點(diǎn)為XS、TGY,退勤地點(diǎn)為L(zhǎng)BC、MJP、NZL三個(gè)車場(chǎng);早班出勤地點(diǎn)為L(zhǎng)BC、MJP、NZL三個(gè)車場(chǎng),退勤地點(diǎn)為XS、TGY。夜早任務(wù)搭配具體要求如下:

(1) 盡量保證乘務(wù)員夜間休息時(shí)間均衡,即做到夜班早退勤,則早班早出勤,反之亦然;

(2) 夜班與早班總駕駛公里不得超過246 km,總工作時(shí)間不得超過11 h;

(3) 夜班退勤地點(diǎn)與早班出勤地點(diǎn)必須一致,夜班出勤地點(diǎn)與早班退勤地點(diǎn)必須一致。

以該線路某次乘務(wù)計(jì)劃編制過程中的部分夜早任務(wù)搭配為例,采用所述方法進(jìn)行求解。需要進(jìn)行夜早搭配的任務(wù)如表2。

表2中夜班任務(wù)依次按照出勤地點(diǎn)、退勤地點(diǎn)、退勤時(shí)間進(jìn)行了排序,早班任務(wù)依次按照退勤地點(diǎn)、出勤地點(diǎn)、出勤時(shí)間進(jìn)行了排序。顯然,若不考慮工作量約束,表中夜早班對(duì)應(yīng)順序即為夜早班銜接的最優(yōu)方案。然而，XL2與LX2銜接,公里數(shù)超出了限制;XM2與MX2銜接,工作時(shí)間超出了限制，因此需要進(jìn)行夜早班優(yōu)化搭配。

表2 夜早班任務(wù)信息

具體求解過程如下:

步驟1:設(shè)計(jì)夜早連乘費(fèi)用函數(shù),并產(chǎn)生費(fèi)用矩陣。

現(xiàn)場(chǎng)調(diào)研了解到,現(xiàn)場(chǎng)對(duì)于出退勤地點(diǎn)一致性要求最高,其次是工作時(shí)間和工作量約束,最后是休息時(shí)間均衡性。根據(jù)此需求,設(shè)計(jì)夜早連乘任務(wù)費(fèi)用函數(shù)如下:

(9)

其中

(10)

根據(jù)式(9),產(chǎn)生表3所示費(fèi)用矩陣。

步驟2:基于夜早連乘任務(wù),采用匈牙利算法[8-9]求解表3的最優(yōu)約簡(jiǎn)矩陣。

根據(jù)匈牙利算法原理可知,最優(yōu)約簡(jiǎn)矩陣中,獨(dú)立零的個(gè)數(shù)恰好為n,找出所有獨(dú)立零對(duì)應(yīng)的變量,這些變量取1,其它變量取0,即為最優(yōu)解。表3中,加粗黑數(shù)字即為獨(dú)立零對(duì)應(yīng)的位置,該位置對(duì)應(yīng)的變量取1,其它變量取0,即為NMC模型的最優(yōu)解。

步驟3:基于最優(yōu)解,獲取最優(yōu)夜早班搭配方案。

將表3中加粗黑數(shù)字對(duì)應(yīng)的夜早班搭配起來,形成最優(yōu)夜早班搭配方案,如表4所示。

由表4可以看出,最優(yōu)搭配方案具有以下特點(diǎn):

(1) 夜早班出退勤地點(diǎn)完全一致。

(2) 夜早連乘任務(wù)工作量滿足限制。所有夜早連乘任務(wù)的駕駛公里和工作時(shí)間均在約束范圍以內(nèi),保證了工作量約束,同時(shí)盡量減少出退勤順序的調(diào)整幅度，避免了表2中XL2與LX2搭配公里數(shù)超出、XM2與MX2搭配工時(shí)超出等問題。

表3 夜早連乘任務(wù)費(fèi)用矩陣

表4 夜早班最優(yōu)銜接方案

(3) 夜早連乘任務(wù)休息時(shí)間盡量均衡。在滿足地點(diǎn)約束和工作量約束的情況下,基本保證了夜班早退勤、早班早出勤的規(guī)則,如MT與TM系列任務(wù),XN與NX系列任務(wù)。

4 結(jié)語

本文以乘務(wù)計(jì)劃編制過程中的夜早班任務(wù)搭配為研究對(duì)象,充分分析夜早班任務(wù)搭配需求,建立了夜早班任務(wù)搭配的NMC模型。NMC模型的核心在于設(shè)計(jì)夜早連乘任務(wù)費(fèi)用函數(shù)。本文根據(jù)夜早任務(wù)搭配需求(出退勤地點(diǎn)一致,夜早連乘工作量約束,乘務(wù)員休息時(shí)間均衡),設(shè)計(jì)了滿足多需求的夜早連乘任務(wù)綜合費(fèi)用函數(shù)。通過分析NMC模型的特性,將其歸納為最優(yōu)分配模型,并結(jié)合傳統(tǒng)匈牙利算法[9-10]進(jìn)行求解。

實(shí)例驗(yàn)證表明,NMC模型求解的最優(yōu)夜早連乘方案能夠滿足所有需求,可提高乘務(wù)夜早班搭配工作的效率,為乘務(wù)計(jì)劃編制的下一步工作(乘務(wù)任務(wù)輪轉(zhuǎn))打下基礎(chǔ)。

[1] 王英,辛繼偉等.地鐵乘務(wù)管理體系標(biāo)準(zhǔn)化探討[J].都市快軌交通,2013，26(3)：62.

[2] 石俊剛,史宏杰,徐瑞華.城市軌道交通乘務(wù)任務(wù)劃分模型及算法研究[J].鐵道學(xué)報(bào),2014,36(5):1.

[3] 石俊剛,周峰,徐瑞華.城軌交通乘務(wù)任務(wù)配對(duì)的集合分割模型及算法[J].同濟(jì)大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,43(2):232.

[4] BEASLEY J E.An algorithm for set covering problems[J].European Journal of Operational Research,1987,31(1):85.

[5] KARLA L,HOFFMAN,MANFRED Padberg.Solving airline crew scheduling problems by branch-and-cut[J].Management Science,1993,39(6):657.

[6] MARSTEN R E,SHEPARDSON F.Exact solutionof crew scheduling problems using the set partitioning model:recent successful applications[J].Networks,1981,11(2):165.

[7] WEDELIN Dag.An algorithm for large scale 0-1 integer programming with applicationto airline crew scheduling[J].Annals of Operations Research,1995,57(1):283.

[8] LAN Guanghui,DEPUY Gail W,WHITEHOUSE Gary E.An effective and simple heuristic for the set covering Problem[J].European Journal of Operational Research,2007,176(3):1387.

[9] KOHL Niklas.Airline crew rostering:problem types,modeling and optimization[J].Annals of Operations Research,2004,127(1-4):223.

[10] 傅家良.運(yùn)籌學(xué)方法與模型[M].上海:復(fù)旦大學(xué)出版社,2006:193.

[11] 裘民民,趙曉波,王建才,等.基于(s,S)庫存策略的分銷系統(tǒng)最優(yōu)分配問題[J].清華大學(xué)學(xué)報(bào)(自然科學(xué)版),2006,46(5):749.

Early and Late Tasks Pairing Model for Urban Rail Transit Crew

DONG Hao, SHI Jungang, ZHOU Feng, XU Ruihua

The early and late tasks pairing rotation strategy is widely adopted by urban rail transit crew in China. A good composition of the early and late tasks pairing scheme can ensure the balance and security of attendants work. Based on the demands of early and late tasks pairing tasks,an optimal allocation model(NMC) is established and a cost function of early and late tasks pairing rotation is designed combined with the traditional Hungarian algorithm to solve the NMC model.A numerical example of a certain rail transit line is analyzed,and the result indicates that the scheme complied by model could meet the field demands and improve the efficiency of the tasks.

urban rail transit; crew schedule plan; early and late tasks pairing; optimal allocation

*中國(guó)博士后科學(xué)基金項(xiàng)目(2014M551454)；國(guó)家自然科學(xué)基金項(xiàng)目(71271153)

F 530.7

10.16037/j.1007-869x.2016.07.007

2015-05-22)