基于改進蟻群算法的高速公路協同救援路徑規劃

張健 范曉武

摘? 要： 針對高速公路多點協同救援路徑規劃問題，文章綜合考慮路段行駛時間和路徑安全性兩個優化目標，設計路徑評價函數。根據高速公路救援的特點，引入“助手結點”的概念來設置信息素初始濃度;引入搜索角、結點直線距離和安全因素設計了啟發函數;使用隨機選擇機制來優化狀態轉移規則;最后引入獎勵機制設計了信息素更新規則，通過這四個方面改進了蟻群算法。在此基礎上，建立多點協同救援模型，采用表上作業法確定救援車輛派遣方案。仿真實驗結果表明，改進的蟻群算法和原始的蟻群算法相比，不但收斂速度更快，而且優化了全局最優解。改進的蟻群算法與表上作業法的結合，實現了多救援點協同救援的路徑規劃功能。

關鍵詞： 路徑規劃; 多點協同救援; 蟻群算法; 表上作業法

中圖分類號：TP391.1? ? ? ? ? 文獻標識碼：A? ?文章編號：1006-8228（2021）03-01-05

Path planning of expressway cooperative rescue using improved ant colony algorithm

Zhang Jian， Fan Xiaowu

（Zhejiang Comprehensive Transportation Big Data Center Co.， Ltd.， Hangzhou， Zhejiang 310018， China）

Abstract： Aiming at the multi-point collaborative rescue path planning for expressway， this paper designs a path evaluation function considering the two optimization objectives of road travel time and path safety. According to the characteristics of expressway rescue， the concept of "assistant node" is introduced to set the initial concentration of pheromone; heuristic function is designed by introducing search angle， linear distance between nodes and safety factor; state transition rule is optimized by using random selection mechanism; pheromone update rule is designed by introducing reward mechanism， thereby the ant colony algorithm is improved. On this basis， the multi-point cooperative rescue model is established， and the dispatching scheme of rescue vehicles is determined by the method of operation on table. The simulation results show that the improved ant colony algorithm not only converges faster than the original one， but also optimizes the global optimal solution. The combination of the improved ant colony algorithm with the method of operation on table realizes the function of multi-point cooperative rescue path planning.

Key words： path planning; multi-point cooperative rescue; ant colony algorithm; operation on table

0 引言

我國高速公路建設規模不斷擴大，交通量持續增加，諸如高危化工品泄露、車輛追尾、碰撞等交通事故的發生頻率也隨之升高。事故發生后，交通指揮部門應及時制定救援方案，實施救援工作，這對于緩解道路擁堵、減少人員傷亡和財產損失具有重要意義。其中，合理地規劃救援路徑，使救援人員和車輛盡可能快的到達事故點是保障救援工作及時開展的關鍵。

救援路徑規劃的優化目標包括出行時間最短、擁堵程度最小、路徑最短、路線安全系數最高等。李紫瑤[1]以出行時間最短和路線長度最短為目標建立了應急車輛路徑尋優模型。何勇[2]建立了救援車輛運輸成本最小、運輸時間最短的優化模型，設計了應急資源配送路徑。Duan等人[3]首先以最短出行時間為目標，在此基礎之上考慮最小擁擠程度，建立了兩階段應急車輛路徑規劃模型。然而，這些研究工作在解決救援路徑規劃問題時大多將時間、擁堵程度和成本等作為優化目標，路徑的可靠性沒有得到研究者的廣泛關注。由于高速公路具有封閉性的特點，若在救援過程中出現二次事故，將會使車流波傳播到更大的路網，導致交通狀況陷入更糟糕的狀態。所以高速公路應急救援需考慮路段行駛時間和道路安全性。王曉剛[4]使用加權求和法考慮路線的行程時間、時間可靠性和安全性，構建多目標路徑選擇模型。肖博[5]從次生危害的角度出發，建立了行駛總時間最小和危險性最小的路徑優化模型。

傳統的路徑規劃方法包括混合蛙跳算法[6]，遺傳算法[7-9]以及蟻群算法。其中蟻群算法具有正反饋、良好的并行搜索能力和全局搜索能力，它可以從復雜解空間的多點同時開始搜索，在解決多目標優化問題方面具有良好的性能，被廣泛應用于求解多目標路徑規劃問題。談曉勇等人[10]提出一種混沌干擾的蟻群系統優化算法來解決以最短距離、最小成本和最小風險為優化目標的應急車輛調度問題。韋曉[11]使用改進的蟻群算法解決了以最短時間和最小成本的多目標救護車路徑規劃問題。

