基于拉格朗日松弛的雙線鐵路列車運行圖優化算法

廖正文， 苗建瑞， 孟令云， 李海鷹， 趙 嵐

(1. 北京交通大學 軌道交通控制與安全國家重點實驗室，北京 100044；2. 北京交通大學 交通運輸學院，北京 100044； 3. 西安鐵路職業技術學院，陜西 西安 710014)

列車運行圖是鐵路行車組織的基礎，編制和優化運行圖是鐵路運輸組織領域的經典問題。對此，各國專家學者建立目標和約束條件各異的優化模型，并根據模型特點，設計不同的求解算法。但利用數學規劃方法對列車運行圖進行優化，精確的算法只能求解小規模算例，對于大規模問題必須采取不同的策略將原

問題分解或簡化，以求降低問題的規模，如國外CAREY[1]、CAREY and LOCKWOOD[2]、CASTILLO[3]，國內周磊山[4]、彭其淵[5]、史峰[6]等均根據問題的不同特點設計基于問題分解的啟發式求解算法。

列車運行圖優化，無論是既有線上以旅客列車總旅行時間最短、貨物列車開行數量最多，還是客運專線上以列車服務頻次高、旅行時間短等為目標，本質均是有限時空資源分配的組合優化問題，盡管當前計算機運算速度和儲存空間有較大發展，但是列車運行圖的組合規模決定人們依然難以使用傳統的方法直接求解大規模問題。因此,目前解決這類問題的思路主要分為兩大類：一類為采用模擬人工編圖的啟發式算法或遺傳算法、模擬退火算法等智能優化算法；另一類為將復雜的原問題分解為相對容易求解的子問題，進而獲得原問題的較優解。國外有研究采用拉格朗日松弛算法求解列車運行圖問題[7-12]，該研究表明拉格朗日松弛算法對于求解列車運行圖問題具有一定的適用性，并且能夠通過分析優化間隔評價求解結果的質量，是解決列車運行圖優化問題的高效方法。

本文針對列車運行圖的大規模有限時空資源分配本質問題，結合拉格朗日松弛算法對資源約束問題良好的分解效果及優化程度可評估的特點，以列車對“行車資源”的占用代替傳統列車追蹤間隔時間表示通過能力約束，考慮實際運營中的列車運行圖要素(起停車附加時分、停站時間和各種追蹤間隔時間)，構建基于累積流變量的雙線鐵路列車運行圖優化模型；構造拉格朗日松弛算法框架，建立“時間-空間-狀態網絡”以求解拉格朗日松弛子問題。最后通過實際運營中的列車運行圖編制算例驗證算法的效率與優化質量。

1 基于累積流變量的列車運行圖優化模型

1.1 模型假設和已知條件

為更好地研究影響列車運行圖求解算法性能的關鍵要素，現對列車運行圖問題進行適當的抽象和假設。假設列車在雙線鐵路網上運行，不考慮列車在站內的進路與到發線安排；行車閉塞方式為自動閉塞，追蹤間隔時間固定且已知；列車在各區間的純運行時分、起停附加時分已知且固定；列車的數量、起訖點、徑路、停站方案已知；運行圖的編制不考慮車底的運用。

模型輸入為：列車的等級、不同等級列車的區間純運行時分、車站起動及停車附加時分、列車追蹤間隔時分；列車運行徑路，列車始發(接入)時間窗(在始發站或接入站的最早出發時刻至最晚出發時刻之間的時間段)、在各站的最小停站時分以及列車的權重。模型輸出為列車在徑路上各站的到達和出發時刻。

據文獻[13]，若將運行圖的時間軸按照最小規劃單位離散化，將列車在線路上的運行過程刻畫為列車對“行車資源”的占用，利用列車占用“行車資源”的排他性表示列車的追蹤間隔，即可采用含有累積流變量的數學等式表達占用“行車資源”的過程，建立數學優化模型，利用拉格朗日松弛方法求解列車運行圖問題。因此，本文將利用占用“行車資源”刻畫列車的追蹤間隔時間，利用累積流變量刻畫列車的運行過程。

