基于地鐵乘務(wù)資源共享的排班計劃優(yōu)化方法

金華，陳紹寬，王志美，張翕然，許鳳志

(北京交通大學，交通運輸部綜合交通運輸大數(shù)據(jù)應(yīng)用技術(shù)交通運輸行業(yè)重點實驗室，北京100044)

0 引言

目前，地鐵以分線獨立運營為主，每條線路所屬乘務(wù)員和乘務(wù)基地獨立使用。本文提出的乘務(wù)資源共享是指列車不跨線運營情形下允許乘務(wù)員跨線值乘，即可在一個班次內(nèi)值乘多條線路的值乘任務(wù)，同時允許乘務(wù)員選擇乘務(wù)基地出退勤，以減少通勤時間。

基于資源共享的運營組織方法與技術(shù)已逐步受到關(guān)注，但仍亟待進一步深化[1]。既有資源共享研究多集中在車輛基地資源共享[2]、車輛資源共享[3]、國鐵與城市軌道交通的資源共享[3]，以及應(yīng)急狀態(tài)下的資源調(diào)配問題研究[4]。乘務(wù)資源共享方面，已有學者提出通過乘務(wù)員共享以均衡不同線路間的工作量，但主要集中在優(yōu)缺點的分析及編制思路的探討[5]，缺少關(guān)于具體排班計劃優(yōu)化方法的深入研究。

本文綜合考慮乘務(wù)員和乘務(wù)基地共享條件下的乘務(wù)排班計劃問題。乘務(wù)員共享可以降低不同線路間值乘任務(wù)工作量的不均衡性，提高乘務(wù)員利用效率。乘務(wù)基地共享可以提供更多的出退勤地點選擇，滿足乘務(wù)員就近出退勤的個性化需求，顯著節(jié)省乘務(wù)員出退勤的通勤時間。

傳統(tǒng)乘務(wù)排班優(yōu)化問題的研究方法分為基于班次的集合覆蓋模型優(yōu)化[6]和基于乘務(wù)區(qū)段的網(wǎng)絡(luò)流問題優(yōu)化[7]。后者可準確表示一些約束不太復(fù)雜的問題，但當問題規(guī)模較大時，其模型復(fù)雜程度通常遠超集合覆蓋模型[8]。針對較大規(guī)模的乘務(wù)排班優(yōu)化問題，除啟發(fā)式方法外，主要采用集合覆蓋模型結(jié)合列生法求解以避免生成規(guī)模龐大的可行班次集合。其中，列生成法的關(guān)鍵點在于定價子問題的求解和整數(shù)解的獲得[8]。文獻[9]構(gòu)建了基于連續(xù)值乘區(qū)段的多層時空網(wǎng)絡(luò)圖以表示班次可行性約束，之后通過生成網(wǎng)絡(luò)圖集合表示所有可行班次，從而將定價子問題轉(zhuǎn)化為最短路問題。相較于傳統(tǒng)乘務(wù)排班問題，乘務(wù)資源共享需要考慮跨線接續(xù)、魯棒性優(yōu)化及不同出退勤地點班次比例的控制，且問題規(guī)模較大，難以用網(wǎng)絡(luò)流方法求解。對此，本文在文獻[9]提出的網(wǎng)絡(luò)圖模型基礎(chǔ)上針對乘務(wù)資源共享需求進行調(diào)整，改造定價子問題的求解，并采用Gurobi求解整數(shù)規(guī)劃問題的整數(shù)解。

1 乘務(wù)資源共享分析

乘務(wù)資源共享對排班問題的影響可以分為執(zhí)行和編制兩個方面。在執(zhí)行層面，為實現(xiàn)跨線值乘應(yīng)將換乘站設(shè)置為輪乘站，并需要乘務(wù)員具備不同線路列車的駕駛資質(zhì)?？紤]乘務(wù)員就近出退勤的需要，應(yīng)將其按照偏好的乘務(wù)基地進行劃分，分組獨立進行輪班。具體到編制層面，乘務(wù)資源共享下的乘務(wù)排班問題相較于傳統(tǒng)排班問題主要有以下難點。

