基于蟻群優(yōu)化算法的高速列車運行調(diào)整研究

(1.蘭州交通大學(xué) 電子與信息工程學(xué)院，甘肅 蘭州 730070； 2.蘭州交通大學(xué) 自動化與電氣工程學(xué)院，甘肅 蘭州 730070)

目前，我國高速鐵路的發(fā)展飛速、列車運行規(guī)模不斷擴(kuò)大，列車的運行速度越來越快，列車在行駛的過程中難免會受到自然原因或者人為原因的影響，導(dǎo)致列車晚點延誤，嚴(yán)重影響列車的行車效率。因此，鐵路調(diào)度中心必須制定針對性的措施，對晚點列車的運行計劃實時、快速地調(diào)整。目前，國內(nèi)外相關(guān)領(lǐng)域的專家學(xué)者也對高速列車運行調(diào)整問題進(jìn)行了大量的研究。張翠平[1]等人根據(jù)圖論理論建立了一種列車運行計劃調(diào)整的圖論模型并采用啟發(fā)式算法(Heuristic Algorithm)對其進(jìn)行求解；雷明[2]等人針對列車運行調(diào)整問題，設(shè)計出了一種新的模型并且使用協(xié)同式進(jìn)化遺傳算法對其進(jìn)行求解；段少楠[3]等人對標(biāo)準(zhǔn)螢火蟲算法實行離散處理，建立一種新的列車運行調(diào)整模型，并使用離散螢火蟲算法(Discrete Firefly Algorithm)對其進(jìn)行求解；廖正文[4]等人設(shè)計了一種將復(fù)雜路網(wǎng)下的列車組合優(yōu)化問題轉(zhuǎn)化為單列車的最短路徑問題并且采用拉格朗日松弛算法進(jìn)行求解；MENG[5]等人設(shè)計一種新的粒子群算法求解列車運行調(diào)整問題；Tornquist[6]等人建立一種以晚點時間和晚點懲罰為目標(biāo)的混合整數(shù)線性規(guī)劃模型；曹巖[7]等人用改進(jìn)差分算法對高速列車運行調(diào)整問題進(jìn)行求解。高鐵列車運行計劃的調(diào)整具有高維數(shù)、非線性混合整數(shù)等特點，求解此類問題具有相當(dāng)大的難度，所以采取恰當(dāng)?shù)乃惴ㄊ墙鉀Q此類問題的關(guān)鍵。解決列車運行調(diào)整問題的方法由最優(yōu)化方法和智能優(yōu)化算法兩種方法構(gòu)成，當(dāng)使用最優(yōu)化算法解決此類問題時，通常要簡化列車運行計劃模型，往往只能得到列車運行調(diào)整問題的較優(yōu)解，與實際列車運行調(diào)整問題的最優(yōu)解還有一定差距，并且隨著列車運行計劃規(guī)模的增大很難得到數(shù)據(jù)的最優(yōu)解，甚至無法得到數(shù)據(jù)的正確結(jié)果。智能算法則可以求解復(fù)雜的列車運行調(diào)整模型，但并不是所有的智能算法都適用于高鐵列車運行計劃調(diào)整問題的求解，例如遺傳算法適合求解無約束條件的優(yōu)化問題，求解多約束條件的模型效果較差[8]；粒子群算法在求解數(shù)值優(yōu)化的問題方面表現(xiàn)良好，但在解決多目標(biāo)組合優(yōu)化的問題上，卻容易陷入局部最小點，難以獲得最優(yōu)解，所以選擇一種適合列車運行計劃調(diào)整問題求解的智能算法至關(guān)重要。蟻群算法目前廣泛應(yīng)用于求解TSP問題、指派問題等多目標(biāo)、多約束條件的組合優(yōu)化問題并且取得很好的效果[9]。本文對蟻群算法進(jìn)行改進(jìn)，使得改進(jìn)后的算法適用于高鐵列車運行調(diào)整問題的求解，是一種新的解決此類問題的方法。

1 模型的構(gòu)造

本文主要以雙線自動閉塞單一方向的高速鐵路線路為研究目標(biāo)，將列車運行圖的計劃線用出發(fā)線與到達(dá)線表示，如圖1所示，縱坐標(biāo)為車站，橫坐標(biāo)為時間，列車的運行計劃線由線段組成，線段與車站出發(fā)線和車站到達(dá)線的交點分別為列車的出發(fā)時間和列車的到達(dá)時間，并將列車運行圖劃分為以分鐘為單位的離散時間點的集合。

