蟻群算法在城軌列車運行調整中的應用

王婧婧

(西南交通大學 信息科學與技術學院，成都 611756)

蟻群算法在城軌列車運行調整中的應用

王婧婧

(西南交通大學 信息科學與技術學院，成都 611756)

當城市軌道交通列車在行車過程中由于設備故障、乘客擁擠等情況發生晚點時，需要對列車時刻表進行調整，使之盡快恢復正點運行。本文以調整區段內總晚點時間最小為目標函數，提出了基于蟻群優化算法的列車調整模型，在Visual C++ 6.0編程環境下，以深圳地鐵6號線為例，對模型的實用性進行了驗證。

列車運行調整；蟻群算法；模型

城市軌道交通由于列車追蹤間隔短、人流量大等因素，列車發生晚點情況無法避免。如果晚點列車沒有及時調整，前行列車的出站晚點很有可能會造成后行列車的緊隨晚點，從而導致局部列車運行秩序紊亂，無法保障區間運行效率。為了保障行車安全和提高運行效率，需要對晚點列車進行實時調整，以便盡快恢復正常運行秩序，保證列車可以按計劃運行。

自從1973年B.Szpigel提出“最優列車調度”問題以來，開始了列車運行調整問題的研究[1]。許多專家學者將運籌學、專家系統、模糊決策、遺傳算法、模糊神經網絡等方法先后用于列車運行調整研究，并取得了相當有價值的研究成果[2～6]。這些調整方法與策略推動了該問題的研究進展，但仍存在一些問題。比如基于運籌學優化理論的調整算法實時性較差，常規解法很難求得全局最優解；基于專家系統的列車調整策略和算法只追求滿意和有效，在一定程度上達不到目標函數最優；基于模糊決策的調整方法對于優先級的定義需要憑經驗確定模型參數；遺傳算法在搜索大規模組合優化問題解空間方面存在過早收斂以及參數優化等問題。

鑒于上述原因，本文建立了列車調整模型，并采用蟻群算法進行求解。由于蟻群算法是一種基于種群尋優的啟發式搜索算法，通過螞蟻個體間釋放的信息素的堆積來尋找最短路徑，具有自組織性、正反饋、分布式計算等特點[7]，符合列車運行調整模型對求解算法的要求，因此本文采用蟻群算法對時刻表數據進行尋優，并取得了較好的效果。

1 列車運行調整模型

1.1 城市軌道交通列車運行特點

城市軌道交通運營范圍一般為幾十千米，往返時間一般在2 h左右；站間距離較短，列車追蹤間隔短，采用CBTC系統的線路安全行車間隔理論上可以達到90 s；客流量較大，在早晚高峰或者節假日期間尤其明顯；運行速度一般最高為80 km/h，有些線路可以達到100 km/h甚至是120 km/h。列車運行圖是運用坐標原理對列車運行時間和空間關系的圖解表示，進行列車運行調整實際上是調整各車在各站的到發時刻從而解決列車與列車在車站和區間因晚點而發生的沖突關系，因此需要考慮最小區間運行時間、最小站停時間、最小追蹤間隔等約束條件。

1.2 模型的構建

設某條運行線調整區段有M個車站，編號為{0，1，……，i，……，M-1}；N列同是上行或下行方向的列車，編號為{0，1，……，k，……，N-1}；調整區段內所有列車均為同一速度等級，不存在越行情況。

定義：變量XDi,k—列車k在車站i的實際到達時刻；—列車k在車站i的計劃到達時刻；XFi,k—列車k在車站i的實際出發時刻；—列車k在車站i的計劃出發時刻；Tsi—列車在車站i的最小停站時間；Tri—列車在相鄰車站i與i+1之間運行的最小區間運行時間；Td—兩追蹤列車的最小追蹤間隔。

1.2.1 目標函數

本文以調整后運行圖與計劃運行圖相比，總到發晚點時間最小為目標函數，式為：

1.2.2 約束條件

列車運行調整受到區間運行時間、停站時間、相鄰列車追蹤間隔以及出發時間的約束，這些約束條件具體如下：

（1）最小停站時間約束。列車在車站的停站時間由開門時間、乘客上下客時間和關門時間3部分組成。其中，乘客上下客時間根據各設計年度車站的高峰小時預測客流量計算確定。列車在車站i的停站時間約束，式為：

（2）最小區間運行時間約束。任意列車k在相鄰兩個車站i，i+1的運行時間受到其最小區間運行時間約束，式為：