(1)乘務(wù)區(qū)段的跨線接續(xù)。乘務(wù)員僅本線值乘時，地鐵排班問題中乘務(wù)區(qū)段接續(xù)關(guān)系有3 種：一是乘務(wù)員連續(xù)值乘同一列車的相鄰乘務(wù)區(qū)段，稱為連續(xù)值乘接續(xù)；其余兩種為不同列車乘務(wù)區(qū)段的接續(xù)，根據(jù)乘務(wù)員在輪乘站進行休息或就餐分為間休接續(xù)和就餐接續(xù)。乘務(wù)區(qū)段跨線接續(xù)僅包含間休接續(xù)和就餐接續(xù)，且只發(fā)生在換乘站，需要在原接續(xù)時間的基礎(chǔ)上增加走行時間，并考慮額外的冗余時間以增強魯棒性。

(2)出退勤比例約束。班次的出退勤地點類型是指班次開始和結(jié)束時所在的乘務(wù)基地位置，需根據(jù)不同出退勤地點偏好的乘務(wù)員數(shù)量比例，控制不同出退勤地點類型班次的比例。

(3)魯棒性。乘務(wù)員僅本線值乘時乘務(wù)計劃受擾動影響較小，乘務(wù)資源共享后擾動可能使跨線接續(xù)無法進行，故乘務(wù)計劃需要更強的魯棒性。

(4)問題規(guī)模增大。多線間乘務(wù)資源共享會增加問題求解規(guī)模。

2 模型構(gòu)建

2.1 優(yōu)化目標

排班問題研究主要以排班計劃效率優(yōu)化為主[8]。對于魯棒性的優(yōu)化考慮增加冗余時間[10]，例如提高最小接續(xù)時間、減小最大工作時間等，或通過減少便乘以降低延誤傳播[7]。其中，便乘是指乘務(wù)員搭乘其他乘務(wù)員值乘的列車轉(zhuǎn)移到其他輪乘站接續(xù)所承擔乘務(wù)區(qū)段的行為。由于最小接續(xù)時間和最大工作時間是模型參數(shù)，本文以班次數(shù)為主要優(yōu)化目標，以總便乘時間為次要目標進行魯棒性優(yōu)化。目標函數(shù)為

式中：J為可行班次集合；xj為決策變量，當班次j為最終排班計劃中的班次時為1，否則為0；μ為魯棒性優(yōu)化目標系數(shù)；cj為班次j的便乘時間。為便于處理定價子問題，將目標中的cj改為班次j的在車時間c′j(包含便乘時間)。由于總車次任務(wù)時間為定值，對總在車時間的優(yōu)化等價于對總便乘時間的優(yōu)化。這種轉(zhuǎn)化主要考慮定價子問題求解中是否屬于便乘難以界定，而在車時間可以由班次包含的乘務(wù)區(qū)段時長進行表示。

為優(yōu)先班次數(shù)，需使總班次數(shù)遠大于總在車時間?？赏频忙绦铦M足

2.2 相關(guān)約束

排班約束分為橫向約束(班次內(nèi)可行性約束)和縱向約束(班次間約束)。其中，橫向約束主要包含8條，較為復(fù)雜，本文設(shè)計網(wǎng)絡(luò)圖進行表示，在2.3節(jié)介紹。

縱向約束包含乘務(wù)區(qū)段的全覆蓋約束和出退勤比例約束。其中，全覆蓋約束保證每個乘務(wù)區(qū)段均有班次覆蓋，即

式中：I為乘務(wù)區(qū)段集合；aij為0-1 變量，當班次j包含乘務(wù)區(qū)段i時為1，否則為0。

出退勤比例約束保證每種出退勤地點類型班次在最終排班計劃中的比例，即

式中：H為出退勤地點類型集合；bhj為班次j是否屬于出退勤地點類型h，屬于為1，否則為0；αh為出退勤地點類型h所占的比例。

