基于遺傳算法的城市軌道交通運行圖自動調(diào)整的仿真研究

楊 柯，孔繁虹

（同濟大學 電氣工程系，上海 200331）

列車自動監(jiān)控系統(tǒng)（ATS），它主要實現(xiàn)對列車運行的監(jiān)督和控制，輔助行車調(diào)度人員對全線列車進行管理，對提高運輸效率和保障行車安全起到重要作用。其中列車運行圖是該系統(tǒng)中工作計劃與調(diào)整基礎，在基于通信的列車控制（CBTC）中，列車是基于運行圖行駛的，由于列車行駛中存在許多不確定性，經(jīng)常出現(xiàn)列車實際運行圖偏離計劃運行圖的現(xiàn)象，這時就要進行列車自動調(diào)整（ATR），使列車恢復正點運行。

本文對一些論文中已有的遺傳算法調(diào)整模型做了修改，比如考慮到列車早點的情況，加入了早晚點列車數(shù)目的判斷標準以及修改了約束條件等，以保證更接近CBTC的真實情況。仿真是在matlab7.5遺傳算法工具箱中進行，該工具箱擁有圖形界面（GU I），封裝了遺傳算法的很多函數(shù)，將編寫好的M文件放入并設置好參數(shù)即可運行，比以前單純編程求解方便許多。仿真結果也證實該算法即方便又可靠。

1 運行圖

1.1 運行圖介紹

列車運行圖表示列車在鐵路各區(qū)間運行時刻及通過時刻的線條圖，記錄了列車在每一站到達和出發(fā)時刻，以及站之間通過時間和車站之間距離等信息。在運行圖上，橫坐標表示時間，豎直線為時間等分，稱為時分線；縱坐標表示車站距離，橫直線為站名線，表示各個車站到發(fā)線中心的位置。斜線表示列車運行線，運行線與水平線的交點表示列車到、發(fā)和停站時間。常用的運行圖有十分格運行圖和二分格運行圖。

（1）十分格運行圖：橫坐標以10 min代表一格，0.5 h用虛線表示，h用實線表示。

（2）二分格運行圖 ：橫坐標以2 min代表一格，對10 min的倍數(shù)用粗線表示（如30 min和60 min線），其他用細線表示。

1.2 運行圖繪制

運行圖表示的是列車的時刻表信息，所以需要數(shù)據(jù)庫來存放車站信息及時刻表信息等，這里采用SQL2005存放數(shù)據(jù)，繪圖則采用mFC的繪圖函數(shù)，大致步驟為：

從數(shù)據(jù)庫中讀取列車的相關數(shù)據(jù),如車站信息和上下行時刻表信息等。并分別將時間和車站距離對應的秒數(shù)轉(zhuǎn)化為像素數(shù)據(jù)保存在數(shù)組中。如12:00:00是43 200，對應X軸；車站距離對應Y軸。然后用mFC里的for循環(huán)和繪圖函數(shù)move to和line to即可繪制出運行圖。

如圖1所示，用Visual C++2005的對話框繪制出二分格運行圖，橫坐標一格代表2 min，縱坐標表示各站之間相對距離；左邊藍色的線表示上行的3輛列車，右邊紅色的線表示下行的3輛列車，拖動水平滾動條可顯示從5:50:00首班車一直到末班車所有的列車運行線（本圖只顯示到7:10）。

圖1 二分格運行圖

2 遺傳算法

遺傳算法的基本原理如下：

（1）編碼：把一個問題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法稱為編碼。

（2）選擇：是群體中選擇生命力強的個體產(chǎn)生新群體的過程。使用選擇算子，適應度高的個體被遺傳到下一代群體中的概率較大。

（3）交叉：是按較大的概率從群體中選擇2個個體，交換2個個體的某個或某部位。交叉運算產(chǎn)生子代，子代繼承了父代的基本特征。

（4）變異：以較小的概率對個體編碼串上的某個或某些位值進行改變，生成新個體。

（5）適應度函數(shù)：根據(jù)目標函數(shù)確定的用于區(qū)分群體中個體好壞的標準，適應度函數(shù)非負的，任何情況下越大越好。而目標函數(shù)可能有正負，或求最大值和最小值，因此需要在目標函數(shù)與適應度函數(shù)之間進行變換

