考慮時間均衡度的城市軌道交通乘務(wù)排班計劃優(yōu)化方法

豐 富，陳紹寬，杜 鵬

（北京交通大學(xué) 城市交通復(fù)雜系統(tǒng)理論與技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，北京100044）

考慮時間均衡度的城市軌道交通乘務(wù)排班計劃優(yōu)化方法

豐 富，陳紹寬*，杜 鵬

（北京交通大學(xué) 城市交通復(fù)雜系統(tǒng)理論與技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，北京100044）

乘務(wù)排班計劃是城市軌道交通乘務(wù)組織的核心內(nèi)容和運(yùn)營管理工作的重要組成部分，其生成質(zhì)量對城市軌道交通的運(yùn)營效率有顯著影響.本文將時間均衡度作為給定周期條件下評價乘務(wù)員值乘時間與休息時間合理程度的指標(biāo)，構(gòu)建了基于該均衡度的乘務(wù)排班計劃優(yōu)化模型.為同時考慮乘務(wù)區(qū)段的最優(yōu)組合與早晚班的匹配問題，本文的求解過程由改進(jìn)遺傳算法和雙相匹配算法兩個部分構(gòu)成.最后將所建模型應(yīng)用于北京市某軌道交通線路的案例研究中，對優(yōu)化結(jié)果與既有乘務(wù)計劃進(jìn)行比較分析，驗(yàn)證模型的有效性.對比發(fā)現(xiàn)，該模型的結(jié)果在較大程度上提高了乘務(wù)排班計劃的時間均衡度.

城市交通;城市軌道交通；優(yōu)化模型；遺傳算法；乘務(wù)排班計劃；時間均衡度

1 引 言

乘務(wù)排班計劃是交通運(yùn)輸運(yùn)營組織工作中的重要環(huán)節(jié)之一，其實(shí)質(zhì)是在給定運(yùn)行時刻表及運(yùn)輸工具的接續(xù)關(guān)系后，制定乘務(wù)人員的工作計劃.如果將乘務(wù)人員的工作時間作為生產(chǎn)投入，則乘務(wù)計劃可轉(zhuǎn)化為一個資源配置問題，合理的乘務(wù)計劃可為運(yùn)輸企業(yè)帶來可觀的經(jīng)濟(jì)效益[1].

近年來有關(guān)乘務(wù)計劃問題的建模和求解算法方面的研究得到廣泛開展.建模方面的主要研究工作主要分為三類：集劃分或集覆蓋形式的模型、以值乘區(qū)段或值乘交路間的接續(xù)關(guān)系為決策變量的物理模型，以及以圖的結(jié)構(gòu)或者其他方式描述乘務(wù)問題的模型[2-4].例如，張?jiān)鲇碌冉⒘丝紤]乘務(wù)作業(yè)段和工作班生成的基于懲罰費(fèi)用的雙層模型，并設(shè)計了Dijkstra算法和離散粒子群算法進(jìn)行求解[5].李獻(xiàn)忠與徐瑞華合作，從時間耗費(fèi)和廣義費(fèi)用兩個角度進(jìn)行了乘務(wù)優(yōu)化研究，獲得的排班計劃顯著提高了乘務(wù)工作的質(zhì)量和效率，相對于傳統(tǒng)依賴經(jīng)驗(yàn)的人工編制乘務(wù)計劃表現(xiàn)出明顯的優(yōu)勢[6,7].Zaepfel和Boegl在考慮值乘區(qū)段或值乘交路間的接續(xù)關(guān)系時加入與乘務(wù)員相關(guān)的因素，對乘務(wù)員的休息時間的安排進(jìn)行了研究[8].

