基于多維網(wǎng)絡的增開列車條件下高速鐵路列車運行圖調(diào)整

高如虎， ?；菝?， 江雨星

(蘭州交通大學 交通運輸學院，甘肅 蘭州 730070)

列車運行圖在確保列車運行安全的前提下，確定列車在途經(jīng)各站的到發(fā)時刻，努力提高行車效率或降低運營成本，如通過能力最大化、減少總旅行時間等，并滿足旅客的出行需求[1]。當客流需求出現(xiàn)較大波動時(如春運或節(jié)假日)，基本運行圖中的開行列車不能滿足高峰客流需求，就需要增開列車并調(diào)整基本運行圖中的列車運行線，從而提高旅客服務質(zhì)量。隨著我國高速鐵路網(wǎng)日臻完善，運輸需求時變特性明顯，僅靠傳統(tǒng)的手工推線方法調(diào)整運行圖，一方面難以保證列車運行圖的質(zhì)量，另一方面也增加了調(diào)度人員的工作負擔。因此，研究增開列車條件下的列車運行圖調(diào)整模型和算法至關(guān)重要。

列車運行圖調(diào)整問題屬于列車運行圖編制(Train Timetabling Problem，TTP)范疇，是NP-hard問題[2]。從時空資源的視角看，列車運行圖是各列車對有限時空資源的相互競爭、相互作用、相互影響以達到資源合理配置的結(jié)果。因此，對列車運行圖的研究，本質(zhì)是對鐵路有限時空資源分配的組合優(yōu)化問題[3]?；诖?，大多文獻通過建立二維時空網(wǎng)絡或多維時空狀態(tài)網(wǎng)絡[4-6]，將原問題中各種難以求解的約束條件轉(zhuǎn)換為網(wǎng)絡中各弧段或節(jié)點的制約關(guān)系(如可達性、不相容性、網(wǎng)絡流量守恒等)，將研究目標轉(zhuǎn)換為占用網(wǎng)絡弧段的最小費用，從而清晰地刻畫復雜的列車運行圖問題并將其轉(zhuǎn)換為容易求解的網(wǎng)絡最短路徑問題。

一般意義上的列車運行圖調(diào)整是指當列車運行狀態(tài)因設備故障、惡劣天氣、突發(fā)事件等影響而偏離了預定值(計劃運行圖)，造成列車運行紊亂時，通過重新調(diào)整列車運行線，使其盡可能恢復列車按圖行車的過程。文獻[7-8]構(gòu)建了城市軌道交通網(wǎng)絡中末班車時刻表調(diào)整的整數(shù)規(guī)劃模型，并設計了相應的啟發(fā)式算法對問題進行求解。文獻[9]構(gòu)建了高速鐵路列車運行調(diào)整的馬氏決策過程模型，并提出了極大加代數(shù)和矩陣的策略優(yōu)化方法。文獻[10]構(gòu)建了區(qū)間突發(fā)故障下的列車運行圖調(diào)整混合整數(shù)規(guī)劃模型，并詳細討論了故障發(fā)生時區(qū)運行列車的停車問題。文獻[11]在研究列車運行圖調(diào)整時，考慮了動車組接續(xù)，并提出基于改進的和聲搜索算法對模型進行求解。事實上，列車在車站的進路對于列車運行圖調(diào)整至關(guān)重要，但僅有少部分文獻考慮了列車運行調(diào)整時列車車站進路的安排。文獻[12]將列車運行調(diào)整和列車進路選擇進行協(xié)同優(yōu)化，構(gòu)建了基于0-1累計變量的混合整數(shù)規(guī)劃模型。

本文所研究的列車運行圖調(diào)整是針對當客流發(fā)生突變，需要增開列車時，如何鋪畫新增列車運行線并對原基本運行圖進行調(diào)整的過程，并綜合考慮了列車車站進路對列車運行調(diào)整的影響。為方便問題描述和模型構(gòu)建，建立了基于Time-Station-Track的多維時空擴展網(wǎng)絡，以刻畫列車對鐵路行車資源的占用，并將原問題轉(zhuǎn)換為求解列車占用網(wǎng)絡最少費用問題。根據(jù)問題特點，設計了拉格朗日松弛算法，將問題進一步分解為求解單列車網(wǎng)絡最短路徑子問題。

1 問題分析及說明

