彭其淵，陸柳洋，占曙光

（西南交通大學，交通運輸與物流學院，成都 610031）

0 引 言

高速鐵路因其速度快，運行平穩(wěn)性好，晚點率低等特性，在我客運市場上占據(jù)一定份額。鐵路系統(tǒng)內部子系統(tǒng)之間具有較強的耦合性，如果鐵路區(qū)間突發(fā)故障之后列車運行調整處理不當，則會出現(xiàn)大面積列車晚點等不良影響。

近年來，如文獻[1]所述，國內外學者對于列車運行調整產(chǎn)生了極大的興趣，并深入研究微干擾情景下的調整方案；文獻[2-6]從微觀角度對微干擾下的列車運行調整問題進行系統(tǒng)研究，采用替代圖的方法構建模型，并基于此開發(fā)了ROMA系統(tǒng)；文獻[7]分析區(qū)間封鎖或半封鎖狀態(tài)的列車運行調整研究；文獻[8]在文獻[7]的基礎上同時考慮車底運用與運行圖調整，最后結合實例驗證。

國內方面，文獻[9-11]研究區(qū)間故障全失效的情況下，利用事件-活動網(wǎng)絡建立混合整數(shù)線性規(guī)劃模型，并用京滬高鐵實例進行驗證。不過文中并沒有詳細考慮故障發(fā)生后，區(qū)間運行列車由于車站能力限制而無法停靠車站的情景；文獻[12]對于不能確定故障持續(xù)時間的列車運行調整問題設計了“兩階段帶補償隨機期望模型”，并在討論多階段遞歸決策概念模型復雜度的基礎上最終給出了不完全連續(xù)多階段決策模型；文獻[13]研究了動態(tài)隨機環(huán)境中的鐵路調度魯棒性問題，建立單線鐵路故障調整模型并采用滾動時域方法求解；文獻[14]在文獻[13]的基礎上，對雙線鐵路網(wǎng)絡進行模糊可靠性優(yōu)化并通過兩階段0-1整數(shù)規(guī)劃模型進行求解。

高速鐵路列車由于運行速度高，除了樞紐站等大站外，中間站只配有少量到發(fā)線。因此在行車密度較大時，極易發(fā)生以下情形：當故障發(fā)生時，在故障區(qū)間（e，e+1）內運行的列車若已經(jīng)越過故障區(qū)域，則該列車仍按計劃運行，否則該列車必須返回后方站e停車，并占用該站到發(fā)線；與此同時，按圖定計劃在相鄰后方區(qū)間（e-1，e）內運行并即將駛入站e的多列列車可能因為車站e沒有足夠的到發(fā)線供其停車而返回后方站e-1停車或區(qū)間停車。

在滿足列車安全運行各項約束的前提下，本文系統(tǒng)考慮了故障發(fā)生時區(qū)間運行列車的停車問題，并基于此做出調整方案，協(xié)助調度員的調度決策。

1 問題描述與界定

問題假設：由于列車運行調整涉及因素復雜，為研究方便，作以下假設（下述假設可以根據(jù)現(xiàn)場實際情況進行適當?shù)乃沙诨蛐薷模?/p>

（1）故障一旦發(fā)生，可以預測故障結束時刻；

（2）所有列車均允許區(qū)間停車且每一區(qū)間內區(qū)間停車列車數(shù)量至多為1列；

（3）列車返回后方車站運行時間可預知。

對于假設（2），根據(jù)廣鐵集團《調度所管理工作細則》第227條規(guī)定，調度員不能以機外停車作為列車運行調整手段，除非遇到行車設備臨時故障、交通事故、自然災害等特殊情況。不過當上述特殊情況發(fā)生時，《調度所管理工作細則》并沒有對列車區(qū)間停車的數(shù)量做出詳細規(guī)定。因此，本文假設每一區(qū)間內區(qū)間停車列車數(shù)量至多為1列。

問題描述：本文定義區(qū)間運行列車特指在某一時刻正在某區(qū)間內運行的列車。本文為處理區(qū)間運行列車停車問題，在故障發(fā)生時區(qū)間運行列車所在位置處設置虛擬站，將列車區(qū)間停車視為虛擬站停車。為了更清楚地描述本文所要研究的問題，下面用一個簡單例子進行說明，見圖1。

