災害情況下基于改進蟻群算法的救援車輛路徑優化

鄧子杰，曾傳華，柴李，申航宇

(西華大學 汽車與交通學院，四川 成都 610065)

近年來，地震、雪災、洪災、泥石流等自然災害頻頻發生，除造成房屋倒塌、道路及設施損壞外，還引發大規模地質災害，對社會帶來不可估量的傷害。自然災害發生后，最重要的任務是救援，然而災后情況復雜，給救援帶來很大阻撓。減少救援時間是災后救援至關重要的一環，救援車輛路徑優化又是救援時間能否加快的關鍵。如何利用最新的路況信息規劃到達救災目的地的最佳行駛路徑，并在救援途中根據道路情況動態調整路徑，提高救災工作效率，是救援工作實施的一大核心。

蟻群算法是根據螞蟻覓食規律提出的一種智能算法，能解決Dijkstra算法和A*算法不能解決的大規模多項式復雜程度的非確定性問題。Hsiao Y.T.等在蟻群算法的基礎上提出一種全局尋優算法，在一定程度上解決了蟻群算法在多優化問題上的局部收斂問題；Kammoun H.M.等設計了一種基于蟻群算法和多智能體系結構的車輛自適應導航系統；范炯對傳統蟻群算法的信息素濃度范圍和更新方式進行改進，在一定程度上提高了算法的搜索性能；王曉東等基于傳統蟻群算法，通過節約矩陣和信息素揮發時間曲線來引導螞蟻搜索，一定程度上解決了傳統蟻群算法存在的局部收斂問題；裴曉芳等提出一種基于模糊函數評價的蟻群算法解決路徑規劃問題，在一定程度上提高了迭代初期的收斂速度。以上研究主要針對常規狀態下車輛路徑優化，對災害情況下車輛路徑優化還需進一步研究。該文考慮災害情況下時間緊迫性和道路動態變化等因素，建立災后車輛路徑優化模型，采用改進蟻群算法優化救援車輛路徑。

1 災后救援的車輛路徑優化模型

傳統蟻群算法適用于數據較小的道路地圖，在道路地圖過大時，道路數據的建立需要很大的內存和時間，在路徑尋優時也需要更多時間達到迭代收斂，且在較寬道路上迭代出的路徑呈曲折狀，不符合車輛通行的實際情況。為此，在傳統蟻群算法的基礎上，結合運籌學中圖論，使螞蟻在進行道路尋優時從原先的路徑長度、路徑遺留信息素濃度轉變為道路節點之間的距離長度、由路徑信息素濃度演變而來的道路節點重要程度分布，以便建立災害情況下車輛通行的相關約束條件。

災害發生時，時間為路徑選擇的最優級，考慮到道路寬度對車速的影響，最優路徑不一定為最短路徑。因此，在傳統蟻群算法模型的基礎上增加圖論約束，約束模型如下：

(1)

(2)

式中：MinT為目標函數，即總時間最短；Sij為節點i到節點j的路徑Lij的長度；Vc(t)為t時刻車輛的行駛速度；Scmax為車輛的最大行駛里程；Vc為車輛行駛速度；Vcmax為車輛行駛最大速度；Wij為根據道路像素確定的道路寬度，取為{4,6,8,10} m；Wij(t)為t時刻車輛所在道路寬度；μ為車速控制因子。

(3)

(4)

路徑Lij上信息素濃度更新規則如下：

τij(t+1)=(1-ρ)·τij(t)+Δτij(t),ρ∈(0,1)

(5)

(6)

式中：ρ為信息素揮發因子，其取值范圍為(0,1)；Δτij(t)為全部螞蟻完成一次遍歷后，搜索路徑(i,j)上殘留的信息素總和，即第N只螞蟻在轉移過程中留在路徑Lij上的信息素濃度，初始時刻設置τij(0)=c，Δτij(0)=0。

