基于模擬退火算法的列車自動調(diào)整能力研究

楊 展，張 博，龔 萍

（西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，成都 611756）

基于模擬退火算法的列車自動調(diào)整能力研究

楊 展，張 博，龔 萍

（西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，成都 611756）

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

列車自動調(diào)整；列車調(diào)整模型；模擬退火算法；最優(yōu)解

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

1 列車調(diào)整原理

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

式（1）～（2）中：

G(j)—在j時(shí)刻全局的列車晚點(diǎn)狀態(tài)；

G (0)—列車未發(fā)生晚點(diǎn)時(shí)的狀態(tài)；

T—由算法決定的狀態(tài)轉(zhuǎn)移算子；

Interfere—最初的晚點(diǎn)偏移量。

圖1 迭代過程原理

2 調(diào)整模型建立

2.1 目標(biāo)函數(shù)

在已知列車發(fā)生晚點(diǎn)的情況下，一般有2種調(diào)整手段來使列車恢復(fù)運(yùn)行圖運(yùn)行。

（1）停站時(shí)間調(diào)整：對列車在站內(nèi)?？繒r(shí)間（從進(jìn)站列車速度變?yōu)?到出站列車速度＞0）進(jìn)行調(diào)整，但是這里會產(chǎn)生一個客流增加與縮小停站時(shí)間的矛盾關(guān)系，需要給予充分的考慮。

（2）區(qū)間運(yùn)行時(shí)間調(diào)整：一般地，計(jì)劃區(qū)間運(yùn)行時(shí)間會留有一部分的時(shí)間冗余，利用這部分的冗余時(shí)間對列車進(jìn)行調(diào)整。

針對這兩個環(huán)節(jié)對目標(biāo)函數(shù)建模是ATR的重中之重。式（3）給出了總目標(biāo)函數(shù)的表達(dá)式：

α—權(quán)重因子列向量；

β—子目標(biāo)因子列向量。

2.1.1 列車總晚點(diǎn)時(shí)間

在列車偏離計(jì)劃后，期望能得到一個能描述全鐵路局晚點(diǎn)程度的量，從而能通過調(diào)整這個量對目標(biāo)函數(shù)進(jìn)行優(yōu)化，列車總晚點(diǎn)時(shí)間描述了一個計(jì)劃內(nèi)所有的晚點(diǎn)時(shí)間加權(quán)總和。

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

2.1.2 列車總晚點(diǎn)數(shù)目

假如把總晚點(diǎn)時(shí)間理解成一個連續(xù)的晚點(diǎn)描述模型，那么列車總晚點(diǎn)數(shù)目則可看作一離散的晚點(diǎn)描述模型，這兩者之間有確切的依賴關(guān)系但是又相互獨(dú)立，不能僅僅以一項(xiàng)指標(biāo)作為優(yōu)化目標(biāo)函數(shù)的依據(jù)。

2.1.3 列車正點(diǎn)率

D—當(dāng)次計(jì)劃中所有列車在分別到達(dá)所有站點(diǎn)時(shí)刻偏離計(jì)劃運(yùn)行圖的總次數(shù)；

A—當(dāng)次計(jì)劃內(nèi)的總到次數(shù)。

列車正點(diǎn)率描述了當(dāng)次計(jì)劃中所有列車的實(shí)際到達(dá)時(shí)間與計(jì)劃到達(dá)時(shí)間的匹配程度。這項(xiàng)指標(biāo)中只統(tǒng)計(jì)每列車在每站到達(dá)的準(zhǔn)晚點(diǎn)，并不考慮出發(fā)準(zhǔn)晚點(diǎn)的情況。

2.2 約束條件確立

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

3 模擬退火算法求解

3.1 SA原理

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

3.2 SA求解步驟

（1）設(shè)置初始溫度t0與馬氏鏈長度，使用狀態(tài)產(chǎn)生函數(shù)在可行解空間范圍內(nèi)隨機(jī)產(chǎn)生初始解并計(jì)算其目標(biāo)函數(shù)值f(x0)，其中，t0應(yīng)該足夠大以滿足