當高速公路同一時間段內發生多起交通事故時，多救援點協同救援將會大大提升總體救援效率，而先前的研究很少考慮多救援點多事故點的情形。針對以上問題，本文綜合考慮路段行駛時間和路徑安全性兩個因素，設計路徑多目標優化評價函數，利用改進的蟻群算法求解救援點到事故點的最佳路徑，根據救援點和事故點的供需關系建立協同派遣模型，采用表上作業法求解模型得到多救援點到多事故點的最優派遣方案。改進的蟻群算法具有更快的收斂速度，并且能獲得更優的目標函數值。

1 問題描述與模型建立

本文將高速公路路網抽象為有向圖[G（V，E）]其中[V]表示頂點集合，[E]表示頂點與頂點之間的連接邊，即路段。假設救援點數量為[N]，事故點數量為[M]，[du]表示事故點u需要的救援車輛數，[rl]表示救援點l所儲備的救援車輛數，[Zlu]表示從救援點[l]到事故點[u]的最優救援路徑的路徑評價函數值，[xlu]為決策變量，表示從救援點[l]派遣到事故點[u]的救援車輛數。每個救援點可以將救援車輛派遣到各個事故點，每個事故點可以接受由多個救援點派遣出的救援車輛的救援，從而達到多救援點協同救援的目的。以總體路徑評價函數值之和最小為目標，建立多救援點協同救援派遣的數學模型，具體如下：

[minZ=ω1Z1+ω2Z2] ⑴

[tij=t01+α1QCβ1] ⑵

[Z1=i=1Nj=1Ntijxij] ⑶

[Z2=i=1Nj=1Neijxij] ⑷

約束條件包括：

[l=1nxlu=du，u∈1，2，…，m] ⑸

[u=1mxlu≤rl，l∈1，2，…，n] ⑹

[u=1mdu≤l=1nrl] ⑺

[xlu≥0，l∈1，2，…，n，u∈1，2，…，m] ⑻

式⑴表示多目標優化評價函數的數值，[Z1]表示該路徑通行所花費的時間，[Z2]表示道路安全因素。[ω1]，[ω2]分別表示[Z1]，[Z2]所占比重。式⑵為BPR函數，[t0]為該路段自由流行駛時間，[Q]為該路段的實際交通流量，[C]為該路段的通行能力，[α1和β1]為待定參數。式⑶中，[xij]為決策變量，表示是否選擇路段（i，j）。式⑷中，[eij]表示路段（i，j）的風險系數。式⑸表示派遣到事故點的救援車輛數要等于事故點所需要的救援車輛數;式⑹表示救援點所儲備的救援車輛數應大于等于該救援點派遣出去的救援車輛數;式⑺表示假設救援點的救援車輛總數能滿足事故點的救援車輛總需求數;式⑻表示決策變量取值范圍。

2 基于改進蟻群算法的多點協同救援

經典蟻群算法全局搜索能力較差，當算法運行一段時間后，由于正反饋的累積作用，蟻群的搜索能力會停滯不前，且收斂速度也會降低。為了提升最佳路徑的搜尋速度，在其已有優勢的基礎上進行改進，來獲得性能更好的蟻群算法，本文采用改進的蟻群算法規劃各救援點到達各事故點的最優救援路徑，建立多救援點協同救援模型，最后采用表上作業法確定目標函數值最小的救援車輛派遣方案。

2.1 改進蟻群算法的設計

2.1.1 初始信息素濃度設置

本文引入“助手結點”的概念，根據目標結點的位置將信息素初始濃度設置為：

[τij0=ε+ε0若j與事故點e相鄰接ε否則] ⑼

其中，[ε]表示一般路段上的信息素初始濃度，[ε+ε0]表示與事故點e相鄰接節點的相鄰路段的信息素初始濃度。

“助手結點”是指與目標事故點e相鄰的結點。式⑼描述的信息素初始濃度設置方式提升了“助手結點”與其周圍節點間路段的信息素濃度，從而路徑的重要程度一開始便得以區分，螞蟻能更快地找到最優路徑。

2.1.2 啟發函數改進

本文綜合多個要求，設計啟發函數為：

[ηij=1μ1dij+μ2dja+μ3Δθπeij] ⑽

其中，[dij]表示路段（i，j）的實際距離，[dja]為節點j與事故點a之間的直線距離，[Δθ]表示直線（i，j）與直線（j，a）之間的夾角。[μ1， μ2， μ3]為待定參數。

從啟發函數計算式可以看出，搜索將優先考慮距離長度短、與終點距離小且指向終點并且路段安全性高的路段。啟發函數的改進加強了搜索的方向性，即優先選擇偏向終點角度小的鄰接節點，縮小了搜索范圍并且加快了搜索速度。