1.2 行車資源占用模型

對雙線鐵路，某車站某銜接方向同一時間內最多只能為某一列車辦理到達或出發作業，只能依次為各列車單獨辦理到達或出發進路。從開始辦理進路至進路解鎖時間段內，其他列車不能辦理相應的作業。因此可將車站某銜接方向用于辦理到達或出發作業的時間看作待分配的時空資源。本文定義車站上列車占用的“行車資源”為各站列車到達與出發作業在時空上的占用許可，見圖1，稱為“接車資源”和“發車資源”。列車的到達(或通過)作業需要占用的行車資源自開始辦理到達進路時開始，至到達進路解鎖時止，見圖2(a)。列車出發(或通過)作業需要占用的行車資源自開始辦理出發進路時開始，至出發進路解鎖時止，見圖2(b)。當有列車辦理到達(或出發)作業時，接車資源(或發車資源)被占用，否則接車資源(或發車資源)空閑。

傳統的列車追蹤間隔時間設置目的是為了保證前后行列車占用同一線路資源,在時間上不沖突，追蹤間隔時間的值可根據辦理列車進路各環節的時間組成計算得到，與本文提出的“行車資源”占用是等價的。因此,可用列車對“行車資源”的占用時間分配刻畫列車的追蹤間隔，具體的分析為:

列車在車站辦理到達或出發進路主要分為3個階段：

(1) 辦理進路、開放信號；

(2) 列車駛過進路；

(3) 列車出清，進路解鎖。

各階段占用時間見圖2。

當列車在本站停站時，占用時間根據以下起止時刻確定：

上述占用時空資源要根據列車速度、車站軌道電路結構、接發車進路情況確定。

列車出發追蹤間隔時間包括：

(1) 前行列車從車站出發至完全離開車站進入區間的時刻；

(2) 與后行列車辦理出發作業時間的組合。

列車到達追蹤間隔包括：

(1) 前行列車到達車站時刻起至到達進路解鎖的時間；

(2) 辦理后行列車到達作業時刻起至該列車到達車站的時間。

列車通過追蹤間隔包括：

(1) 前行列車通過車站時刻起至列車完全離開車站進入區間的時刻；

以上分析說明，列車車站追蹤間隔時間可用列車占用車站“行車資源”組合等價表示。車站的到達、出發追蹤間隔時間一般是列車追蹤間隔時間的決定性因素，但對于長大閉塞分區等區間追蹤間隔時間是決定性因素的情況，可通過數據預處理，將列車在區間追蹤間隔的最大值用該區間前方站的出發間隔時間或后方站的到達間隔時間表示，以統一使用列車的車站行車資源表示追蹤間隔。

1.3 基于累積流變量的列車運行過程建模方法

定義路網中車站節點集合為V，區間弧段集合為E，車站節點標號為i,j,k；列車集合F，集合中各列車標號為f。

在列車運行圖的時間維度上，采用累積流變量(Cumulative Flow Variables)的建模方法。累積流變量是在時間軸上，將時間按照固定的單位長度進行離散化，并使用一組0-1變量表示某參量在每個離散時刻的狀態。

例如圖6(b)中，列車在t=5時離開車站i，則t<5時，dfi,t=0，t≥5時，dfi,t=1。在時間軸上表示車站i的累積流變量dfi,t序列時，累積流變量的性質決定該序列最多僅可能在某一時刻發生1次從0到1的突變。在此突變位置t=5之前，即t=1,…,4時，dfi,t=0，dfi,t-1=0，在此突變位置之后，即t=6,7,8,…,T時，dfi,t=1，dfi,t-1=1，該兩種情況t×dfi,t-dfi,t-1均為0。只有在突變的位置，即t=5時，dfi,t=1，dfi,t-1=0，則t×dfi,t-dfi,t-1=t。在式(1)求和的各項中，只有在t=5時，該項的值為t，其余項均為0，因此，有等式( 1 )成立。等式( 2 )同理。

