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

董 皓 石俊剛 周 峰 徐瑞華

(1.北京城建設(shè)計發(fā)展集團股份有限公司,100037,北京; 2.華東交通大學(xué)軌道交通學(xué)院，330013，南昌;3.同濟大學(xué)交通運輸工程學(xué)院,201804,上?！蔚谝蛔髡?，工程師)

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

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

(1.北京城建設(shè)計發(fā)展集團股份有限公司,100037,北京; 2.華東交通大學(xué)軌道交通學(xué)院，330013，南昌;3.同濟大學(xué)交通運輸工程學(xué)院,201804,上?！蔚谝蛔髡撸こ處?

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

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

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

1 問題的提出

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

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

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

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

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

圖1 夜早連乘示意圖

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

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

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

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

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

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

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

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

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

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

(1)

式中：

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

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

(2)

(3)

0-1約束:

(4)

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

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

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

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

(5)

式(5)中：

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

(6)

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

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

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

(8)

式中：

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

Tmax——允許的最大工作時間。

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

(7)

式中：

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

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

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

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

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

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

3 算例分析

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

圖3 線路示意圖

夜班出勤地點為XS、TGY,退勤地點為LBC、MJP、NZL三個車場;早班出勤地點為LBC、MJP、NZL三個車場,退勤地點為XS、TGY。夜早任務(wù)搭配具體要求如下:

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

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

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

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

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

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

具體求解過程如下:

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

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

(9)

其中

(10)

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

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

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

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

[3] 石俊剛,周峰,徐瑞華.城軌交通乘務(wù)任務(wù)配對的集合分割模型及算法[J].同濟大學(xué)學(xué)報(自然科學(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] 傅家良.運籌學(xué)方法與模型[M].上海:復(fù)旦大學(xué)出版社,2006:193.

[11] 裘民民,趙曉波,王建才,等.基于(s,S)庫存策略的分銷系統(tǒng)最優(yōu)分配問題[J].清華大學(xué)學(xué)報(自然科學(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

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

F 530.7

10.16037/j.1007-869x.2016.07.007

2015-05-22)