基于改進(jìn)蟻群算法的物流無(wú)人機(jī)路徑規(guī)劃

寧雨舟 趙蕊

（安徽財(cái)經(jīng)大學(xué) 安徽省蚌埠市 233000）

快遞行業(yè)如今存在的問(wèn)題以及無(wú)人機(jī)的優(yōu)勢(shì)：

（1）快遞人員送貨車輛不統(tǒng)一，類型較為復(fù)雜。在城區(qū)中人員來(lái)往密集，街上車流量較大，傳統(tǒng)車輛送貨方式不僅效率低下，而且容易發(fā)生交通事故。而無(wú)人機(jī)相較于這種傳統(tǒng)的運(yùn)送方式，不僅運(yùn)輸效率高，而且其可以不受地面交通情況的影響，安全系數(shù)也大大提高。

（2）安全問(wèn)題和技術(shù)問(wèn)題。電子商務(wù)的迅速發(fā)展，快遞運(yùn)輸過(guò)程中的安全問(wèn)題也越來(lái)越被人們所重視；但大部分情況下快遞人員都是直接上崗工作的，專業(yè)技能有限。而無(wú)人機(jī)對(duì)于人力的要求低，對(duì)技術(shù)要求同樣不高，一個(gè)快遞員可以同時(shí)操作數(shù)十架無(wú)人機(jī)進(jìn)行送貨，大大降低了運(yùn)送成本，同時(shí)使貨物在運(yùn)送過(guò)程中的安全性得到提高。

（3）鄉(xiāng)村地區(qū)派件難，運(yùn)輸成本高。在經(jīng)濟(jì)發(fā)達(dá)的城區(qū)快遞配送仍存在問(wèn)題的今天，經(jīng)濟(jì)落后的鄉(xiāng)村地區(qū)快遞配送更是難上加難，雖然鄉(xiāng)村人流量較小，但是鄉(xiāng)村客戶分散，物流集中點(diǎn)少，且各配送點(diǎn)之間距離較遠(yuǎn)，采用車輛運(yùn)輸不僅會(huì)出現(xiàn)繞路，還使得配送成本大幅度提高。而無(wú)人機(jī)的主要能源為電能，可以節(jié)省成本，同時(shí)，無(wú)人機(jī)可以去到汽車難以去往的地方，在偏遠(yuǎn)山區(qū)及農(nóng)村的快遞配送過(guò)程中將會(huì)發(fā)揮更大優(yōu)勢(shì)。

創(chuàng)新部分：

1 無(wú)人機(jī)的路線規(guī)劃

1.1 模型構(gòu)建

問(wèn)題描述：假設(shè)在某個(gè)城市區(qū)域內(nèi)進(jìn)行無(wú)人機(jī)配送任務(wù)，其中物流倉(cāng)庫(kù)與若干起降點(diǎn)的坐標(biāo)均已知，現(xiàn)在需要尋找一條在無(wú)人機(jī)從物流倉(cāng)庫(kù)出發(fā)到達(dá)各起降點(diǎn)卸載貨物，并返回物流倉(cāng)庫(kù)的一條最短最優(yōu)路線。如何在保證飛機(jī)安全飛行，供電充足的情況下尋找到一條最優(yōu)最短路徑將是本實(shí)驗(yàn)的重點(diǎn)。蟻群算法是受到20所示50年代仿生學(xué)的啟發(fā)，由意大利學(xué)者M(jìn).Dorigo 等首先提出的一種新型的模擬進(jìn)化算法，該算法在求解組合問(wèn)題中表現(xiàn)出優(yōu)良的特性。因此，蟻群算法也一直被用來(lái)解決路徑規(guī)劃問(wèn)題。蟻群算法求解路徑問(wèn)題的關(guān)鍵部分是在信息素矩陣的更新。更新的結(jié)果直接導(dǎo)致蟻群算法的最優(yōu)路線。每一代螞蟻行走的路線表示待優(yōu)化的可行解，蟻群行走的所有路徑構(gòu)成解空間，每一只螞蟻行走的時(shí)候都會(huì)釋放一種信息素。隨著時(shí)間的推進(jìn)，每一代螞蟻?zhàn)哌^(guò)的相同路徑的信息素就會(huì)越來(lái)越高（當(dāng)然也會(huì)伴有一定數(shù)量的信息素?fù)]發(fā)），那么信息素較高的路徑就有更大概率被選擇，從而找出更優(yōu)路線。