( 1 )

( 2 )

( 3 )

( 4 )

列車越行問題本質是列車在區間的運行順序在某車站發生交換。由于車站接車方向與發車方向的行車資源是分別定義的，二者相互獨立。當列車發生越行對于越行站是同一對前后行列車占用接車資源與發車資源的占用順序發生交換。若車站銜接多方向，可對每個銜接方向的線路各定義一組出發與到達行車資源，當不考慮車站內進路沖突的前提假設下，使模型能夠適應多方向情況。

使用累積流變量方法建模可使用線性方程刻畫列車對行車資源占用的過程以及行車資源狀態隨時間變化的過程，即將線性優化與離散系統仿真融合在一起，為軌道交通運輸組織優化中引入復雜要素提供手段；其次，用該方法建立的模型，重點在于列車對行車資源的占用關系，而非傳統運行圖優化模型中的列車與列車運行間隔時間關系，便于對原問題進行分解，實現復雜問題求解的目標。

1.4 基于累積流變量的列車運行圖優化模型

對于列車運行圖編制的目標，有列車總旅行時間最短、旅客換乘時間最少等。本文研究的重點在于可接受的求解時間內提升列車運行圖求解的質量，而導致問題難以獲得最優解的原因在于復雜的約束條件，目標函數可以根據不同的編制目標進行改進。因此，選取目標中最具有代表性的加權總旅行時間最短為目標，對于有特定目標的編圖問題，目標函數可以在此基礎之上擴充。

列車運行圖優化模型的目標函數是加權總旅行時間最短為

( 5 )

式中：of、sf為列車f的始發車站和終到站；pf為列車f的權重。由于不同列車等級不同，相同等級的列車也可能存在一定的重要程度差異，此權重體現編圖人員對于列車規劃優先等級的考慮。

模型約束條件為

(1) 列車到達、出發事件狀態約束

dfi,t-1≤dfi,t

?f∈F?t∈T:t≠0 ?i∈V

( 6 )

afi,t-1≤afi,t

?f∈F?t∈T:t≠0 ?i∈V

( 7 )

該組約束保證對于表示列車f在車站上作業的同一組累積流變量隨著時間的推移最多只能發生1次變化，且只能從0向1變化，保證列車進入弧段或離開弧段事件從“尚未發生”到“已經發生”的狀態轉變最多只能發生1次。

(2) 區間進出先后順序約束

dfi,t≤afj,t

?f∈F?t∈T?(i,j)∈E

( 8 )

該約束保證列車進入區間的時刻不得晚于離開本區間的時刻。

(3) 出發時間窗

dfof,t=0

?f∈F?t∈T∧t

( 9 )

dfof,t=1

?f∈F?t∈T∧t>LSTf

(10)

式中：ESTf、LSTf分別為列車f最早始發時間和最晚始發時間。

設置出發時間窗約束，可以保證列車在規定的時間范圍內出發，尤其是接入到本區段的列車，需要以銜接區段交出列車的時刻作為本區段列車運行圖編制的輸入條件。同時設置出發時間窗也可以減小問題的解空間，縮小搜索的范圍。

(4) 車站最小客運業務停站時間

?f∈F?i∈V

(11)

式中：wfi為列車f在i站的最小停站時間。運行圖的編制必須滿足列車開行方案規定的?？空军c以及停站時間。車站i的出發時刻與到達時刻之差即為列車在該站的停站時間。

(5) 區間運行時分約束

?f∈F?i∈V

(12)

?f∈F?i∈V

(13)

FTfi,j+xfi×DAfi+xfj×AAfj=

?f∈F?i,j∈E

(14)

式(12)～式(14)中：xfi為列車f在i車站是否停車，變量取值為0表示不停車，1為停車；FTf(i,j)為在弧段i,j上的純運行時分；DAfi、AAf(j)分別為起動附加時分和停車附加時分。