2.1.3 使用隨機選擇機制改進狀態轉移規則

[pkij=τijαηijβwijrjτijαηijβwijrk，j∈allowedk0others] ⑾

[j=arg maxτijαηijβwijr，r∈（0，q1）pkij，r∈（q1，q2）argmaxwij，r∈（q2，1）] ⑿

其中，式⑾為傳統蟻群算法的狀態轉移公式，[τij]表示路段（i，j）上的信息素濃度;[ηij]表示路段（i，j）之間的啟發式信息;[wij]為路段（i，j）之間路阻通行時間的倒數;[α]為信息素權重因子;[β]為啟發式信息權重因子;[r]為路阻通行時間權重因子。式⑿為使用隨機選擇機制改進的狀態轉移規則，[q1，q2]為分類選擇參數，[r]為隨機因子。

本文使用隨機選擇機制改進的狀態轉移規則用[q1，q2]分類選擇參數將下一個要訪問的節點分類為三種選擇。這樣既保證了搜索的收斂性好，又增強了搜索策略的多樣性。同時結合應用場景，將路阻通行時間最小路段的相應節點作為概率轉移中的一項選擇。

2.1.4 改進信息素更新策略

當螞蟻k經過某個路段（i，j）時，路段（i，j）上的信息素濃度被更新。

[τijt+Δt=1-ρτijt+log1+k=1mΔτkijt] ⒀

[Δτkijt=ψkQZk，螞蟻k經過路段i，j0，否則] ⒁