圖1 列車區(qū)間停車運行調整示意圖Fig.1 The diagram of train interval parking rescheduling

已知下行方向有4列列車t1、t2、t3和t4，分別用實線表示其運行線；設置7個車站，橫向實線表示實際存在的車站s1，s2，s5，s7；橫向虛線表示虛擬站s3，s4，s6。假設在時刻h1，車站s5和s7之間的區(qū)間內發(fā)生故障，導致該區(qū)間喪失通過能力，并初步估計故障將持續(xù)到h2。故障發(fā)生時，列車t1、t2和t3仍在區(qū)間內運行。若此時車站s2，s5剩余可用到發(fā)線數(shù)量分別2條和1條。為了避免列車停在故障區(qū)間影響救援，列車t1需返回后方站s5停車，虛線運行線表示返回過程。根據(jù)車站能力，車站s5則無法再停靠其他列車。由此，列車t2可根據(jù)晚點影響最小化目標，選擇區(qū)間停車或返回后方車站停車，此處，列車t2可選擇區(qū)間停車，即停留在虛擬站s4。按照假設規(guī)定，列車區(qū)間停車數(shù)至多為1列，因此列車t3返回車站s2，并占用1條到發(fā)線。此時車站s2仍有1條到發(fā)線剩余，因此相鄰后方車站可向區(qū)間(s1,s2)發(fā)車，那么列車t4從站s1出發(fā)，并運行至車站s2停車。故障結束后調度員還需合理調整列車t1、t2、t3和t4的出發(fā)順序和到發(fā)時刻，減少故障帶來的影響。

2 模型建立

2.1 符號說明

在模型中未解釋的參數(shù)符號與變量將分別在表1與表2中統(tǒng)一說明。

表1 參數(shù)符號及意義Tab.1 Parameter notations

表2 變量符號及意義Tab.2 Variable notations

2.2 模型構建

一般情況下，故障發(fā)生時仍在區(qū)間內運行的列車能夠在前方站停車。但考慮車站能力限制和故障隨機性，可能出現(xiàn)區(qū)間運行列車不能進入前方車站停車，模型構建時定義虛擬車站集合Sf和真實車站集合SF，S=Sf∪SF。

2.2.1 基本模型

目標函數(shù)式（1）表示列車到達晚點最小化；式（2）表示調整后列車發(fā)車時刻不早于圖定時刻；式（3）限定列車在某一區(qū)間的運行時分并考慮起停附加時分，其上下限可根據(jù)實際情況更改，本文限定運行時分上限為列車區(qū)間純運行時分加起停附加時分，下限為列車區(qū)間運行時分加實際起停附加時分；式（4）表示如果列車t在車站s停站，則其在該站的停站時間必須大于最小停站時間，如果該列車在車站s不停車，則列車在該站的停站時間為0；式（5）表示如果某列車按計劃運行圖在某站停車（αts=1），則調整后該列車也必須在該站停車（θts=1）；式（6）中e表示故障區(qū)間（e,e+）端點站的索引號，該式表示：如果列車t在故障發(fā)生時尚未進入故障區(qū)間（dte≥h1），那么，列車需等到故障結束后尚可從e站出發(fā)；式（7）和（8）表示干擾發(fā)生之前，列車按照計劃運行圖運行，但是不包含在h1時刻的區(qū)間運行列車；式（9）限定變量的取值范圍。

2.2.2 列車間隔與能力約束

（1）相鄰列車運行間隔約束

根據(jù)自動閉塞要求，相鄰列車運行過程中必須滿足一定的間隔時間約束。間隔時間主要有三種：出發(fā)間隔時間I1、到達間隔時間I2及發(fā)到間隔時間I3。正常情況下，列車運行順序在計劃運行圖中已經(jīng)給定，但是在故障情況下，相鄰列車之間的運行順序可能會改變。因此，對于每個區(qū)間內相鄰列車之間的先后順序，定義0-1變量

① 列車之間的出發(fā)間隔約束與到達間隔約束

對于任意兩列列車t和t′在任意區(qū)間（s,s+）的端點站s和s+的出發(fā)與到達之間滿足如下關系：