(6) 列車占用行車資源標記約束

?f∈F?t∈T?i∈V

(15)

?f∈F?t∈T?i∈V

(16)

式中：

(7) 能力約束

每個行車資源被占用的次數是有限的，同一行車資源僅能被一列車占用。

(17)

2 基于拉格朗日松弛的模型求解方法

拉格朗日松弛原理是將問題中的難約束松弛，并將其作為懲罰項添加到目標函數中，使約束條件簡化。通過求解拉格朗日松弛問題，可以獲得原問題的最優邊界，同時通過不斷迭代更新拉格朗日乘子，使得松弛問題的解逐漸逼近原問題的最優解[10]。

2.1 拉格朗日松弛問題

基于累積變量的列車運行圖優化模型中，通常認為制約模型求解效率的約束是能力約束[9]。即式(17)表達的約束。該約束導致列車之間相互作用，從而引發大規模的組合。因此，將其松弛，并將該約束作為懲罰項添加到目標函數中，形成拉格朗日對偶問題Z(D)。

目標函數為

(18)

通過對上述目標函數式進行恒等變換，可得到

(19)

式中：

2.2 基于時空狀態網絡最短路徑的子問題求解方法

在拉格朗日對偶問題ZD中，由于松弛約束式(17)，使用式( 6 )～式(16)刻畫單個列車運行過程中的時空邏輯，使各列車之間的關聯被解除，而目標函數是各列車時空路徑的目標函數LRf之和。實質上是列車時空最短路徑問題，對于此類問題，通過逐一枚舉各列車所有符合約束條件(6)～約束條件(16)可選時空路徑，構建時空網絡，然后通過最短路徑算法快速高效地求得LRf子問題的最優解。

由于約束中包含列車是否停站的決策變量xf(i)，對應的求解子問題的時空網絡也可表示列車在車站的作業性質(到達、出發或通過)。因此需要構建改進的列車運行時空網絡，將原“時空”網絡擴展為“時空狀態”網絡。時空狀態網絡有4類節點：

(1) 列車的時空邏輯起點和邏輯終點表示列車在時空網絡中的生成與消失；

(2) 到達節點表示列車的到達作業；

(3) 出發節點表示列車的出發作業；

(4) 通過節點表示通過列車的到達與出發作業。

在上述的節點上根據列車的作業類型不同構建弧段，正確地表示車站起停附加時分和列車間隔時間。

時空網絡中有3類弧段：

(1) 起止弧表示列車從邏輯起點進入時空網絡，以及列車從時空網絡離開前往終止節點的弧段；

(2) 運行弧表示列車在兩個車站間的運行；

(3) 停站弧表示列車在某車站內從到達至出發的狀態轉變。

通過模型中各種約束建立每列車對應的所有可選時空路徑構成1個完整的時空網絡，通過求解該時空網絡的最短路徑可求得問題LRf的最優解，見圖8。

2.3 拉格朗日乘子更新方法

在2.1節中，拉格朗日松弛對偶問題ZD在給定拉格朗日乘子時其解是一定的，為使拉格朗日對偶問題的解逐漸逼近原問題的最優解，要通過迭代更新拉格朗日乘子的值。迭代過程中，采用次梯度方法對拉格朗日乘子進行更新，為

(20)

式(20)表示新的拉格朗日乘子與當前的拉格朗日乘子及本次迭代求解得到的時空資源占用次數有關，在當前拉格朗日乘子的基礎上，根據本次求解中列車對該資源的占用次數，對拉格朗日乘子進行調整。

