董 皓 石俊剛 周 峰 徐瑞華

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

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

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

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

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

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

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

1 問題的提出

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

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

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

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

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

圖1 夜早連乘示意圖

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

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

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

2 數學建模及求解

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

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

圖2 夜早任務搭配示意圖

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

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

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

(1)

式中：

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

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

(2)

(3)

0-1約束:

(4)

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

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

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

表1 夜早連乘任務費用矩陣

(5)

式(5)中：

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

(6)

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

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

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

(8)

式中：

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

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

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

(7)

式中：

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

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

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

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

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

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

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。夜早任務搭配具體要求如下:

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

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

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

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

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

表2 夜早班任務信息

具體求解過程如下:

步驟1:設計夜早連乘費用函數,并產生費用矩陣。

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

(9)

其中

(10)

根據式(9),產生表3所示費用矩陣。

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

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

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

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

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

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

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

表3 夜早連乘任務費用矩陣

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

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

4 結語

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

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

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

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

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

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

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

F 530.7

10.16037/j.1007-869x.2016.07.007

2015-05-22)