式（10）～（12）分別保證同一區(qū)間內兩列車t和t′在區(qū)間兩端點站的出發(fā)間隔時間和到達間隔時間滿足最小間隔時間要求，且該相鄰列車在區(qū)間一端點站的出發(fā)順序和在同區(qū)間下一端點站的到達順序保持相同，那么列車在區(qū)間不發(fā)生越行。

② 相鄰列車發(fā)到間隔約束

對于在某一車站某出發(fā)列車與后續(xù)某到達列車之間的先后順序，文中定義0-1變量利用該變量建立列車發(fā)到時間約束。

式（13）保證每個車站內，列車t從車站出發(fā)先于后續(xù)列車t′到達同一車站的發(fā)到間隔時間滿足最小間隔時間要求。

（2）車站能力約束

本文以車站到發(fā)線數(shù)量代表車站能力?，F(xiàn)實中若列車在站停車，那車站需提前預留一條到發(fā)線供列車占用；不停站通過的列車從車站正線通過，此時車站不需要提前預留空閑到發(fā)線。因此表達車站s到發(fā)線占用情況約束如下：

式（14）表示：列車t′即將進入車站s停車時該站必須預留空閑到發(fā)線。列車t′通過車站時則該站不需預留空閑到發(fā)線。

（3）有效不等式

① 列車越行與停站之間的關系約束

式（15）表示列車t被列車t′越行時，列車t必須在車站s停車（θts=1）。

② 列車發(fā)到順序與區(qū)間運行順序之間的關系約束

列車t從s發(fā)車先于t′到達該站，則列車t到達s站必定先于列車t′到達該站則建立如下約束：

2.2.3 故障時刻區(qū)間內運行列車停車約束

當區(qū)間故障發(fā)生時，由于車站能力限制，列車前方站并不能容納所有區(qū)間運行列車，此時應考慮組織某些列車在區(qū)間停車或返回后方站停車。區(qū)間（e,e+）內發(fā)生故障時，若列車t仍在某區(qū)間內運行，則列車t所處位置設虛擬車站s，且僅允許列車t停車。由定義可知，虛擬站s與列車t之間存在一一對應關系，所以定義虛擬站s所對應列車記為t(s)。上述列車集合為設置0-1變量φts，定義如下：時刻h1,安排區(qū)間運行列車t在車站s停車否則

（1）虛擬車站屬性約束

為了表示列車區(qū)間停車，模型設置虛擬車站。虛擬站實際上為某運行方向（上行或下行）上的一段鐵路線路，不具有車站全部功能。如虛擬車站不組織列車越行；虛擬車站能力可視為1；由此建立如下約束：

式（17）規(guī)定虛擬站只允許1列列車停車；式（18）和（19）表示每個虛擬站（s∈Sf）不允許其他列車停車，除了對應列車t(s)；式（20）表示虛擬站（s∈Sf）不組織列車越行。

（2）單列列車停車方案唯一性約束

故障發(fā)生時列車必須要在故障區(qū)域之前停車，假如此時某一列車（t∈）在區(qū)間內運行，則該列車必須在某一車站停車。建立約束如下：

式（21）表示故障發(fā)生時區(qū)間運行列車t(s′)在某一車站停車。

（3）車站能力約束

（4）區(qū)間停車數(shù)量約束

區(qū)間停車數(shù)量可根據(jù)現(xiàn)場實際情況進行確定。本文規(guī)定，相鄰真實車站組成的區(qū)間內至多允許1列列車區(qū)間停車，則

式（23）中{s'|s-＜s'＜s}表示相鄰真實車站組成的區(qū)間(s-,s)內的虛擬車站集合。那么該式表示某一區(qū)間內的區(qū)間停車數(shù)不超過1列。

（5）單列列車返回后方站停車后再次出發(fā)的時刻約束

由于故障引起區(qū)間通過能力喪失，前方站能力限制以及區(qū)間停車數(shù)量限制，極可能需要組織故障時刻區(qū)間運行列車（t∈）返回后方實際車站停車。那么考慮如下情景：如果φts(′s)=1，s′∈SF，且車站索引號s′小于列車t(s)所對應的虛擬站索引號s，即s′＜s，那么列車t(s)返回后方車站s′停車。這說明列車t(s)的前方車站能力已經(jīng)飽和，所以列車t(s)返回車站s′后的出發(fā)時刻至少為故障結束時刻h2，做如下約束：

