張哲銘， 王 瑩， 廖正文,3， 曹文慧

(1. 杭州派邇信息技術(shù)有限公司， 浙江 杭州 311100； 2. 北京交通大學 交通運輸學院， 北京 100044；3. 北京交通大學 軌道交通控制與安全國家重點實驗室， 北京 100044； 4. 北京國郵科迅科技發(fā)展有限公司， 北京 100032)

乘務(wù)計劃問題(CPP)是高速鐵路調(diào)度領(lǐng)域的經(jīng)典問題，計劃結(jié)果直接影響高速鐵路的運營效率和成本。乘務(wù)交路計劃問題(CSP)作為CPP中的核心問題一直備受國內(nèi)外學者關(guān)注。CSP是VRP類問題，其難點在于需要動態(tài)考慮乘務(wù)組休息和用餐時間，使該問題不能如同VRP一樣利用基于時空網(wǎng)絡(luò)(Time Space Network，TSN)的網(wǎng)絡(luò)流模型刻畫，故多數(shù)既有研究將其轉(zhuǎn)化為基于可行乘務(wù)交路的集合覆蓋問題，并借助列生成技術(shù)[1-6]或啟發(fā)式算法[7-10]求解。

在網(wǎng)絡(luò)和模型構(gòu)造方面，TSN按構(gòu)造方式主要分為兩類：時空接續(xù)網(wǎng)(Time Space Connection Network，TSCN)和時空軸線網(wǎng)(Time Space Time Line Network，TSTLN)[11]。在鐵路運輸組織領(lǐng)域，TSCN由表示具體運行任務(wù)的點和表示任務(wù)間可行接續(xù)關(guān)系的弧組成，適用于刻畫帶有相對時間——“時長”約束的問題，見圖1。TSTLN由表示運行任務(wù)時空節(jié)點的點和表示相鄰時空節(jié)點間連續(xù)關(guān)系的弧組成，適用于刻畫帶有絕對時間——“時刻”約束的問題，見圖2。在高速鐵路CSP的乘務(wù)規(guī)則中，既有“時長”約束(如乘務(wù)組單次駕駛時長等)，又有“時刻”約束(如用餐時間窗)。因此CSP是同時包含“時長”和“時刻”約束的混合時間問題。但是，既有研究大多選擇TSCN描述該問題，詳細刻畫“時長”約束，而很少考慮“時刻”約束。以用餐約束為例，在規(guī)定的時間段吃一日三餐是大多數(shù)中國人的習慣，既有研究通常假設(shè)乘務(wù)組休息時用餐，且不固定休息時間段，這導致了乘務(wù)組用餐時間不規(guī)律。只有文獻[12]考慮了固定時間窗用餐約束，但其只針對公交領(lǐng)域，與高鐵領(lǐng)域還有所差別。在求解算法方面，采用列生成技術(shù)求解帶有資源約束最短路的價格子問題時，每次搜索最短路時都要考慮乘務(wù)規(guī)則，設(shè)計多標簽最短路算法，效率不高。啟發(fā)式算法盡管求解速度快，但卻無法保證求解質(zhì)量。

對此，本文以高速鐵路CSP作為混合時間問題的代表，在構(gòu)建網(wǎng)絡(luò)模型時一次性考慮乘務(wù)規(guī)則約束，生成可以涵蓋所有可行乘務(wù)交路的網(wǎng)絡(luò)，針對網(wǎng)絡(luò)規(guī)模過大導致求解效率與質(zhì)量無法保證的問題，將乘務(wù)規(guī)則轉(zhuǎn)化為可以控制網(wǎng)絡(luò)規(guī)模的網(wǎng)絡(luò)生成策略，并借助拉格朗日松弛技術(shù)求解。首先，基于二維TSTLN構(gòu)建三維時空狀態(tài)網(wǎng)絡(luò)(Time Space State Network，TSSN)刻畫CSP。即在TSTLN上引入狀態(tài)維度，每個點新引入的狀態(tài)坐標代表乘務(wù)組訪問該點時的乘務(wù)狀態(tài)，相鄰節(jié)點間狀態(tài)坐標的變化表示一個符合乘務(wù)規(guī)則的任務(wù)弧，而由若干個任務(wù)弧組成的，從起點到終點的一條時空路徑就是一個乘務(wù)交路。其次，基于乘務(wù)規(guī)則，提出時空節(jié)點狀態(tài)坐標遞推原則和乘務(wù)任務(wù)可行轉(zhuǎn)化判定條件，將乘務(wù)規(guī)則解析為網(wǎng)絡(luò)生成策略融入TSSN，控制網(wǎng)絡(luò)規(guī)模，同時簡化數(shù)學模型。然后，基于TSSN建立0-1整數(shù)規(guī)劃模型，通過拉格朗日松弛算法松弛“難約束”，從而將原CSP分解為多個獨立乘務(wù)交路的時空最短路徑子問題集合，摘除子問題間的耦合性，同時保證求解質(zhì)量和效率。最后，通過實例對本文方法進行驗算。

