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

(北京交通大學(xué) 城市交通復(fù)雜系統(tǒng)理論與技術(shù)教育部重點實驗室，北京 100044)

高速鐵路列車運行調(diào)整策略優(yōu)化

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

(北京交通大學(xué) 城市交通復(fù)雜系統(tǒng)理論與技術(shù)教育部重點實驗室，北京 100044)

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

高速鐵路；列車運行調(diào)整；策略優(yōu)化；極大加代數(shù)

0 引言

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

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

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

1 問題描述

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

圖1 策略優(yōu)化方法

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

2 高速鐵路列車運行調(diào)整策略優(yōu)化模型

2.1模型假設(shè)

高速鐵路列車運行調(diào)整策略優(yōu)化模型的基本假如下：

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

(2)后續(xù)列車需要越行時，避讓和越行只發(fā)生在車站內(nèi)，且調(diào)整區(qū)段首尾站不進行越行;

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

2.2定義相關(guān)參數(shù)及決策變量

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

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

2.3模型構(gòu)建

目標函數(shù)：

(1)

約束條件：

越行約束：

lj≥li，(i、j∈P)

(10)

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

3 列車運行調(diào)整策略匹配分析

3.1基礎(chǔ)調(diào)整策略適用分析

策略1：

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

圖2 策略1調(diào)整情況

策略2：

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

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

圖4 k站越行情況

圖5 k+1站越行情況

(11)

(12)

策略3：

圖6 策略3針對基本情況

圖7 策略3新增越行情況

3.2構(gòu)建列車晚點情況與基礎(chǔ)策略匹配關(guān)系

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

表1 情景-策略匹配表

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

4 算法設(shè)計

4.1算法的數(shù)據(jù)表示及求解思路

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

Step1：列車n在站m的到發(fā)時間；

Step2：后續(xù)列車在站m的到發(fā)時間；

Step3：后續(xù)車站的列車的到發(fā)時間；

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

對于大面積晚點情況，則根據(jù)限速值對應(yīng)轉(zhuǎn)換區(qū)間最小運行時分數(shù)據(jù)，同理求解即可.

4.2算法流程

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

圖8 算法流程圖

5 實例分析

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

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

圖9 調(diào)整區(qū)段基本運行圖

表2 假設(shè)晚點調(diào)整結(jié)果

(1)策略匹配度分析

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

表 3 單一策略調(diào)整與綜合策略優(yōu)化方法的匹配度對比

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

(2)晚點時間降低分析

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

表4 優(yōu)化后晚點降低情況

(3)調(diào)整效率分析

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

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

6 結(jié)論

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

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

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

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

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

[5] 陳雍君,周磊山.基于序優(yōu)化方法的列車運行調(diào)整算法研究[J].鐵道學(xué)報,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]刑錦江.虛擬現(xiàn)實環(huán)境中的策略生成[D].北京:北京航空航天大學(xué),2008.

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

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

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

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

下期待發(fā)表文章摘要預(yù)報

激波矢量控制噴管性能分析與結(jié)構(gòu)優(yōu)化設(shè)計

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

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

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

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

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

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

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

E-mail15120941@bjtu.edu.cn.

A