高速鐵路列車運行調整策略優化

戴楊鋮，宋瑞，畢明凱，陳旭超

(北京交通大學 城市交通復雜系統理論與技術教育部重點實驗室，北京 100044)

高速鐵路列車運行調整策略優化

戴楊鋮，宋瑞，畢明凱，陳旭超

(北京交通大學 城市交通復雜系統理論與技術教育部重點實驗室，北京 100044)

在分析高速鐵路列車運行調整問題及策略優化思想的基礎上，以列車加權總晚點時間最小為目標，考慮列車運行時分、車站間隔時間等約束，建立了高速鐵路列車運行調整策略優化模型 .針對不同適用情況，提出三種基礎調整策略，構建情景-策略匹配表，并基于極大加代數的時刻表遞推思路，運用 C#軟件進行求解 .最后以京廣高鐵區段為例，隨機假設晚點情景，分析調整結果 .優化后策略匹配度為100%， 晚點時間平均減少24.07 min，晚點幅度降低 4.2%～53.5%，求解效率顯著提升，驗證了模型和算法的有效性.

高速鐵路；列車運行調整；策略優化；極大加代數

0 引言

高速鐵路是指列車速度超過250 km/h的新建線路和超過200 km/h的既有線改造線路.一般情況下，列車是按照基本運行圖來運行的.列車運行調整[1]是指當列車的運行狀態偏離預定值時，通過重新規劃列車運行時刻表，盡可能恢復有序運行狀態的過程.

在高鐵列車運行調整優化方面，許多專家學者進行了深入研究.石雨[2]將問題進行轉化，針對局部調整和大面積調整分別提出了模型及算法.吳麗然[3]建立了以總晚點車數最少為優化目標的數學規劃模型.李曉娟[4]及陳雍君[5]都使用了序優化方法進行列車運行調整，并取得了足夠好的解.J.T.Krasemann[6-7]則使用了貪婪算法進行實時的列車調整，有效減少了后續列車的連帶晚點現象.

現有研究多為靜態分析，且側重于建模和算法，使得求解結果過于理論化，實用性下降.策略優化思想則兼顧優化理論和實際經驗，其基礎調整策略均是基于實際經驗給出，在此之上，進一步通過優化組合理論，確定多種隨機晚點情況下最優調整策略，從而達到列車運行調整的目標.本文針對列車運行調整中的晚點情況，在已有研究基礎上構建高鐵列車運行調整策略優化模型，提出三種基礎調整策略，并構建情景-策略匹配表進行研究分析.

1 問題描述

策略是指對將來任意可能的狀態采取行動的規則[8]，如在生產調度工作中，策略是指推遲加工設備的開、完工時間或調整加工設備的加工順序等[9].列車運行調整問題的原理亦是如此.如發生晚點，調度員采用的調整方法是后續列車依次開行，還是快速列車對中速列車進行越行，就類似于調整計劃工作時間、變更工序的策略.傳統優化方法以某些指標為優化目標，采用固定的算法(或稱單一策略)進行仿真求解.但實際運用中，晚點情況紛繁不一，當晚點復雜時，采用簡單的算法求解便得不到最優結果；當晚點輕微時，采用復雜的算法勢必影響求解效率.而策略優化方法是以策略而非傳統目標值為對象的優化方法，能夠根據實際情況匹配最為合理的策略進行求解，更好地適應環境的多變性和隨機性，滿足高鐵調度準確性、高效性的要求.策略優化方法的求解思路如圖1.

圖1 策略優化方法

文獻[10-11]把列車運行調整原則和措施的結合作為列車運行調整策略，這也是現有研究的常用定義方式.本文結合可選越行原則及調整列車到發時間、順序的措施，根據晚點列車的實際情況，增添不同的越行判斷，進行相應的策略分析.

2 高速鐵路列車運行調整策略優化模型

2.1模型假設

高速鐵路列車運行調整策略優化模型的基本假如下：

(1)調整區段為快、中速列車混行，所有列車均不發生早點情況;

(2)后續列車需要越行時，避讓和越行只發生在車站內，且調整區段首尾站不進行越行;