（3）列車追蹤間隔約束。為保障同向列車的安全運行，兩輛追蹤列車需要滿足追蹤間隔約束，式為：

（4）出發時間約束。為保證列車按圖行駛，實際列車出發時間不能小于列車計劃出發時間，即列車不能提前發車，出發時間約束，式為：

2 列車運行調整算法

2.1 蟻群算法概述

1991年，M.Dorigo等人首次提出了蟻群優化算法。螞蟻在覓食時，總能找到蟻穴與食物源之間的最短路徑。研究表明，螞蟻之間是通過一種遺留在其來往路徑上的分泌物來進行通信和協調的，螞蟻產生的分泌物稱為信息素，是一種揮發性化學物質。路徑上的信息素越多，螞蟻選擇該路徑的可能性越大，形成了正反饋現象，使得蟻群逐漸聚集到最短的那條路徑上來。

蟻群算法是通過模擬真實蟻群在覓食路徑上釋放信息素最終可以在蟻穴和食物源之間找到最短路徑這一特征工作的。算法可以通過螞蟻尋找食物時候的信息素原理，不斷去修正原來的路線，使整個路線越來越短，即隨著迭代次數的增加，所獲得的路徑就越接近最優路徑。

2.2 蟻群優化算法的設計

本文在Visual C++ 6.0平臺下編程，實現了蟻群算法用于模型的求解，算法流程圖如圖1所示，算法步驟為：

（1）初始化，設置蟻群算法參數；（2）輸入調整區段內編號k=0的列車到達車站i=0的晚點時間，單位為秒；（3）在滿足約束條件的前提下，每只螞蟻并行地構建搜索計劃時刻表上的時間點所對應的調整后時刻表的時間點的路徑，搜索完所有時間點后計算目標函數值，即總晚點時間，檢查每只螞蟻的目標函數值，若目標函數值為負數，則進行調整；（4）更新信息素，比較每只螞蟻所求得的目標函數值，得到其中最小值，作為此次迭代的最優解； （5）判斷此次迭代是否結束，若結束則進行下一次迭代，否則轉至步驟（3）；（6）比較每次迭代的最優解，得到其中最小值，作為算法得到的最終解，即時刻表調整后的總晚點時間；（7）判斷算法是否結束，若是則輸出最優結果，否則轉至步驟（3）。

圖1 算法流程圖

3 仿真實例

本文以深圳地鐵6號線為例進行分析，調整區段為從深圳北站到上屋北站一共是7個站。已知列車追蹤間隔Td=240 s，停站時間和最小區間運行時間如表1所示。

表1 調整區段內最小停站時間和區間運行時間

程序中定義時刻表數據結構如下：

將計劃時刻表數據按照定義的數據結構形式保存在本地，通過文件讀取，并將時刻數據轉換成以秒為單位的整型數據，當輸入首列車晚點時間時，蟻群調整算法搜索晚點后時刻表，并計算目標函數值，即總到發晚點時間。程序中設置螞蟻為20只，迭代次數為50，圖2所示為當首列車晚點20 s時，每次迭代搜索得到的目標函數值以及目標函數值的收斂曲線。收斂曲線的橫坐標為迭代次數，縱坐標為目標函數值，即總到發晚點時間。

圖2 蟻群搜索過程

由圖2可知，當調整區段內首列車到達第1個車站晚點20 s時，搜索得到的最佳總到發晚點時間為122 s；由收斂曲線可知，隨著迭代次數的增加，目標函數值逐漸收斂，最后趨于穩定。

將搜索過程中的最優解所對應的時刻數據保存并讀取，得到調整后的時刻表數據，如圖3所示。

Ant Colony Optimization Algorithm applied to train operation adjustment of Urban Transit

WANG Jingjing
( School of Information Science &Technology,Southwest Jiaotong University,Chengdu 611756,China)

It is necessary to adjust the train timetable and let the train recovery on time as soon as possible when the train of Urban Transit in the process of operation is late due to equipment fault,passengers congestion,etc.Taking the minimum total delay time as the objective function,this article proposed a train adjustment model based on Ant Colony Optimization (ACO) Algorithm.Shenzhen Metro Line 6 was taken as an example to verify the practicality of the model under the Visual C++ 6.0 programming environment.

train operation adjustment;Ant Colony Optimization (ACO) Algorithm;model

U231.92∶TP39

A

1005-8451（2016）07-0001-04

2015-12-18

王婧婧，在讀碩士研究生。