（2）對當(dāng)前解引入隨機(jī)干擾，產(chǎn)生當(dāng)前解的領(lǐng)域解并計(jì)算其目標(biāo)函數(shù)值f(x')。

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

（4）當(dāng)抽樣結(jié)果趨于穩(wěn)定或者達(dá)到固定的馬爾可夫抽樣次數(shù)，轉(zhuǎn)（5），否則返回（2）。

（5）使用溫度衰減函數(shù)t*=λt退火冷卻系統(tǒng)。

（6）當(dāng)t達(dá)到終止溫度或系統(tǒng)滿足某個收斂準(zhǔn)則，轉(zhuǎn)（7），否則轉(zhuǎn)（2）。

（7）將當(dāng)前解作為系統(tǒng)最優(yōu)解輸出。SA流程如圖2所示。

圖2 SA流程圖

3.3 ATR設(shè)計(jì)

3.3.1 解空間

列車在線路運(yùn)行過程中，當(dāng)檢測到列車運(yùn)行發(fā)生偏離的時(shí)刻即根據(jù)瞬時(shí)偏移量生成解空間,解空間的生成是從晚點(diǎn)時(shí)刻開始向后計(jì)算結(jié)合約束條件確定，但僅靠約束條件還是不嚴(yán)謹(jǐn)?shù)模驗(yàn)榧s束條件全是下界約束，并沒約束上界，這與優(yōu)化目標(biāo)相矛盾，所以要在合情合理的情況下壓縮解空間三圍，使得尋解過程帶有一定的方向性，否則可能會產(chǎn)生等值傳播或增強(qiáng)傳播的初解，這對于ATR這樣一個實(shí)時(shí)系統(tǒng)而言是不利的，因?yàn)檫@樣會加劇全局調(diào)整的時(shí)間復(fù)雜度。

3.3.2 編碼方式

列車在運(yùn)行過程中基本的時(shí)間計(jì)量單位是秒，所以每個站點(diǎn)的到發(fā)時(shí)間“HH:MM:SS”可以編碼為從當(dāng)天凌晨零點(diǎn)開始到此刻的秒數(shù)S。

將當(dāng)次計(jì)劃中所有對應(yīng)的需要調(diào)整的列車依照先后順序按照式（13）的方式進(jìn)行編碼并排列為列車運(yùn)行矩陣A：行為車計(jì)劃，列為站計(jì)劃。

式（14）～（15）中：

k—需要調(diào)整的列車數(shù)量；

tji—第j輛車在第i站的到發(fā)站時(shí)刻。

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

3.3.3 鄰域解產(chǎn)生函數(shù)

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

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

4 實(shí)例仿真結(jié)果

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

（1）晚點(diǎn)參數(shù)選擇

列車號：10403；晚點(diǎn)車站：第4站；晚點(diǎn)時(shí)間：240 s。

（2）算法控制參數(shù)選擇

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

圖3中，紅色線為計(jì)劃圖，藍(lán)色線為實(shí)跡預(yù)測圖，在無運(yùn)行干擾產(chǎn)生的情況下，藍(lán)線覆蓋紅線, 發(fā)生晚點(diǎn)后計(jì)劃圖與預(yù)測圖列車運(yùn)行軌跡發(fā)生偏離，觸發(fā)ATR調(diào)動偏離時(shí)間，算法收斂時(shí)間大約2 s，這對于全鐵路局系統(tǒng)的調(diào)整來說是可以忽略不計(jì)的。通過實(shí)驗(yàn)仿真結(jié)果，可以看到在從發(fā)生晚點(diǎn)的時(shí)刻開始通過算法的迭代逐步尋優(yōu)后經(jīng)過7個區(qū)間站點(diǎn)的調(diào)整，每個站點(diǎn)的總晚點(diǎn)時(shí)間依次遞減并最終變?yōu)?，使得晚點(diǎn)列車10403恢復(fù)到按計(jì)劃圖運(yùn)行的目標(biāo)，說明算法很好地達(dá)到了運(yùn)行軌跡逼近計(jì)劃軌跡的要求。

5 結(jié)束語

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

圖3 仿真效果圖

[1] 張亦南.基于GA的列車自動調(diào)整算法在CBTC系統(tǒng)中的應(yīng)用研究[D]. 北京：北京交通大學(xué)， 2008.

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

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

[4] 張大華. 列車自動調(diào)整系統(tǒng)[J]. 地鐵與輕軌，1999（3）.

[5] 朱顥東，鐘 勇. 一種改進(jìn)的模擬退火算法[J]. 計(jì)算機(jī)技術(shù)與發(fā)展， 2009（6）.

[6] 龐 峰. 模擬退火算法的原理及算法在優(yōu)化問題上的應(yīng)用[D]. 長春：吉林大學(xué)，2006.

責(zé)任編輯 徐侃春

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

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