(3)列車在區間內運行速度不變(安排額外的停站時不考慮起停車附加時分).

2.2定義相關參數及決策變量

設Q為調整區段上車站的集合，共q個車站；E為相鄰車站的區間集合，共q-1個區間；P為開行的列車集合，共p輛列車；li表示列車i的等級，由列車的種類決定；Z表示運行調整的周期；分別表示車站k的不同時到發、發到、到達、發車的作業間隔時間；表示列車i在車站k的停站情況，若停站，則否則；表示列車i在車站k的停站時間最小值；表示列車i在區間e上的純運行時分最小值；表示列車在車站k的起車附加時分；表示列車在車站k的停車附加時分；為基本圖中列車i在車站k的出發時刻；為基本圖中列車i在車站k的到達時刻.

定義：Θ為設定的計算符號，當a≥b時，aΘb=a-b，當alt;b時，aΘb=a-b+Z.

2.3模型構建

目標函數：

(1)

約束條件：

越行約束：

lj≥li，(i、j∈P)

(10)

其中，式(1)為目標函數，表示調整區間、時段內所有列車加權總晚點時間最小，式(2)～(5)分別為車站不同時發車、到達、到發、發到作業間隔時間約束，式(6)為列車區間運行時間約束，根據區間運行時分及圖定停站情況決定，式(7)為列車停站時間約束，式(8)為不早點約束，式(9)為調整時間范圍約束及整數約束，式(10)為基本越行原則下前后車等級約束.

3 列車運行調整策略匹配分析

3.1基礎調整策略適用分析

策略1：

策略1為依次開行策略，即列車發生晚點后，后續列車依次順延，利用運行圖緩沖時間恢復正點.如圖2所示，記tw為列車i在k+1站的晚點時間，后車j根據車站間隔時間調整至當前可行的最早到達時間即可，tt為調整時間.該策略施行難度小，求解速度最快，是調度工作中最常用的調整策略.

圖2 策略1調整情況

策略2：

當中速列車發生晚點時，可能會與后續快速列車形成如圖3所示的沖突，記t0為列車i與列車j在k站的發車時間差，此時若仍采取策略1進行調整，將造成嚴重的連帶晚點現象.針對這種情況，策略2新增了快速列車可越行中速列車的越行判斷(其余情況同策略1)，此時必須滿足ljgt;li.

圖3 策略2針對沖突基本情況

圖4 k站越行情況

圖5 k+1站越行情況

(11)

(12)

策略3：

圖6 策略3針對基本情況

圖7 策略3新增越行情況

3.2構建列車晚點情況與基礎策略匹配關系

因策略3考慮的情況較為全面，因此，無論晚點情景如何，理論上均可采用策略3得到最優調整結果.但隨著求解規模擴大至路局，甚至路網，單獨采用策略3也會極大地影響調度效率.而傳統的人工調度多采用策略1進行調整，少數的越行操作僅憑借經驗進行判斷，不具備足夠的前瞻性和規劃性.因此，必須構建合理的情景-策略匹配表，確定綜合調整方案，達到最優的求解效果.

表1 情景-策略匹配表

本文將晚點情景分為兩大類：局部晚點及大面積晚點.局部晚點指的是單一列車自發晚點的情景，此時，應依據晚點列車和周圍(如臨近1-2位)列車的種類、圖定運行情況及晚點程度(如輕微：5 min及以下，嚴重：5 min以上)來預測是否需要越行，并針對性地匹配調整策略.大面積晚點指的是由于天氣、自然災害等因素，導致所有列車在某區間內集體限速的情況.此時由于各列車之間不存在速差，因此均采用依次開行策略.結合3.1中各策略適用情況，得到情景-策略匹配結果，如表1.其中，“輕微”、“嚴重”、“周圍”等要素均可根據運用實例進行調整.

4 算法設計

4.1算法的數據表示及求解思路

采用文獻[12]給出的基于極大加代數的時刻表遞推思路，運用矩陣表示相關數據，定義自發晚點列車為列車n，發生晚點的車站為站m，晚點時間為delta，使用C#軟件進行求解.具體步驟為：

Step1：列車n在站m的到發時間；