1.1 問題分析

對于某條高速鐵路線路：U為車站集合，U={0,1,2,…,u,u+1,…,V,V+1}，其中0、V+1分別為虛擬起、終點站，1、V站分別為實際起、終點站；Pu為車站u進路集合，不同車站，進路數(shù)量不同。列車在車站的進路包括進站進路、到發(fā)線占用和出站進路，由于高速鐵路車站進、出站咽喉區(qū)具有足夠多的平行進路，所以列車之間在車站的作業(yè)沖突主要體現(xiàn)為不同列車對車站到發(fā)線資源的占用沖突。一般情況下，高速鐵路上下行方向列車相互獨立運行并成對開行，車站進路也分方向設置，本文僅選取線路上行方向進行研究。在該線路上：Ie為原基本運行圖中計劃開行列車集合；Ia為需要增開列車集合；I為所有列車集合，I=Ie∪Ia。運營時段按照1 min為粒度進行離散處理，T為優(yōu)化時段中的時刻集合。

一般情況下，在調(diào)整列車運行圖時，原基本運行圖中列車相比新增列車具有較高的優(yōu)先權(quán)，并且原基本運行圖中的列車都有預先確定的列車時刻表和停站方案。當新增列車占用時空資源費用較大(旅行時間較大或出現(xiàn)資源占用沖突)時，可對原基本運行圖的列車運行線進行局部調(diào)整。本文以在原基本運行圖調(diào)整量最少的同時降低新增列車旅行時間作為優(yōu)化目標。

在研究列車運行圖調(diào)整時，若不考慮列車在車站的進路安排，由于車站到發(fā)線能力的限制，在列車到發(fā)密集時段可能導致列車運行圖不可行。因此，在規(guī)劃新增列車時，需要為新增列車安排合理的車站進路并對原基本運行圖中列車的車站進路進行相應調(diào)整。

為進一步簡化問題，本文作出如下假設：

假設1為盡可能減少因列車運行調(diào)整而導致的旅客乘車不便的影響，在調(diào)整原基本運行圖中的列車運行線時，僅對列車始發(fā)時刻進行調(diào)整，而對停站方案及停站時間不做調(diào)整。

假設2在高速鐵路線路上，當列車通過車站而不停站時，一般從正線通過，并且車站正線一般不辦理列車到發(fā)作業(yè)。本文對所有車站進路進行編號，假定所有車站的1號進路為通過進路，其他進路為到發(fā)進路。

假設3在不同速度等級列車共線匹配運行模式下，為研究方便，假定高速鐵路線路上僅運行高等級和低等級兩類列車，且同等級列車之間不允許越行。在鐵路實際運營中，應盡量減少低等級列車在車站被高等級列車連續(xù)越行的次數(shù)，本文假定低等級列車在車站最多被高等級列車連續(xù)越行2次。

1.2 變量及參數(shù)

I為列車集合；i、j為列車，i,j∈I；U為車站集合；u、v為車站，u,v∈U；Pu為車站進路集合；m、n為車站進路，m,n∈Pu；T為時刻集合；t、t′、t″、l為時刻，t,t′,t″,l∈T。

模型決策變量為

xi(u,t,m;v,l,n)=

2 網(wǎng)絡構(gòu)建

本文所建立的TST網(wǎng)絡中包含3類弧段，下面對各類弧段的特性進行分析，并對各類弧段的費用進行定義。

2.1 弧段特性分析

(1) 起始弧

對于原基本運行圖中列車，由于本文研究的是高速鐵路線路，因此，基本運行圖中的列車在調(diào)整時，均不能提前出發(fā)，即

對于運行圖中新增列車

(2) 終止弧

對于原基本運行圖中列車，即i∈Ie

對于運行圖中新增列車，即i∈Ia，由于列車停站方案不確定，因此

(3) 運行弧

為方便說明，下面以原基本運行圖中的一列車為例說明網(wǎng)絡的構(gòu)建過程，新增列車的網(wǎng)絡與此類似。假設線路由3個車站組成，每個車站有3條進路。該列車在原基本圖中的始發(fā)時刻為9 min，可調(diào)整時間為2 min，該列車在第2站不停站通過，對應在網(wǎng)絡中僅占用通過進路(1號進路)。當列車停站時，可對其到發(fā)進路進行調(diào)整。對應TST網(wǎng)絡見圖1。

