基于列車車次的動車組運用優化模型與算法

鐘慶偉 ，張永祥 ，王 典 ，殷 勇 ，閆 旭 ，彭其淵

（1. 西南交通大學交通運輸與物流學院，四川 成都 611756；2. 西南交通大學綜合交通運輸智能化國家地方聯合工程實驗室，四川 成都 611756）

動車組作為重要的移動設備資源，是執行列車運行圖的最終載體. 動車組主要由動車段及其下屬的動車運用所負責管理，通常情況下其運用計劃等由動車調度員進行編制. 隨著我國高速鐵路路網規模的擴大，動車段（所）及動車組的數量也不斷增加，如何合理地使用動車組資源成為了鐵路公司關注的一個科學難題[1]. 目前，現場動車調度員先根據發布的運行圖編制動車組交路計劃（即一組有序列車車次的集合），然后以固定的動車組交路計劃為基礎，在考慮不同等級維修限制的條件下編制動車組運用計劃（即運用計劃與檢修計劃的協同編制）. 當下，全國正在推廣實施列車運行圖的“一日一圖”編制方法[2]，動車組運用的相關計劃也將隨之進行動態調整. 在復雜高鐵網絡背景下，人工經驗編制方法難以滿足時效性要求，且編制的計劃質量及各計劃間的協調程度也難以得到保證. 因此，有必要借助數學優化方法對日益復雜的高速鐵路動車組運用問題進行研究.

過去數十年，動車組運用計劃的編制得到了國內外學者的廣泛關注. 文獻[3]以早高峰時期的座位短缺最少為優化目標，研究了動車組的分配問題；文獻[4-5]引入了動車組的改編作業；文獻[6-7]以固定的動車組交路計劃為基礎，通過對動車組交路計劃的調整，引入動車組的距離維修約束. 類似的研究還有文獻[8-9]，在交路調整過程中加入了時間和距離維修約束；文獻[10]以動車組可行運用計劃為決策變量，以最大化待檢動車組檢修前的累計運行里程為目標，建立了檢修計劃優化模型，并設計了分支定價算法求解；文獻[11-12]研究了動車組的運用與檢修計劃的優化編制方法，從接續網絡和離散處理的角度分別構建了0-1整數規劃模型，并設計了基于粒子群算法的求解策略；文獻[13]以復合網絡（hypergraphs）為基礎描述動車組運用問題，并考慮了動車組運用的時間和距離維修約束.

文獻[3, 8-12]未考慮動車組的重聯和摘解作業；文獻[3-4]未考慮動車組的維修限制；文獻[6-7, 9-12]僅考慮了車輛的距離檢修約束，與目前動車組的實際運用條件有所差異；文獻[9]未對動車組進行分類；文獻[4-5, 10-12]中考慮的路網結構較為簡單；文獻[3-5, 10-12]在進行動車組運用計劃的編制時，均以動車組交路計劃作為已知輸入，這種做法適合長期的周期性運行圖，能夠計算一段時間內的動車組運用計劃方案，當列車運行圖臨時更換或調整時，對應的交路方案也將發生變化，從而影響上述文獻中根據固定交路計劃編制的運用計劃的可行性；文獻[8-9]與本文的出發點相似，都沒有使用固定的動車組交路計劃作為輸入，不同之處在于文獻[8-9]采用啟發式方法生成交路段，然后進行交路段的重新組合，而本文則是在考慮多個實際運營約束的條件下基于列車車次生成可改編路徑；文獻[13]在求解實際規模的問題時需要耗費較長時間.

綜上，既有研究文獻有待完善之處主要體現在：1） 問題設定的條件較為簡單，如僅考慮單方面的動車組維修約束、路網結構簡單及無改編作業等；2） 多將動車組交路計劃作為已知輸入，不能很好地適應運行圖臨時更換或調整的情況；3） 未對動車組進行類別劃分或僅以動車組類別為研究單元來添加維修約束，不能精確地描述不同類型的單個動車組在執行任務前的初始狀態；4） 模型和算法復雜，實際應用的計算時間較長. 因此，本文針對運行圖臨時更換或調整的情況，研究包含多動車（段）所、多車種的高速鐵路網絡中帶時間和距離日常檢修限制的動車組運用計劃編制問題. 與基于固定交路段的研究不同，本文基于列車車次進行建模，能夠靈活地應對運行圖臨時更換或調整. 為提高求解效率，還設計了一個基于路徑生成的迭代逼近算法框架. 最后，文中所建立的模型能夠靈活地控制動車組的改編策略，更加適合未來的動車組靈活編組模式[14-15].

