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

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

0 引言

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

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

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

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

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

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

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

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

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

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

2 模型構(gòu)建

2.1 優(yōu)化目標(biāo)

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

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

為優(yōu)先班次數(shù)，需使總班次數(shù)遠(yuǎn)大于總在車時間。可推得μ需滿足

2.2 相關(guān)約束

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

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

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

出退勤比例約束保證每種出退勤地點(diǎn)類型班次在最終排班計(jì)劃中的比例，即

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

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

參考文獻(xiàn)[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é)束點(diǎn)表示連續(xù)值乘區(qū)段的開始和結(jié)束事件，并用任務(wù)弧連接對應(yīng)同一連續(xù)值乘區(qū)段的任務(wù)開始和結(jié)束點(diǎn)；用源點(diǎn)和匯點(diǎn)表示班次的開始和結(jié)束，并用源點(diǎn)弧連接源點(diǎn)與就餐前層的所有任務(wù)開始點(diǎn)，用匯點(diǎn)弧連接就餐后層的所有任務(wù)結(jié)束點(diǎn)與匯點(diǎn)。為解決出退勤比例約束，在源點(diǎn)弧和匯點(diǎn)弧中間額外插入對應(yīng)每個輪乘站地點(diǎn)的二級源點(diǎn)和二級匯點(diǎn)，并在其提出的網(wǎng)絡(luò)圖生成算法基礎(chǔ)上通過改變一級源點(diǎn)(匯點(diǎn))與二級源點(diǎn)(匯點(diǎn))之間的連接將網(wǎng)絡(luò)圖集合分割為對應(yīng)不同出退勤地點(diǎn)類型的網(wǎng)絡(luò)圖集合，每個網(wǎng)絡(luò)圖集合都只包含對應(yīng)出退勤地點(diǎn)類型的班次，網(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é)束點(diǎn)和開始點(diǎn)，如圖1中A、B、C 與D、D′之間的接續(xù)。

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

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

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

(6)強(qiáng)制就餐約束。包含就餐時段的班次需安排就餐，故采用分層結(jié)構(gòu)的網(wǎng)絡(luò)圖，例如圖1包含就餐前和就餐后兩層相同的網(wǎng)絡(luò)圖。源點(diǎn)、二級源點(diǎn)和源點(diǎn)弧只連接就餐前層，匯點(diǎn)、二級匯點(diǎn)和匯點(diǎn)弧只連接就餐后層。兩層之間僅通過就餐弧和跨線就餐弧連接，因此任何一條從源點(diǎn)到匯點(diǎn)的路徑都會經(jīng)過一條就餐弧或跨線就餐弧。對于不包含就餐的班次則通過單層網(wǎng)絡(luò)圖進(jìn)行表示，其結(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為準(zhǔn)備階段，構(gòu)建對應(yīng)的網(wǎng)絡(luò)圖集合和初始可行班次，網(wǎng)絡(luò)圖生成算法如圖2所示；階段2為傳統(tǒng)的列生成迭代優(yōu)化階段；階段3為整數(shù)解獲取階段。

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

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

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

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

式中：Z1,j完全取決于班次j覆蓋的乘務(wù)區(qū)段；Z2,j取決于班次j的出退勤地點(diǎn)類型。因此，只要將網(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的出退勤地點(diǎn)類型，只需獲得每種出退勤地點(diǎn)類型對應(yīng)的網(wǎng)絡(luò)圖集合Gh的最短路，其中必然有一條為定價子問題搜索的最優(yōu)解。具體到算法中表現(xiàn)為在階段2 列生成迭代中，將所有出退勤地點(diǎn)類型對應(yīng)的網(wǎng)絡(luò)圖集合Gh的最短路都加入主問題的班次集合P中。

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

4 案例分析

4.1 案例背景

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

表1 線路信息Table 1 Line related parameters

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

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

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

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

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

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

5 結(jié)論

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