2.3 網(wǎng)絡(luò)圖模型

參考文獻[9]提出的時空網(wǎng)絡(luò)圖模型的構(gòu)建思路，用單層和雙層網(wǎng)絡(luò)圖表示無就餐和包含就餐班次的所有可行性約束，通過網(wǎng)絡(luò)圖生成算法考慮不同班次類型和就餐情況分別生成網(wǎng)絡(luò)圖以盡可能表示所有可行班次。以圖1所示雙層網(wǎng)絡(luò)圖模型為例介紹網(wǎng)絡(luò)圖的構(gòu)成。枚舉所有僅通過連續(xù)值乘接續(xù)的連續(xù)值乘區(qū)段，用任務(wù)開始和結(jié)束點表示連續(xù)值乘區(qū)段的開始和結(jié)束事件，并用任務(wù)弧連接對應(yīng)同一連續(xù)值乘區(qū)段的任務(wù)開始和結(jié)束點；用源點和匯點表示班次的開始和結(jié)束，并用源點弧連接源點與就餐前層的所有任務(wù)開始點，用匯點弧連接就餐后層的所有任務(wù)結(jié)束點與匯點。為解決出退勤比例約束，在源點弧和匯點弧中間額外插入對應(yīng)每個輪乘站地點的二級源點和二級匯點，并在其提出的網(wǎng)絡(luò)圖生成算法基礎(chǔ)上通過改變一級源點(匯點)與二級源點(匯點)之間的連接將網(wǎng)絡(luò)圖集合分割為對應(yīng)不同出退勤地點類型的網(wǎng)絡(luò)圖集合，每個網(wǎng)絡(luò)圖集合都只包含對應(yīng)出退勤地點類型的班次，網(wǎng)絡(luò)圖生成算法如圖2所示。除采用間休弧和就餐弧表示間休和就餐接續(xù)活動，本文還增加了跨線間休弧和跨線就餐弧以表示跨線接續(xù)。

圖1 雙層網(wǎng)絡(luò)圖模型示意圖Fig.1 Diagram of double-layer network

結(jié)合網(wǎng)絡(luò)圖對8條橫向約束的表示，網(wǎng)絡(luò)圖構(gòu)建規(guī)則如下。

(1)最大連續(xù)駕駛時間約束。連續(xù)值乘接續(xù)不能超過最大連續(xù)駕駛時間，枚舉所有滿足最大連續(xù)駕駛時間約束的連續(xù)值乘區(qū)段作為網(wǎng)絡(luò)圖最小任務(wù)單元。

(2)最小和最大接續(xù)時間約束。就餐和間休接續(xù)應(yīng)滿足各自的最大和最小接續(xù)時間，對應(yīng)到網(wǎng)絡(luò)圖中，規(guī)定間休弧和就餐弧只連接滿足接續(xù)時間約束的任務(wù)結(jié)束點和開始點，如圖1中A、B、C 與D、D′之間的接續(xù)。

(3)跨線接續(xù)約束?？缇€接續(xù)需在原最小和最大接續(xù)時間基礎(chǔ)上增加走行和冗余時間，且只發(fā)生在換乘站。在網(wǎng)絡(luò)圖中跨線間休和就餐接續(xù)用跨線間休弧和跨線就餐弧表示，只連接換乘站中滿足相關(guān)時間約束的任務(wù)結(jié)束點和開始點，例如圖1中A、B、C與E、E′之間的接續(xù)。

(4)空間接續(xù)約束。接續(xù)乘務(wù)區(qū)段的開始地點與被接續(xù)乘務(wù)區(qū)段的結(jié)束地點相同，對應(yīng)到網(wǎng)絡(luò)圖中表現(xiàn)為間休弧、就餐弧、跨線間休弧和跨線就餐弧都只連接同一輪乘站的結(jié)束點和開始點。

(5)就餐時段約束。就餐需在給定就餐時段內(nèi)，故就餐弧和跨線就餐弧僅存在于就餐時段內(nèi)，例如圖1中17:00-19:00時段。

