楊 柯，孔繁虹

（同濟大學 電氣工程系，上海 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ù)轉化為像素數(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）編碼：把一個問題的可行解從其解空間轉換到遺傳算法所能處理的搜索空間的轉換方法稱為編碼。

（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ù)轉換成矩陣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.