中國鐵道科學研究院 通信信號研究所 許偉
 
 摘要：針對列車調度指揮系統在開通天津集中臺的過程中，出現的列車運行階段計劃調整方案不能滿足調度指揮要求的問題，研究天津集中臺列車運行階段計劃自動調整方案。天津集中臺管轄車站多，車站間環狀相連，連接方向多，列車走行徑路有300多條。為此，建立以列車優先級別、列車追蹤間隔時間、列車區間運行時分、列車起停車附加時分、車站股道接車能力、旅客列車最早發車時間和列車固定停站時間為約束條件，以列車加權晚點總時間最小為目標函數的調整模型。采用動態規化算法進行求解，設計相應的算法步驟，并以天津集中臺天津（臨時）至下直通場間的車站為例進行驗證。計算結果表明：采用上述模型和求解算法進行列車階段計劃調整，能夠快速給出列車運行階段計劃的有效調整方案。該方法在天津集中臺已經得到了應用。  

 
  關鍵字： 列車運行；階段計劃；計劃調整；列車調度指揮系統

    列車調度指揮系統（Train Dispatching Command System，TDCS）[1]在開通北京鐵路局天津集中臺的過程中，出現傳統列車運行階段計劃調整方案難以滿足當前調度指揮的需要。主要原因是,天津集中臺管轄方向多，列車徑路復雜，集中臺在調整時經常會造成多方向的列車沖突,從而造成列車大面積積壓，新增列車晚點。本文根據TDCS協同式閉環系統[2]的特點和對以往列車運行計劃調整模型[3－5]的研究，針對天津集中臺具體情況建立列車運行階段計劃調整模型，采用動態規劃算法求解，得到天津集中臺有效的列車運行階段計劃調整方案。

     1．模型的建立
 
     1.1 天津集中臺概況

    天津集中臺管轄3個客運站、10個貨運站（場）和7個臺間站（兩個行調臺共同管理的車站，鄰臺階段計劃傳入該車站），車站連接圖如圖1所示。車站連接方向多，有的甚至超過8個方向，且車站間成環狀相連,列車走行徑路有300多條。南倉地區下行到達場和下行直通場，客貨列車徑路交叉嚴重。天津集中臺連接方向多，連接北京方向、京九方向、德州方向、京山方向、北環方向、津薊支線、港口支線。在這種網狀線路情況下，區間和列車徑路均嚴格受到時間和空間的動態限制,移動1條運行線可能會導致一系列的列車運行沖突,緊緊依靠調度員的手工調整不能滿足當前的鐵路運輸要求。本文在對影響列車運行因素分析的基礎上，以列車的總晚點時間最小為目標，采用動態規劃算法進行優化調整列車運行階段計劃。

                                 
 

                            圖1、天津集中臺車站連接圖

    1.2參數定義

    設天津集中臺管轄調度區段內有車站m個，則j＝1,2,…m；運行的列車數為n列, 則i＝1,2,…,n；每個區間線路用具體的編號s表示，s=1,2,…,S；由于兩站間的聯絡線較多，同時,不同參照模式可能導致區間上下行混淆，因此取消區間上下行的概念。

     （1）列車階段計劃運行線為

