列車運行調整問題研究綜述

陳 東，李永輝，張儀彬

（1.西南交通大學峨眉校區 交通運輸系，四川 峨眉 614202；2.西南交通大學峨眉校區計算機與通信工程系，四川 峨眉 614202）

列車運行調整問題研究綜述

陳 東1，李永輝2，張儀彬1

（1.西南交通大學峨眉校區 交通運輸系，四川 峨眉 614202；2.西南交通大學峨眉校區計算機與通信工程系，四川 峨眉 614202）

列車運行調整是鐵路行車組織研究的重點，在研究方法和內容上都有較為豐碩的成果。在分析諸多列車運行調整研究內容的基礎上，歸納闡述了列車運行調整目標、調整措施和調整研究對象，通過分類比較各種列車運行調整研究方法，從研究手段的選擇、計算機仿真的應用和今后的研究方向等方面進行研究展望，提出加強研究手段、拓展研究內容，探索新的優化算法，并將技術站車流接續作為運行調整的約束和目標等是值得研究的方向。

鐵路；列車運行調整；車流組織；專家系統

列車在運行過程中會受到諸如不良天氣、接觸網故障、旅客上車延誤、技術站始發晚點等因素的影響，使其偏離圖定列車運行線。列車運行調整是在遇到上述情況時，通過運用合理的調整策略，使列車進入新的有序狀態的過程。列車運行調整問題是實現列車調度指揮系統智能化、自動化的核心和基礎。由于列車運行調整需考慮的因素眾多、各種組合方案的規模龐大，求解算法的實現難度和求解效率等，決定了這類研究成果的實用化程度。

1 列車運行調整研究概述

1973年，B?Szpigel 首次提出“最優列車調度”問題[1]，開始了列車運行調整問題的研究。Sauder 于 1983年提出了一個優化的列車調度模型，并開發出用于單線鐵路的全局優化方法。歐美、日本鐵路多采用規劃型的運輸組織模式，對列車運行的準點性要求更高，在列車運行調整方面有豐富的研究成果。其成果在注重算法優化的同時，更重視專家系統、仿真等研究手段的運用。日本新干線列車運行管理系統(COSMOS)、歐洲鐵路運輸管理系統(ERTMS)和北美高級列車控制系統(ATCS)等是這一領域較為優秀的研究成果，為列車運行管理和調整提供了良好的平臺與手段，也推動了該領域研究的進一步深化。

《日本新干線上的列車運行調整》(謝文炳，1979)系統地介紹了日本新干線鐵路的運行調整方法及效果，對國內列車運行調整的研究起到了良好的促進作用。《用計算機編制列車運行調整計劃的研究》(程宇，1988)對列車運行調整進行了比較系統的研究。進入 20 世紀 90年代，列車運行調整的研究受到諸多學者的重視。由于在基礎理論和研究手段方面，列車運行調整和運行圖的計算機編制存在很多共同點，很多研究手段、算法和研究成果都是通用的，因此這一時期的研究成果極為豐富，研究手段呈現多樣化，數學規劃、離散事件動態建模、人工智能等在這些成果中得到了很好的應用。近年來，隨著城市軌道交通、高速鐵路等軌道運輸方式的快速發展，研究對象也進一步擴展。理論研究促進了實作系統的開發，其成果已初步應用于鐵路運輸調度指揮系統，極大地提高了我國鐵路調度指揮生產效率。

2 列車運行調整研究

2.1 列車運行調整目標

列車運行調整用于糾正因各種原因使列車偏離運行計劃的行為，因此列車運行調整的總目標是恢復列車預定運行計劃。基于這一原則，運行調整目標可以表述為總晚點列車數最少、總晚點時間最少、加權總晚點時間最少等。尤其是基于不同的運行調整對象，有的研究提出了分類調整目標。例如，結合城市軌道交通客運服務的特點，吳洋提出城際列車的運行調整目標是盡快恢復列車運行計劃或均衡列車的發車間隔，而不是簡單地恢復運行計劃[2]，這一目標有利于客運站的工作組織，相關研究成果對于城市軌道交通的列車調度調整有一定的借鑒意義。

2.2 列車運行調整措施

