基于模擬退火算法的列車自動調整能力研究

楊 展，張 博，龔 萍

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

基于模擬退火算法的列車自動調整能力研究

楊 展，張 博，龔 萍

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

列車自動調整（ATR）系統是ATS系統中十分重要的一個環節，對保障行車效率起到了舉足輕重的作用。本文首先仔細研究了列車調整多目標多約束的特點，再結合經驗性方法對列車調整進行模型建立。然后利用模擬退火算法的收斂于全局最優解的特性對所建模型進行求解，并通過VS2010仿真平臺對結論進行驗證。

列車自動調整；列車調整模型；模擬退火算法；最優解

城市軌道交通列車由于人為因素或者土建線路因素等干擾條件而產生的偏離運行圖計劃時刻表運行會導致列車運輸能力減少，運輸效率下降，總體收益降低，有時甚至會產生嚴重的影響。通過列車自動調整（ATR，AutomaticTrain Regulation）和人工調整的結合可以很大程度地減少發生運行偏離所引起的損失。傳統的人工調整主要應對大面積列車嚴重偏離時刻表的情況，但會根據操作員經驗性知識的不同而產生不同的操作結果，并無統一規范。而列車自動調整通過系統算法與計算機的強大處理能力，在遇到較小范圍內（單車晚點，多車晚點等）的運行偏離等情況能得到較好的調整效果。列車自動調整涉及到很多問題的求解優化，是一個多目標多約束的組合優化NP問題，對其采取的解決方法也多種多樣。模擬退火方法在處理此類問題中可以避免系統過早收斂陷入局部最優解并且在控制冷卻表適度的情況下能以近似概率1收斂于全局最優解。

1 列車調整原理

在運行正常未遇到列車故障或外部干擾的情況下，列車嚴格依據運行圖時刻表運行，但是在實際過程中，難免會因為某些隨機發生的事件導致列車偏離計劃軌跡行車。故而為了保障列車運行的準點，高效，在發生這些不期望的干擾時能在最短的時間之內恢復按計劃圖運行，ATR子模塊會綜合線路參數,列車運行限制以及列車群相互之間的制約關系以發生晚點的時刻向后調整。為了使得調整后的運行圖能逼近計劃圖，需要引入迭代算子將當前時刻的狀態與調整后的狀態進行加權迭代產生新的狀態并用于下一次迭代調整，直到滿足系統的需求為止。把這樣的計算機演算過程稱為預調整，調成完成后會在運行圖上生成一條列車運行指導（預測）軌跡線，ATS依據ATR演算的結果給ATO傳送停站時間信息與區間運行等級信息從而使得后續列車根據預調整的軌跡線運行。式（1）與圖1描述了列車調整過程。

式（1）～（2）中：

G(j)—在j時刻全局的列車晚點狀態；

G (0)—列車未發生晚點時的狀態；

T—由算法決定的狀態轉移算子；

Interfere—最初的晚點偏移量。

圖1 迭代過程原理

2 調整模型建立

2.1 目標函數

在已知列車發生晚點的情況下，一般有2種調整手段來使列車恢復運行圖運行。

（1）停站時間調整：對列車在站內停靠時間（從進站列車速度變為0到出站列車速度＞0）進行調整，但是這里會產生一個客流增加與縮小停站時間的矛盾關系，需要給予充分的考慮。

（2）區間運行時間調整：一般地，計劃區間運行時間會留有一部分的時間冗余，利用這部分的冗余時間對列車進行調整。

針對這兩個環節對目標函數建模是ATR的重中之重。式（3）給出了總目標函數的表達式：

α—權重因子列向量；

β—子目標因子列向量。

2.1.1 列車總晚點時間

在列車偏離計劃后，期望能得到一個能描述全鐵路局晚點程度的量，從而能通過調整這個量對目標函數進行優化，列車總晚點時間描述了一個計劃內所有的晚點時間加權總和。

式（4）～（5）是一種通用的總晚點時間計算模型，假設一條線路上有m個車站，有n組列車在線路上運行，式中p'di,j表示的是第i輛列車在車站j的實際到達時間， pdi,j表示的是第i輛列車在車站j的計劃到達時間，p'fi,j表示的是第i輛列車在車站j的實際出發時間， pfi,j表示的是第i輛列車在車站j的出發時間。由于發生晚點，列車的到站時間將會向后延誤，并且假設客流分部是均勻的，那么在延誤的這段時間內涌入站內的客流量會與正常計劃中的客流發生疊加。當列車到站后，假設上下車客流密度不變的情況下，這時列車屏蔽門開啟到關閉的時間是會隨著客流增加而增加，這與總晚點時間最小是相矛盾的，所以需要加上一個懲罰因子F。F的設計原則是將列車實際停站時間與計劃停站時間偏差進行加權平方，以期望得到的F能盡量地小。