1.2 環(huán)境模型構(gòu)建

若要對(duì)無(wú)人機(jī)的配送路徑進(jìn)行科學(xué)的規(guī)劃，首先要對(duì)城市的三維飛行環(huán)境進(jìn)行建模。本實(shí)驗(yàn)采用柵格法對(duì)城市模型進(jìn)行建模，柵格法是利用VB 等軟件對(duì)地圖建模的一種方法，簡(jiǎn)單來(lái)說(shuō)就是將障礙物模擬成小方格的集合，相當(dāng)于將場(chǎng)景的所有事物進(jìn)行二值化替代，障礙物為1，非障礙物為0。假設(shè)該城市區(qū)域是一個(gè)三維空間中的長(zhǎng)方體，其長(zhǎng)寬高分別由a，b，c 個(gè)正方體柵格所組成。其中a=ROUNDUP（xmax/Mlength），b=ROUNDUP（ymax/Mlength），c=ROUNDUP（zmax/Mlength），Mlength為每個(gè)柵格正方體的長(zhǎng)度，xmax，ymax，zmax，為三維長(zhǎng)方體模型的長(zhǎng)寬高，ROUNDUP（）為向上取整函數(shù)。柵格法構(gòu)建完成后飛行的環(huán)境如圖1所示，當(dāng)無(wú)人機(jī)從物流倉(cāng)庫(kù)出發(fā)后，經(jīng)歷各起降點(diǎn)選擇一條最優(yōu)最短的路徑飛行。

圖1

1.3 約束條件

（1）最大載重約束：由于無(wú)人機(jī)大小以及動(dòng)力限制，無(wú)人機(jī)可運(yùn)送的貨物重量也必須控制在一定的范圍內(nèi)，否則會(huì)增加飛行過(guò)程中的安全隱患，同時(shí)難以完成正常的配送任務(wù)。

（2）最大續(xù)航約束：無(wú)人機(jī)電池的存儲(chǔ)能力有限，考慮到無(wú)人機(jī)的起降以及在特殊情況下的懸停造成的耗能，無(wú)人機(jī)的整個(gè)配送過(guò)程中的耗能應(yīng)為其電池最大儲(chǔ)能的85%～90%。

（3）最大高度約束：通過(guò)柵格法對(duì)環(huán)境模型的構(gòu)建，無(wú)人機(jī)在配送過(guò)程中高度的確定除了不能超過(guò)該城市約定的最大高度外，還應(yīng)考慮到配送路徑上各建筑的高度。

（4）最大轉(zhuǎn)彎角度約束：為保證無(wú)人機(jī)在運(yùn)輸過(guò)程中飛行姿態(tài)的穩(wěn)定以及對(duì)貨物的保護(hù)，其在配送過(guò)程中的轉(zhuǎn)彎角度應(yīng)當(dāng)小于其最大轉(zhuǎn)彎角度。

2 模型求解

2.1 蟻群算法

2.1.1 傳統(tǒng)的信息素濃度

在真實(shí)環(huán)境里，隨著時(shí)間的推移螞蟻釋放的信息素會(huì)逐漸蒸發(fā)。假設(shè)蒸發(fā)速度一定，那么在相同時(shí)間內(nèi)，信息素濃度越高的路徑殘留的信息量則越多。這一特性對(duì)下一代螞蟻尋路有很好的指導(dǎo)作用。據(jù)此，給出信息素的更新公式：

式中，τij(t)為t 時(shí)刻在ij 連線上殘留的信息量，初始時(shí)刻設(shè)每條路徑上的信息量相等，即τij(t)=C（C 為常數(shù)），ρ 為新系數(shù)殘留系數(shù)（取值在0～1 之間）， 表示第k 只螞蟻在本次循環(huán)中留在路徑ij 上的信息量。

在這些計(jì)算公式的假設(shè)下，用不同的方式設(shè)置這些參數(shù)，即有以下三種模型：

（1）Ant-Circle System 模型（也稱蟻圈模型）。根據(jù)M.Dorigo 的Ant-Circle System 模型，有：