列車運行調整措施是指當列車運行發生偏差后，為恢復列車運行計劃所采取的措施。其主要包括變更列車到發時刻、變更列車到發順序、改變列車車站行車方式、變更列車標準運行時間、增開列車、取消列車、壓縮車站作業時間、組織高速列車利用渡線在區間越行中速列車等。這些措施在既有普速鐵路的列車運行調整中應用非常廣泛。對于高速鐵路和城市軌道交通，列車運行調整的措施還有運用備用動車組、運用其他站空閑動車組、變更列車接續時間，以及中速列車下線運行、變更動車組交路和反向行車等[3]。不同的措施實施難度差別很大，對后續列車運行的影響也各不相同。

2.3 列車運行調整研究對象

根據研究對象的不同，可將列車運行調整分為既有普速鐵路、高速鐵路(客運專線)和城市軌道交通線路 3 類。基于各類軌道交通的不同運輸特點對研究對象進行分類，提高了研究的針對性，降低了研究難度，這一分類方法也被多數研究者采納。

既有普速鐵路分為單線和雙線，采用客貨共線的運輸組織模式。由于貨物列車與旅客列車的等級差別明顯，在列車運行調整時可以賦予這兩類列車不同的權限，通過犧牲貨物列車的運行效率而獲得旅客列車運行計劃的優先恢復，這是日常調度指揮中經常采用的組織措施。單線和雙線鐵路在調整目標、調整措施等方面基本相同。不同的是，單線鐵路因某一時間范圍內只能有一列車占用某一閉塞區間，對向列車間的交會和同向列車的越行等作業只能在車站進行，列車運行調整問題需要考慮因素更多、約束條件更復雜，具有很強的優化必要性，是近年來研究的熱點[4-8]。

高速鐵路(客運專線)在閉塞方式、列車種類、天窗設置、運行調整目標及調整措施等方面與既有普速鐵路存在較大的不同，研究的重點也不同。隨著我國高速鐵路的快速發展，與高速列車運行調整相關的研究，包括調度系統的建設和運行圖的計算機鋪畫，成為近年來的研究熱點。

城市軌道交通在閉塞方式、列車種類、列車運行調整目標等方面不同于其他軌道交通。隨著城市軌道交通的快速發展，以城市軌道交通為背景的研究近年來也十分豐富。

3 列車運行調整研究方法的分類比較

3.1 基于規劃方法的列車運行調整研究

列車運行調整問題具有涉及變量多、組合數量大等特點，是完全的NP 問題。數學規劃方法因其表達清晰、模型成熟，被眾多研究者所青睞。例如，建立描述網絡線路列車運行圖的通用化模型，并提出時空局域滾動算法完成列車運行圖的求解[9-11]；建立運行調整問題的數學規劃模型，利用專業知識對模型進一步簡化，并在此基礎上提出遺傳算法、協調優化算法、分枝定界等方法對模型進行求解[4-7，12]。從這些研究成果可知，由于解的空間巨大，常規解法很難得到全局最優解，運用專業知識對模型進行合理簡化，縮小解的空間及尋找可行的求解算法成為這類研究方法的重點。經過多年的研究，所建立的模型已經相對成熟。目前，各類研究更傾向于尋找更為高效、合理的算法[7，12-13]，計算復雜度和實時性成為衡量這類研究方法的一個重要指標。

3.2 基于專家系統的列車運行調整研究

專家系統具有直觀、能較好地利用經驗性知識等特點，也是經常采用的研究手段。日本新干線列車運行管理系統(COSMOS)、歐洲鐵路運輸管理系統(ERTMS)和北美高級列車控制系統(ATCS)等專家系統的建立，為列車運行管理和調整提供了良好的平臺與手段。隨著研究的進一步深入，相關成果也不斷涌現[14-17]。在我國，程宇等提出了用于編制雙線自動閉塞區段列車運行調整計劃的專家系統[18-19]，張莉艷等提出了基于移動閉塞條件下的列車運行調整專家系統[20]。但該類系統的知識庫、方法庫、模型庫在建立時缺乏統一性描述，其算法的優劣取決于算法設計者的計算機表達水平。基于不同平臺的專家系統通用性差，難以借鑒、拓展，成為制約其發展的瓶頸。