(6)強制就餐約束。包含就餐時段的班次需安排就餐，故采用分層結(jié)構(gòu)的網(wǎng)絡(luò)圖，例如圖1包含就餐前和就餐后兩層相同的網(wǎng)絡(luò)圖。源點、二級源點和源點弧只連接就餐前層，匯點、二級匯點和匯點弧只連接就餐后層。兩層之間僅通過就餐弧和跨線就餐弧連接，因此任何一條從源點到匯點的路徑都會經(jīng)過一條就餐弧或跨線就餐弧。對于不包含就餐的班次則通過單層網(wǎng)絡(luò)圖進行表示，其結(jié)構(gòu)與雙層網(wǎng)絡(luò)圖類似，僅包含一層，且不考慮就餐和跨線就餐弧。

(7)最大工作時間約束。每種班次類型有各自的最大工作時間，故將網(wǎng)絡(luò)圖的時間跨度設(shè)為對應(yīng)班次類型的最大工作時間。

(8)工作時間范圍約束。每種類型班次需在對應(yīng)班次類型的時間范圍內(nèi)，因此在網(wǎng)絡(luò)圖生成過程中根據(jù)不同班次類型，在其時間范圍內(nèi)分別生成網(wǎng)絡(luò)圖來表示，網(wǎng)絡(luò)圖生成算法如圖2所示。

圖2 網(wǎng)絡(luò)圖生成算法流程Fig.2 Flow chart of network generation algorithm

單層網(wǎng)絡(luò)圖結(jié)構(gòu)類似，但只包含一層，且無就餐與跨線就餐弧。

3 求解算法

在網(wǎng)絡(luò)圖模型的基礎(chǔ)上，將定價子問題轉(zhuǎn)化為若干個網(wǎng)絡(luò)圖集合的最短路問題，采用列生成法求解。列生成法將問題劃分為主問題(Master Problem，MP)和定價子問題(Pricing Problem，PP)，循環(huán)迭代求解，總體算法流程如圖3所示。階段1為準備階段，構(gòu)建對應(yīng)的網(wǎng)絡(luò)圖集合和初始可行班次，網(wǎng)絡(luò)圖生成算法如圖2所示；階段2為傳統(tǒng)的列生成迭代優(yōu)化階段；階段3為整數(shù)解獲取階段。

階段2 中定價子問題的求解是列生成法的關(guān)鍵，根據(jù)主問題確定定價子問題的表達式。標準排班計劃主問題可表示為

式中：I*=I?H，包含全覆蓋約束和出退勤比例約束；c*j為標準化后目標的價值系數(shù)，根據(jù)式(1)可以推得c*j =1+μ·c′j；a*ij和d*i為標準化后約束的消耗系數(shù)和資源限制系數(shù)，根據(jù)式(3)和式(4)，可得

代入c*j和a*ij可以得到定價子問題為

式中：σj為班次j的檢驗數(shù)；ηi為第i個乘務(wù)區(qū)段全覆蓋約束的影子價格；η′h為出退勤地點類型h出退勤比例約束的影子價格；c′j為班次j的在車時間，可轉(zhuǎn)化為每個乘務(wù)區(qū)段在車時間ti之和。據(jù)此，式(10)可轉(zhuǎn)化為

式中：Z1,j完全取決于班次j覆蓋的乘務(wù)區(qū)段；Z2,j取決于班次j的出退勤地點類型。因此，只要將網(wǎng)絡(luò)圖中的任務(wù)弧弧長設(shè)置為

式中：λl為任務(wù)弧l的弧長；Il為任務(wù)弧l對應(yīng)的連續(xù)值乘區(qū)段所包含的乘務(wù)區(qū)段集合。即可通過最短路算法獲得每個網(wǎng)絡(luò)圖中Z1,j最小的班次。

Z2,j完全取決于班次j的出退勤地點類型，只需獲得每種出退勤地點類型對應(yīng)的網(wǎng)絡(luò)圖集合Gh的最短路，其中必然有一條為定價子問題搜索的最優(yōu)解。具體到算法中表現(xiàn)為在階段2 列生成迭代中，將所有出退勤地點類型對應(yīng)的網(wǎng)絡(luò)圖集合Gh的最短路都加入主問題的班次集合P中。