實(shí)際排班工作中，對乘務(wù)員的值乘時間、休息時間，以及兩者均衡程度方面關(guān)注更多，但目前尚無較深入的研究成果.列車運(yùn)行圖規(guī)模較大時，由于工作環(huán)境和值乘需求，乘務(wù)員的工作量和休息時間的分配可能會出現(xiàn)較嚴(yán)重的局域傾斜現(xiàn)象[8].在實(shí)際的運(yùn)營管理中，乘務(wù)員的人數(shù)與運(yùn)營中的需求之間應(yīng)基本平衡且留有余量.然而就乘務(wù)員個體來說，乘務(wù)任務(wù)和休息時間往往很難實(shí)現(xiàn)理想的平衡[9].

本文考慮合理分配乘務(wù)員值乘和休息時間因素，提出基于時間均衡度的優(yōu)化目標(biāo)函數(shù)，構(gòu)建乘務(wù)排班計劃模型，并設(shè)計適當(dāng)?shù)那蠼馑惴ㄋ褜M意解，為乘務(wù)排班計劃的制定與優(yōu)化提供方法支撐.

2 問題描述

城市軌道交通排班計劃是根據(jù)給定的列車運(yùn)行圖、乘務(wù)規(guī)則、動車或車底交路、乘務(wù)基地條件等，考慮一定的優(yōu)化目標(biāo)，對乘務(wù)員的出退乘時間與地點(diǎn)、值乘車次與時刻等做出具體安排，以確保列車運(yùn)行計劃的實(shí)現(xiàn)[10].編制排班計劃的一般流程是：分割列車運(yùn)行徑路形成值乘區(qū)段；根據(jù)乘務(wù)規(guī)則和優(yōu)化目標(biāo)將值乘區(qū)段進(jìn)行組合；如果考慮較長時間的排班計劃，可進(jìn)一步編制長周期乘務(wù)排班計劃.

乘務(wù)排班計劃編制過程中一般根據(jù)乘務(wù)基地對于資源配置和停留時間的要求，選擇較大型且停留時間較長的可換乘車站作為乘務(wù)基地[11].在確定乘務(wù)基地的基礎(chǔ)上，以其為節(jié)點(diǎn)對列車運(yùn)行線進(jìn)行分割，進(jìn)而形成列車乘務(wù)員的值乘區(qū)段.乘務(wù)排班計劃工作則是按照乘務(wù)規(guī)則對值乘區(qū)段進(jìn)行分配，形成值乘交路，同時實(shí)現(xiàn)值乘時間、乘務(wù)員數(shù)量等評價指標(biāo)的最優(yōu)化[12].

在乘務(wù)規(guī)則方面主要有以下考慮.

（1）值乘區(qū)段的完全覆蓋.每一個值乘區(qū)段都有其對應(yīng)的值乘交路，值乘交路與值乘區(qū)段的歸屬關(guān)系方面遵從互斥原則.

（2）值乘區(qū)段的鄰接關(guān)系.值乘區(qū)段序列中前后兩個相鄰的值乘區(qū)段必須滿足一定的時間間隔.

（3）值乘時間約束.指乘務(wù)員的值乘時間具有規(guī)定的上下限.

（4）休息時間限制.指乘務(wù)員連續(xù)值乘時間達(dá)到某一閥值的時候必須安排休息時間.休息時間通常分為兩種，相鄰值乘區(qū)間之間的休息時間和晚班與早班之間的夜間休息時間.在城市軌道交通運(yùn)營工作中，通常是指晚班值乘的乘務(wù)員繼續(xù)值乘接續(xù)早班的夜間休息時間.

（5）吃飯時間約束.乘務(wù)員值乘期間的吃飯時間必須按規(guī)定進(jìn)行設(shè)置.

3 模型構(gòu)建

3.1 時間均衡度

時間均衡度是由排班計劃的時間成本、乘務(wù)員值乘時間和夜間休息時間共同衡量，旨在兼顧排班計劃的時間成本與乘務(wù)員工作時間、休息時間分配的合理程度.乘務(wù)排班計劃優(yōu)化模型的目標(biāo)函數(shù)如下所述.

（1）乘務(wù)排班計劃值乘時間成本.

乘務(wù)排班計劃的時間成本是由值乘交路的值乘時間和時間價值共同確定的.具體的計算公式為