3.3 基于離散事件動態建模的列車運行調整研究

列車運行調整的實質是處理列車與車站、列車與區間，以及列車之間的關系，規定列車占有區間和站線的合理時機。如果將列車占用區間與車站看成事件，那么由列車、區間、車站、信聯閉設備，以及區段內各種技術設備組成的列車運行系統是一個離散事件動態系統[21]。周磊山建立了離散事件動態系統驅動的狀態空間調整模型，提出了網絡分層并行算法(NHPA)[22]。該模型算法和求解思路都有較強的優勢，兼顧了事件順序設定法和列車順序設定法的優點，并以此為思路建立了“計算機編制列車運行圖系統”運用于哈爾濱鐵路局。周磊山教授及其研究團隊運用該研究方法在運行圖鋪畫、列車運行調整、運行圖與動車組運用一體優化方面取得了一系列的研究成果。章優仕在后續文獻中運用離散事件的拓撲圖模型對單線列車的運行調整進行研究，建立了單線列車運行圖的離散事件拓撲圖模型，并在此基礎上提出了單線列車運行調整的迭代修復算法[8，13]。該算法具有良好的實時性，較好地拓展了離散事件動態系統的研究手段。

3.4 其他智能研究方法

除上述規劃方法、專家系統、離散事件動態建模等方法外，粗糙集、智能體(Agent)、計算機仿真等方法在列車運行調整中的研究也相當活躍。

粗糙集理論(Rough Set)作為智能信息處理技術的新成果，是由波蘭科學家 Z.Pawlak 教授提出來的對不完整數據進行分析、推理、學習、發現的新方法，在許多科學領域和工程領域得到成功應用。黃康和陳東等提出了采用粗糙集方法構造列車運行調整系統，給出了模型結構和知識獲取規則、自學習的粗糙規則提取算法和列車運行調整算法[23-24]。該研究手段能通過對以往調度規則的分析，通過知識約簡，得到列車運行在不同情況下的調整策略，供調度人員參考。該研究手段強調調度人員的知識及其行之有效的經驗性策略在列車運行調整中的作用，并具有很好的實時性。

Agent 是一個具有控制問題求解機理的計算單元，其特點是具有自治性、交互性、反應性和預動性。利用這一特性，實現列車運行調整方案的自動生成及調整，改變以往以人為主體的調度指揮方式，實現智能調度系統和人員共同工作的人機互控模式。多智能體系統(Multi-Agent System，MAS)是由多個可互相交互的稱為Agent的計算單元組成的系統，具有很強的分布式特性，可用于構建列車運行調度指揮系統。賈傳峻等結合已有技術，提出了依托列車調度指揮系統建立多智能體調度集中系統的方案[25]。路飛建立了基于多Agent的地鐵列車運行調整系統[26]。 王宏剛建立了基于Agent的客運專線綜合運營管理調度系統[27]。這些研究對于Agent 在鐵路運輸中的應用進行了有效的嘗試，并取得了一定的研究成果。Agent 中對于調度指揮規則的簡潔、正確的描述和知識表達的通用性，成為Agent 應用中的關鍵。Agent在分析復雜的社會經濟活動中取得了很豐富的研究成果，對列車運行調整這一復雜的組合優化問題，也有良好的應用前景。

嚴格地說，計算機仿真不能單獨列為一類研究方法，因為上述的離散事件動態建模、MAS 等研究手段也涉及計算機仿真，其研究成果相當豐富。Pascal Rebreyend 介紹了一個專門用于列車調度和調整的軟件 DisTrain，能較快地校驗各種調整方法的調整效果，具有較強的實用性[28]。有關研究也介紹了仿真方法在運行調整中的應用[8，15，20-21]。列車運行過程隨機性特點明顯，采用仿真的方法推演其運行及調整過程，并基于其研究成果建立實用系統，是一個非常有發展潛力的研究手段。

4 研究展望