Step2：后續列車在站m的到發時間；

Step3：后續車站的列車的到發時間；

Step4：終到站q的列車的到達時間.

對于大面積晚點情況，則根據限速值對應轉換區間最小運行時分數據，同理求解即可.

4.2算法流程

如圖8，首先輸入已知數據、晚點情況及情景-策略匹配表，然后根據m的值進行下一步計算并循環，直至m=q，得到完整的調整時刻表及F，結束算法.

圖8 算法流程圖

5 實例分析

以京廣高鐵許昌東至安陽東區段上行方向的列車運行圖為例，該區段內共有6個車站，調整時段為某日的18∶00-21∶20，時段內有15列車，按上行順序及列車進入區段的先后順序將其采用自然數編號.其中，8車(G506)、12車(D2202)為中速列車，列車等級定義為1，一般快速列車按速度比定義為1.25，3車(G504)、9車(G70)為重點車，根據調研結果將其等級定為2.5.調整區段的基本運行圖如圖9所示，區間運行時分、車站間隔時間、列車停站情況等已知數據可參見京廣高鐵列車運行圖資料.

隨機給出20個局部晚點(列車n在站m自發晚點delta)情況和2個大面積晚點(h區間內列車集體限速為speed)情況.將晚點情況代入表1進行匹配，得到對應策略，然后分別采用三種策略進行調整，得出不同策略下的加權總晚點時間F1～F3(單位為min)，調整結果如表2所示.

圖9 調整區段基本運行圖

表2 假設晚點調整結果

(1)策略匹配度分析

定義“最優策略F優”為F值最小且最簡便的策略，“策略匹配度”為某種調整方法下最優策略所占的比例.對比表2中F1～F3的值，可得單獨采用某種策略進行調整的方法(傳統方法)和綜合策略優化方法的策略匹配度，如表3.傳統方法無法兼顧調整結果和求解效率，而策略優化方法可以很好地解決這個問題，策略匹配度達100%.

表 3 單一策略調整與綜合策略優化方法的匹配度對比

此外，局部晚點時，匹配策略1的情況為65%，策略2為25%，策略3為10%；大面積晚點時，均匹配策略1.可見，基本運行圖已經充分考慮了列車到發順序、運行緩沖時間等，對于大部分晚點情況，依次開行策略即為最優策略，符合策略1～策略3針對情況依次復雜化的設計思路.

(2)晚點時間降低分析

在假設晚點情況下，將采用綜合策略(匹配策略2和策略3)所得的F優與采用單獨策略1(傳統調度策略)所得F1進行對比，得到晚點時間減少量F減.此時，加權晚點時間平均減少24.07min，晚點幅度降低4.2%～53.5%，具體如表4.實際工作中，由于自發晚點列車周圍運行線的密集程度和辦理越行的車站位置等因素，均對策略調整后的晚點優化效果產生直接影響，因此F減的分布呈無固定規律性.

表4 優化后晚點降低情況

(3)調整效率分析

針對本文使用的6車站、15列車、200 min調整時段的實例，使用計算機進行各種策略下的求解，并模擬人工調度過程，耗時如表5所示.綜合策略下，相比單獨采用策略2或3，求解效率可分別提升20%和31.4%，且所有策略算法均具備良好的計算機適應性，求解效率較人工調度大幅提升.未來隨著求解規模的擴大，策略優化對于高鐵調度工作效率的意義將愈發顯著.

表 5 各策略下求解效率對比

6 結論

將策略優化思想運用于高鐵列車運行調整，結合優化理論和實際經驗，解決了傳統優化方法無法兼顧調整結果與求解效率的問題.在區間運行時分及車站間隔時間等基礎約束上，以列車加權總晚點時間最小為目標函數，構建高鐵列車運行調整策略優化模型.針對不同的適用情況，設計策略，并構建情景-策略匹配表.基于極大加代數的時刻表遞推思路，編寫算法，運用C#軟件求解.最后，以京廣高鐵區段為例，隨機假設多種晚點情況，計算得到優化調整結果，分析得：優化后策略匹配度為100%，晚點時間平均減少24.07 min，晚點幅度降低4.2%～53.5%，驗證了模型及策略匹配的可行性.同時，求解效率顯著提高，為進一步研究列車運行調整中的計算機智能決策問題奠定基礎.