在拉格朗日松弛問題中，拉格朗日乘子的現實含義是“時空資源費用”，即列車占用“時空資源”的代價，更新拉格朗日乘子的次梯度法則是根據本次迭代中列車對資源的競爭結果情況對“時空資源費用”進行動態更新。將列車對時空資源的請求看作“需求”，將線路能力看作“供給”，將拉格朗日乘子的值看作“價格”。各次列車首先根據時間效益最大的路徑，獨立地向時空資源發出占用請求，各時空資源根據所有列車的占用請求與自身能力的匹配情況，使用次梯度法更新拉格朗日乘子值，即根據“供需關系”對各資源“定價”，從而影響下次迭代中各列車在時空網絡中的路徑選擇。通過“資源定價”與“路徑選擇”過程的不斷迭代，從而解決運行圖優化的核心問題——有限時空資源的優化分配。

2.4 獲得可行解的啟發式算法

由于使用拉格朗日松弛方法將原問題分解后，得到的解可能是不可行解。因此需要提供高效獲得原問題可行解的方法?，F使用啟發式算法，即把拉格朗日松弛求解得到的結果作為啟發信息，按照一定的順序逐個列車進行規劃，從而求得可行解。

該啟發式方法在本質上是滾動式求解方法，關鍵是如何確定進入規劃列車的順序。采用按照列車的LRPf由大到小的順序對列車進行滾動優化求解，LRPf的計算方法為

LRPf=

(21)

LRPf的值越大說明該列車沖突越嚴重，沖突疏解的難度較大，可調整余地較??；該值越小說明該列車沖突越少，可調整余地越大，故按照由難到易的順序逐個對列車的運行線進行鋪畫。

鋪畫過程中，使用與求解拉格朗日松弛問題同樣的最短路徑方法進行求解，并同時對占用進行標記。算例驗證中，如果該啟發式方法不能獲得可行解，即有列車不能被規劃，則調整這些規劃失敗列車的優先級，優先鋪畫前次規劃失敗的列車。

3 算例分析

將京廣高速鐵路武漢—廣州南區段(共18座車站)作為算例對模型與算法的可行性和求解效率進行分析。使用ILOG CPLEX V12.3軟件求解原問題與線性松弛問題，拉格朗日松弛算法框架在Visual Studio 2012平臺上使用C#語言實現，算法運行環境為1臺CPU為Intel Xeon E5520 2.27 GHz×2，8 GB內存的臺式計算機。

首先采用武漢—長沙南區段7座車站對算法的可行性和性能進行初步驗證。算例設置求解總時間長度為180 min，時間離散化后的鋪畫時間單位為1 min，列車出發時間窗為全時間域(0～180 min)，列車權重均設為相等，測試隨著列車數量增加求解質量與求解時間的變化。實驗首先使用CPLEX分別計算模型的最優解與線性松弛解(下界)。針對相同實驗數據集，再次利用拉格朗日松弛算法框架進行200次迭代計算。求解結果表明，隨著列車數量增大，CPLEX求最優解變得越來越困難，當列車數增加到8列時，在設定時間內(7 200 s)不能完成求解過程，但將原問題進行線性松弛后，CPLEX能夠較快地求解出問題的下界。

表1 算法求解性能分析

與CPLEX求解出的線性松弛生成的下界相比，求解8列車時，拉格朗日松弛算法得到的下界質量有11.13%的提升。

進一步分析CPLEX與拉格朗日松弛算法在求解問題下界方面的效率，當列車數量較少時，CPLEX求解速度比使用拉格朗日松弛算法快，但是當列車數量增多(大于32列)時，拉格朗日松弛算法具有明顯的效率優勢。

使用拉格朗日松弛算法時，上下界間隔將隨著列車的數量增加而增加，見圖9。

以武漢—廣州南全線下行方向為背景測試模型和算法的性能。設定全天(1 440 min)下行方向開行110列車，時間離散化后的鋪畫時間單位為1 min，為每列車設置30 min的始發站出發時間窗，并根據列車的等級、停站數量、旅行時間設置權重。利用拉格朗日松弛算法進行200次迭代，總耗時10 448 s，收斂的上下界間隔為0.19%，見圖10。

4 結論

