寧雨舟 趙蕊

（安徽財經(jīng)大學 安徽省蚌埠市 233000）

快遞行業(yè)如今存在的問題以及無人機的優(yōu)勢：

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

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

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

創(chuàng)新部分：

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

1.1 模型構建

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

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

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

圖1

1.3 約束條件

（1）最大載重約束：由于無人機大小以及動力限制，無人機可運送的貨物重量也必須控制在一定的范圍內，否則會增加飛行過程中的安全隱患，同時難以完成正常的配送任務。

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

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

（4）最大轉彎角度約束：為保證無人機在運輸過程中飛行姿態(tài)的穩(wěn)定以及對貨物的保護，其在配送過程中的轉彎角度應當小于其最大轉彎角度。

2 模型求解

2.1 蟻群算法

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

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

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

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

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

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

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

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

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

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

2.1.2 選擇概率

ηij=1 ?dij

2.2 A*算法

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

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

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

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

3 基于A*算法的蟻群算法改進

3.1 殘留信息量改進

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

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

3.2 選擇概率改進

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

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

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

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

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

然后以一定的權重將這兩點加入到代價函數(shù)中。

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

圖2

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

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

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

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

mi表示無人機在配送點i 的重量，（xi，yi）表示無人機在配送點i 的坐標，（xj，yj）表示無人機在配送點j 的坐標。配送點i 和配送點j 是配送路徑中兩個相連續(xù)的配送點。當i=0 時，則認為是起點。

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

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

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

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

圖3

3.6 算法流程

實驗仿真：

3.6.1 初始化參數(shù)

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

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

3.6.2 實驗仿真數(shù)據(jù)

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

如圖4所示。

圖4

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

如圖5所示。

圖5

（3）實驗分析。

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

4 結語

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