1 問題描述

在實際生產運營過程中，當列車運行圖臨時更換或調整時，相應動車段（所）的動車調度員就需要基于當前的動車組配屬、運用及檢修等情況，結合列車運行圖要求，快速地制定短期的動車組運用計劃（通常為動車組運用日計劃）. 如前文所述，此時就需要進行動車組交路計劃、日常檢修計劃及運用計劃的協同優化編制.

以包含5個車站、1個動車運用所、14條列車運行線以及2種不同類型動車組所構成的高速鐵路網絡為例進行說明，如圖1所示. 圖中：s1～s5為車站，綠色虛線為動車所銜接站，配有長度為15 km的出入線，其他車站為藍色實線；1～14為列車運行線編號；Ⅰ、Ⅱ分別代表一列8編組和一列重聯16編組的動車組，動車組的數量由列車運行線的預測客流量決定；“1-Ⅱ”代表列車車次1需要一列重聯16編組的動車組擔當，其余類推；運營時間段為06：00—24：00. 原則上所有的動車組在運營時段結束后返回動車所進行相應的檢修作業. 實際運營中，由于某些運行線的走行距離較長，可能會出現動車組在配屬所外過夜的情況. 兩種類型的動車組服務于該路網，動車組單元類型、累積運行時間、運行里程等基本信息如表1所示. 其中AL類動車組一旦出所其編組保持不變，A類動車組能夠在配備動車所連接線的車站返回到動車所進行改編. 同種類型的動車組之間能夠進行改編.

圖1 列車時刻表及站間距信息Fig. 1 Information of timetable and interval of stations

根據圖1中列車運行圖要求以及動車組單元的初始狀態，在不違反日常檢修規定（即動車組單元累積運行時間不超過2 d，且累積運行里程不超過5000 km）時，可獲得多種動車組運用計劃. 以列車運行線為節點、列車運行線間的可行接續關系為弧，將運行圖抽象為動車組接續網絡圖，基于該接續網絡的3種可行計劃方案如圖2所示. 圖中：D為動車段（所）；中括號中的路徑為對應各動車組單元的路徑詳情；各方案的空駛線、動車所連接線、段外過夜線有多種顏色，以區分不同的路徑.

表 1 動車組單元基本量信息Tab. 1 Basic information of EMUs

圖2 3種可行的動車組運用計劃方案示例Fig. 2 Three kinds of possible train-set scheduling

以圖2（a）中路徑D—1—9—D為例，該路徑表示從D出發，完成運行線1和運行線9然后返回D，由于運行線1和運行線9的始發/終到車站都沒有動車所連接線，因此該路徑包含部分空駛. 根據動車組單元的自身初始狀態，可由1號與2號動車組單元重聯完擔當該路徑任務. 對于包含多動車段（所）、多車種的復雜高速鐵路網絡而言，由運行圖中運行線任務可產生數萬種可行的動車組路徑方案，再結合各動車組的初始狀態及維修限制條件，調度員很難憑借經驗在短時間內編制一個高質量的動車組運用計劃，由此說明了本文研究的必要性.

2 基于列車車次的優化模型建立

在復雜高鐵網絡下，考慮運行時間和距離維修約束且包含改編作業的動車組運用優化問題是一類較為復雜的組合優化問題[11,14]. 為了降低問題的求解難度，在此將整個問題（whole problem，WP）分解為主問題（master problem，MP）模型和子問題（subproblem，SP）模型兩部分. 其中，MP是基于多商品網絡流理論建立的混合整數線性規劃模型，其目的是生成多種備選的可改編動車組路徑方案. SP是動車組可行路徑分配模型，其作用主要是根據動車組的運行時間和距離維修約束來檢驗和挑選備選路徑方案中的合理路徑. MP模型和SP模型之間以特定的過程進行迭代，逼近全局最優解，見第3節的迭代算法框架.

2.1 建模假設

便于問題的建模及描述，進行以下假設：

