基于時(shí)空狀態(tài)網(wǎng)絡(luò)的高速鐵路乘務(wù)交路計(jì)劃優(yōu)化研究

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

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

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

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

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

1 問(wèn)題描述

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

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

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

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

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

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

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

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

2 TSSN

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

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

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

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

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

具體情況見(jiàn)圖4、圖5。

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

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

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

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

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

2.2.1 時(shí)空節(jié)點(diǎn)狀態(tài)坐標(biāo)遞推原則

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

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

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

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

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

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

2.3.1 無(wú)用餐規(guī)則

假設(shè)：(1)最小換乘時(shí)間為10 min；(2)不規(guī)定固定的用餐時(shí)間窗；(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)過(guò)程中，TSTLN中的每個(gè)時(shí)空節(jié)點(diǎn)的不同狀態(tài)均會(huì)被轉(zhuǎn)化為T(mén)SSN中的一個(gè)時(shí)空狀態(tài)節(jié)點(diǎn)，相鄰時(shí)空節(jié)點(diǎn)間不同的狀態(tài)轉(zhuǎn)換均會(huì)被轉(zhuǎn)化為T(mén)SSN中的一條時(shí)空狀態(tài)轉(zhuǎn)換弧，從而構(gòu)成TSSN，記為Gtss=(Vtss,Atss)，Gtss表示TSSN，Vtss和Atss分別表示TSSN中的點(diǎn)集合和弧集合。簡(jiǎn)而言之，在TSTLN中引入狀態(tài)維度后的變化為：(1)時(shí)空節(jié)點(diǎn)i的m個(gè)狀態(tài)ωi=[ωi(1),ωi(2),…,ωi(m)]變?yōu)門(mén)SSN中m個(gè)時(shí)空狀態(tài)節(jié)點(diǎn)；(2)連接各個(gè)時(shí)空狀態(tài)節(jié)點(diǎn)的弧表示不同的乘務(wù)任務(wù)。

Step1統(tǒng)計(jì)乘務(wù)基地個(gè)數(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ù)總累計(jì)時(shí)間最小的總目標(biāo)；式( 2 )表示所有乘務(wù)區(qū)段必須被覆蓋約束，且該乘務(wù)區(qū)段允許“便乘”；式( 3 )表示流平衡約束，式( 4 )表示每個(gè)乘務(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ì)是利用拉格朗日乘子對(duì)“難約束”所對(duì)應(yīng)的資源“定價(jià)”，將“難約束”松弛到目標(biāo)函數(shù)中，原問(wèn)題隨即被分解為由多個(gè)“簡(jiǎn)單約束”構(gòu)成的子問(wèn)題，簡(jiǎn)化模型求解，同時(shí)又為原問(wèn)題提供了一個(gè)可靠下界，然后不斷迭代求解子問(wèn)題，在此過(guò)程中持續(xù)通過(guò)次梯度算法持續(xù)更新拉格朗日乘子，這也就相當(dāng)于對(duì)“難約束”所對(duì)應(yīng)的資源“動(dòng)態(tài)定價(jià)”，從而不斷提升下界，直至收斂。在CSP中，需要被“動(dòng)態(tài)定價(jià)”的資源有兩類(lèi)，一類(lèi)是式( 2 )對(duì)應(yīng)的乘務(wù)區(qū)段資源l，其決定了乘務(wù)組值乘的乘務(wù)內(nèi)容；另一類(lèi)是停駐資源，其保證了乘務(wù)組大休。此外，由于CSP是“匿名”計(jì)劃，所有p之間無(wú)差別，這種對(duì)稱(chēng)性會(huì)導(dǎo)致收斂效果不佳。對(duì)此，本文在不破壞3.1節(jié)中模型結(jié)構(gòu)的前提下，通過(guò)兩個(gè)方法解決上述問(wèn)題：(1)添加式(10)對(duì)停駐資源“動(dòng)態(tài)定價(jià)”；(2)為?p∈P賦予權(quán)重gp規(guī)定p之間的順序。

( 6 )

( 7 )

( 8 )

( 9 )

(10)

(11)

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

3.3 拉格朗日對(duì)偶問(wèn)題

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

L(ρ,δ)=

(12)

(13)

(14)

(15)

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

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

(16)

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

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

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

ρk+1(l)=

(17)

δk+1(i)=

(18)

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

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

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

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

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

綜上所述，拉格朗日松弛算法框架見(jiàn)圖10。

4 實(shí)例驗(yàn)證

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

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

據(jù)此，以京津城際158個(gè)乘務(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，對(duì)偶間隙為17.48%，求解時(shí)間為27 001.27 s。計(jì)算結(jié)果見(jiàn)表2，迭代曲線和部分乘務(wù)交路見(jiàn)圖11、圖12。

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

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

以鄭州和鄭州東動(dòng)車(chē)用所27條動(dòng)車(chē)交路劃分的166個(gè)乘務(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，對(duì)偶間隙為20.86%，求解時(shí)間為38 279.98 s。計(jì)算結(jié)果見(jiàn)表3，迭代曲線見(jiàn)圖13。

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

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

5 結(jié)論

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

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

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