根據我國雙線鐵路列車運行圖編制特點，考慮列車起停附加時分和列車追蹤間隔等關鍵要素，構建基于累積流變量的列車運行圖0-1整數規劃模型。

針對運行圖優化問題求解困難的問題，結合模型特點提出拉格朗日松弛算法框架，對問題按照列車分解，針對子問題特點，提出改進的列車運行時空狀態網絡并設計子問題的最短路徑求解方法。

算例結果表明，拉格朗日松弛算法能夠高效地求解大規模列車運行圖問題，并能夠通過比較優化上下界的間隔確定運行圖的優化程度。同時說明，拉格朗日松弛方法所求得下界質量比線性松弛更優，使用啟發式方法求解上界速度比較快。當列車數量增加時，運行線之間的沖突將更加頻繁。因此，可能導致拉格朗日松弛算法的上下界間隔隨著列車的數量增加而逐漸變大。

參考文獻：

[1] CAREY M. A Model and Strategy for Train Pathing with Choice of Lines，Platforms，and Routes[J]. Transportation Research Part B：Methodological，1994，28(5)：333-353.

[2] CAREY M，LOCKWOOD D. A Model，Algorithms and Strategy for Train Pathing[J]. Journal of the Operational Research Society，1995，46(8)：988-1 005.

[3] CASTILLO E，GALLEGO I，URENA J M，et al. Timetabling Optimization of A Mixed Double and Single-tracked Railway Network[J]. Applied Mathematical Modelling，2011，35(2)：859-878.

[4] 周磊山，胡思繼，馬建軍，等. 計算機編制網狀線路列車運行圖方法研究[J]. 鐵道學報，1998，20(5)：16-22.

ZHOU Leishan，HU Siji，MA Jianjun，et al. Network Hierarchy Parallel Algorithm of Automatic Train Scheduling[J]. Journal of the China Railway Society，1998，20(5)：16-22.

[5] 彭其淵，朱松年，王培. 網絡列車運行圖的數學模型及算法研究[J]. 鐵道學報，2001，23(1)：1-8.

PENG Qiyuan，ZHU Songnian，WANG Pei. Study on A General Optimization Model and Its Solution for Railway Network Train Diagram[J]. Journal of the China Railway Society，2001，23(1)：1-8.

[6] 史峰，黎新華，秦進，等. 單線列車運行圖鋪劃的時間循環迭代優化方法[J]. 鐵道學報，2005，27(1)：1-5.

SHI Feng， LI Xinhua，Qin Jin，et al. A Timing-cycle Iterative Optimizing Method for Drawing Single-track Railway Train Diagrams[J]. Journal of the China Railway Society，2005，27(1)：1-5.

[7] CAPRARA A，FISCHETTI M，TOTH P. Modeling and Solving the Train Timetabling Problem[J]. Operations Research，2002，50(5)：851-861.

[8] CAPRARA A，MONACI M，TOTH P. A Lagrangian Heuristic Algorithm for A Real-world Train Timetabling Problem[J]. Discrete Applied Mathematics，2006，154(5)：738-753.

[9] MENG Lingyun，ZHOU Xuesong. Simultaneous Train Rerouting and Rescheduling on An N-track Network：A Model Reformulation with Network-based Cumulative Flow Variables[J]. Transportation Research Part B：Methodological，2014，67：208-234.

[10] FISHER M L. An Applications Oriented Guide to Lagrangian Relaxation[J]. Interfaces，1985，15(2)： 10-21.

[11] GOH C J，MEES A I. Optimal Control on A Graph with Application to Train Scheduling Problems[J]. Mathematical and Computer Modelling，1991，15(2)：49-58.

[12] BRANNLUND U，LINDBERG P O，NOU A，et al. Railway Timetabling Using Lagrangian Relaxation[J]. Transportation Science，1998，32(4)：358-369.

[13] HARROD S. A Tutorial on Fundamental Model Structures for Railway Timetable Optimization[J]. Surveys in Operations Research and Management Science，2012，17(2)：85-96.