式（24）表示若列車返回后方站停車，那么列車從該站再次出發(fā)的時刻至少為h2。

3 算法設計

由于列車運行調整屬于NP-hard問題，隨著列車和車站數(shù)的增加，模型求解呈指數(shù)型增長，直接求解模型十分困難。目前既有算法有時域滾動算法[15]，二階段算法[10]以及其他啟發(fā)式算法。前兩種算法的本質思想是在保障解的質量的情況下，減小求解規(guī)模并提高求解速度。本文采用二階段算法進行求解。算法步驟如下：

第一階段：首先輸入列車參數(shù)、車站參數(shù)以及故障信息：包括列車運行時刻X，車站到發(fā)線數(shù)目C，車站間隔時分I，起停附加時分τ，故障區(qū)間(e,e+)，故障起止時刻h1,h2。然后運用CPLEX計算式（1）～（24）。其中式（14）只對故障發(fā)生時段內的列車起作用，并輸出初始方案。

第二階段：輸入第一階段的初始方案，接著固定h2之前的運行圖，然后用式（14）檢驗h2之后的調整方案是否可行。若可行，則該方案為整體最優(yōu)解；若不可行，調度員可先執(zhí)行h2之前的調整方案，然后基于初始方案，運用CPLEX計算式（1）～（16）調整h2之后的運行方案。

分析算法特性：故障結束時刻h2之前的調整方案可以快速求得，且必定滿足車站能力要求；而h2之后的調整方案則需要車站能力約束檢驗。

4 算例分析

本文用武廣客運專線實例來驗證模型有效性。實例包含全天列車63列，車站16個。參數(shù)取列車發(fā)到間隔時間2min，發(fā)車間隔和到達間隔時間2min，列車的起停附加時分別為2min，3min。

本文根據(jù)不同區(qū)間故障和故障持續(xù)時間，設置以下3個場景進行算例分析：

場景1：下行方向第7個區(qū)間故障，故障發(fā)生時間為上午9：00，記為（7，9：00）；

場景2：下行方向第10個區(qū)間故障，故障發(fā)生時間為下午13：30，記為（10，13：30）；

場景3：下行方向第8個區(qū)間故障，故障發(fā)生時間為下午15：40，記為（8，15：40）。

模型使用CPU為Inter（R）Core（TM）i5-45903.30GHz、內存為8GB的計算機求解。求解軟件為CPLEX并設定計算時間為300 s。各場景列車運行圖調整結果如表3所示。

表3 運行圖調整結果Tab.3 Train rescheduling result

當調整目標為列車到達晚點時間最小時，列車區(qū)間停車總比列車返回后方站停車節(jié)省時間。因此如表3所示，同一故障場景下不同故障情景的區(qū)間運行列車停車方案是相同的，即不隨故障持續(xù)時間變化而變化。當然如果在目標函數(shù)中加入列車區(qū)間停車懲罰值，那么不同故障情景可能會有不同的區(qū)間列車停站方案，但列車區(qū)間停車懲罰系數(shù)難以確定，本文暫不討論。

表3統(tǒng)計了場景1至3的關鍵數(shù)據(jù)，分別包括目標值、計算時間以及誤差。

文章認為誤差不大于10%的解是可以接受的近似最優(yōu)解。當計算結果的誤差超過10%時，例如情景（7，9：00，120），則用二階段算法進行求解。第一階段計算結果誤差為9.58%，不過h2之后的調整方案不滿足車站能力約束；然后進行第二階段的計算，結果表明目標值在第一階段基礎上增加13min，且比CPLEX正常求解至誤差為10%的目標值小1.9%，求解質量良好。

下面以故障情景（7，9：00，60）和（8，15：40，90）為例，給出調整后的運行圖如圖2、3所示。圖中橫坐標表示時間；縱坐標表示車站；列車運行圖中實線運行線代表列車未偏離計劃運行圖，虛線運行線代表列車偏離計劃運行圖。

圖2 列車運行調整方案Fig.2 Train rescheduling scheme

圖2是情景（7，9：00，60）通過模型調整之后的運行圖。區(qū)間8中的矩形是故障區(qū)域。