式中 t1j、t2j、t3j是早班、白班、晚班值乘交路 j的持續(xù)時間（小時）；c1、c2、c3分別是其對應(yīng)的時間價值（元/小時）.

（2）值乘時間均衡程度.

值乘時間的均衡程度是指排班計劃中同一班次中所有乘務(wù)人員的值乘時間的均衡程度，本文采用隸屬度函數(shù)表示，隸屬度越大則值乘時間均衡度越好.值乘時間均衡程度的隸屬度函數(shù)式為

其中，fun1() t1j是早班值乘時間的隸屬度，其解析式為

式中 參數(shù)t0、α1、α2由早班值乘時間的數(shù)據(jù)樣本來確定.類似地，可確定 fun2(t2j)和 fun3(t3j).

（3）夜班時間均衡程度.

夜班時間的均衡程度主要體現(xiàn)為“晚-早同員”乘務(wù)員的夜間休息時間和夜班值乘時間的差異程度.夜間休息時間是指乘務(wù)員晚班下班至早班上班之間的休息時間，其差異程度越小則均衡度越好.具體的計算公式為

式中 {d ri}是“晚-早同員”乘務(wù)員的集合；D(·)是方差函數(shù)；β是權(quán)重系數(shù)；D(tn)是乘務(wù)員夜間休息時間的方差；D({ dri})是“晚-早同員”乘務(wù)員夜班值乘時間的方差.

（4）時間均衡度.

f1、f3的值增大時，時間均衡度增大；f2增大時，時間均衡度減小.因此定義時間均衡度為

式中 k為權(quán)重調(diào)整系數(shù).

3.2 優(yōu)化模型

考慮時間均衡度的乘務(wù)排班計劃優(yōu)化模型以時間均衡度為目標(biāo)函數(shù)，以值乘區(qū)段的完全覆蓋、值乘區(qū)段的鄰接關(guān)系、值乘時間約束、休息時間限制和吃飯時間約束為約束條件.具體的排班計劃優(yōu)化模型如下.

式中 tpi(i ,ts,te,td)——表示值乘區(qū)段i的信息，i是值乘區(qū)段的編號，ts是該值乘區(qū)段的開始時刻，te是該值乘區(qū)段的結(jié)束時刻，te是該值乘區(qū)段的持續(xù)時間；

dyj(j ,cj,{t pi})——表示值乘交路 j的信息，j是值乘交路的編號，cj是值乘交路 j對應(yīng)的乘務(wù)員，{tpi}的是組成值乘交路 j的值乘區(qū)段的集合，tpi按時序排列；

drk(k ,tdk,luk,suk)——表示乘務(wù)員k的信息，其中k是乘務(wù)員的編號，同對應(yīng)的值乘交路的編號相同，tdk是其連續(xù)的值乘時間.luk為0-1變量，取1時該乘務(wù)員需要午餐時間，取0時則不需要，suk為0-1變量，取1時該乘務(wù)員需要晚餐時間，取0時則不需要.

式(6)保證值乘交路對值乘區(qū)段的完全覆蓋.

式(7)描述了值乘區(qū)段和值乘交路的唯一對應(yīng)關(guān)系.

式(9)為值乘時間約束.其中,nj是屬于值乘交路 j的值乘區(qū)段的數(shù)目;分別是值乘交路j中最后一個值乘區(qū)段的結(jié)束時刻、第一個值乘區(qū)段的開始時刻，即值乘交路 j的結(jié)束時刻和開始時刻.

式(11)、式(12)為夜間休息時間限制.其中，xk是0-1變量，取1表示乘務(wù)員k的連續(xù)值乘時間已經(jīng)超過閥值而必須進(jìn)行休息；M是一個大數(shù).