1 問題描述

CSP是根據(jù)乘務(wù)規(guī)則確定各乘務(wù)組從乘務(wù)基地出乘至返回該基地退乘過程中執(zhí)行乘務(wù)任務(wù)的順序。乘務(wù)任務(wù)包括：(外段)出乘任務(wù)、接續(xù)任務(wù)、運行任務(wù)、用餐任務(wù)、換乘任務(wù)、間休任務(wù)、外段駐班任務(wù)、(外段)退乘任務(wù)。高速鐵路乘務(wù)交路的時間長度通常為1 d，但也存在2～3 d長交路的情況，此時需要安排乘務(wù)組外段駐班，每天的作業(yè)內(nèi)容稱為乘務(wù)交路段。具體的乘務(wù)規(guī)則如下[2]：

(1) 交路段規(guī)則μ為乘務(wù)組每天從出乘至退乘的上班時長，min；Tμ、Tμ分別為乘務(wù)交路段最小、最大時長，min。必須滿足μ∈[Tμ,Tμ]。

(2) 換乘規(guī)則 乘務(wù)組連續(xù)擔當不同動車交路的乘務(wù)區(qū)段時，ε為其間隔時間，min；Tε、Tε分別為最小、最大乘務(wù)換乘時間，min。必須滿足ε∈[Tε,Tε]。

(3) 間休規(guī)則 乘務(wù)組連續(xù)擔當乘務(wù)區(qū)段一段時間后必須進行間休，τ為間休時間，min；Tτ、Tτ分別為最小、最大間休時間，min。必須滿足τ∈[Tτ,Tτ]。

(4) 連續(xù)駕駛規(guī)則λ為乘務(wù)組連續(xù)擔當乘務(wù)區(qū)段的線上工作時間(含換乘時間)，min；Tλ、Tλ分別為最小、最大連續(xù)乘務(wù)時間，min。必須滿足λ∈[Tλ,Tλ]，且連續(xù)駕駛后必須進行間休后方可值乘下一駕駛?cè)蝿?wù)。

(5) 外段駐班規(guī)則 乘務(wù)組外段退乘休息時，η為其休息時間，min；Tη、Tη分別為最小、最大非基地乘務(wù)休息時間，min。必須滿足η∈[Tη,Tη]。

(6) 用餐規(guī)則 乘務(wù)組必須在中午或晚間規(guī)定的用餐時間窗Wlun、Wdin內(nèi)用餐。e為用餐時長，min；Te、Te分別為最小、最大用餐時長，min。必須滿足e∈[Te,Te]。

(7) 乘務(wù)交路規(guī)則 乘務(wù)組的出乘和退乘站點必須是同一乘務(wù)基地，最大持續(xù)天數(shù)不超過Tv。

2 TSSN

2.1 狀態(tài)維度的定義

TSTLN中，包含表示時刻的時間屬性t和表示地點的空間屬性s。而在TSSN中，除時間屬性t和空間屬性s，還需狀態(tài)屬性ω，即(t,s,ω)。如第i個時空節(jié)點的第m個狀態(tài)定義為