[1]張翠平. 高速旅客列車運行調整問題的圖論模型與啟發式算法[D]. 北京:北京交通大學,2010.

[2]石雨.客運專線列車運行調整的策略、模型與算法[D]. 北京:北京交通大學,2010.

[3]吳麗然.高速鐵路列車運行調整問題研究[D]. 成都:西南交通大學,2011.

[4] 李曉娟,韓寶明,李得偉,等.基于轉換極大代數和序優化的高速列車運行調整方法[J].中國鐵道科學,2013(6):124-130.

[5] 陳雍君,周磊山.基于序優化方法的列車運行調整算法研究[J].鐵道學報,2010(3):1-8.

[6]KRASEMANN J T. Design of an effective algorithm for fast response to the re-scheduling of railway traffic during disturbances [J]. Transportation Research Part C,2012.

[7]KRASEMANN J T. Greedy algorithm for railway traffic re-scheduling during disturbances: a Swedish case [J]. IET Intelligent Transport Systems,2010,4(4):1-12.

[8]刑錦江.虛擬現實環境中的策略生成[D].北京:北京航空航天大學,2008.

[9]WHITE D J. Markov Decision Processes [M]. Chi Chester: Wiley Press, 1993.

[10]賀振歡,李海鷹,苗建瑞,等.鐵路客運專線列車運行調整策略仿真分析[J].系統仿真學報,2010(1):262-265.

[11]聶磊,張星臣,趙鵬,等.高速鐵路列車運行調整策略的研究[J].鐵道學報,2001(4):1-6.

[12]李傳賓.基于矩陣表示和極大代數法的高鐵周期列車運行圖編制方法研究[D]. 北京:北京交通大學,2012.

下期待發表文章摘要預報

激波矢量控制噴管性能分析與結構優化設計

李麗，張琳琳，呂錫昌，李東明

(大連交通大學 機械工程學院,遼寧 大連 116028)

摘要：采用試驗設計方法進行激波矢量控制噴管氣動性能數值分析與優化設計，綜合研究了二次流幾何參數對二元收擴噴管氣動性能的影響.基于超拉丁立方設計方法得到噴管二次流參數近似擬合模型和最優解區域，并利用多島遺傳算法尋找最優解.研究的設計參數包括二次流口距離、二次流口寬度及二次流長度.數值仿真結果表明，二次流口距離對矢量偏轉角的影響最大，二次流口寬度次之，二次流長度對矢量偏轉角的影響最小.

OptimizationMethodforRe-SchedulingStrategyofHigh-SpeedRailway

DAI Yangcheng，SONG Rui，BI Mingkai，CHEN Xuchao

(Moe Key Laboratory for Urban Transportation Complex Systems Theory and Technology, Beijing Jiaotong University, Beijing 100044, China)

In order to analyze operation problem of high-speed train and strategy optimization, a strategy optimization model is constructed to minimize the total weighting delay time with the constraints of operation time and station interval time. Based on multiple types of delay scenarios, three basic adaptive adjustment strategies are proposed, and situation-strategy matching forms are built using the idea of max-plus algebra to derive the timetable and computed the results with a software based on C sharp. Besides, the case of a high speed section of Jingguang railway administration which is from Xuchang East Station to Anyang East Station is used and the optimized results of delay adjustment under the randomly simulated scenarios are obtained. The results show that after the optimization, the strategy matching degree reachs 100%, the delay time is reduced by 24.07 min equally, and the range of delay is decreased by 4.2-53.5%. The computational efficiency is enhanced significantly, and the effectiveness of the strategy matching model is validated.

high-speed railway；train regulation；strategy optimization；max-plus algebra

1673- 9590(2017)06- 0012- 07

2017- 03- 02

中國鐵路總公司科技開發計劃資助項目(2016F023)

戴楊鋮(1992-)，男，碩士研究生；

宋瑞(1971-)，女，教授，博士，主要從事交通運輸管理的研究

E-mail15120941@bjtu.edu.cn.

A