圖3 求解算法流程Fig.3 Flow chart of solution method

4 案例分析

4.1 案例背景

以北京市2條地鐵線路為背景進行案例分析，線路信息如表1所示。輪乘站A 為兩條線路的換乘站，班次的出退勤地點包括A、B兩個輪乘站及車輛段。假設(shè)乘務(wù)員對輪乘站A、B有各自偏好，但均可以接受在車輛段出退勤。根據(jù)出退勤地點可將班次劃分為4 種類型，如表2所示。偏好輪乘站A的乘務(wù)員可接受類型1 和3 的班次，偏好輪乘站B的可接受類型2 和3 的班次，類型4 班次分別在輪乘站A、B出退勤，其數(shù)量比例得到控制。

表1 線路信息Table 1 Line related parameters

表2 班次出退勤地點分類Table 2 Shift classification based on starting and ending locations

4.2 優(yōu)化結(jié)果分析

以分線單獨優(yōu)化排班計劃作為對照組，實驗組為基于乘務(wù)資源共享的5 組方案，如表3所示。表中最后3列為方案的出退勤比例約束參數(shù)。例如，方案3 要求類型1 加類型3，以及類型2 加類型3 的班次比例均不小于45%，類型4的班次比例不大于10%，分別對應(yīng)對輪乘站A、B有偏好及對出退勤地點無偏好的乘務(wù)員比例。對照組在構(gòu)建網(wǎng)絡(luò)圖時不考慮跨線就餐和間休弧，其余模型算法與方案1相同。

表3 案例方案設(shè)計Table 3 Set of cases

算法階段3中采用Groubi求解整數(shù)規(guī)劃問題，最大求解時間設(shè)為4 h。案例結(jié)果如表4所示，其中，工作效率為有效駕駛時間除以總工作時間。對比對照組與實驗組的結(jié)果可知：乘務(wù)資源共享之后可節(jié)省3個班次，提高工作效率0.33%～1.77%，說明乘務(wù)資源共享可緩解值乘任務(wù)時空上的不均衡性進而提高乘務(wù)員利用率；方案5與方案1相比，可減少39.05%的便乘數(shù)量，證明魯棒性優(yōu)化可以有效減少便乘，降低延誤傳播風險，但多線路協(xié)同優(yōu)化及對出退勤地點的限定產(chǎn)生一定的便乘需求，因此優(yōu)化結(jié)果中存在一定比例的便乘，增加了不同輪乘站間司機轉(zhuǎn)移的需要和乘務(wù)員便乘時跨線值乘的需要；方案3～方案5 的結(jié)果表明，乘務(wù)基地和乘務(wù)員共享可更好地滿足乘務(wù)員對出勤地點的個性化需求，在班次數(shù)小幅減小的前提下仍能達到不同出退勤地點類型班次的比例。例如，對不同出退勤地點類型班次數(shù)進行推算，方案5 比方案1 每天可多滿足27 位乘務(wù)員的出退勤地點偏好需求，顯著提高了乘務(wù)員的通勤出行便捷性。

表4 案例結(jié)果分析Table 4 Analysis on results from case studies

5 結(jié)論

本文對基于地鐵乘務(wù)資源共享的排班計劃優(yōu)化問題進行了研究，考慮乘務(wù)基地和乘務(wù)員共享對排班問題的影響，設(shè)計網(wǎng)絡(luò)圖模型和優(yōu)化方法，并通過實際線路開展了案例研究。案例結(jié)果表明：考慮乘務(wù)資源共享可提高不同線路間乘務(wù)資源的利用效率，增加排班效率并小幅減少班次數(shù)；在給定不同出退勤地點類型班次比例的情況下，可更好地滿足乘務(wù)員對出退勤地點的偏好，提高乘務(wù)員通勤出行的便捷性。