假設1列車運行線及其對應的預測客流量大小由列車運行圖確定，其中客流量大小轉換為符合運營規定的動車組編組方式.

假設2動車組可在具備條件的特定車站停放過夜，過夜停留時間均為6 h，由調度員給出可行的備選過夜運行線集合.

假設3動車組采用不固定區段的運營模式，空車調撥可在動車所之間、從動車所始發以及終到動車所時進行. 空駛運行線集合根據運行線可行接續關系提前生成.

假設4每個動車所都能進行不同種類的動車組改編作業，動車組從動車所始發或終到動車所時需要進行相應的改編作業.

假設5研究過程中僅考慮動車組的日常檢修限制條件，具體維修作業細節不作研究.

2.2 MP模型：可改編路徑方案生成模型

2.2.1 符號說明

定義集合及索引：B、b分別為動車所集合和索引，b∈B；U、u分別為動車組型號集合和索引，u∈U；M、m分別為動車組編組方式集合和索引，m∈M；T、t分別為列車運行線集合和索引，t∈T；Tf、Te、Tn分別為圖定列車運行線集合、可用空駛運行線集合、可用過夜運行線集合，Tf∪Te∪Tn=T；C、c分別為所有可行的列車運行線接續組合集合和索引，c∈C.

定義參數：Γ、τ分別為計算時間范圍和時刻；fc、sc分別為c中的第1個和第2個列車運行線；Zc,m,m′為c對應的所有可能動車組編組方式，其中m和m′分別 為 組合c中fc和sc的編 組 方式；Nu,b,1、Nu,b,2分別為運營開始前和運營結束后b中u型號動車組的數量；αc,m,m′為c中從m改編為m′所產生的費用；βt,m為t上使用m的費用； ε、ξ、ζ分別為動車所存車數偏離期望、總空駛里程以及總過夜時間的懲罰參數；Nu,m,m′,1、Nu,m,m′,2分別為從m改編為m′時重聯和摘解的u型號動車組數量；ηc、μc分別為c中摘解完畢時刻和重聯完畢時刻；lt、At、Dt、ρt分別為t的運行距離、終到車站、始發車站和過夜時間；Nm為m中需要的動車組單元數量；eu,b為b中u型號動車組的容量限制.

定義變量：yt,m為0-1決策變量，若t的編組方式為m，值取1，否則取0；Ju,b為整數變量，代表b在運營時間段結束后u類型動車組偏離期望的數量；Fc,m,m′為0-1決策變量，若m和m′分別為c中fc和sc的編組方式，值取1，否則取為非負整數變量，分別代表c中u類型動車組重聯和摘解的數量；qb,c,u、gb,c,u為0-1決策變量，分別代表c中重聯和摘解的u類型動車組是否來自b，若是，值取1，否則取0；wτ,u,b為非負整數變量，代表在時刻τ動車所b內u型號動車組的數量；σ 、 λ為整數輔助變量 ，分別為動車組總空駛里程及動車組總過夜時間.

2.2.2 目標函數

如式（1）所示，MP模型目標函數為最小化動車組運行成本、改編成本，并通過降低動車組非生產使用時間的占比（減少動車組的總空駛里程）來提高運用效率. 此外，對動車組在動車所外過夜及動車所庫存不均衡的情況進行懲罰. 為了統一目標函數各部分的單位，通過設置懲罰參數將總空駛里程等轉化為綜合運營費用. 總空駛里程和總過夜時間可根據最終使用的運行線進行計算.

式中：zMP為MP模型的目標函數；σ 和 λ可根據最終使用的運行線進行計算[16].

2.2.3 約束條件

1） 運行線擔當唯一性約束

定義第1天和第2天需要完成的列車運行線集合分別為T1和T2，第1天需要完成的列車運行線t∈T1，對應第2天列車運行線t′∈T2. 為了完成一天內列車運行圖中所有需要擔當的列車運行線，T1∪T2中相互對應的列車運行線有且只有某一動車組擔當，即

空駛列車運行線以及過夜運行線在運營過程中至多被使用一次，即

式中：t需滿足

2） 動車組接續平衡約束

為了保證動車組運用的接續平衡關系，需要滿足式（4）、（5）.

式（4）、（5）中：t需滿足At,Dt?B；式（4）中c需滿足fc=t，同時其第1個和第2個列車運行線的編組方式組合為可行的組合，即 (m,m′)∈Zc,m,m′；同理，式（5）中c需滿足