式(13)為進(jìn)餐時間約束.其中，tm是進(jìn)餐間隔，實(shí)際中至少為24 min；lm是0-1變量，用來判斷當(dāng)前時刻是否處于進(jìn)餐區(qū)間中：ltm取1時表示當(dāng)前時刻處于進(jìn)餐區(qū)間中，否則不處于進(jìn)餐區(qū)間中.

4 求解算法

針對上述構(gòu)建模型的特點(diǎn)，設(shè)計求解算法如下.

（1）求解思路.

模型的求解過程分為三步，首先是值乘區(qū)段組合構(gòu)成值乘交路的過程，然后再使用雙向匹配來完成“晚—早同員”的搭配，最終計算優(yōu)化整個排班計劃的時間均衡度.

根據(jù)乘務(wù)規(guī)則，對列車運(yùn)行線進(jìn)行分割，從而得到值乘區(qū)段集合.值乘區(qū)段按照乘務(wù)規(guī)則進(jìn)行組合，形成值乘交路.值乘交路分成早班、白班和夜班三個班次，使用雙向匹配來完成“晚—早同員”的搭配.

（2）遺傳算法及流程.

求解上述模型采用遺傳算法，染色體采用0-1編碼.染色體設(shè)置為m×n的矩陣（Am×n），其中m是值乘區(qū)段的個數(shù)，n是班次的數(shù)目（排班計劃包含早班、白班和晚班）.該矩陣中的元素xij為0-1決策變量，xij=1時值乘區(qū)段i被分配在班次 j中，xij=0則值乘區(qū)段i不在班次 j中.根據(jù)值乘區(qū)段的唯一完全覆蓋約束，有

遺傳算法的適應(yīng)度函數(shù)由模型的目標(biāo)函數(shù)和懲罰函數(shù)兩部分組成，其公式為

式中 pi(Am×n)是第i個約束條件對應(yīng)懲罰函數(shù).

求解算法由初始種群的產(chǎn)生、交叉、變異、適應(yīng)度函數(shù)計算和求解過程終止判斷五個環(huán)節(jié)組成.交叉、變異等操作均通過改變?nèi)旧w矩陣中某些行的順序完成，算法流程如圖1所示.圖1中虛線框內(nèi)染色體根據(jù)乘務(wù)規(guī)則確定方法分為三個班次，左側(cè)的操作是不同班次的值乘時間和休息時間的隸屬度函數(shù)的計算，右側(cè)則是使用遺傳算法獲得最優(yōu)的“晚—早同員”匹配.這兩部分的計算結(jié)果與懲罰函數(shù)的和作為染色體的適應(yīng)度函數(shù).

圖1 算法流程圖Fig 1 Flow chart of the developed algorithm

5 案例研究

本文以北京某城市軌道交通線路作為案例進(jìn)行所建優(yōu)化模型的驗(yàn)證分析.該線作為北京城市軌道交通網(wǎng)絡(luò)東西向骨干線路的東段延長線，連接了北京中心城區(qū)及東部的新城.全長19.0 km，共設(shè)13座車站，乘務(wù)基地設(shè)置在最東端的盡頭站.客流高峰時最小追蹤間隔3.5 min.值乘區(qū)段平均時長1 h 6 min.既有排班計劃采用人工編制，主要依賴于編制工作人員的經(jīng)驗(yàn).

（1）模型中參數(shù)的標(biāo)定及其依據(jù)如表1所列.

為確保求解結(jié)果的穩(wěn)定性，本文進(jìn)行10次優(yōu)化模型的求解運(yùn)算.將10次求解結(jié)果取算術(shù)平均值

（2）求解結(jié)果與分析.

經(jīng)過分析比較，案例求解結(jié)果在初始種群規(guī)模為100，迭代次數(shù)為2 000次的情況下得到了較好的結(jié)果.適應(yīng)度收斂曲線如圖2所示.

表1 案例參數(shù)取值情況Table 1 Value of parameters in the case study

圖2 適應(yīng)度收斂曲線Fig 2 Convergence curves of fitness function

模型優(yōu)化結(jié)果與既有排班計劃的對比如表2所列.