1.1 變量定義

針對高速列車運行調(diào)整模型，有如下定義。

① 車站總數(shù)為M，區(qū)間總數(shù)為M-1。

② 列車數(shù)量為L。

⑥W(i)(i∈{1,2,3,…,L})為列車等級的優(yōu)先級，W(i)的值越小，列車等級的優(yōu)先級越低，W(i)的值越大，列車等級的優(yōu)先級越高。

⑦εi,k為第i(i∈{1,2,3,…,L})列車在第k(k∈{1,2,3,…,M})個車站的最小作業(yè)時間。

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

列車運行調(diào)整是一個多目標(biāo)、多方面的優(yōu)化問題，各種各樣的情況都可能會導(dǎo)致列車晚點，所以實際列車運行計劃的調(diào)整比較復(fù)雜。選擇以每輛列車的到發(fā)時間作為變化量，并且將加權(quán)后所有列車的總晚點時間F0作為目標(biāo)函數(shù)。通過調(diào)整區(qū)間內(nèi)所有列車到發(fā)時間，同時考慮每輛列車優(yōu)先級的影響，使得每輛列車到達(dá)該車站的發(fā)車順序發(fā)生改變，最終使得目標(biāo)函數(shù)F0最小。

(1)

1.3 約束條件

為了保障高速列車安全運行，列車在運行調(diào)整過程中需受到下列條件的約束。

(1) 所有列車的實際發(fā)車時刻不可早于計劃發(fā)車時刻。

(2)

(2) 列車在車站停車，不能小于該車站規(guī)定的停站時刻：

SNi,k-APi,k≥εi,k

(3)

③ 列車在兩個車站之間的運行時間，應(yīng)滿足該區(qū)間的最小運行時刻。

(4)

④ 兩個追蹤列車應(yīng)滿足最小發(fā)車時刻。

(5)

⑤ 兩個追蹤列車應(yīng)滿足到達(dá)時間的最小間隔。

(6)

⑥ 列車越行條件：只有滿足以下，列車j才可以越行列車i(j為后車，i為前車)。

W(j)>W(i)

(7)

2 蟻群算法概述

2.1 蟻群算法的基本原理

20世紀(jì)90年代，意大利的專家學(xué)者M(jìn).Dorigo、A.Colorni 等人通過螞蟻覓食的過程得到啟發(fā)，提出了蟻群算法[10]。如圖2所示，在螞蟻覓食的過程中，螞蟻能夠通過信息素的交換，從而實現(xiàn)在未知的環(huán)境下找出洞穴與食物之間的最短路徑。

圖2 螞蟻覓食過程

采用按站調(diào)整的列車運行圖調(diào)整方法，確定晚點的列車所在的車站并且按照相應(yīng)的約束條件改變該車站晚點列車和之后列車的發(fā)車順序，通過調(diào)整區(qū)間的冗余度，使得晚點列車盡快恢復(fù)到正點。將列車運行圖劃分為許多以分鐘為單元的時間點，通過算法搜尋這些帶有信息素信息的時間點，并對這些時間點做出相應(yīng)的調(diào)整。當(dāng)各只螞蟻都完成路徑創(chuàng)建后，存儲在時間點上的信息素將會進(jìn)行蒸發(fā)。

τit=(1-ρ)τit

(8)

式中，τit為螞蟻第i輛列車在第t個時刻上的信息素；ρ(ρ∈[0,1])為信息素?fù)]發(fā)因子，ρ的作用是使螞蟻能夠選擇更好的路徑，擺脫先前所選擇不良路徑，使得螞蟻能夠在較好路徑上累積信息素，從而讓更多的螞蟻向著具有信息素濃度更高的路徑上移動。

當(dāng)信息素蒸發(fā)以后，每只螞蟻都會在其經(jīng)過的時刻釋放信息素，此時，這個時刻更新后的環(huán)境信息素是之前螞蟻留存的信息素和螞蟻新釋放的信息素的總和。

(9)

(10)

式中，Cm為第m只螞蟻調(diào)整后時刻表所對應(yīng)的目標(biāo)函數(shù)值，如果螞蟻所創(chuàng)建的路徑所對應(yīng)的目標(biāo)函數(shù)值越小，在時間線上對應(yīng)時刻上的信息素濃度越大，則該時刻就更容易在之后的迭代中引起更多的螞蟻來選擇，使得蟻群最終搜索到目標(biāo)函數(shù)值最小的時間節(jié)點。