2.1.2 列車總晚點數目

假如把總晚點時間理解成一個連續的晚點描述模型，那么列車總晚點數目則可看作一離散的晚點描述模型，這兩者之間有確切的依賴關系但是又相互獨立，不能僅僅以一項指標作為優化目標函數的依據。

2.1.3 列車正點率

D—當次計劃中所有列車在分別到達所有站點時刻偏離計劃運行圖的總次數；

A—當次計劃內的總到次數。

列車正點率描述了當次計劃中所有列車的實際到達時間與計劃到達時間的匹配程度。這項指標中只統計每列車在每站到達的準晚點，并不考慮出發準晚點的情況。

2.2 約束條件確立

列車自動調整亦存在多約束限制。為方便理解，可以以晚點產生的位置為首節點把需要調整的列車群想象為一個多節點的彈簧阻尼系統。其首節點發生瞬時位移后，后面的節點會受到拉力作用而向前節點靠攏，同時又拉動后節點共同作用，并且在跨過平衡位置靠近前節點時，會受到前節點的排斥力而保持“安全距離”，最終系統在自適應調節下趨于平衡態。這與ATR調整過程非常相似，處于平衡態兩邊的拉力和斥力恰好能描述約束的上下界限制，一般情況下，約束條件為：

3 模擬退火算法求解

3.1 SA原理

模擬退火算法（SA ，Simulated Annealing）成形于20世紀80年代初，是一項隨機啟發式搜索技術。它不同于傳統優化算法的隨機搜索策略，不僅使用了隨機因素還引入物理退火過程的自然機理，能以一定概率接受劣質解，最終使尋解過程能以近似概率1收斂于全局最優解。SA算法的基本思路是從選取的初始解開始，在借助于控制參數t衰減與等溫抽樣時產生的一系列馬爾可夫鏈中,利用一個新解產生機制和接受原則, 重復進行“生成新解—計算新老目標函數差—判斷是否接納新解—接納或放棄新解”，不停地對當前解循環迭代，從而使目標函數趨于最優的執行過程。由于固體退火過程必須緩慢降低溫度, 才可以使固體在每一溫度下都達到熱平衡，最終趨于平衡狀態。因此控制參數t的值必須緩慢衰減，才能確保模擬退火算法最終趨于優化問題的整體最優解。

3.2 SA求解步驟

（1）設置初始溫度t0與馬氏鏈長度，使用狀態產生函數在可行解空間范圍內隨機產生初始解并計算其目標函數值f(x0)，其中，t0應該足夠大以滿足