3） 動車所庫存能力限制約束

動車組在動車所內庫存數量的變化與動車組的改編作業相關，列車運行線接續組合中某類型動車組重聯和摘解的數量分別為

式（6）、（7）中：c需滿足(m,m′)∈Zc,m,m′.

動車所b內在時刻τ的u型動車組單元數量為

式中：c1～c4為C的索引，用不同符號以示區分；c1需滿足Dfc1=b且 ηc1≤τ；c2需滿足Asc2=b且 μc2≤τ；c3需滿足fc3,sc3∈Tf且 μc3≤τ；c4需滿足fc4,sc4∈Tf，且

式（8）中使用的動車組單元被分成僅在動車所始發、終到時進行改編作業的動車組單元和包含額外改編作業的動車組單元. 動車所內某類型動車組單元的容量限制為

4） 動車所庫存平衡約束

任一動車所b內某類型的動車組單元偏離期望值的數量為

式 中： Γ0和 Γ1分別為計算時間段的結束和開始時刻.

2.3 SP模型：帶維修約束的動車組指派模型

2.3.1 符號說明

定義集合及索引：R、r分別為動車組單元集合和索引，r∈R；Pr、p分別為r的所有路徑集合和索引，p∈Pr.

定義參數：ar為r的啟動費用，根據每個動車組單元根據的自身狀態不同設置相應不同的啟動費用；kr、lr分別為r的初始累積運行時間和初始累積運行距離，需在完成檢修后重置；ur、br分別為r的類型和初始停放動車所；up、bp、hp分別為p所要求的動車組類型、始發動車所和運行時間；mt為t的圖定動車組編組要求；ot,p為0-1參數，當t是p的一部分時，值取1，否則取0.

定義變量：xp,r為0-1變量，若r擔當路徑p時，值取1，否則取0.

2.3.2 目標函數

在SP模型目標函數中引入一個虛擬啟動費用，并規定啟用新的動車組單元（剛完成一級維修的動車組單元）有更高的啟動費用. 通過最小化動車組的虛擬啟動費來充分使用動車組，即

式中：zSP為SP模型的目標函數.

2.3.3 約束條件

包含列車運行線覆蓋、路徑唯一性、時間和距離維修限制約束3類約束，如式（12）～（15）.

式（12）滿足每個列車運行線的編組要求；式（13）保證一個動車組單元最多分配一條可行路徑；式（14）和式（15）分別保證每一個動車組單元在執行任務的過程中均滿足其日常檢修的時間和距離維修約束，其中r和p需滿足

3 基于路徑生成的迭代逼近算法

算法框架包含3部分，除了上述已經介紹的MP模型和SP模型部分，還有一個連接（connection part，CP）模型部分. CP是基于深度搜索的路徑生成模型，目的是將MP模型生成的每種備選動車組路徑方案中的路徑轉換為單個動車組單元的可行路徑集合. 整個迭代算法的框架如圖3所示，圖中：n為迭代循環次數；M為1次迭代過程中MP模型產生的備選交路計劃方案數（解池填充次數）；U0為整個問題的上界值.

圖3 基于路徑生成的迭代逼近算法流程Fig. 3 Flow chart of iterative gap reducing algorithm

3.1 WP有效下界證明

圖3中MP模型可以為WP提供下界L0，而在MP模型產生的可行解集合中能夠通過SP模型檢驗的可行解為WP提供上界U0，從而算法框架可以通過不斷地更換上、下界之間的最優間隙W0，迫使產生更接近于下界的新可行解. 定義zWP為 WP模型目標函數，為MP模型的任一可行解為不考慮維修限制的WP（稱為RWP）的任一可行解，為WP的任一可行解. 不難理解，若松弛SP模型中的維修限制條件，則通過CP模型轉換后都是松弛維修限制后的SP模型的可行解，此時；若SP模型中保留維修限制條件，則MP模型獲得的可行解集合中通過CP模型轉換后能夠通過SP模型檢驗的可行解才是WP的可行解不難推出，WP的解空間屬于MP模型的解空間，即由于WP是求目標函數值最小的優化問題，所以此時MP模型的最優解就是WP的下界.