改進蟻群算法將每條道路上的信息素濃度儲存到蟻群算法節點中，得到Message信息素濃度矩陣Mj。Mj(t)為t時刻Message信息素矩陣中節點j的信息素濃度，反映選擇道路節點的重要程度，計算公式如下：

Mj(t)=τij(t)

(7)

M1(t)=c

(8)

式中：M1(t)=c為起點的信息素濃度。

(9)

式中：Q為信息素強度，為完成一次路徑搜尋后殘留下的信息素總和；LN為當前仿真試驗的螞蟻完成一次搜尋后選取的所有路徑長度。

2 基于圖論的改進蟻群算法

算法流程如下：

(1) 截取GIS地圖中部分道路作為救援車輛路徑研究的道路基礎模型(見圖1)。設置節點時，因地圖上存在一些道路缺口，補齊上方兩處和下方兩處位于主干道的節點，以方便后續車輛路徑仿真實現。

圖1 道路節點示意圖

(2) 在圖1左側設置起點，右側設置終點。

(3) 設置迭代次數K、螞蟻數量N，利用蟻群算法讓螞蟻從起點出發。

(4) 在已有節點通行數據Lij下進行迭代尋優，螞蟻每次從節點i到節點i+1時對行進路程和時間進行記錄并存儲到Data文件中。

(5) 在通過節點i時在節點處將信息素濃度信息轉換為節點重要程度，并儲存到信息素矩陣Message中，當下一只螞蟻位于i時，螞蟻便可根據其可通行的所有節點的信息素濃度情況選擇下一個節點。

(6) 每只螞蟻同一次路徑搜尋不得兩次經過同一個節點，當無路可走或到達目標點時，尋找終止。

(7) 每次迭代選擇多只螞蟻的路徑尋優結果，從中選擇最優路徑，同時更新信息素矩陣，當迭代趨于收斂或達到迭代次數時，結束迭代，輸出最優路徑(見圖2)。

圖2 改進蟻群算法的計算流程

3 仿真實現

對地圖中道路交叉口進行節點標記，并存儲到節點關系矩陣中。為便于后續仿真試驗，補齊上下共4個處于主干道的節點。仿真試驗中共計68個節點(見圖3)，起點位于左側，終點位于右側。同時設置3個無人機探測障礙點。仿真區域為6 km×3.5 km。

圖3 限制受災不予通行道路后道路節點示意圖

道路寬度及通行關系情況根據道路像素組成大小儲存在Width矩陣中，迭代次數K=200 次，仿真試驗螞蟻個數N=500個；信息素起始濃度τij(0)=1；Mj(t)=1；信息素揮發因子ρ=0.3；信息啟發和期望啟發因子α、β分別取1和7；Q=1；Vcmax=120 km/h；Scmax=500 km；Wij={4,6,8,10} m；μ=15。設置4種情況進行仿真，并與傳統蟻群算法進行對比，驗證所建模型的有效性。

情況1：限制受災不予通行道路、限制車輛通行最快速度和行駛里程(一般情況)。該情況下車輛路徑規劃見圖4，迭代情況及路徑長度見圖5。從圖4、圖5可看出：車輛會較高概率選擇路徑相對短的小路；迭代200次后趨于收斂，最終路徑長度為7.098 km。

圖4 一般情況下車輛路徑規劃圖

圖5 一般情況下迭代情況與路徑長度

道路寬度影響救援車輛的通行速度、通行安全性等，擬定路網中道路有4 m、6 m、8 m、10 m 4種寬度。情況2：設定道路寬度為4 m的路徑為不安全通行道路，不予通行，通行條件為Wij≥6 m。限制道路通行情況下車輛路徑規劃見圖6，迭代情況及路徑長度見圖7。從圖6、圖7可看出：車輛選擇道路時會避開小路而優先選擇副干道和主干道；200次迭代后已收斂，最終路徑長度為7.204 km，車輛行駛時間為0.161 3 h。

圖6 限制道路通行情況下車輛路徑規劃圖

圖7 限制道路通行情況下迭代情況與路徑長度

