地鐵調度命令列車運行路徑自動生成研究

鄧純凈

（佛山市軌道交通發展有限公司，廣東 佛山 528000）

0 引 言

調度命令是地鐵運營組織的重要憑證，分為口頭和書面調度命令兩種形式?？陬^調度命令主要用于運營生產過程中因特殊原因需要進行臨時或局部運營調整的情況，書面調度命令主要用于對線路24 小時及以上限速或取消限速、施工需要加開工程列車或調試列車、封鎖、開通線路以及其他特殊情況。

地鐵行車調度維修施工中的調度命令一般是以書面命令的形式下發給車輛段信號樓值班員排列列車出廠進路，乘務駕駛列車，車站監控列車運行使用，施工負責人組織現場施工使用，是地鐵行車設備施工的重要因素，也是保障施工工程車或者調試列車安全作業的重要憑證。目前地鐵行業內，施工書面調度命令均是由一名行車調度擬寫，搭檔行車調度進行審核，再發送到值班主任進行審核，審核通過后流轉到擬寫調度命令的行車調度處進行下發執行（詳細業務流程見圖1），全程均是人工根據施工作業需求進行擬寫及審核，再以郵件或者其他形式進行發布。

圖1 施工書面調度命令發布業務流程

1 研究現狀

目前已有學者及研究人員對調度命令的信息化流程進行研究，陳文等通過以北京地鐵1 號線為試點，分析地鐵的調度命令作業流程，抽象核心邏輯，對整個業務過程進行建模，研發了一套面向地鐵的調度命令電子化系統，實現對調度命令的收發管理、調度命令的顯示管理、長期調度命令的管理、調度命令存儲管理和調度命令的打印管理等。西南交通大學廖靜在其碩士論文《面向地鐵的調度命令管理系統》中對目前地鐵調度命令的發布不足進行分析，以“北京地鐵1 號線調度命令管理”項目為依托，設計并開發了面向地鐵的調度命令管理系統，實現書面命令的快速編輯、準確發布、高效查詢和更安全的保存。呼和浩特鐵路局信息技術所劉鹿提出設計鐵路局調度命令系統，從命令流轉、功能設計、開發工具等方面解決傳統鐵路調度方式存在耗時多、難以統計的困難。通過分析目前國內對調度命令信息技術應用研究現狀，發現大部分地鐵公司對調度命令的審核、查詢、發布、管理等流程進行電子化，即用信息化系統代替常規的電子郵件或其他方式，但是還是需要人工對調度命令的內容進行編寫與發布，這樣雖然減少了各項流程的耗時、提高了效率和規范化了管理，但是對于調度命令內容的可靠性和正確性并沒有提高。

由于調度命令內容為人工進行擬寫，存在大量的人工審核工作，以及人的不穩定因素，導致實際運作過程中存在命令內容和施工作業計劃不匹配、列車運行路徑不正確、地點不匹配，或者列車運行車次錯誤等失誤的情況出現，對現場工程車運行或車站運作帶來不安全因素。彭其淵，胡雨欣，魯工圓在《基于預警文本信息的調度命令智能生成模型》文中，通過對鐵路日常和應急調度命令的擬寫過程進行分析，建立了由神經網絡和調度命令修正模塊兩部分組成調度命令智能生成模型，自動生成應急調度命令。受彭其淵等的啟發，研究利用計算機技術，實現地鐵行車調度維修施工調度命令自動生成，根據日常的施工計劃要求，自動生成調度命令，減少人工介入，釋放技術力量，即提高了調度名利的正確性及可靠性，同時將技術力量用于施工組織等方面，保障夜間施工的有序與安全性。

2 難點分析

地鐵行車調度維修施工調度命令分為加開、封鎖以及解封命令，加開書面調度命令是工程車運行、車廠值班員、車站及調度組織列車運行的重要憑證，需要包含工程車所需要配合的作業、出回廠走行路徑、運行憑證、待令地點，具體內容如表1所示。

表1 某地鐵公司加開書面命令內容

利用信息技術實現施工調度命令自動生成時，需要解決兩個方面的難點，一是通過施工作業計劃提取書面調度命令的內容要素，二是解決路徑問題。目前國內地鐵行業有嚴格的施工計劃管理機制，對施工計劃的內容進行系統的規定，包含了請銷點、出廠地點、回廠地點、作業區域以及作業內容等要素，如圖2所示，在自動生成調度命令時將施工計劃中相關要素進行提取即可；對于自動生成命令列車運行路徑生成的難點，目前均是通過人工經驗進行梳理，這一方式比較便捷，但存在路徑局限性，本案例借助于人工智能算法——蟻群算法，對列車運行的最優路徑和有效路徑進行搜索，為調度命令生成提供多重路徑選擇。