TSTLN和TSSN的對比見圖3。圖3中A、B、C分別表示站點，A站為乘務(wù)基地所在站，點0和點9分別代表乘務(wù)基地虛擬起、終點，其余點均為乘務(wù)區(qū)段時空節(jié)點。

本文定義了兩種用餐方式：

(1) 間休用餐 乘務(wù)組的用餐時間窗與間休時間窗交集，且交集部分不小于Te，此時默認組員在間休時用餐。

具體情況見圖4、圖5。

2.2 網(wǎng)絡(luò)生成策略

在TSSN，時空節(jié)點狀態(tài)坐標遞推原則和乘務(wù)任務(wù)可行轉(zhuǎn)化判定條件為點和弧生成策略。

點生成策略：除虛擬起點外所有節(jié)點的狀態(tài)坐標，均由該點的前繼節(jié)點的狀態(tài)坐標和入弧所代表的乘務(wù)任務(wù)遞推得出。

弧生成策略：除出乘弧外所有節(jié)點的出弧任務(wù)，均由該點的入弧代表的乘務(wù)任務(wù)和狀態(tài)坐標遞推得出。

因此，在所有乘務(wù)基地的虛擬起點和出乘弧已知的條件下，不斷交替使用點和弧生成策略即可構(gòu)建TSSN。

2.2.1 時空節(jié)點狀態(tài)坐標遞推原則

2.2.2 乘務(wù)任務(wù)可行轉(zhuǎn)化判定條件

在TSSN中，所有類型的乘務(wù)任務(wù)均可通過不同類型的弧表示，除虛擬起點外的所有節(jié)點的出弧所代表的乘務(wù)任務(wù)均由該點的狀態(tài)坐標和入弧任務(wù)決定。乘務(wù)任務(wù)可行轉(zhuǎn)化關(guān)系見圖7。

表1 乘務(wù)任務(wù)可行轉(zhuǎn)化判定條件

2.3 網(wǎng)絡(luò)生成示例

為了詳細說明TSSN的生成策略，本文分別列舉在無用餐規(guī)則和有用餐規(guī)則條件下的TSSN生成過程。

以圖3(a)為例，uij為線段所代表乘務(wù)任務(wù)。假設(shè)：(1)各區(qū)間運行時間均為30 min；(2)列車在B站的接續(xù)時間為10 min；(3)列車在C站的折返時間為20 min；(4)A站為乘務(wù)基地所在站，乘務(wù)組的出乘時間tg、退乘時間tb為tg=tb=60 min；(5)點1所在時刻為11:00。

2.3.1 無用餐規(guī)則

假設(shè)：(1)最小換乘時間為10 min；(2)不規(guī)定固定的用餐時間窗；(3)連續(xù)值乘3 h左右退乘；(4)乘務(wù)規(guī)則參數(shù)：[Tλ,Tλ]=[150,180]min、[Tτ,Tτ]=[+∞,+∞]、[Tε,Tε]=[10,100]min、 [Tμ,Tμ]=[270,300]min。

2.3.2 有用餐規(guī)則

2.4 構(gòu)建TSSN

2.4.1 建立TSTLN

2.4.2 狀態(tài)維度的引入

在廣度優(yōu)先遍歷(Breadth First Search，BFS)過程中，TSTLN中的每個時空節(jié)點的不同狀態(tài)均會被轉(zhuǎn)化為TSSN中的一個時空狀態(tài)節(jié)點，相鄰時空節(jié)點間不同的狀態(tài)轉(zhuǎn)換均會被轉(zhuǎn)化為TSSN中的一條時空狀態(tài)轉(zhuǎn)換弧，從而構(gòu)成TSSN，記為Gtss=(Vtss,Atss)，Gtss表示TSSN，Vtss和Atss分別表示TSSN中的點集合和弧集合。簡而言之，在TSTLN中引入狀態(tài)維度后的變化為：(1)時空節(jié)點i的m個狀態(tài)ωi=[ωi(1),ωi(2),…,ωi(m)]變?yōu)門SSN中m個時空狀態(tài)節(jié)點；(2)連接各個時空狀態(tài)節(jié)點的弧表示不同的乘務(wù)任務(wù)。