（2）對當前解引入隨機干擾，產生當前解的領域解并計算其目標函數值f(x')。

（3）按照Metropolis法則接受新解：如果f(x*)＜f(x) ，則接受解x*為當前狀態。否則產生一在[0,1]上服從均勻分布的隨機數p,若式式中T為當前溫度，k是物理學中的玻耳茲曼常數,則接受新解x*為當前狀態，但是對較優解不能直接舍去，而應存儲起來以作為一個后備回歸解。

（4）當抽樣結果趨于穩定或者達到固定的馬爾可夫抽樣次數，轉（5），否則返回（2）。

（5）使用溫度衰減函數t*=λt退火冷卻系統。

（6）當t達到終止溫度或系統滿足某個收斂準則，轉（7），否則轉（2）。

（7）將當前解作為系統最優解輸出。SA流程如圖2所示。

圖2 SA流程圖

3.3 ATR設計

3.3.1 解空間

列車在線路運行過程中，當檢測到列車運行發生偏離的時刻即根據瞬時偏移量生成解空間,解空間的生成是從晚點時刻開始向后計算結合約束條件確定，但僅靠約束條件還是不嚴謹的，因為約束條件全是下界約束，并沒約束上界，這與優化目標相矛盾，所以要在合情合理的情況下壓縮解空間三圍，使得尋解過程帶有一定的方向性，否則可能會產生等值傳播或增強傳播的初解，這對于ATR這樣一個實時系統而言是不利的，因為這樣會加劇全局調整的時間復雜度。

3.3.2 編碼方式

列車在運行過程中基本的時間計量單位是秒，所以每個站點的到發時間“HH:MM:SS”可以編碼為從當天凌晨零點開始到此刻的秒數S。

將當次計劃中所有對應的需要調整的列車依照先后順序按照式（13）的方式進行編碼并排列為列車運行矩陣A：行為車計劃，列為站計劃。

式（14）～（15）中：

k—需要調整的列車數量；

tji—第j輛車在第i站的到發站時刻。

多車晚點可以看作是i個單車晚點的疊加情況，所以這里只討論單車晚點的情形。在當次計劃中，列車的晚點模式分為接車晚點與發車晚點，但無論描述哪一種情況都需要包括本次計劃內以晚點車次為首的后續所有的車次計劃，這是因為列車晚點是一個后效過程，晚點列車的前行列車并不會受到后車晚點的影響。這里面還包括2種情形：（1）線路中間晚點，這種情形只針對本次計劃的上行或下行列車群進行調整，所有需要調整的列車都在本次計劃內；（2）線路終點晚點，這種情況首先會影響到下次計劃的正常出發，在折返冗余時間不足夠抵消晚點帶來的影響時下次發車時間會受到拖延，所以這種情況應該把下次計劃也納入編碼范圍內，編碼長度是第1種情形的2倍。

3.3.3 鄰域解產生函數

新解產生是通過原始解與隨機干擾的疊加再進行約束檢測得到。設ψ方差為1，均值為0的高斯分布矩陣Nk?m，其中每一個元素ξi,j都服從N(0,1)。再對ψ進行定量處理得到ψ*， ψ*中的每個元素表示為定量規則：若則；若則；否則。新解的產生如式（16）所示：

對A*的約束條件進行判定，若滿足條件后則將A*作為新解與舊解執行Metropolis判別準則，否則縮小隨機干擾比例尺，重新生成新解。

4 實例仿真結果

本論文仿真的實例對象選擇的是成都某一運營線路，通過仿真驗證算法可行性。該線路建有17個站，全長18.5 km，全線發車間隔為低峰330 s，列車平均速度設為37 km/h。

（1）晚點參數選擇

列車號：10403；晚點車站：第4站；晚點時間：240 s。

（2）算法控制參數選擇

初始溫度：1 000；降溫系數：0.95；馬氏鏈長度：50。

圖3中，紅色線為計劃圖，藍色線為實跡預測圖，在無運行干擾產生的情況下，藍線覆蓋紅線, 發生晚點后計劃圖與預測圖列車運行軌跡發生偏離，觸發ATR調動偏離時間，算法收斂時間大約2 s，這對于全鐵路局系統的調整來說是可以忽略不計的。通過實驗仿真結果，可以看到在從發生晚點的時刻開始通過算法的迭代逐步尋優后經過7個區間站點的調整，每個站點的總晚點時間依次遞減并最終變為0，使得晚點列車10403恢復到按計劃圖運行的目標，說明算法很好地達到了運行軌跡逼近計劃軌跡的要求。

5 結束語

SA算法在本文的案例中有著很好的擺脫局部最優的性能，但是若出現系統過于復雜或者狀態空間太大的情況，由于模擬退火算法對整個狀態空間的情況了解不大，不便于使搜索范圍進入到最有希望的搜索區域，使得模擬退火算法的計算效率不高。而當今客流量的增大又對城軌列車運行效率提出了更高的要求，在基于算法的列車調整系統中，模型是復雜且多元的，將來在這方面的研究中，算法也應該規避單一，由多種方法相結合，比如將SA的全局尋優性能結合粒子群算法的快速收斂性能，或是結合遺傳算法對模型依賴小的特點等，只有這樣才能獲得魯棒性好并且效能高的處理此類問題的方法。

圖3 仿真效果圖

[1] 張亦南.基于GA的列車自動調整算法在CBTC系統中的應用研究[D]. 北京：北京交通大學， 2008.

[2] 馮玉蓉. 模擬退火算法的研究及其應用[D]. 昆明： 昆明理工大學，2005.

[3] 肖 鵬.城市軌道交通列車自動調整模型算法研究[D].成都： 西南交通大學, 2006.

[4] 張大華. 列車自動調整系統[J]. 地鐵與輕軌，1999（3）.

[5] 朱顥東，鐘 勇. 一種改進的模擬退火算法[J]. 計算機技術與發展， 2009（6）.

[6] 龐 峰. 模擬退火算法的原理及算法在優化問題上的應用[D]. 長春：吉林大學，2006.

責任編輯 徐侃春

Automatic train regulation capability based on Simulated Annealing Algorithm

YANG Zhan, ZHANG Bo, GONG Ping
( School of Information Science & Technology, Southwest Jiaotong University, Chengdu 611756, China )

Automatic Train Regulation System was a very important part in the ATS System. it played an important role to ensure traffc effciency. The paper carefully considered the multi-objective and multi-constraint characteristics of train automatic regulation, combined with empirical methods to set up the model of train regulation. The Simulated Annealing Algorithm was with the feature of converging to global optimal solution. The model was solved by using this feature. The simulation platform VS2010 was used to validate the conclusions.

ATR; train regulation model; Simulated Annealing Algorithm; optimal solution

U284.48∶TP39

A

1005-8451（2015）09-0006-05

2015-01-09

楊 展，在讀碩士研究生；張 博，在讀碩士研究生。