在本文所構(gòu)建的TST網(wǎng)絡中，不單獨設列車停站弧，而是將停站行為包含于列車運行弧中。值得注意的是：運行弧中起點所對應的時刻為列車在該弧起點所對應車站的出發(fā)時刻，而運行弧終點所對應時刻不是該列車在該弧終點所對應車站的真實到達時刻，在后文模型建立部分中會有所體現(xiàn)。

2.2 弧段費用

本文以在原基本運行圖中列車時刻表調(diào)整量最少的基礎(chǔ)上，降低新增列車旅行時間作為優(yōu)化目標，因此，原運行圖中列車和新增列車在TST網(wǎng)絡中占用弧段的費用不同，各類弧段費用定義見表1。值得注意的是，原運行圖中列車在網(wǎng)絡中的旅行弧和終止弧及新增列車起始弧和終止弧不影響問題優(yōu)化目標，因此，為方便計算，全部設為常數(shù)1。γ為原運行圖中列車時刻表調(diào)整量懲罰因子，η為新增列車旅行時間懲罰因子。

表1 弧段費用

3 模型建立

3.1 基于TST網(wǎng)絡的0-1整數(shù)規(guī)劃模型

3.1.1 目標函數(shù)

通過網(wǎng)絡構(gòu)建，將本文優(yōu)化目標轉(zhuǎn)化為所有列車占用弧段費用最小，即

xi(u,t,m;v,l,n)

(1)

3.1.2 約束條件

(1) 流量守恒

(2)

(2) 區(qū)間能力

出發(fā)安全間隔約束為

(3)

如前文所述，由于本文所建網(wǎng)絡中列車占用運行弧的終止頂點對應時刻并不是列車的實際到達時刻，因此需要將其轉(zhuǎn)換為真實的到達時刻。

到達安全間隔約束為

(4)

由于高速鐵路線路上運行不同等級的列車，因此，需要解決不同等級列車的越行沖突，越行約束為

?(u,t),i≠j

(5)

(3) 車站能力約束

若不同列車占用同一車站的同一進路，則必須滿足最小安全間隔

(6)

(4) 變量約束

xi(u,t,m;v,l,n)∈{0,1}

(7)

3.2 Lagrangian松弛及問題分解

列車運行圖優(yōu)化模型中，通常認為制約模型求解效率的難約束是能力約束。對于本文所建立模型，區(qū)間能力和車站能力約束式(3)—式(6)導致列車之間相互作用、相互影響，從而發(fā)生大規(guī)模的組合。因此，通過引入拉格朗日乘子將此類難約束作為懲罰項松弛到目標函數(shù)中，形成拉格朗日松弛問題。本文引入ρu,t、φi,u,t、πu,t,m3類非負拉格朗日乘子。

拉格朗日松弛問題為

(8)

通過轉(zhuǎn)換，可將上式重新整理為

(9)

式中：Ω為關(guān)于拉格朗日乘子的常數(shù)。

(10)

為獲得拉格朗日松弛問題的最大下界，需求解以下拉格朗日對偶問題

(11)

s.t. 式(2)、式(7)。

其中

LRi=

(12)

利用次梯度法對拉格朗日乘子進行更新，如對乘子ρu,t更新為

(13)

式中：q為迭代次數(shù)；αq為第q次迭代的歩長。

αq更新公式為

αq=1/(1+q)

(14)

其他乘子更新方法同ρu,t。

根據(jù)式(11)和式(12)，顯然，原問題被分解成求解單列車的網(wǎng)絡最短路徑問題。通過拉格朗日算法不斷迭代可求解原問題的解。值得說明的是，拉格朗日松弛算法的對偶解可能不可行，因此，本文利用基于列車優(yōu)先序列的啟發(fā)式調(diào)整方法對對偶解可行化，基本思想類似于文獻[12-14]。拉格朗日松弛算法框架如下：

Step1初始化。令q=1，上界UB0=+，下界LB0=-。初始化拉格朗日乘子值ρu,t，φi,u,t，πu,t,m。

Step2下界計算。利用Dijkstra最短路算法依次求解各個列車在Time-Station-Track網(wǎng)絡中的最短路徑；并計算下界LBq，更新LBq=max{LBq,LBq-1}。

Step3基于列車優(yōu)先序列的上界計算。

