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

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

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

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

1 災(zāi)后救援的車輛路徑優(yōu)化模型

傳統(tǒng)蟻群算法適用于數(shù)據(jù)較小的道路地圖，在道路地圖過大時，道路數(shù)據(jù)的建立需要很大的內(nèi)存和時間，在路徑尋優(yōu)時也需要更多時間達(dá)到迭代收斂，且在較寬道路上迭代出的路徑呈曲折狀，不符合車輛通行的實(shí)際情況。為此，在傳統(tǒng)蟻群算法的基礎(chǔ)上，結(jié)合運(yùn)籌學(xué)中圖論，使螞蟻在進(jìn)行道路尋優(yōu)時從原先的路徑長度、路徑遺留信息素濃度轉(zhuǎn)變?yōu)榈缆饭?jié)點(diǎn)之間的距離長度、由路徑信息素濃度演變而來的道路節(jié)點(diǎn)重要程度分布，以便建立災(zāi)害情況下車輛通行的相關(guān)約束條件。

災(zāi)害發(fā)生時，時間為路徑選擇的最優(yōu)級，考慮到道路寬度對車速的影響，最優(yōu)路徑不一定為最短路徑。因此，在傳統(tǒng)蟻群算法模型的基礎(chǔ)上增加圖論約束，約束模型如下：

(1)

(2)

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

(3)

(4)

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

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

(5)

(6)

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

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

Mj(t)=τij(t)

(7)

M1(t)=c

(8)

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

(9)

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

2 基于圖論的改進(jìn)蟻群算法

算法流程如下：

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

圖1 道路節(jié)點(diǎn)示意圖

(2) 在圖1左側(cè)設(shè)置起點(diǎn)，右側(cè)設(shè)置終點(diǎn)。

(3) 設(shè)置迭代次數(shù)K、螞蟻數(shù)量N，利用蟻群算法讓螞蟻從起點(diǎn)出發(fā)。

(4) 在已有節(jié)點(diǎn)通行數(shù)據(jù)Lij下進(jìn)行迭代尋優(yōu)，螞蟻每次從節(jié)點(diǎn)i到節(jié)點(diǎn)i+1時對行進(jìn)路程和時間進(jìn)行記錄并存儲到Data文件中。

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

(6) 每只螞蟻同一次路徑搜尋不得兩次經(jīng)過同一個節(jié)點(diǎn)，當(dāng)無路可走或到達(dá)目標(biāo)點(diǎn)時，尋找終止。

(7) 每次迭代選擇多只螞蟻的路徑尋優(yōu)結(jié)果，從中選擇最優(yōu)路徑，同時更新信息素矩陣，當(dāng)?shù)呌谑諗炕蜻_(dá)到迭代次數(shù)時，結(jié)束迭代，輸出最優(yōu)路徑(見圖2)。

圖2 改進(jìn)蟻群算法的計(jì)算流程

3 仿真實(shí)現(xiàn)

對地圖中道路交叉口進(jìn)行節(jié)點(diǎn)標(biāo)記，并存儲到節(jié)點(diǎn)關(guān)系矩陣中。為便于后續(xù)仿真試驗(yàn)，補(bǔ)齊上下共4個處于主干道的節(jié)點(diǎn)。仿真試驗(yàn)中共計(jì)68個節(jié)點(diǎn)(見圖3)，起點(diǎn)位于左側(cè)，終點(diǎn)位于右側(cè)。同時設(shè)置3個無人機(jī)探測障礙點(diǎn)。仿真區(qū)域?yàn)? km×3.5 km。

圖3 限制受災(zāi)不予通行道路后道路節(jié)點(diǎn)示意圖

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

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

圖4 一般情況下車輛路徑規(guī)劃圖

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

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

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

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

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

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

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

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

圖10 綜合情況下車輛路徑規(guī)劃圖

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

傳統(tǒng)蟻群算法下路徑規(guī)劃見圖12，迭代情況及路徑長度見圖13。從圖12、圖13可看出：采用傳統(tǒng)蟻群算法進(jìn)行路徑規(guī)劃，車輛行駛路徑存在多次轉(zhuǎn)折，這是因?yàn)樵诟駯诺貓D中，白色道路并不一定是由單個格柵為道路寬度來組成，而可能是由2個及以上格柵為道路寬度來組成；迭代200次時趨于收斂，但并未完全收斂，由于道路中存在的折線路段較多，且路徑不是最優(yōu)，規(guī)劃的最終路徑長度為8.393 km。

圖12 傳統(tǒng)蟻群算法路徑規(guī)劃圖

圖13 傳統(tǒng)蟻群算法迭代情況及路徑長度

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

表1 不同算法仿真結(jié)果對比

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

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

圖14 車輛行駛路徑中障礙點(diǎn)分布

4 結(jié)語

針對災(zāi)害情況下車輛路徑優(yōu)化問題，考慮災(zāi)后救援時效性和救援道路通過性動態(tài)化等因素，建立車輛路徑優(yōu)化模型，采用基于圖論的改進(jìn)蟻群算法進(jìn)行車輛路徑規(guī)劃。仿真結(jié)果表明，采用該算法進(jìn)行救援車輛路徑優(yōu)化，能保證救援車輛安全、迅速地到達(dá)救援目的地。

下一步可考慮無人機(jī)和車輛協(xié)同問題，通過無人機(jī)的圖像識別和優(yōu)化無人機(jī)對受災(zāi)地區(qū)的巡回路線，使車載中心盡快找到新的最優(yōu)路徑，縮短車輛到達(dá)救援點(diǎn)的時間。