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

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

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

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

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

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

1 基于累積流變量的列車運行圖優(yōu)化模型

1.1 模型假設和已知條件

為更好地研究影響列車運行圖求解算法性能的關鍵要素，現(xiàn)對列車運行圖問題進行適當?shù)某橄蠛图僭O。假設列車在雙線鐵路網(wǎng)上運行，不考慮列車在站內(nèi)的進路與到發(fā)線安排；行車閉塞方式為自動閉塞，追蹤間隔時間固定且已知；列車在各區(qū)間的純運行時分、起停附加時分已知且固定；列車的數(shù)量、起訖點、徑路、停站方案已知；運行圖的編制不考慮車底的運用。

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

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

1.2 行車資源占用模型

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

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

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

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

(2) 列車駛過進路；

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

各階段占用時間見圖2。

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

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

列車出發(fā)追蹤間隔時間包括：

(1) 前行列車從車站出發(fā)至完全離開車站進入?yún)^(qū)間的時刻；

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

列車到達追蹤間隔包括：

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

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

列車通過追蹤間隔包括：

(1) 前行列車通過車站時刻起至列車完全離開車站進入?yún)^(qū)間的時刻；

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

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

定義路網(wǎng)中車站節(jié)點集合為V，區(qū)間弧段集合為E，車站節(jié)點標號為i,j,k；列車集合F，集合中各列車標號為f。

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

例如圖6(b)中，列車在t=5時離開車站i，則t<5時，dfi,t=0，t≥5時，dfi,t=1。在時間軸上表示車站i的累積流變量dfi,t序列時，累積流變量的性質(zhì)決定該序列最多僅可能在某一時刻發(fā)生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 )

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

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

1.4 基于累積流變量的列車運行圖優(yōu)化模型

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

列車運行圖優(yōu)化模型的目標函數(shù)是加權總旅行時間最短為

( 5 )

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

模型約束條件為

(1) 列車到達、出發(fā)事件狀態(tài)約束

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在車站上作業(yè)的同一組累積流變量隨著時間的推移最多只能發(fā)生1次變化，且只能從0向1變化，保證列車進入弧段或離開弧段事件從“尚未發(fā)生”到“已經(jīng)發(fā)生”的狀態(tài)轉(zhuǎn)變最多只能發(fā)生1次。

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

dfi,t≤afj,t

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

( 8 )

該約束保證列車進入?yún)^(qū)間的時刻不得晚于離開本區(qū)間的時刻。

(3) 出發(fā)時間窗

dfof,t=0

?f∈F?t∈T∧t

( 9 )

dfof,t=1

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

(10)

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

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

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

?f∈F?i∈V

(11)

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

(5) 區(qū)間運行時分約束

?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) 能力約束

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

(17)

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

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

2.1 拉格朗日松弛問題

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

目標函數(shù)為

(18)

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

(19)

式中：

2.2 基于時空狀態(tài)網(wǎng)絡最短路徑的子問題求解方法

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

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

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

(2) 到達節(jié)點表示列車的到達作業(yè)；

(3) 出發(fā)節(jié)點表示列車的出發(fā)作業(yè)；

(4) 通過節(jié)點表示通過列車的到達與出發(fā)作業(yè)。

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

時空網(wǎng)絡中有3類弧段：

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

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

(3) 停站弧表示列車在某車站內(nèi)從到達至出發(fā)的狀態(tài)轉(zhuǎn)變。

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

2.3 拉格朗日乘子更新方法

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

(20)

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

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

2.4 獲得可行解的啟發(fā)式算法

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

該啟發(fā)式方法在本質(zhì)上是滾動式求解方法，關鍵是如何確定進入規(guī)劃列車的順序。采用按照列車的LRPf由大到小的順序?qū)α熊囘M行滾動優(yōu)化求解，LRPf的計算方法為

LRPf=

(21)

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

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

3 算例分析

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

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

表1 算法求解性能分析

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

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

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

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

4 結論

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

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

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

參考文獻：

[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] 周磊山，胡思繼，馬建軍，等. 計算機編制網(wǎng)狀線路列車運行圖方法研究[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] 彭其淵，朱松年，王培. 網(wǎng)絡列車運行圖的數(shù)學模型及算法研究[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] 史峰，黎新華，秦進，等. 單線列車運行圖鋪劃的時間循環(huán)迭代優(yōu)化方法[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，F(xiàn)ISCHETTI 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.