(1) 確定列車可行順序：首先，將列車按照式(10)的計算結(jié)果從大到小進行排序；然后，再按照原基本運行圖中列車在前，新增列車在后的順序排序。

(2) 計算最短路并標定：根據(jù)(1)列車可行順序，利用Dijkstra最短路算法計算各個列車在TST網(wǎng)絡中的最短路徑，標定該列車最短路占用TST網(wǎng)絡弧段，并令該列車占用弧段的費用為+。

(3) 可行解判定：若所有列車全部規(guī)劃完畢，則轉(zhuǎn)(4)；若存在列車不能被規(guī)劃，則改變規(guī)劃失敗列車的優(yōu)先權(quán)，優(yōu)先規(guī)劃前次失敗的列車，轉(zhuǎn)(2)。

(4) 計算上界UBq并更新UBq=min{UBq,UBq-1}。

Step4拉格朗日乘子更新。按照式(13)，利用次梯度方法對各類乘子進行更新。

Step5gap值計算。gap=(UBq-LBq)/UBq。

Step6終止條件判斷。若gap≤ε或者q≥M，算法停止，輸出；否則q=q+1 ，轉(zhuǎn)Step2。其中，ε、M分別為預先確定的預期gap值及最大迭代次數(shù)。

4 算例

新增低等級列車的最大停站時間示意見圖3。

表2 區(qū)間運行時間 min

表3 原運行圖中高等級列車在始發(fā)站的原出發(fā)時刻和停站方案

表4 新增低等級列車最早最晚出發(fā)時刻

對實例利用Lagrangian松弛算法求解，算法在Visual Studio 2013平臺上使用C++語言實現(xiàn)，算法運行環(huán)境為1臺CPU Intel，4 GB內(nèi)存的個人計算機。算法迭代100次，運行時間3 862 s，gap值為1.05%。

上下界迭代過程見圖4，從算法迭代過程及gap值可以看出，該算法具有較好的收斂性。優(yōu)化后的列車運行圖見圖5，由于篇幅限制，各列車占用車站進路不再展示。

由于本文原問題目標為在基本運行圖中列車時刻表調(diào)整最小的基礎(chǔ)上，減少新增列車的旅行時間。在建立的TST網(wǎng)絡中表現(xiàn)為兩類列車占用弧段費用不同，即γ>η，其內(nèi)涵為基本運行圖中列車占用TST網(wǎng)絡時空資源費用高于新增列車。事實上，兩懲罰參數(shù)對拉格朗日松弛算法的迭代次數(shù)有影響，而對最終求解結(jié)果影響不大，經(jīng)過反復對參數(shù)進行測試，γ=1，η=2時，算法的收斂效果最好。從計算結(jié)果分析可知，一般對基本運行圖中列車時刻表不做調(diào)整，僅當車站資源占用出現(xiàn)沖突時，可通過調(diào)整列車再車站的進路或者調(diào)整列車在始發(fā)站的出發(fā)時刻，如列車編號27、28、34。對于新增的低等級列車，雖然優(yōu)化目標中降低其旅行時間，但由于線路能力限制，在車站需要待避原基本運行圖中高等級列車，導致停站次數(shù)較多，停站時間也較長。

5 結(jié)論

(1) 列車運行圖問題屬于典型的NP-hard問題，并且列車運行圖問題所涉及車站和列車數(shù)量眾多。本文對新增列車條件下的列車運行圖調(diào)整進行了研究，并綜合考慮了列車車站進路選擇。

(2) 本文通過構(gòu)建TST三維時空擴展網(wǎng)絡將列車運行調(diào)整問題轉(zhuǎn)換為求解列車在TST時空擴展網(wǎng)絡中占用弧段的最小費用問題，并利用拉格朗日松弛算法，將原問題進一步分解為單列車網(wǎng)絡最短路徑子問題。由于利用拉格朗日松弛算法將原問題分解后，得到的解可能是不可行解，因此，設計了基于列車優(yōu)先序列的啟發(fā)式算法求原問題的可行解并獲得拉格朗日松弛算法的上界。

(3) 通過實例驗證了本文所建立模型的正確性和所設計算法的適用性。下一步將考慮面向時變客流需求條件下的高速鐵路列車運行調(diào)整問題，并將提出更加高效的算法對此類復雜的組合優(yōu)化問題進行求解。