Step1統(tǒng)計乘務(wù)基地個數(shù)Ncb，并將乘務(wù)基地排序，令循環(huán)變量k=1。

Step3若k=Ncb，算法停止；否則，k=k+1，轉(zhuǎn)入Step2。

3 基于拉格朗日松弛的優(yōu)化模型及求解方法

3.1 初始模型

( 1 )

( 2 )

( 3 )

( 4 )

( 5 )

式( 1 )表示乘務(wù)任務(wù)總累計時間最小的總目標；式( 2 )表示所有乘務(wù)區(qū)段必須被覆蓋約束，且該乘務(wù)區(qū)段允許“便乘”；式( 3 )表示流平衡約束，式( 4 )表示每個乘務(wù)交路的初始任務(wù)必須為出乘任務(wù)約束；式( 5 )表示決策變量取值范圍約束。

3.2 優(yōu)化模型

在TSSN中，若乘務(wù)交路p∈P出現(xiàn)在最優(yōu)解中，則意味著p包含具體由乘務(wù)任務(wù)??；否則，p選中虛擬停駐弧，代表執(zhí)行p的乘務(wù)組處于休息狀態(tài)。本文采用拉格朗日松弛算法求解，其本質(zhì)是利用拉格朗日乘子對“難約束”所對應(yīng)的資源“定價”，將“難約束”松弛到目標函數(shù)中，原問題隨即被分解為由多個“簡單約束”構(gòu)成的子問題，簡化模型求解，同時又為原問題提供了一個可靠下界，然后不斷迭代求解子問題，在此過程中持續(xù)通過次梯度算法持續(xù)更新拉格朗日乘子，這也就相當于對“難約束”所對應(yīng)的資源“動態(tài)定價”，從而不斷提升下界，直至收斂。在CSP中，需要被“動態(tài)定價”的資源有兩類，一類是式( 2 )對應(yīng)的乘務(wù)區(qū)段資源l，其決定了乘務(wù)組值乘的乘務(wù)內(nèi)容；另一類是停駐資源，其保證了乘務(wù)組大休。此外，由于CSP是“匿名”計劃，所有p之間無差別，這種對稱性會導致收斂效果不佳。對此，本文在不破壞3.1節(jié)中模型結(jié)構(gòu)的前提下，通過兩個方法解決上述問題：(1)添加式(10)對停駐資源“動態(tài)定價”；(2)為?p∈P賦予權(quán)重gp規(guī)定p之間的順序。

( 6 )

( 7 )

( 8 )

( 9 )

(10)

(11)

與初始模型相比，該模型改變了目標函數(shù)，增加權(quán)重gp、迭代次數(shù)k和式(10)。式( 6 )中g(shù)p為乘務(wù)區(qū)段l對于p的“會員折扣”，p在選擇l時所付“實際費用”等于l的“市場價格”(弧長)與“會員折扣”的乘積。雖然gp會改變初始模型的總目標，但不會改變完成CSP所用的實際乘務(wù)組數(shù)，所以引入gp并不破壞模型結(jié)構(gòu)。式(10)表示第k次迭代時，乘務(wù)基地i的虛擬停駐弧被覆蓋的次數(shù)不小于前k-1次迭代的最優(yōu)值，該約束不僅能對停駐資源“定價”，還能通過當前最優(yōu)上界給拉格朗日對偶問題反饋，加速收斂。

3.3 拉格朗日對偶問題

在優(yōu)化模型中，式( 7 )和式(10)使p間相互制約而耦合，為該模型的“難約束”，影響求解速度。因此，通過拉格朗日乘子懲罰項的形式將其松弛到目標函數(shù)中，余下所有約束均作用于單個p，原CSP被分解為針對每個p的時空最短路徑問題集合，從而解除各個p間的耦合性，提高求解效率。拉格朗日松弛對偶問題優(yōu)化模型為

L(ρ,δ)=

(12)

(13)

(14)

(15)

式中：ρ(k)(l)、δ(k)(i)分別為第k次迭代乘務(wù)區(qū)段資源和停駐資源的拉格朗日乘子，代表解不滿足式( 7 )和式(10)時的懲罰值。