第m只螞蟻隨機(jī)放到列車計劃到發(fā)時間所對應(yīng)的時間點上，每一條邊都有初始化信息素，在創(chuàng)建路徑的每一步上，螞蟻n按照公式?jīng)Q定下一步準(zhǔn)備向滿足約束條件的列車計劃到發(fā)時間所對應(yīng)的任意一點的概率。

(11)

2.2 蟻群算法的改進(jìn)

采用蟻群算法解決列車運行計劃調(diào)整問題時存在一些缺陷，蟻群的規(guī)模會隨著問題規(guī)模的增大而快速擴(kuò)大，當(dāng)需要調(diào)整的列車運行計劃越來越多時，螞蟻在較短的時間里很難找到一條較好的路徑，甚至給出錯誤的調(diào)整結(jié)果，所以降低蟻群的選路時間，提高蟻群的選路效率至關(guān)重要[11]。因此針對這種情況，采取4種方法，對蟻群算法的選路策略進(jìn)行優(yōu)化，提高算法的運算效率。

① 減小螞蟻選路次數(shù)。假設(shè)螞蟻選路的行為是獨立并行的，隨著節(jié)點數(shù)目e和螞蟻個數(shù)m的急劇增加，在每次螞蟻選擇路徑完成以后，比較m只螞蟻所選擇的路徑的長度，選擇出路徑最短的那只螞蟻，讓它執(zhí)行選路操作，當(dāng)該螞蟻抵達(dá)下一個節(jié)點后，再次計算路徑長度并與上面的路徑進(jìn)行對比，直到有一只螞蟻走完全部節(jié)點e，算法結(jié)束。

② 已知最短路徑方法。引入變量Lmin記錄每輪求解路徑的最小值，并將該值初始化為較大值，如果求得螞蟻選路后的路徑值小于該值，本輪循環(huán)繼續(xù)，直到求得螞蟻選路后的路徑值大于該值結(jié)束，并進(jìn)行另外一輪循環(huán)。

③ 減小螞蟻選路計算量。在螞蟻進(jìn)行選路操作時，選擇概率僅基于當(dāng)前節(jié)點的前X個距離最近的且未經(jīng)過的候選節(jié)點來計算。

④ 引入混沌序列。內(nèi)隨機(jī)性和遍歷性是混沌序列的兩大特點，利用Chebyshev映射產(chǎn)生的混沌序列，替代螞蟻選擇下一條路徑時的隨機(jī)數(shù)。

xi+1=cos(rarccos(xi))

(12)

式中，xi為經(jīng)Chebyshev映射轉(zhuǎn)化后的值；r為控制參數(shù)，當(dāng)r=1.8時，Chebyshev完全處于混沌狀態(tài)。

2.3 算法流程

運行蟻群算法的基本步驟如下。

① 初始化算法各項的基本參數(shù)。

③ 按照約束條件，每只螞蟻構(gòu)建路徑對該車站的晚點列車i和之后到達(dá)該車站k的列車計劃時刻進(jìn)行調(diào)整。

④ 檢查每只螞蟻的函數(shù)值，并按照每列列車優(yōu)先級W(i)，對晚點列車的到發(fā)時間進(jìn)行調(diào)整，根據(jù)調(diào)整后的時刻，改變列車的發(fā)車順序。

⑤ 更新信息素，對更新后的所有螞蟻的目標(biāo)函數(shù)進(jìn)行排序，得到最小值，作為此次迭代的最優(yōu)解。

⑥ 判斷最優(yōu)解是否滿足結(jié)束條件，如果滿足結(jié)束條件則停止搜索，輸出本車站的調(diào)整結(jié)果，即最優(yōu)的調(diào)整結(jié)果；否則將繼續(xù)執(zhí)行步驟③，繼續(xù)搜索下一個車站并對晚點列車進(jìn)行調(diào)整。

3 算例分析

選取了某高速鐵路下行線路上的6個車站，并且分別使用改進(jìn)后的蟻群算法、文獻(xiàn)[1]中的啟發(fā)式算法和文獻(xiàn)[3]中的離散螢火蟲算法對算例進(jìn)行仿真對比。

3.1 算例設(shè)計

算例的初始條件如下。

① 設(shè)定有4種不同類型的14列列車，每一列列車都是從車站1始發(fā)到車站6到達(dá)終點，區(qū)間總數(shù)為5。

② 14輛高速列車所對應(yīng)的優(yōu)先級矩陣為:W(i)=[0.3,0.3,0.3,0.2,0.2,0.1,0.1,0.1,0.1,0.1,0.4,0.4,0.4,0.4]。