式中Lk為第k 只螞蟻在本次循環(huán)中所走路徑長(zhǎng)度，Q 為常量。

（2）Ant-Quantity System 模型（也稱蟻量模型）。

式中dij為節(jié)點(diǎn)i 到節(jié)點(diǎn)j 之間的距離。

（3）Ant-Density System 模型（也稱蟻密模型）。

在以上三種模型中，后兩種模型都是利用的局部信息，而第一種模型利用的是整體信息。

2.1.2 選擇概率

ηij=1 ?dij

2.2 A*算法

A*被廣泛應(yīng)用于路徑規(guī)劃的啟發(fā)式算法，通過(guò)估價(jià)函數(shù)f*判斷無(wú)人機(jī)的飛行軌跡點(diǎn)的優(yōu)劣，引導(dǎo)算法快速收斂，即：

f(x)=g(x)+h(x)

g(x)為起點(diǎn)到當(dāng)前節(jié)點(diǎn)的實(shí)際代價(jià)，h(x)為當(dāng)前節(jié)點(diǎn)到終點(diǎn)的預(yù)估代價(jià)，即啟發(fā)函數(shù)。

用A*算法進(jìn)行路徑搜索時(shí)，可將搜尋區(qū)域簡(jiǎn)化成一組可量化的節(jié)點(diǎn)，查找最短路徑時(shí)，從起點(diǎn)開(kāi)始，檢查其相鄰的方格，然后向四周擴(kuò)展，直至找到目標(biāo)。

3 基于A*算法的蟻群算法改進(jìn)

3.1 殘留信息量改進(jìn)

設(shè)m 為蟻群中螞蟻的數(shù)量，n 為包含配送中心在內(nèi)的所有配送點(diǎn)的數(shù)量，dij(i,j=1,2,3,4,...,n)為配送點(diǎn)i 到配送點(diǎn)j 的距離，bi(t)為t 時(shí)刻位于配送點(diǎn)i 的螞蟻只數(shù)。如果在時(shí)間間隔（t，t+1）中，m 只螞蟻都從當(dāng)前城市選擇下一個(gè)城市，則經(jīng)過(guò)n 個(gè)時(shí)間間隔，所有的螞蟻都走完n 個(gè)城市，構(gòu)成一輪循環(huán)，此時(shí)按照以下方法修改各條路徑上的殘留信息：

式中，L.set為所有螞蟻經(jīng)過(guò)路徑ij 點(diǎn)在本次循環(huán)中所走路徑長(zhǎng)度L 的集合。

3.2 選擇概率改進(jìn)

f(xj)為估價(jià)函數(shù)，通常估價(jià)函數(shù)越小越容易被選擇，所以這里使用估價(jià)函數(shù)的倒數(shù)。

3.3 估價(jià)函數(shù)——f(xj)

f(xj)=g(xj)+h(xj)，通常情況下取啟發(fā)式函數(shù)h(xj)=djs(djs為當(dāng)前位置到終點(diǎn)的距離），但由于該路徑起點(diǎn)和終點(diǎn)是同一個(gè)位置，不能用歐氏距離求解當(dāng)前位置到終點(diǎn)的距離。同時(shí)，配送問(wèn)題僅僅只考慮距離問(wèn)題遠(yuǎn)遠(yuǎn)不夠，因此，設(shè)置代價(jià)函數(shù)時(shí)考慮以下兩點(diǎn)：

（1）距離某兩個(gè)配送點(diǎn)距離相同，優(yōu)先考慮配送較重的物件。

（2）全局配送距離的能耗。

然后以一定的權(quán)重將這兩點(diǎn)加入到代價(jià)函數(shù)中。

如圖2所示，如果L1=L4，在配送點(diǎn)1 可卸貨物重量m1 大于在配送點(diǎn)m3 可卸貨物重量，那么按照?qǐng)D中配送方式相比于從“起點(diǎn)→配送點(diǎn)3 →配送點(diǎn)2 →配送點(diǎn)1 →終點(diǎn)”將會(huì)更加節(jié)能。

圖2

據(jù)此設(shè)置代價(jià)函數(shù)f(xj)如下：

f(xj)=μ*g(xj)+λ*h(xj)