[ψk=1+Zavg-ZkZavg-Zbest，Zk

其中，式⒀中[τijt]表示第t輪迭代時路段（i，j）上的信息素濃度，[ρ]表示信息素的揮發程度，[Δτkij（t）]表示螞蟻k經過路段（i，j）留下的信息素增量，m表示螞蟻數量。式⒁中[Zk]表示第k只螞蟻的路徑評價函數值。式⒂為“激勵度”系數[ψk]。

改進后的信息素更新規則通過引入獎勵機制，對于走得比平均水平更好的螞蟻給予獎勵。可在短時間內通過信息素的增量上的差別來增大優秀路徑和其他路徑之間的信息素濃度的差距，最終能引導算法收斂到的結果為全局最優路徑，同時加快算法的收斂速度。

2.2 改進蟻群算法的流程

改進蟻群算法流程圖如圖1所示。

本文提出的改進蟻群算法的實現步驟如下。

Step 1：根據高速公路路網結構信息和交通流數據，用路網矩陣表示相關信息。

Step 2：初始化參數，根據式⑼設置各路段初始信息素濃度，在救援點節點放置m只螞蟻，將事故點作為目標終點。

Step 3：螞蟻k根據式⑽計算可選節點的啟發函數，隨后根據式⑿選擇下一個路徑節點j。

Step 4：判斷螞蟻當前訪問的路徑節點是否為目標事故點，若不是則轉step 3;若為目標事故點則結束該螞蟻的路徑尋找。

Step 5：根據式⑴計算路徑的路徑評價函數值，更新最優救援路徑和相應的路徑評價函數值。

Step 6：根據式⒀更新每條路徑上的信息素含量。

Step 7：判斷是否滿足終止條件，如果迭代次數[Nc≥Nmax]則迭代結束，否則清空禁忌表進行新的迭代。

2.3 采用表上作業法確定協同救援方案

當同一時段內有多個應急事件發生時，如何從各個救援點調度資源是決定救援是否高效的重要舉措。假設救援點所儲備的救援車輛數量大于等于該救援點派遣出去的救援車輛數量，故協同救援本質上是產銷不平衡的運輸問題，已有學者針對產銷不平衡的運輸問題進行了研究[12]。

在采用改進蟻群算法得到各救援點到各事故點的最優救援路徑和相應的路徑評價函數值的基礎上，設置一個假想事故點[M+1]來接收多余的救援車輛，從而將供需不平衡問題轉換為供需平衡問題。假想事故點[M+1]需要的救援車輛數為多余的救援車輛數[dM+1=l=1nrl-u=1mdu]，并將這些救援車輛從救援點到假想事故點[M+1]的路徑評價函數值Z設置為0，由此可以得到供需平衡問題下的各救援點到各事故點的路徑評價函數值表。最后采用表上作業法確定救援車輛派遣方案，實現多救援點協同救援。具體步驟如下。

Step1：采用伏格爾法獲得初始基變量可行解。

Step2：利用位勢法驗證初始基變量可行解是否為最優解。

Step 3：利用閉回路調整法改進可行解，直到可行解為最優解，即最優派遣方案。

表上作業法求解流程圖如圖2所示。

3 實驗與結果分析

3.1 模型參數設置

以杭州市周邊高速公路路網為例，驗證本文算法的有效性。路網中共有45個結點，其中交通樞紐有14個，高速互通有31個，如圖3所示。本文改進的蟻群算法的各項基本參數分別為：迭代次數[Nmax]=100，螞蟻數量m=10，啟發因子α=0.3，β=1，信息素因子Q=1，權重因子γ=0.6，經過反復實驗，取分類選擇參數q1=0.1，q2=0.9。

3.2 實驗結果

將蟻群算法的起點設置為結點6，終點設置為結點34，兩個算法最終的運行結果如圖4所示。

由圖4可以發現，雖然兩個算法最后都收斂到了同一個目標函數值，但是改進的蟻群算法收斂速度比傳統的蟻群算法更快。由于改進的蟻群算法在計算啟發函數時考慮了多種因素，并在信息素更新策略中引入了獎勵機制，從而使改進的蟻群算法和傳統蟻群算法相比，收斂速度更快。

以結點6為起點結點34為終點，兩種算法各運行10次，得到的平均目標函數值如表1所示。

由表1可以發現，改進的蟻群算法和傳統的蟻群算法相比，收斂到的平均目標函數值更小。這是因為改進的蟻群算法在啟發函數中考慮了路段發生二次事故的概率，而傳統蟻群算法只考慮下一結點與當前結點的距離大小，在應急救援路徑規劃中考慮的因素過于單一，從而導致其目標函數值偏高。

為驗證多地協同救援派遣方案的正確性，假設各救援點的救援車輛儲備數和各事故點的救援車輛需求數如表2所示。

利用改進的蟻群算法對表2中各個救援點到各個事故點進行路徑規劃，得到各條路徑的目標函數值，如表3所示，并結合表上作業法進行車輛派遣，實驗結果如表4所示。

表4中，第一行表示勾莊互通救援點派出1輛救援車到半山互通，派出1輛救援車到五常互通，其余依此類推。可以看到表上作業法較好地解決了多點協同救援問題。

4 結束語

本文在經典蟻群算法的基礎上，提出改進的蟻群算法來解決高速公路多點協同救援問題，從初始信息素濃度設置、啟發函數、狀態轉移規則、信息素更新規則等方面進行改進，解決了蟻群算法在路徑尋優過程中出現的停滯現象、收斂過慢的問題。本文將改進的蟻群算法與表上作業法相結合，實現了多救援點協同救援的路徑規劃功能，為高速公路救援工作爭取了寶貴的時間，具有很大的實用價值。

參考文獻（References）：

[1] 李紫瑤.應急救援車輛路徑尋優——基于多目標改進蟻群算法[J].技術經濟與管理研究，2011.9：7-10

[2] 何勇.應急救援物資配送模型及算法研究[D].廣東工業大學，2016.

[3] Duan P， Xiong S， Jiang H. Multi-objective optimization

model based on heuristic ant colony algorithm for emergency evacua-tion[C]//International IEEE Conference on Intelligent Transportation Systems. IEEE，2012.

[4] 王曉剛，韓印.救援車輛多目標實時路徑規劃模型[J].物流科技，2019.42（9）：15-17，31

[5] 肖博.基于多目標優化的震后應急物流路徑規劃研究[D].長安大學，2019.

[6] Jiandong Z， Yujie G， Xiaohong D. Dy-namic Path

Planning of Emergency Vehi-cles Based on Travel Time Prediction[J]. Journal of Advanced Transportation，2017.2017：1-14

[7] Roberge V， Tarbouchi M， Labonte G. Comparison of

Parallel Genetic Algorithm and Particle Swarm Optimization for Re-al-Time UAV Path Planning[J].IEEE Transactions on Industrial Informatics，2013.9（1）：132-141

[8] 陳曉燕，姚高偉，張鯤等.基于遺傳算法的無線傳感器節點定

位在農業的應用[J].軟件，2015.36（4）：1-5

[9] 聶敬云，李春青，李威威等.關于遺傳算法優化的最小二乘支持向量機在MBR仿真預測中的研究[J].軟件，2015.36（5）：40-44

[10] 談曉勇，林鷹.基于混沌蟻群算法的應急救援車輛調度優化[J].計算機應用研究，2014.31（009）：2640-2643

[11] 韋曉.基于改進蟻群算法的應急物流車輛路徑問題研究[D].濟南大學碩士學位論文，2015.

[12] 張孟飛，王鐵旦，李建楠.基于表上作業法的產銷不平衡運輸問題應用[J].價值工程，2018.037（023）：24-27