（6）約束條件：一般采用懲罰函數(shù)法，對不滿足約束條件的個體計算其適應度時，處一個懲罰函數(shù)，降低該個體適應度，使該個體被遺傳到下一代的概率減小。

3 列車自動調(diào)整模型

3.1 模型的建立

列車自動調(diào)整的目的是使列車的實際到站和發(fā)車時間與計劃到站發(fā)車時間絕對值最小。由于列車運行是一個連續(xù)的系統(tǒng)，某輛車的晚點可能會引起后面幾輛車的晚點，為了使列車受到影響的范圍最小化，實施運行調(diào)整的范圍也盡量小。

3.2 編碼

編碼就是解得遺傳表示。為方便求解可以采用直接整數(shù)編碼的方式，用時間對應的秒數(shù)進行編碼。如12:00:00秒數(shù)是43 200，編碼表示就是43 200。

具體編碼可采取矩陣的形式:

公式（1）表示第1輛車在各站的到站時間，同理第2輛車為d21～d213,發(fā)車時間為f21～f213。

3.3 目標函數(shù)確定

列車調(diào)整有2個目標：

（1）列車到達早晚點時間絕對值與列車發(fā)車早晚點時間絕對值總和最小。

其中：n1為上行列車數(shù)，n2為下行列車數(shù)，m是車站數(shù)目。分別為列車實際到站、離站時間di;k, fi;k分別為列車計劃到站、離站時間。

（2）列車到達早晚點數(shù)目和出發(fā)總晚點數(shù)目

上式表示列車到站和發(fā)車誤差小于10 s時不算晚點，大于10 s時該列車晚點，早晚點數(shù)記一次。

這樣可得出列車調(diào)整目標函數(shù)為Z=Z1+Z2：

其中w1、w2為權重值，根據(jù)實際情況確定。

3.4 約束條件的處理

約束1：發(fā)車條件約束，實際發(fā)車時間不能早于計劃發(fā)車時間。

約束2：最小停站時間約束，實際停站時間不能小于最小停站時間。

約束3：最小區(qū)間運行時間約束，2站之間運行時間不能小于最小運行時間，其數(shù)值與線路限速有關。

約束4：列車追蹤時間約束，相連2輛列車運行間隔不能小于規(guī)定的運行間隔，以保證行車安全。

3.5 遺傳算法參數(shù)確定

本例采用的是matlab7.5中自帶的遺傳算法與直接搜索工具箱，它有一個圖形用戶界面GUI，可以直接輸入各參數(shù)。遺傳算法的主要參數(shù)有種群參數(shù)、選擇參數(shù)、再生參數(shù)、變異參數(shù)、交叉參數(shù)、遷移參數(shù)和停止條件參數(shù)等。

種群參數(shù)：本例由于變量較多，所以種群規(guī)模應該盡量大，一般為300～500之間。

選擇參數(shù)：通過保留最優(yōu)個體的選擇方式，一般采用輪盤賭選擇算法，個體被選擇的概率用公式表示

公式（9）表示個體被選擇的概率，f(xi)是個體xi的適應度值，Nind是個體數(shù)量。該選擇方式考慮了適應度對選擇的影響，保留了最優(yōu)個體，防止早熟現(xiàn)象出現(xiàn)。

再生參數(shù)：指定將生存到下一代個體數(shù)，一般取小于等于種群尺度的正整數(shù)，缺省值為2。

變異參數(shù)：通過小的隨機數(shù)改變種群的個體而創(chuàng)建變異的子輩。這里采用均勻變異，變異概率取0.01。

交叉參數(shù)：交叉是組合2個個體或雙親，為下一代形成新的子個體。本文采用隨機配對，2點交叉的方式，即在編碼中隨機設置2個交點，再進行部分基因交換。

遷移參數(shù)：個體在子種群間移動，用一個子種群最好的個體代替另一種群中最差的個體。一般采用默認值。

停站條件：決定什么引起算法的終止。本文設置最大執(zhí)行代數(shù)為600，停滯代數(shù)、停滯時間、適應度限和執(zhí)行時間都設置為Inf，即無限制。

4 仿真結果及分析

以上海地鐵二號線的時刻表為例，一共有13個車站，現(xiàn)用3輛車，分上下行共6個車次進行仿真。

各已知條件如下：

（1）車站總數(shù)M=13，站名可看圖1的運行圖；

（2）列車總數(shù)N=3×2=6；