圖3是情景（8，15：40，90）通過模型調整之后的運行圖。區(qū)間8中的矩形是故障區(qū)域。列車在虛擬站（橫向虛線表示）停車，即列車29在區(qū)間7停車；列車30返回車站8停車。

圖3 列車區(qū)間停車運行調整方案Fig.3 Rescheduled interval parking

5 結束語

列車運行過程中不可避免會受到來自鐵路系統(tǒng)內部和外部的干擾，而導致區(qū)間喪失通過能力，此時需要讓區(qū)間運行列車在故障區(qū)域前停車。但是故障發(fā)生的時間和地點具有隨機性，因此區(qū)間運行列車很有可能因為車站能力限制而不能在前方站停車。當前方車站能力不足時，本文考慮組織列車返回后方車站或區(qū)間停車，并且在模型中加入列車起停附加時分參數(shù)，更貼近列車運行實際，具有更好的現(xiàn)場適用性。最后模型采用武廣63列車16個車站的高速鐵路列車數(shù)據(jù)進行測算，當模型規(guī)模較大時，采用二階段算法進行求解，求解質量有明顯提高。

[1] CACCHIANI V，HUISMAN D，KIDD M，et al. An overview of recovery models and algorithms for real-time railway rescheduling [J]. Transportation Research Part B Methodological，2014，63（2）：15-37.

[2] D’ARIANO A，PRANZO M，HANSEN I A. Conflict resolution and train speed coordination solving real-time timetable perturbations [J]. IEEE Transactions on Intelligent Transportation Systems，2007，8（2）：208-222.

[3] CORMAN F，D’ARIANO A，PACCIARELLI D，et al.Bi-objective conflict detection and resolution in railway traffic management [J]. Transportation Research Part C Emerging Technologies，2012，20（1）：79-94.

[4] CORMAN F，D’ARIANO A，PACCIARELLI D，et al.Centralized versus distributed systems to reschedule trains in two dispatching areas [J]. Public Transport，2010，2（3）：219-247.

[5] D’ARIANO A，PACCIARELLI D，PRANZO M. A tabu search algorithm for rerouting trains during rail operations [J]. Transportation Research Part B Methodological，2010，44（1）：175-192.

[6] CORMAN F，D’ARIANO A，HANSEN I A，et al. Optimal multi-class rescheduling of railway traffic [J]. Journal of Rail Transport Planning & Management，2011，1（1）：14-24.

[7] LOUWERSE I，HUISMAN D. Adjusting a railway timetable in case of partial or complete blockades [J].European Journal of Operational Research，2014，235（3）：583-593.

[8] VEELENTURF L P，KIDD M P，CACCHIANI V，et al.A railway timetable rescheduling approach for handling large scale disruptions[J]. Transportation Science，2016，50（3）：841-862.

[9] ZHAN S，KROON L G，VEELENTURF L P，et al.Real-time high-speed train rescheduling in case of a complete blockage[J]. Transportation Research Part B Methodological，2015，78：182-201.

[10] 占曙光，趙軍，彭其淵，等. 高速鐵路區(qū)間能力失效條件下列車運行實時調整研究[J]. 鐵道學報，2015，37（11）：1-9.

[11] 占曙光. 區(qū)間通過能力臨時失效下高速鐵路列車運行實時調整模型與算法研究[D]. 成都：西南交通大學，2016.

[12] 孟令云，楊肇夏，李海鷹. 單線鐵路區(qū)間能力失效條件下列車運行調整模型[J]. 系統(tǒng)工程理論與實踐，2012，32（4）：885-894.

[13] MENG L，ZHOU X. Robust single-track train dispatching model under a dynamic and stochastic environment：a scenario-based rolling horizon solution approach [J].Transportation Research Part B Methodological，2011，45（7）：1080-1102.

[14] YANG L，ZHOU X，GAO Z. Credibility-based rescheduling model in a double-track railway network：a fuzzy reliable optimization approach [J]. Omega，2014，48（10）：75-93.

[15] 彭其淵，楊明倫，聶勛煌. 單線區(qū)段實用貨物列車運行圖的優(yōu)化模型及算法[J]. 鐵道學報，1995（03）：15-20.