式(12)經(jīng)等價變換后可得

(16)

對于每個p的時空最短路徑問題，本文選擇前向動態(tài)規(guī)劃算法(Forward Dynamic Programming，F(xiàn)DP)[13]求解。

3.4 拉格朗日乘子的更新方法

L(ρ,δ)的目標值隨著ρ和δ的變化而改變。因此，在迭代過程中，需要不斷更新ρ和δ。次梯度更新方法如下：

ρk+1(l)=

(17)

δk+1(i)=

(18)

式(17)、式(18)中，求和公式分別表示各資源被覆蓋的次數(shù)，迭代過程中相應(yīng)資源被選中的次數(shù)一旦變化，ρ和δ的值也會隨之改變，而每一次變化都相當于在下一次迭代中對各資源重新“定價”，“動態(tài)定價”的特性就體現(xiàn)于此。每一次“動態(tài)定價”后，各個乘務(wù)交路會選擇由各資源組成的“最便宜”的時空路徑以滿足需求。

推而廣之，不僅僅是CSP， 諸如VRP類的帶有“混合時間”約束的活動資源優(yōu)化問題均可以采用此種求解策略。通過對固定資源(CSP中是乘務(wù)區(qū)段)的“動態(tài)定價”和活動資源(CSP中是乘務(wù)交路)為滿足自身需求對固定資源的“市場選擇”這兩個過程的不斷迭代[14]，從而解決活動資源優(yōu)化的本質(zhì)問題——活動資源和固定資源的最佳時空映射關(guān)系問題[6]。

3.5 拉格朗日松弛啟發(fā)式算法

在求解L(ρ,δ)時，所得下界解不一定是原問題的可行解。當下屆解不可行時，需要設(shè)計拉格朗日松弛啟發(fā)式算法求得可行上界解。本文設(shè)計的拉格朗日松弛啟發(fā)式算法是根據(jù)下界解中各乘務(wù)區(qū)段被覆蓋情況作為啟發(fā)信息。在迭代過程中，被下界解選中的乘務(wù)區(qū)段被視為有利于乘務(wù)組值乘的區(qū)段，故在啟發(fā)式算法中應(yīng)該優(yōu)先被乘務(wù)交路選擇。若上界解中存在多次被選中的乘務(wù)區(qū)段，則意味著乘務(wù)組“便乘”在此區(qū)段發(fā)生。在實際問題中，乘務(wù)組“便乘”會增加運營成本，所以在求解時應(yīng)盡可能避免。所有乘務(wù)區(qū)段均被執(zhí)行后，應(yīng)安排剩余的乘務(wù)交路選擇虛擬停駐弧，避免乘務(wù)資源浪費。具體算法如下：

Step5若p=Np，算法結(jié)束；否則，令p=p+1，轉(zhuǎn)入Step3。

綜上所述，拉格朗日松弛算法框架見圖10。

4 實例驗證

本文分別利用發(fā)車密度大的城際鐵路和高速鐵路網(wǎng)CSP實例(以鄭州東站乘務(wù)基地為中心，京廣線北京西至武漢段、鄭西線、鄭徐線和鄭州城際線組成的路網(wǎng)，以下簡稱“鄭州東路網(wǎng)”)對該本文方法進行驗算。在城際鐵路CSP實例中，因其發(fā)車密度大、換乘機會多適宜采用本文設(shè)計的固定時間窗用餐規(guī)則進行乘務(wù)任務(wù)安排，而在發(fā)車密度小、換乘機會少的鄭州東路網(wǎng)CSP實例采用何時休息何時用餐的規(guī)則。TSSN和拉格朗日松弛算法均利用C#語言在運行環(huán)境為Intel(R) Core (TM)i7-7500U 2.70 GHz，8.00 GB內(nèi)存的個人計算機上編程實現(xiàn)。

京津城際鐵路的交路時間長度較短，假設(shè)：(1)單司機值乘；(2)到站立即折返，最小折返時間15 min；(3)允許換乘；(4)不允許外段駐班；(5)設(shè)置用餐時間窗；(6)線上值乘4 h左右后直接退乘；(7)出、退乘時間各1 h。