（3）列車在各區(qū)間的計劃運行時分為（時間單位：s，以下類同）：

[70 90 150 150 140 150 150 90 150 150 90 210]；

（4）列車在各站計劃停站時間為：

[180 30 30 30 40 30 30 30 30 30 30 30 30 120]；

（5）該區(qū)段列車追蹤間隔時間為180 s；

（6）列車區(qū)間最小運行時分為：

[65 85 137 137 124 137 137 86 135 136 85 193]；

（7）列車最小停站時間為：

[170 25 25 25 35 25 25 25 25 25 25 25 110]。

該仿真過程是一個連續(xù)的調(diào)整過程，即先確定晚點列車車次、晚點車站和晚點時間，然后由遺傳算法預測該車在剩余幾個站的到站和發(fā)車時間，以保證總晚點時間最小，如果到折返站晚點仍然存在，則繼續(xù)調(diào)整。直到列車恢復正點運行為止。

例如列車1在上行第3站晚點200 s，則遺傳算法編碼時前2站的實際時刻表編碼仍與計劃時刻表相同，從第3站發(fā)車開始以后幾站的到發(fā)時間都設成變量求解，直到折返站，若仍然晚點，則對下行時刻繼續(xù)求解，直到正點運行。比如求得第4站晚點95 s，到13站時仍晚點20 s，則對下行繼續(xù)循環(huán)，若下行到第10站晚點時間為0，則調(diào)整結束。

在matlab中用gatool命令打開遺傳算法工具箱，將編寫好的目標函數(shù)M文件train在Fitness function位置設置為@train,同理將約束條件函數(shù)轉(zhuǎn)換成矩陣A?x≤b形式,A處填寫矩陣A，b寫矩陣b,變量個數(shù)根據(jù)待求解的列車和車站個數(shù)計算，本文設置為45；其他參數(shù)按照章節(jié)3的設定。

具體仿真結果如表1和圖2所示，表1為計劃時刻表，表2為根據(jù)圖2結果顯示的秒數(shù)（只顯示了部分變量）換算成調(diào)整的實際時間。

圖2 遺傳算法運行結果

對比兩表可以看出，在上行第3站晚點200 s以后經(jīng)過連續(xù)調(diào)整，到下行第12站到達時已恢復正點，此后一直按計劃時刻運行。從結果可以看出，該算法仿真的結果良好，列車在遵從約束條件情況下緩慢的將列車調(diào)整至正點運行，并保證了列車的總晚點時間最小。

表1 列車在上下行、在各站的計劃時刻表

表2 列車在上下行、在各站的實際時刻表

5 結束語

本文研究從不同角度修改列車調(diào)整模型已保證其更接近真實情況并驗證其正確性；并展示了一個更方便的遺傳算法求解過程，使求解效率提高。

在實際列車運行中經(jīng)調(diào)整后的數(shù)據(jù)由ATS中的ATR模塊發(fā)送給列車自動運行系統(tǒng)（ATO），ATO根據(jù)此數(shù)據(jù)控制列車區(qū)間行駛及停站時間，并將實際運行的數(shù)據(jù)反饋給ATS運行圖繪制模塊，繪制出實際運行圖。可實現(xiàn)列車實際運行圖從偏離計劃運行圖到慢慢恢復到計劃運行圖的過程，從而實現(xiàn)了列車運行圖的自動調(diào)整。

[1] 雷英杰，張善文，李續(xù)武，周創(chuàng)明.MATLAB遺傳算法工具箱及應用[M].西安：電子科技大學出版社，2005：1-258.

[2] 劉洪寬.城市軌道交通ATS關鍵技術及仿真平臺研究[D].成都：西南交通大學，2008：33-53.

[3]馬海民，趙庶旭，黨建武.基于多目標遺傳算法的客運專線列車運行調(diào)整[C].全國博士生學術論壇電氣工程論文集，2008：1998-2004.

[4] 高強周.城市軌道交通列車運行圖設計實現(xiàn)與評價[D].北京：北京交通大學，2008：19-54.

[5] 王慧妮.客運專線列車運行調(diào)整模型及算法研究[D].成都：西南交通大學，2006：26-47.

[6] Li Mao jun.COOPERATIVE EVOLUTION GENETIC ALGORITHM ON BIDDING OF POWER MARKET [A].IMACS Multiconference on"Computational Engineering in SystemsApplications"(CESA), 2006.