表2 模型優(yōu)化結(jié)果與既有排班計劃效率比較Table 2 Efficiency comparisons between the improved model and existing method

通過表2中優(yōu)化結(jié)果與既有排班計劃比較可知，優(yōu)化模型獲得的乘務(wù)排班計劃值乘時間成本降低1.99%，值乘時間均衡程度和夜間休息時間均衡度的改善顯著，優(yōu)化率分別為11.87%和61.09%.

案例中20個乘務(wù)班次的早班值乘時間、白班值乘時間、晚班值乘時間，夜班值乘時間和夜間休息時間5項(xiàng)指標(biāo)的既有排班計劃和模型優(yōu)化結(jié)果數(shù)據(jù)對比如圖3（a）至（e）所示.

圖3 既有排班計劃值乘班次數(shù)據(jù)與優(yōu)化結(jié)果比較Fig.3 Comparisons the detailed results from the improved model and existing method

從圖3可知，優(yōu)化模型得到20個乘務(wù)班次的晚班值乘時間、夜班值乘時間、夜間休息時間和白班值乘時間的均衡度與既有排班計劃相比顯著改善；早班值乘時間的均衡度略有下降，但并不顯著，表明本文所構(gòu)建模型總體上改善了乘務(wù)排班計劃的各項(xiàng)均衡度指標(biāo).此外，既有排班計劃需要安排26個班次才能完成值乘任務(wù)，通過優(yōu)化模型獲得的乘務(wù)排班計劃則僅需20個班次就能完成相同的值乘任務(wù)，明顯提高了值乘任務(wù)的安排效率.

6 研究結(jié)論

根據(jù)城市軌道交通乘務(wù)排班計劃工作的實(shí)際需要，考慮了值乘區(qū)段的間隔時間、各班次的值乘時間、夜間休息時間等影響排班計劃時間均衡度的因素，構(gòu)建了基于時間均衡度的排班計劃優(yōu)化模型，采用遺傳算法對模型進(jìn)行了求解.以實(shí)際城市軌道交通線路的乘務(wù)排班工作為例，應(yīng)用所建模型在既有運(yùn)行圖基礎(chǔ)上進(jìn)行排班計劃優(yōu)化研究，并將優(yōu)化結(jié)果與既有排班計劃進(jìn)行了對比分析，獲得以下結(jié)論.

（1）基于時間均衡度的排班計劃優(yōu)化模型可有效提高排班計劃的時間均衡度.通過案例研究可知，排班計劃時間成本降低了1.99%，值乘時間均衡度提高了11.87%，夜間休息時間均衡程度提高了61.09%，所需乘務(wù)班次數(shù)量減少6個.

（2）對不同班次（早班、晚班、白班、夜班）值乘時間的分析可知，優(yōu)化模型總體上改善了乘務(wù)排班計劃的效率與值乘時間均衡度，但部分班次優(yōu)化效果不顯著，在后續(xù)研究工作中需要進(jìn)一步改善.

[1] 褚飛躍，田志強(qiáng)，倪少權(quán).高速鐵路單循環(huán)乘務(wù)排班計劃編制模型與算法[J].鐵道學(xué)報，2012,34(7):1-9. [CHU F Y,TIAN S Q,NI S Q.Model and algorithm for formulation of the single cycle crew rostering plans of high-speed railways[J].Journal of the China Railway Society,2012,34(7):1-9.]

[2] 王瑩，劉軍，苗建瑞.客運(yùn)專線乘務(wù)交路計劃編制的優(yōu)化模型與算法[J].鐵道學(xué)報，2009,31(1):15-19. [WANG Y,LIU J,MIAO J R.Modeling and solving the crew scheduling problem of passenger dedicated line[J]. Journal of the China Railway Society,2009,31(1):15-19.]

[3] Steinzen I,Gintner V,Suhl L,et al.A time-space network approach for the integrated vehicle-and crewscheduling problem with multiple depots[J]. Transportation Science,2010,44(3):367-382.