3.2 CP模型主要步驟

步驟1根據MP模型決策變量取值Fc,m,m′明確列車車次之間的接續關系及其動車組編組方式，以動車所為起點、終點搜索獲得的路徑集合F.

步驟2將獲得的路徑集合F分為兩部分，即僅在動車所始發、終到時產生改編作業的路徑集合F1（如圖2中的路徑D—3—5—12—14—D）和包含額外改編作業的路徑集合F2（如圖2中的路徑D—3—5—7—8—11—13—D）. 以運行線編號索引為點V，列車運行線接續組合為邊E，構建有向圖G=(V,E) . 對任一f1∈F1，根據MP的變量yt,m提供的運行線動車組編組方式，將f1分解為單個動車組單元的路徑p1，并得到路徑集合P1. 對任一f2∈F2，根據MP模型變量qb,c,u、gb,c,u獲取額外改編作業對應的動車所相關信息，然后向G中添加新的有向邊.以動車所為起點和終點，采用改進的深度搜索算法搜尋路徑p2，并得到路徑集合P2.

步驟3對路徑集合P0=P1∪P2中的路徑進行統一編號，構建新的有向圖G′=(V′,E′) ，其中點V′為路徑的索引，邊E′為路徑之間可行接續. 以動車所為起點和終點，采用改進的深度搜索算法搜尋完整路徑集合Pr.

3.3 多日計劃求解方法

多日計劃有以下兩種方法可以實現：

1） 在MP模型中導入多日的運行圖數據. 在CP模型生成路徑集合時，根據計算周期及對應的維修等級，向每條路徑添加可行的維修弧，然后更改對應SP模型中的維修約束進行計算.

2） 選取獲得的任一可行運用計劃中的動車組路徑集合，將該路徑集合作為固定動車組交路，然后更改SP模型的維修限制條件（需增加新的累積變量和可行維修?。┻M行計算. 此方法類似人工編制的流程，即先確定交路計劃，然后在考慮相應等級維修限制的情況下進行長時間段的動車組運用計劃編制.

3.4 計劃調整優化方法

若某日列車運行圖已經執行了一部分時突然需要進行調整，此時只需要在MP模型中根據已經執行的運行線信息，固定對應的決策變量Fc,m,m′和wτ,u,b的取值，即

式（16）、（17）中：c為已執行列車運行線構成的接續組合，即fc,sc∈Tfix，Tfix為已經執行的列車運行線集合；同時c中列車車次編組需確定，即yfc,m=1且ysc,m=1 ；nτ,u,b為當前時刻τ動車段（所）b內u型車輛的可用數量.

通過添加式（16）、（17）來固定已經執行的運行線及已使用的動車組單元，然后基于未執行運行線信息、線路結構信息（可添加的空車調配線信息等）以及實時可用動車組單元信息（現有各車的狀態信息及可啟用的備用車狀態等）重新計算.

4 算例分析

以鄭州局集團有限公司所轄動車組開行的高鐵路網為算例背景，該路網包含36個主要車站及2個動車所，其結構如圖4所示. 選取兩套列車運行圖實際數據作為臨時更換后的運行圖，其對應各動車所不同類型的動車組單元保有量信息（每個動車組單元的初始狀態由于篇幅所限未列出）如表2所示，表中：數據1為2017年9月某日至2018年7月某日的實際圖，包含159條運行線（均為集成運行線，如昆明到鄭州東只算1條運行線，下同）；數據2為2018年8月某日至2019年7月某日的實際圖，包含212條運行線. 在統計可添加的人工空駛運行線和過夜運行線后，數據1總共包含377條運行線，數據2總共包含490條運行線.

可用4種類型的動車組，其中380AL類型在擔當運輸任務的中途不能改編（只有16編一種方式），其他3種類型的動車組列車則可在滿足條件的情況下進行改編（有8編和16編）.

