基于改進(jìn)蟻群算法的高速公路協(xié)同救援路徑規(guī)劃

張健 范曉武

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

關(guān)鍵詞： 路徑規(guī)劃; 多點協(xié)同救援; 蟻群算法; 表上作業(yè)法

中圖分類號：TP391.1? ? ? ? ? 文獻(xiàn)標(biāo)識碼：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 引言

我國高速公路建設(shè)規(guī)模不斷擴(kuò)大，交通量持續(xù)增加，諸如高?；て沸孤?、車輛追尾、碰撞等交通事故的發(fā)生頻率也隨之升高。事故發(fā)生后，交通指揮部門應(yīng)及時制定救援方案，實施救援工作，這對于緩解道路擁堵、減少人員傷亡和財產(chǎn)損失具有重要意義。其中，合理地規(guī)劃救援路徑，使救援人員和車輛盡可能快的到達(dá)事故點是保障救援工作及時開展的關(guān)鍵。

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

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

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

1 問題描述與模型建立

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

[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] ⑻

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

2 基于改進(jìn)蟻群算法的多點協(xié)同救援

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

2.1 改進(jìn)蟻群算法的設(shè)計

2.1.1 初始信息素濃度設(shè)置

本文引入“助手結(jié)點”的概念，根據(jù)目標(biāo)結(jié)點的位置將信息素初始濃度設(shè)置為：

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

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

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

2.1.2 啟發(fā)函數(shù)改進(jìn)

本文綜合多個要求，設(shè)計啟發(fā)函數(shù)為：

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

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

從啟發(fā)函數(shù)計算式可以看出，搜索將優(yōu)先考慮距離長度短、與終點距離小且指向終點并且路段安全性高的路段。啟發(fā)函數(shù)的改進(jìn)加強(qiáng)了搜索的方向性，即優(yōu)先選擇偏向終點角度小的鄰接節(jié)點，縮小了搜索范圍并且加快了搜索速度。

2.1.3 使用隨機(jī)選擇機(jī)制改進(jìn)狀態(tài)轉(zhuǎn)移規(guī)則

[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）] ⑿

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

本文使用隨機(jī)選擇機(jī)制改進(jìn)的狀態(tài)轉(zhuǎn)移規(guī)則用[q1，q2]分類選擇參數(shù)將下一個要訪問的節(jié)點分類為三種選擇。這樣既保證了搜索的收斂性好，又增強(qiáng)了搜索策略的多樣性。同時結(jié)合應(yīng)用場景，將路阻通行時間最小路段的相應(yīng)節(jié)點作為概率轉(zhuǎn)移中的一項選擇。

2.1.4 改進(jìn)信息素更新策略

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

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

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

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

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

改進(jìn)后的信息素更新規(guī)則通過引入獎勵機(jī)制，對于走得比平均水平更好的螞蟻給予獎勵?？稍诙虝r間內(nèi)通過信息素的增量上的差別來增大優(yōu)秀路徑和其他路徑之間的信息素濃度的差距，最終能引導(dǎo)算法收斂到的結(jié)果為全局最優(yōu)路徑，同時加快算法的收斂速度。

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

改進(jìn)蟻群算法流程圖如圖1所示。

本文提出的改進(jìn)蟻群算法的實現(xiàn)步驟如下。

Step 1：根據(jù)高速公路路網(wǎng)結(jié)構(gòu)信息和交通流數(shù)據(jù)，用路網(wǎng)矩陣表示相關(guān)信息。

Step 2：初始化參數(shù)，根據(jù)式⑼設(shè)置各路段初始信息素濃度，在救援點節(jié)點放置m只螞蟻，將事故點作為目標(biāo)終點。

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

Step 4：判斷螞蟻當(dāng)前訪問的路徑節(jié)點是否為目標(biāo)事故點，若不是則轉(zhuǎn)step 3;若為目標(biāo)事故點則結(jié)束該螞蟻的路徑尋找。

Step 5：根據(jù)式⑴計算路徑的路徑評價函數(shù)值，更新最優(yōu)救援路徑和相應(yīng)的路徑評價函數(shù)值。

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

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

2.3 采用表上作業(yè)法確定協(xié)同救援方案