圖2 某地鐵施工計劃要素

3 解決方案

3.1 構造點邊矩陣

利用蟻群算法解決調度命令中路徑選擇問題，首先需要對線路圖轉化為“點—邊”圖。轉化原則是每個站點上下行各為一個點，每一條存車線為一個點，出入廠線分別為一個點，相鄰的點以順序為原則進行連接。圖3為某地鐵線路示意圖，其轉換為“點—邊”圖如圖4所示。

圖3 線路示意圖

圖4 點—邊圖

3.2 建立蟻群算法模型

蟻群算法（Ant Algorithm,AA）又稱蟻群優化算法（Ant Colony Optimization,ACO），是由意大利學者M.Dorigo 于1991年模擬螞蟻種群外出覓食行為提出的仿生算法。蟻群優化算法是一種群集智能算法，是模擬螞蟻覓食的原理設計出的。螞蟻在覓食過程中能夠在其經過的路徑上留下一種稱之為信息素的物質，并在覓食過程中能夠感知這種物質的強度，并指導自己行動方向，它們總是朝著該物質強度高的方向移動，因此大量螞蟻組成的集體覓食就表現為一種對信息素的正反饋現象。某條路徑越短，路徑上經過的螞蟻越多，其信息素遺留的也就越多，信息素的濃度也就越高，螞蟻選擇這條路徑的概率也就越高，由此構成的正反饋過程，從而逐漸地逼近最優路徑，找到最優路徑，式（1）—（4）為普通蟻群算法模型。

在本案例中，由于螞蟻的起點是固定的，即出廠線或入場線，而終點是線路上的任何點，所以在螞蟻搜尋食物過程中不需要搜尋所有的點，故本案例中引入有效路徑模型，減少螞蟻搜尋長度，加速迭代，避免螞蟻走太多的回頭路，如圖4中，若需到，雖然螞蟻由→→也能到達，但是在實際運用中永遠不會用到這條路徑，故為無效路徑，具體模型如式（5）：

式中：len（c）——第只螞蟻所走的點的長度；a為螞蟻需要到達的終點；|a-|為螞蟻需要到達的終點與起點的差距；∑為線路終點至與起點的差距。

3.3 算法流程

基于普通蟻群算法的原理分析以及本案例對于有效路徑的特殊，在普通蟻群算法的基礎上增加對有效點數模型的匹配，從而減少在非有效路徑上的計算資源，提高搜尋的有效性，具體算法流程如圖5所示。

圖5 有效路徑蟻群算法求解流程

3.4 仿真實驗

本文采用C#通過對普通蟻群算法和加入有效路徑后的蟻群算法對列車運行路徑進行仿真實驗，圖6為普通蟻群算法，圖7為加入有效路徑后的蟻群算法求解。其中以點到為列，螞蟻數量為20 只，最大迭代數均取20，信息啟發因子=1，距離啟發因子=2，信息蒸發系數=0.5。通過對比發現普通蟻群算法（圖6）在搜索過程中多次出現局部最優解的情況，且在收斂過程中不穩定，迭代至30 代后才收斂；通過對比發現，加入有效路徑后的蟻群算法（圖7）與普通蟻群算法（圖6）最大的優勢在于收斂代數（第17 代），在收斂過程中存在很小的局部收斂情況。

圖6 普通蟻群算法C#仿真結果

圖7 加入有效路徑后的蟻群算法C#仿真結果

由于行車路徑是行車調度組織列車在正線運行的重要因素，故在利用蟻群算法解決路徑問題時除了獲取最小路徑外，還需要將有效路徑搜索出來供調度員選擇。圖6與圖7是分別仿真了兩種算法有效路徑的結果，通過對比發現普通蟻群算法輸出了較多的無效路徑，即“回頭路”，而加入有效路徑模型后，大大減少無效路徑的輸出。

4 結 論

蟻群算法作為解決路徑規劃的常用智能優化算法，在各領域均得到非常普遍的運用。本文通過結合調度員在日常行車組織中的特殊情況，引入有效路徑模型，對普通蟻群算法求解過程進行優化，最后利用C#對兩種算法進行模擬仿真，通過對比發現加入有效路徑后算法的收斂代數較普通算法更快，在搜索路徑時能有效避開無效路徑，最終為調度員的行車組織提供其他有效路徑的選擇，最終解決調度命令自動生成出（回）廠路徑的難點。