算法框架在Visual Studio 2015環境中采用C#語言編程實現，混合整數線性規劃模型部分調用商業優化軟件CPLEX 12.8.0進行求解. 求解MP模型時，需使用多重可行解生成算法來生成多個備選路徑方案，可通過調用CPLEX中的populate函數實現，其中求解強度參數（pool intensity）設置為3，初始最優間隙（absolutely gap）W0設置為10000000，解池填充次數（populate times）M設置為50，其他參數均為默認值. 算法框架每一次從解池M中選取的備選路徑方案F設定為10. 此外，式（1）中的懲罰參數 ε、ξ 和 ζ 的取值分別設置為100000、1和4；αc,m,m′及 βt,m的取值通過與調度員商議后確定，由于篇幅限制在此并未列出. 迭代逼近算法的迭代時間、最優間隙終止條件分別設置為不超過120 s和小于等于0.0001%，不同運營策略下的運用計劃方案關鍵技術統計指標見表3. 表中：RS和OP分別為方案使用的動車組單元數量和動車所外過夜的動車組單元數量；ARL、MRL、MARL、AERL及ERL分別為方案所使用動車組單元的平均走行距離、最小走行距離、最大走行距離、平均空駛距離以及該方案的總空駛距離；OBJ、OBJSP以及CT分別為方案的目標函數值、對應SP模型目標函數值以及求解時間；策略1為沒有動車組在運行途中的額外改編作業，策略2為允許額外的改編作業. 策略1與策略2均保證動車所內動車組單元的庫存平衡. 在策略2中，規定額外的重聯作業耗時12 min、摘解作業耗時8 min，其他參數與前述保持一致.

圖4 測試的高鐵路網絡結構Fig. 4 Tested high-speed railway network

表2 各動車所不同類型的動車組單元保有量信息Tab. 2 Information of EMUs for different depots 組

由表3可以看到：數據1中兩種策略下的算法方案均能夠在120 s內求得最優解. 需要注意，數據1中策略1的算法方案與下界方案并不是同一方案，雖然兩個方案大部分關鍵指標一致，但OBJSP有差異，表示兩種方案使用的具體動車組單元并不相同.說明通過文中的方法能夠在短時間內縮小求解空間，迫使其不斷尋求更接近下界的優質解. 數據2能在120 s內獲得接近下界方案目標函數值的高質量解，其兩種策略下算法方案的目標值收斂過程如圖5所示，圖5中兩種策略下的最終目標值與下界值之間的差值均小于0.01%.

與人工方案相比，數據1和數據2算法方案的動車組總空駛距離的平均下降值分別為38%和9%，動車組單元平均空駛距離的平均下降值分別為32%和3%. 兩組數據結果上的差異主要來自數據2中動車組單元初始停放位置的調整（如表2所示）. 數據1和數據2中算法方案的動車組單元平均走行距離的平均上升值分別為7.9%和6.4%. 總空駛距離的下降及平均走行距離的上升，都從側面反映出動車組單元使用效率的提升. 同時，從表3中能夠看出，算法方案相比人工方案更能夠節省動車組單元的使用，且算法方案的目標函數值更?。ㄟ\營成本降低）.此外，不難發現允許額外改編作業的方案能夠進一步節省動車組單元的使用數量并降低綜合運營成本. 所有方案的動車所外過夜的動車組單元數量相同，說明所外過夜是不可避免的，如：鄭州（東）至昆明南、鄭州（東）至廈門北等. 綜上，通過上述多組實驗數據分析表明，相比于人工方案，算法方案結果中的動車組綜合運營成本平均下降10.5%、總空駛里程平均減少23%.

表 3 不同策略下各案例的動車運用計劃關鍵技術指標Tab. 3 Key statistics of train-set scheduling cases under different scenarios

圖5 不同策略下目標函數值收斂過程示意Fig. 5 Convergence process of objective function value process under different scenarios

5 結 論

1） 本文在包含多動車段（所）、多類型動車組的復雜高速鐵路網絡背景下，以最小化綜合運營成本和總空駛里程為優化目標，考慮動車組運營安全、動車所庫存能力、動車組日常維修限制等約束條件，建立了基于列車車次的可改編動車組運用優化混合整數線性規劃模型，并設計了一個基于路徑生成的迭代逼近算法框架.

2） 所提出的模型和算法能夠快速地編制滿足日常維修限制的動車組運用計劃，其合理性與有效性在以鄭州局為實例背景的算例中得到驗證，相比已有的研究更加適應列車運行圖更換或臨時調整的情況.

3） 未來可對算法框架進行改進，以提高求解效率；此外，還將對某些特殊場景（如突發自然災害或人為破壞等）下的動車組運用計劃實時調整做進一步探討.