[4] Mesquita M,Paias A.Set partitioning∕covering-based approaches for the integrated vehicle and crew scheduling problem[J]. Computer & Operations Research,2008,35(5):1562-1575.

[5] 張?jiān)鲇拢ＨA，杜鵬，等.基于懲罰費(fèi)用的城市軌道交通乘務(wù)排班優(yōu)化模型與算法[J].交通運(yùn)輸系統(tǒng)工程與信息，2014,14(2):113-120.[ZHANG Z Y,MAO B H,DU P,et al.Urban rail transit crew scheduling model and algorithm based on punishment costs[J].Journal of Transportation Systems Engineering and Information Technology,2014,14(2):113-120.]

[6] 李獻(xiàn)忠，徐瑞華.基于時間耗費(fèi)的城市軌道交通乘務(wù)排班優(yōu)化[J].鐵道學(xué)報，2007,29(1):21-25.[LI X Z, XU R H.Optimization of crew scheduling for urban rail transportation based on time costs[J].Journal of the China Railway Society,2007,29(1):21-25.]

[7] 李獻(xiàn)忠，徐瑞華.基于乘務(wù)廣義費(fèi)用的城市軌道交通排班[J].同濟(jì)大學(xué)學(xué)報，2007,35(6):750-754.[LI X Z, XU R H.An optimal wide crew-related costs-based scheduling for crew of urban rail transportation[J]. Journal of Tongji University(Natural Sciense),2007,35(6):750-754.]

[8] Zaepfel G,Boegl M.Multi-period vehicle routing and crew scheduling with outsourcing options[J]. International Journal of Product Economics,2008,113 (2):980-996.

[9] Jutte S,Albers M,Thonemann U W,et al.Optimizing railway crew scheduling at DB schenker[J].Interfaces, 2011,41(2):109-122.

[10] 胡思繼.列車運(yùn)行圖編制理論[M].北京:中國鐵道出版社，2007.[HU S J.Theory of train diagram[M]. Beijing:China Railway Press,2007.]

[11] 銀大偉.乘務(wù)計劃編制系統(tǒng)的研究與設(shè)計[D],西南交通大學(xué)，2008.[YIN D W.Research and design of crew scheduling system[D]. The Southwest Jiaotong University,2008.]

[12] Yunes T H,Moura A V,de Souza C C.Hybrid column generation approaches for urban transit crew management problems[J].Transportation Science,2005, 39(2):274-288.

Time Equitability-based Crew Scheduling Optimization for Urban Rail Transit

FENG Fu,CHEN Shao-kuan,DU Peng
(The MOE Key Laboratory for Urban Transportation Complex Systems Theory and Technology,Beijing Jiaotong University, Beijing 100044)

Crew scheduling of urban rail transit system,whose quality have a significant influence on the operational efficiency of urban rail transit,is an important part of urban rail transit operational management. This paper imports equilibrium as the indicator assessing the reasonability of the whole crew’s shift and rest in given period with minimum cost,on the basis of which an improved model for crew scheduling is established.Then in order to take into count the best match of shifts and the proper combination of morning and night shifts synchronously,the solution for the model is disassembled into two consistent phases that refers to the greedy algorithm and bi-direction matching method.Finally,this model is applied in the case study of the urban rail transit system in Beijing and achieves a better performance compared to the existing crew scheduling solution.As a result,the improved model upgrades effectively the time equitability of the crew scheduling.

urban traffic;urban rail transit;optimization model;genetic algorithm;crew scheduling;time equitability

2014-06-21

2014-09-11錄用日期：2014-09-27

國家重點(diǎn)基礎(chǔ)研究發(fā)展計劃（2012CB725406）；國家自然科學(xué)基金項(xiàng)目（71131001）；北京市科技新星計劃（Z121106002512028）.

豐富（1990-），男，湖北黃岡人，碩士生. *

shkchen@bjtu.edu.cn

1009-6744(2014)06-0164-07

U268.6

A