③ 4種等級的列車在5個區(qū)間內(nèi)的最小運行時間及列車在6個車站對應(yīng)的最小作業(yè)時間(單位：min)矩陣為

列車的計劃運行時刻表如表1所示，本次算例設(shè)置6號車輛作為晚點列車，列車晚點發(fā)生在第3車站與第4車站的區(qū)段中，列車的晚點時間為25 min。

表1 列車計劃運行時刻表 單位：min

采用的實驗仿真平臺為Windows 7，Matlab 2017b，CPU為Intel?Core?i7-3615QM，2.30 GHz，內(nèi)存為4.0 GB。經(jīng)過多次實驗分析，對蟻群優(yōu)化算法的基本參數(shù)設(shè)置如下：螞蟻的數(shù)目m=50，迭代次數(shù)n=500，信息啟發(fā)式因子α=2，期望啟發(fā)式因子β=4，信息素殘留因子1-ρ=0.9。

針對列車晚點的情況，使用改進(jìn)后的蟻群算法對本次算列中存在的晚點列車的運行計劃進(jìn)行相應(yīng)的調(diào)整，最終得到算法的調(diào)整后的列車運行時刻表如表2所示。

表2 蟻群優(yōu)化算法調(diào)整后的列車運行時刻表 單位：min

3.2 數(shù)據(jù)分析

采用3種算法對第6輛晚點列車進(jìn)行調(diào)整，首先確定晚點列車的優(yōu)先級，優(yōu)先調(diào)整優(yōu)先級高的列車，當(dāng)中等級的列車晚點時間較短時，隨后出發(fā)的中等級的列車和高等級的列車不受其影響，都能迅速恢復(fù)到正點，但是一旦中等級列車的晚點時間過長，之后出發(fā)的列車都會受到一定影響，但是隨著列車不斷運行，高等級的列車在之后的每個車站都將進(jìn)行調(diào)整，將列車總晚點時間調(diào)整到最小，甚至使列車恢復(fù)到正點。

仿真結(jié)果如圖3所示，蟻群優(yōu)化算法和啟發(fā)式算法都優(yōu)先對優(yōu)先級高的第11輛列車、第12輛列車、第13輛列車、第14輛列車進(jìn)行調(diào)整，使得優(yōu)先級高的列車沒有發(fā)生晚點，并且在第5車站蟻群優(yōu)化算法和啟發(fā)式算法都實現(xiàn)了對第8輛列車、第9輛列車、第10輛列車的越行。然而，啟發(fā)式算法同時也對第7輛列車越行，使得第7輛列車晚點75 min，從而使最終調(diào)整效果受到較大影響。離散螢火蟲算法沒能很好地對晚點列車進(jìn)行調(diào)整，僅僅對優(yōu)先級高的第13輛列車、第14輛列車進(jìn)行調(diào)整，對第9輛列車、第10輛列車、第11輛列車、第12輛列車采取站內(nèi)越行，最終得到的調(diào)整效果一般。

圖3 仿真結(jié)果

通過對比3種算法的數(shù)據(jù)結(jié)果，如表3所示，蟻群優(yōu)化算法計算算例得到的目標(biāo)函數(shù)值最小，即加權(quán)后所有列車的總晚點時間最少，然而啟發(fā)式算法與離散螢火蟲算法得到的目標(biāo)函數(shù)值較大，很難得到問題的最優(yōu)解。

表3 3種算法的數(shù)據(jù)結(jié)果

4 結(jié)束語

本文充分考慮了在列車在運行過程中列車的發(fā)車時間、列車的到達(dá)時間、車站到發(fā)線數(shù)量等約束條件的影響，建立了以加權(quán)總晚點時間最小為目標(biāo)函數(shù)的高速列車運行調(diào)整模型，并對蟻群算法進(jìn)行優(yōu)化改進(jìn)，使得該算法適用于求解列車運行調(diào)整問題。本文使用了計算機(jī)仿真技術(shù)，利用Matlab平臺實現(xiàn)了對列車運行計劃調(diào)整模型進(jìn)行仿真，并采用啟發(fā)式算法、離散螢火蟲算法和蟻群優(yōu)化算法分別對算例進(jìn)行求解，實驗結(jié)果表明，蟻群優(yōu)化算法的目標(biāo)函數(shù)值最小，即所有列車的總晚點時間最小，從而證明該算法能夠有效處理高速列車運行調(diào)整問題。