μ、λ 是對(duì)代價(jià)函數(shù)g(xj)和啟發(fā)式函數(shù)h(xj)設(shè)置的權(quán)重。滿足：μ+λ=1 且λ>0.5。

3.4 代價(jià)函數(shù)——g(x)

mi表示無(wú)人機(jī)在配送點(diǎn)i 的重量，（xi，yi）表示無(wú)人機(jī)在配送點(diǎn)i 的坐標(biāo)，（xj，yj）表示無(wú)人機(jī)在配送點(diǎn)j 的坐標(biāo)。配送點(diǎn)i 和配送點(diǎn)j 是配送路徑中兩個(gè)相連續(xù)的配送點(diǎn)。當(dāng)i=0 時(shí)，則認(rèn)為是起點(diǎn)。

3.5 啟發(fā)式函數(shù)——h(xj)

h(xj)=mj*（Lk-d0j）

Lk表示螞蟻在本次循環(huán)中所走過(guò)的路勁長(zhǎng)度，d0j表示起始點(diǎn)到配送點(diǎn)j 的距離。

如圖3所示，如果L1=L4，在配送點(diǎn)1 可卸貨物重量m1 大于在配送點(diǎn)m3 可卸貨物重量，那么按照?qǐng)D中配送方式相比于從“起點(diǎn)→配送點(diǎn)3 →配送點(diǎn)2 →配送點(diǎn)1 →終點(diǎn)”將會(huì)更加節(jié)能。

圖3

3.6 算法流程

實(shí)驗(yàn)仿真：

3.6.1 初始化參數(shù)

本次實(shí)驗(yàn)在matalb 軟件下進(jìn)行仿真，用m×m 大小的宮格模擬試驗(yàn)環(huán)境，黑色方格表示障礙物，白色方格表示可行點(diǎn)，紅色方格則表示算法走過(guò)的路徑。最大迭代次數(shù)Nmax為100，每條路徑的初始信息量C 為8，初始無(wú)人機(jī)數(shù)量m 為50，L.set，allowed集合初始化為空。

參數(shù)參數(shù)數(shù)值α 2 β 4 μ 0.4 γ 0.6 ρ 0.5

3.6.2 實(shí)驗(yàn)仿真數(shù)據(jù)

（1）未優(yōu)化仿真路徑；

如圖4所示。

圖4

（2）經(jīng)優(yōu)化后仿真路徑；

如圖5所示。

圖5

（3）實(shí)驗(yàn)分析。

改進(jìn)的蟻群算法計(jì)算出可行節(jié)點(diǎn)的選擇概率之后，使用輪盤(pán)賭對(duì)可行解點(diǎn)進(jìn)行選擇，經(jīng)過(guò)一輪循環(huán)之后，構(gòu)建出一組可行解。通過(guò)以上實(shí)驗(yàn)數(shù)據(jù)分析得出：改進(jìn)后的蟻群算法收斂速度更加穩(wěn)定迅速，尋找最優(yōu)路徑的能力相較于傳統(tǒng)的蟻群算法較為顯著。

4 結(jié)語(yǔ)

本文針對(duì)城市環(huán)境中無(wú)人機(jī)的路徑規(guī)劃問(wèn)題，利用柵格法對(duì)城市環(huán)境進(jìn)行三維模型構(gòu)建，同時(shí)考慮到無(wú)人機(jī)在運(yùn)輸過(guò)程最大載重，最大續(xù)航，最大高度，最大轉(zhuǎn)彎角度等約束條件，提出了一種基于A*算法的改進(jìn)蟻群算法。在模型的求解中，通過(guò)對(duì)殘留信息量以及選擇概率的改進(jìn)，引導(dǎo)系統(tǒng)向最優(yōu)解的方向進(jìn)化。引入估價(jià)函數(shù)，代價(jià)函數(shù)，啟發(fā)式函數(shù)，使無(wú)人機(jī)在路徑規(guī)劃以及能源消耗方面更具優(yōu)勢(shì)。仿真結(jié)果表明，改進(jìn)的蟻群算法在路徑點(diǎn)數(shù)、時(shí)間規(guī)劃、能源消耗方面都具有明顯減少。證明了該改進(jìn)算法的可應(yīng)用性。