經過多年的研究，在眾多學者的努力下，列車運行調整研究取得了豐碩的成果。隨著鐵路網規模的擴大，隨著普速鐵路、高速鐵路、城市軌道交通等的快速發展，列車運行調整目標、約束條件也在不斷發展。同時，隨著計算機軟硬件技術的提高、新的優化算法的提出，使得局限于計算能力的一些問題的解決成為可能。可以認為，今后列車運行調整仍然是研究的熱點。

（1）研究手段的選擇。數學規劃的方法雖然表達清晰，但求解困難，實時性較差，探索更加高效、優化的算法是這類研究手段的主要方向。專家系統和人工智能類算法因能充分借鑒專業知識，縮小解的空間，并能充分借鑒經驗性知識，在這類問題的求解上有一定優勢。這類方法在實際運用時仍存在一些缺點，如過程性知識表述困難、模型庫和方法庫的通用性差等，這些缺點的克服將促進這類研究方法的發展。

（2）計算機仿真的應用。計算機仿真能較直觀地演示各種調整措施的執行情況，并對其實施效果進行評價，是一種非常好的研究手段。國外在交通運輸領域非常重視仿真，并開發了很多實作或驗證仿真平臺，國內相關研究則有待進一步深入。

（3）今后的研究方向。對于列車運行調整，綜合諸因素的一體優化是下一步的研究方向。鐵路運輸是一個大的聯動系統，涉及專業和其他因素眾多，僅列車運行調整就涉及機車(動車組)、車輛、供電、車流接續等眾多因素。在現有研究中，已有針對機車(動車組)、車底和運行計劃的一體優化。但是，針對列車運行調整和車流接續一體優化的研究則較少。由于鐵路運輸組織的復雜性，在實際運輸生產中，為降低指揮難度，將聯系緊密的車流組織和列車運行組織分割成兩部分，大運轉列車的車流組織工作交給技術站完成，調度所除調整路網列車運行之外，還管理區段內的摘掛車流在中間站的組織工作。列車的到發時間和編組內容是這兩項工作的接口，這一分割有效地解決了鐵路調度指揮系統智能化程度不高和計算能力不足條件下的列車運行調度指揮問題。縱觀全局，車流組織雖然是車站的主要工作，但其生成的列流是組成運行線的源；反之，運行線如不能與車流組織很好的配合，則待發列車等待時間增大，車小時增加。因此，在列車運行調整中，將技術站的車流接續納入其中進行考慮，兼顧點、線運輸組織情況，將技術站的車流接續作為列車運行調整的約束和目標，達到滿意的“中時、停時、旅速、周時”等運輸指標，是值得研究的方向。

：

[1] B Szpigel. Optimal Train Scheduling on A Single Line Railway[J]. Operations Research，1973，7(2)：344-351.

[2] 吳 洋，羅 霞. 一種晚點地鐵列車實施調整策略及其動態速控模式[J]. 中國鐵道科學，2005，26(6)：113-118.

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

[4] 曹家明. 單線鐵路列車運行調整優化模型及算法[J]. 鐵道學報，1994，16(3)：72-78.

[5] 趙 強. 單線鐵路列車運行調整優化模型與算法研究[J]. 系統工程，1999，17(6)：12-18.

[6] 史 峰，黎新華，秦 進，等. 單線列車運行調整的最早沖突優化方法[J]. 中國鐵道科學，2005，26(1)：107-113.

[7] 章優仕，金煒東. 基于遺傳算法的單線列車運行調整體系[J]. 西南交通大學學報，2005，40(2)：147-152.

[8] 章優仕，金煒東. 單線列車運行調整的梯度搜索算法仿真研究[J]. 系統仿真學報，2010，22(11)：2496-2501.

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

[10] 彭其淵，朱松年，王 培. 網絡列車運行圖的數學模型及算法研究[J]. 鐵道學報，2001，23(1)：1-8.

[11] 彭其淵，王寶杰，周黨瑞. 基于實用的一種網絡列車運行圖計算方法[J]. 西南交通大學學報，1999，34(5)：588-593.

[12] 羅 晴，金福才，胡思繼. 列車運行調整問題的分解協調計算模型[J]. 北京交通大學學報，2004，28(6)：87-94.

[13] 章優仕，金煒東. 基于離散事件拓撲圖模型的單線列車運行調整迭代修復算法[J]. 系統仿真學報，2009，21(21)：7003-7007.