情況3：限制通行速度。前兩種情況的目標函數是路程最短，而時間是災害發生后救援救災中的重要因素。根據道路寬度與車速的關系，道路越寬，車速越快。限制通行速度情況下車輛路徑規劃見圖8，迭代情況及路徑長度見圖9。從圖8、圖9可看出：限制速度情況下車輛會根據車速選擇耗時更短的道路；200次迭代后已經收斂，最終路徑長度為7.375 km，車輛行駛時間為0.121 1 h。

圖8 限制通行速度情況下車輛路徑規劃圖

圖9 限制通行速度情況下迭代情況與路徑長度

情況4：限制所有約束條件(綜合情況)。綜合情況下車輛路徑規劃見圖10，迭代情況及路徑長度見圖11。從圖10、圖11可看出：綜合情況下車輛路徑規劃與限制速度時最佳優化路線相同；200次迭代后已收斂，在限制因素增加的情況下，路線的起始長度與最終路徑長度相差不大，最終路徑長度為7.375 km，車輛行駛時間為0.121 1 h。

圖10 綜合情況下車輛路徑規劃圖

圖11 綜合情況下迭代情況與路徑長度

傳統蟻群算法下路徑規劃見圖12，迭代情況及路徑長度見圖13。從圖12、圖13可看出：采用傳統蟻群算法進行路徑規劃，車輛行駛路徑存在多次轉折，這是因為在格柵地圖中，白色道路并不一定是由單個格柵為道路寬度來組成，而可能是由2個及以上格柵為道路寬度來組成；迭代200次時趨于收斂，但并未完全收斂，由于道路中存在的折線路段較多，且路徑不是最優，規劃的最終路徑長度為8.393 km。

圖12 傳統蟻群算法路徑規劃圖

圖13 傳統蟻群算法迭代情況及路徑長度

根據相關文獻和存在障礙物的較小地圖下仿真試驗結果，增加迭代次數可能會在一定程度上改善轉折情況，但不會完全消除。而采用基于圖論的改進蟻群算法可避免這種現象的發生。由于道路提取時存在誤差，在很多道路中存在斷點，這種存在斷點的道路在路徑尋優時不滿足通行條件，故采用傳統算法仿真時會形成錯誤規劃。采用改進蟻群算法可規避這種情況。2種算法的仿真結果對比見表1。

表1 不同算法仿真結果對比

從表1可看出：傳統蟻群算法下車輛行駛路徑最長；采用改進蟻群算法，在限制道路通行情況下，因車輛不再選擇道路最窄的路段，車輛行駛總路程比普通情況有所增加；在限制道路通行速度和綜合情況(限制所有約束條件)下，車輛行駛總路程相對于其他兩種情況有所增加，但在目標函數時間最短的限制下，所選擇道路的狀況較好，在犧牲路徑長度的情況下可縮短行駛時間，從而保障災害情況下救援救災車輛的時效性和安全性，保證救援車輛能更安全、迅速地到達救援目的地。

當車輛在救援途中識別到當前道路存在障礙點(見圖14)無法滿足通行條件時，通過無人機巡回飛行等方法獲取備選道路信息，基于改進蟻群算法，重新規劃后續車輛行駛路徑。車輛根據障礙點信息重新規劃的路徑見圖15，迭代情況及路徑長度見圖16。避開障礙點后規劃的行駛路徑長度為8.594 km，行駛時間為0.144 1 h。

圖14 車輛行駛路徑中障礙點分布

4 結語

針對災害情況下車輛路徑優化問題，考慮災后救援時效性和救援道路通過性動態化等因素，建立車輛路徑優化模型，采用基于圖論的改進蟻群算法進行車輛路徑規劃。仿真結果表明，采用該算法進行救援車輛路徑優化，能保證救援車輛安全、迅速地到達救援目的地。

下一步可考慮無人機和車輛協同問題，通過無人機的圖像識別和優化無人機對受災地區的巡回路線，使車載中心盡快找到新的最優路徑，縮短車輛到達救援點的時間。