當(dāng)同一時段內(nèi)有多個應(yīng)急事件發(fā)生時，如何從各個救援點調(diào)度資源是決定救援是否高效的重要舉措。假設(shè)救援點所儲備的救援車輛數(shù)量大于等于該救援點派遣出去的救援車輛數(shù)量，故協(xié)同救援本質(zhì)上是產(chǎn)銷不平衡的運(yùn)輸問題，已有學(xué)者針對產(chǎn)銷不平衡的運(yùn)輸問題進(jìn)行了研究[12]。

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

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

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

Step 3：利用閉回路調(diào)整法改進(jìn)可行解，直到可行解為最優(yōu)解，即最優(yōu)派遣方案。

表上作業(yè)法求解流程圖如圖2所示。

3 實驗與結(jié)果分析

3.1 模型參數(shù)設(shè)置

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

3.2 實驗結(jié)果

將蟻群算法的起點設(shè)置為結(jié)點6，終點設(shè)置為結(jié)點34，兩個算法最終的運(yùn)行結(jié)果如圖4所示。

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

以結(jié)點6為起點結(jié)點34為終點，兩種算法各運(yùn)行10次，得到的平均目標(biāo)函數(shù)值如表1所示。

由表1可以發(fā)現(xiàn)，改進(jìn)的蟻群算法和傳統(tǒng)的蟻群算法相比，收斂到的平均目標(biāo)函數(shù)值更小。這是因為改進(jìn)的蟻群算法在啟發(fā)函數(shù)中考慮了路段發(fā)生二次事故的概率，而傳統(tǒng)蟻群算法只考慮下一結(jié)點與當(dāng)前結(jié)點的距離大小，在應(yīng)急救援路徑規(guī)劃中考慮的因素過于單一，從而導(dǎo)致其目標(biāo)函數(shù)值偏高。

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

利用改進(jìn)的蟻群算法對表2中各個救援點到各個事故點進(jìn)行路徑規(guī)劃，得到各條路徑的目標(biāo)函數(shù)值，如表3所示，并結(jié)合表上作業(yè)法進(jìn)行車輛派遣，實驗結(jié)果如表4所示。

表4中，第一行表示勾莊互通救援點派出1輛救援車到半山互通，派出1輛救援車到五?；ネǎ溆嘁来祟愅??？梢钥吹奖砩献鳂I(yè)法較好地解決了多點協(xié)同救援問題。

4 結(jié)束語

本文在經(jīng)典蟻群算法的基礎(chǔ)上，提出改進(jìn)的蟻群算法來解決高速公路多點協(xié)同救援問題，從初始信息素濃度設(shè)置、啟發(fā)函數(shù)、狀態(tài)轉(zhuǎn)移規(guī)則、信息素更新規(guī)則等方面進(jìn)行改進(jìn)，解決了蟻群算法在路徑尋優(yōu)過程中出現(xiàn)的停滯現(xiàn)象、收斂過慢的問題。本文將改進(jìn)的蟻群算法與表上作業(yè)法相結(jié)合，實現(xiàn)了多救援點協(xié)同救援的路徑規(guī)劃功能，為高速公路救援工作爭取了寶貴的時間，具有很大的實用價值。

參考文獻(xiàn)（References）：

[1] 李紫瑤.應(yīng)急救援車輛路徑尋優(yōu)——基于多目標(biāo)改進(jìn)蟻群算法[J].技術(shù)經(jīng)濟(jì)與管理研究，2011.9：7-10

[2] 何勇.應(yīng)急救援物資配送模型及算法研究[D].廣東工業(yè)大學(xué)，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] 王曉剛，韓印.救援車輛多目標(biāo)實時路徑規(guī)劃模型[J].物流科技，2019.42（9）：15-17，31

[5] 肖博.基于多目標(biāo)優(yōu)化的震后應(yīng)急物流路徑規(guī)劃研究[D].長安大學(xué)，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] 陳曉燕，姚高偉，張鯤等.基于遺傳算法的無線傳感器節(jié)點定

位在農(nóng)業(yè)的應(yīng)用[J].軟件，2015.36（4）：1-5

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

[10] 談曉勇，林鷹.基于混沌蟻群算法的應(yīng)急救援車輛調(diào)度優(yōu)化[J].計算機(jī)應(yīng)用研究，2014.31（009）：2640-2643

[11] 韋曉.基于改進(jìn)蟻群算法的應(yīng)急物流車輛路徑問題研究[D].濟(jì)南大學(xué)碩士學(xué)位論文，2015.

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