[14] C S Chang，B S Thia. Online Rescheduling of Mass Rapid Transit Systems：Fuzzy Expert System Approach[J]. Electric Power Applications，IEEE Proceedings，143(4)：307-316.

[15] Kiyotoshi Komaya. A New Simulation Method and Its Application to Knowledge-based Systems for Railway Scheduling[C]//Institute of Electrical and Electronics Engineers/American Society of Mechanical Engineers.Proceedings of 1991 IEEE/ASME Joint 1991 Railroad Conference. St Louis：Institute of Electrical and Electronics Engineers/American Society of Mechanical Engineers，1991：59-66.

[16] Hellstom P. An Evaluation of Algorithms and Systems for Computer Aided Train Dispatching[J]. Computer in Railway，1998，1998(7)：585-595.

[17] Lu Fei，Song Mumin，Tian Guohui，et al. The Integrated Intelligent Control Framework of Subway Train Based-on Multi-agent[C]//Proceedings of the 26th Chinese Control Conference. Zhangjiajie：Institute of Electrical and Electronics Engineers，2007：395-398.

[18] 程 宇. 列車運行調整專家系統的探討[J]. 北方交通大學學報，1989，13(4)：115-123.

[19] 程 宇，秦作睿. 列車運行調整專家系統的研究[J]. 鐵道學報，1992，14(2)：43-51.

[20] 張莉艷，李 平，賈利民，等. 在移動閉塞條件下列車運行調整的仿真研究[J]. 系統仿真學報，2004，16(10)：2257-2263.

[21] 王起龍，張宏勛. 對分層滾動列車運行調整算法的部分改進[J]. 鐵道學報，1996，18(增)：42-45.

[22] 周磊山，秦作睿. 列車運行計劃與調整的通用算法及其計算機實現[J]. 鐵道學報，1994，16(3)：56-65.

[23] 黃 康. 基于粗糙集理論的行車指揮知識獲取與決策的應用研究[D]. 北京：中國鐵道科學研究院，2003.

[24] 陳 東，李永輝，張強鋒，等. 基于粗糙集理論的列車運行調整方法研究[J]. 中國鐵路，2009(7)：44-46.

[25] 賈傳峻，胡思繼，楊宇棟. 基于多智能體的鐵路雙線調度指揮系統[J]. 北京交通大學學報，2005，29(6)：13-17.

[26] 路 飛. 移動閉塞條件下的地鐵列車的運行優化[D]. 濟南：山東大學，2007.

[27] 王宏剛. 客運專線綜合運營調度系統 Agent 結構和規則描述[J]. 交通運輸工程學報，2008，8(6)：93-98.

[28] Pascal Rebreyend. DisTrain：A Simulation Tool for Train Dispatching[C]//Proceeding of The 8th International IEEE Conference on Intelligent Transportation Systems. Vienna：Institute of Electrical and Electronics Engineers，2005：801-806.

Study on Problems of Train Operation Adjustment

CHEN Dong1,LI Yong-hui2,ZHANG Yi-bin1

(1. Traffic and Transportation Department,Ermei School of Southwest Jiaotong University,Ermei 614202,Sichuan,China; 2. Computer and Communication Engineering Department,Ermei School of Southwest Jiaotong University,Ermei 614202,Sichuan,China)

Train operation adjustment is the key of railway running organization and has plentiful achievements on study method and content. Based on analyzing study contents of many train operation adjustment,this paper expounds the train operation adjustment target,adjustment measures and adjustment study object. Through classifying and comparing each study method of train operation adjustment,the paper makes prospection through aspects of selection of study approach,utilization of computer simulation and further study orientation,puts forward many valuable study orientations such as strengthening study approach,developing study content,exploring new optimization algorithm and taking vehicle flow connection in technical stations as restriction and target of operation adjustment.

Railway; Train Operation Adjustment; Vehicle Flow Organization; Expert System

1003-1421(2012)12-0026-05

U292.4

B

2012-09-20

中央高校科研業務專項經費創新基金(SWJTU 2011CX002EM)；教育部春暉計劃(Z2011117)

王學智