式中： ， 分別為s線路中列車i在j站的到達時刻、出發時刻。

     （2)列車基本圖運行線為
    

     式中： ， 分別為s線路中列車i在j站的圖定到達時刻、圖定出發時刻。

    （3) 列車階段計劃調整時間域為(ｔ1,ｔ2]。

     1.3約束條件^[6，7]

     列車運行調整受列車優先級別、列車追蹤間隔時間、列車區間運行時分、列車起停車附加時分、車站股道接車能力、旅客列車最早發車時間和列車固定停站時間的約束。

    （1）列車優先級別約束條件[8] 為 
           ⁽¹⁾

    式中：Wij為列車的優先級別； m_ij為列車的權重因子，由專家系統^[9]根據列車運行知識庫中的列車等級、晚點度、旅程完成度等重要信息結合調度員的指令產生；P_v 為列車i在j站的列車等級(由高到低的順序)； L_v為列車的晚點度,由接入本臺的晚點時分確定比值； C_v為列車的旅行完成度,等于完成的旅程和總旅程的比值。

     (2）列車追蹤間隔時間約束條件為

                                  (2)

       式中： _mmT^j_ijs， 分別為兩列車在j站s線路上的最小發車時間間隔、最小接車時間間隔。

    (3）列車區間運行時分約束條件為

    (3)

    式中：（ ）為s線路中列車i在j+1站和j站間的計劃運行時分, 為列車i在j+1站和j站間s線路上的最小運行時分；（ ）為s線路中列車i在j+1站和j站間的圖定運行時分。

    (4)列車起停車附加時分約束條件為

   (4)

    式中： 為s線路中列車i在j+1站的通過時分； ， 分別為s線路中列車i在后方j站的到達、出發時間； 為s線路中列車i在j站的起動附加時分； 為s線路中i車在j+1站與j站之間的最小運行時分； 為s線路中列車i在j+1站的到達時間； 為s線路中列車i在j+1站的停車附加時分。

     (5)車站股道接車能力約束條件為

   (5)

      其中:   

    式中： 為接車站在時刻t股道s方向的占用總數； 為車站j在s線路方向總的股道數目。

   （6）旅客列車最早發車時間約束條件為

                      (6)

式中： , 分別為列車i在j站的出發時間、圖定發車時間。

（7）列車固定停站時分約束條件為

           (7)

式中：（ ）為列車i在j站的停車時間； 為列車i在j站的最小作業時間（如列檢、司乘交班等）。

（8）區間可用約束條件為

(8)

式中： 為j站t時刻s方向線路是否可用。

   （9）其他約束條件為：在實際生產中，影響列車運行的因素還有施工天窗、施工慢行、設備故障、設備技改、區間裝卸、惡劣天氣（暴雪、大風、大霧等）等，在自動調整過程中，根據現場設備的實時信息和調度員輸入的控制命令，專家系統將這些因素關聯于約束條件（1）－（8），例如，第j站s線路區間“天窗” 施工，專家系統直接將其作為約束條件（8）處理。

     1.4目標函數

    列車運行階段計劃調整的最終目標是：實現列車貼近基本圖行車,提高列車的正點率。因此，建立滿足式（1）－式

   （8）約束條件的、以列車加權晚點總時間最小為目標函數的調整模型。即

    （9）約束條件為：式（1）－式（8）。

    2．模型求解算法原理及步驟

    2.1 算法原理

     列車運行是一個動態過程, 隨著時間的變化，空間也在不斷變化（車站各方向的接車能力、咽喉、股道的占用情況在不斷變化）。因此，對模型采用動態規劃算法[10]求解，將列車運行階段計劃調整分為N個優化階段（k=1,2…N， N ），該N個階段無后向性[10]，且每個階段的狀態無后效性[10]，即第k+1階段的狀態只取決于第k階段的狀態。調整過程中，每趟列車從第 k個階段進入到第 k＋1階段都有不同的決策，依據列車在第k 階段的狀態和最佳階段效益[10]（從第 k個階段到第 k＋1階段的最小晚點時分），選取本階段的最優決策。根據每個優化階段產生的最小晚點時間，式（9）可以轉化為如下基于動態規劃算法的優化模型，即
   
         （10）

     約束條件仍然是式（1）－式（8）。

     式中： 表示第k階段調整后的總晚點時分； M為第1個階段調整后得出的晚點時間； 為第k-1階段列車的調整決策對本階段列車調整的影響； 為第k個階段的狀態變量， 為第k個階段的決策。

     2.2 算法步驟 

     Step1：初始化列車階段運行計劃調整的參數以滿足約束條件（1）－（8）。確定調整范圍的起止時間、調整范圍內的列車數目以及每列車的接入狀態。根據列車運行的時間和空間動態變化，確定調整的優化階段數N。

     Step2：根據上一階段所采取的全部可能決策，確定本階段所采取的可能決策 ，記錄本次列車本階段調整方案，根據約束條件（1）－（8），記錄下 的集合。

     Step3： 根據上一個階段取得的總晚點時間 和本階段所選取的最優決策 ，確定本次列車運行的決策 。

     Step4：根據k是否取到最大值，判斷調整是否完畢。若調整完畢，則選取最后一個階段調整中 最小的方案即列車晚點時間最小，根據此方案確定的到、發時間 鋪畫調整后的列車運行階段計劃；否則， 返回Step2繼續調整。

    3．運行調整實例

    3.1基礎數據

     以天津集中臺天津（臨時）至下直通場間的車站為例，采用上述模型和求解算法進行列車階段計劃調整。包括的車站有天津（臨時）（含臨時客站、天津四號樓）、二號樓（含天津站一樓、天津站四調、天津站三號樓）、天津北、下直通、上到場。臺間站為天津（臨時）、下直通、天津西、漢溝鎮、北倉北、北倉、上到場作為接收鄰臺計劃的接入站。表1為天津集中臺列車在不同線路上規定的運行時分。圖2為天津集中臺接收鄰臺計劃后未調整的運行圖部分截圖。

                                表1 天津集中臺部分線路列車基本運行數據 
                

                 
                           圖2 天津集中臺部分線路調整前的列車運行階段計劃

     3.2 列車階段計劃調整過程與結果

    在列車運行階段計劃調整過程中，首先接收鄰臺傳來的階段計劃，確定7個入口列車的接入時刻，然后根據各個入口列車的正晚點情況以及本臺內始發列車，進行初始化，即 ，調整階段計劃時間范圍為12:00至15:00，經過上述Step1－Step4過程得出調整后的每條運行線的 ，畫出調整后的列車運行圖，即圖3為天津集中臺階段計劃調整后的運行圖部分截圖。

    圖2和圖3中藍色圓圈中的數字表示列車的晚點時分。兩圖比較，調整效果顯而易見。圖3中交出車站的晚點時分即藍色圓圈大大減少，達到列車運行階段計劃調整的目的，驗證了動態規化算法在列車運行階段計劃調整中的可行性。
 
                  
                           圖3：天津集中臺部分線路調整后的列車運行階段計劃

     4．結束語

     列車運行階段計劃自動調整是列車調度指揮系統減少列車調度員工作強度的關鍵之一。本文在詳細分析影響列車運行限制條件的基礎上，提出用動態優化算法來求解列車優化模型，保證了系統的實時性；同時，避免了影響列車運行的離散事件在動態優化過程中眾多事件尋找最小事件的計算量，能夠快速的給出列車調整方案。此種方法在北京鐵路局天津集中臺得到了比較滿意的應用。 

     參考文獻

[1] 鐵道科學研究院通信信號研究所．鐵路運輸調度指揮信息管理系統說明書(匯編)[z]．北京：鐵道科學研究院通信信號研究所,2002。

[2] 傅京孫，蔡自興，徐光右．人工智能及其應用[M]．北京：清華大學出版社,1995。

[3] 張京波，胡思繼。列車運行調整模型的研究[J]．鐵路計算機應用,2001，10（7）：9-12。
（ZHANG Jingbo, Hu Siji，Research of Mathematical Model for Train Dispatching and Disposal[J]． Railway Computer Application, 2001，10（7）：9—12。in Chinese）

[4] 王宏剛,張 琦,王建英,等。 基于遺傳算法的高速鐵路行車調整模型[J]。中國鐵道科學,2006,27（3）：97—100
(WANG Honggang, ZHANG Qi, WANG Jianying,et al. GA-Based Model of Train Operation Adjustment for High-Speed Railway[J]. China Railway Science, 2006,27（3）：97-100 in Chinese)

[5] 周磊山，秦作睿。列車運行計劃與調整的通用算法及其計算機實現，鐵道學報，1994，16（3）：56-65
(ZHOU Leishan，QIN Zuorui. General Algorithm and Its Realization on Computer for the Train Operation Adjustment System[J]．Journal of the China Railway Society, 1994，16（3）：56－65 in Chinese)

[6] 彭其淵，楊名倫，倪少權。單線使用貨物列車運行圖計算機編制系統[J]。西南交通大學學報,1995，30（5）：536-542。
(PENG Qiyuan, YANG Mingquan, NI Shaoquan. A System of Making Train Working Graph on Single-Track Lines with Computer [J]. Journal of the Southwest Jiaotong University,1995,30（5）：536－542。in Chinese）

[7] 北京鐵路局．2007年列車運行圖技術資料[Z]。北京：北京鐵路局，2007．

[8] 中華人民共和國鐵道部。中華人民共和國鐵道部鐵道運輸調度規則[Z]。北京：中國鐵道出版社,2007．

[9] 劉 雋，張銘娣，張一軍。TDCS系統列車運行階段計劃的處理方法。中國鐵道科學，2006，27（4）：97-100。
(LIU Jun, ZHANG Mingdi, ZHANG Yijun. Train Execution Plan Processing Algorithms in TDCS [J]. China Railway Science, 2006,27（4）：97-100 in Chinese)

[10] 陳理榮.數學建模導論[M]。北京：北京郵電大學出版社，1998。