據(jù)此，以京津城際158個乘務(wù)區(qū)段為輸入，各乘務(wù)規(guī)則參數(shù)如下：Np=60(北京南站和天津站各30條)，[Tμ,Tμ]= [300,370], [Tε,Tε]= [15,40]，[Tτ,Tτ]=[+∞,+∞]，[Tη,Tη]=[+∞,+∞]， [Tλ,Tλ]= [180,250]，[Te,Te]= [20,40]，Wlun= [11:00,13:00]，Wdin= [17:00,19:00]。迭代1 000次，共求得47條乘務(wù)交路，北京南站23條，需23組乘務(wù)組，天津站24條，需24組乘務(wù)組，用餐5次，最優(yōu)上界為98 726.00，最優(yōu)下界為81 466.68，對偶間隙為17.48%，求解時間為27 001.27 s。計算結(jié)果見表2，迭代曲線和部分乘務(wù)交路見圖11、圖12。

表2 京津城際CSP計算結(jié)果

鄭州東路網(wǎng)長短交路結(jié)合，假設(shè)：(1)短交路到站立即折返；(2)長交路允許外段駐班，駐班時長不低于16 h；(3)不設(shè)置用餐時間窗；(4)允許乘務(wù)組在鄭州站—鄭州東站間采取任意形式交通工具“空乘調(diào)撥”(deadhead)[15]；(5)其余乘務(wù)規(guī)則同上例。

以鄭州和鄭州東動車用所27條動車交路劃分的166個乘務(wù)區(qū)段為輸入，各乘務(wù)規(guī)則參數(shù)如下：Np=60，[Tμ,Tμ]= [330,420], [Tε,Tε]= [15,40]，[Tτ,Tτ]=[+∞,+∞]，[Tη,Tη]= [960,1 880]，[Tλ,Tλ]= [210,300]，[Te,Te]= [+∞,+∞]，Wlun=[+∞,+∞]，Wdin=[+∞,+∞]。迭代1 000次，共求得51條乘務(wù)交路，外段駐班27次，共需78組乘務(wù)組，最優(yōu)上界為269 955.00，最優(yōu)下界為213 640.07，對偶間隙為20.86%，求解時間為38 279.98 s。計算結(jié)果見表3，迭代曲線見圖13。

表3 鄭州東路網(wǎng)CSP計算結(jié)果

注：OG開頭的車次為乘務(wù)員“空乘調(diào)撥”。

5 結(jié)論

本文基于乘務(wù)規(guī)則提出時空節(jié)點狀態(tài)坐標遞推原則和乘務(wù)任務(wù)可行轉(zhuǎn)化判定條件，以此為基礎(chǔ)構(gòu)建TSSN，建立基于TSSN的0-1整數(shù)規(guī)劃模型。

針對模型的特點，在拉格朗日松弛框架下，將CSP松弛為時空最短路徑問題集合，分別利用FDP算法和拉格朗日啟發(fā)式算法求解下上界。

結(jié)果表明，TSSN配合拉格朗日松弛算法不僅可以求解發(fā)車密度大的的城際鐵路CSP，而且同樣適用于高速鐵路網(wǎng)CSP。針對大規(guī)模混合時間問題而言，該方法的優(yōu)勢在于：(1)TSSN可以通過狀態(tài)維度將一些難于刻畫的混合時間約束溶解在網(wǎng)絡(luò)中，控制網(wǎng)絡(luò)規(guī)模，簡化數(shù)學模型；(2)拉格朗日松弛算法可以將剩余“難約束”松弛，將原問題分解為若干個小規(guī)模的子問題集合，從而加速求解，并結(jié)合對偶間隙判定解的質(zhì)量。故二者結(jié)合使用可以有效解決大規(guī)?；旌蠒r間問題。當然，由于CSP是具有強對稱性，其松弛程度往往不便控制，從而導致下界質(zhì)量難以達到最佳，所以還需要對松弛控制方法進行深入研究。