基于GA-SA組合算法的山區(qū)復雜環(huán)境無人機起降點選址

李章萍, 賀亞蒙

(中國民航大學交通科學與工程學院, 天津 300300)

隨著前端科技不斷創(chuàng)新,無人機技術不斷成熟,無人機貨運時發(fā)展的新趨勢,發(fā)展無人機貨運,起降點的選址分配是重點環(huán)節(jié),是保證高效安全運輸的關鍵。

目前,中外對于無人機貨運研究的重點主要集中在城區(qū)物流末端配送環(huán)節(jié),王垚等[1]對無人機任務分配問題轉化為多旅行商問題,并將Metropolis準則引入遺傳算法,分別求解不同規(guī)模的旅行商問題,驗證改進算法的適用性;劉書山等[2]針對無人機的航跡優(yōu)化問題,引進了全局搜索能力強的遺傳算法和局部收斂速度快的模擬退火算法相結合的GA-SA組合算法,并將問題轉化為旅行商問題進行求解,結合了兩種算法的優(yōu)勢,本文研究將該思路應用到無人機的選址和任務分配問題研究中;宋育武等[3]無人機群體任務分配研究中建立了整數線性規(guī)劃任務分配模型,但是僅僅以時間消耗最短為目標,目標函數較為單一;Zhang等[4]提出了一種無人機任務分配多目標優(yōu)化方法,即最大化成功分配任務數量、最大化任務效益、最小化資源成本、最小化時間成本,并采用克隆算法進行求解;郭興海等[5]將區(qū)塊鏈思想引入拍賣算法中來解決最后一公里物流配送的任務分配問題,對無人機編隊任務分配進行優(yōu)化計算,計算方式由集成中心式計算轉變?yōu)榉植际接嬎?張連東等[6]以運輸成本最小和客戶滿意度最大為目標函數,設計改進遺傳算法,采用含精英保留的多輪盤賭選擇機制和多種交叉與變異方式相結合的方式。這些有關城區(qū)末端無人機物流配送起降點的研究有些將問題簡化為普通的物流中心選址問題,未考慮無人機飛行的特點以及自身設備的性能約束;有些未能考慮空域的可達性約束對分配結果的影響;有些未考慮備選起降點是否與潛在需求點需求規(guī)模匹配;有些研究考慮約束因素單一,與實際應用場景不符。

由此還可以看出,目前大量無人機應用研究集中在城區(qū)末端物流配送到終端用戶這一環(huán)節(jié)[7],物流前端貨物集散的無人機應用研究較少。特別是中國幅員遼闊,很多貨物產地地處山區(qū),地面交通運輸困難,采用無人機進行前端貨物運輸能夠節(jié)省時間成本;另一方面,在山區(qū)突發(fā)自然災害條件下,特別是發(fā)生地震、泥石流等難以短時間內組織救援人員抵達災害現場,無人機可迅速響應并承擔運輸醫(yī)療救援包以及食物等應急物資的任務[8]。

因此,現從無人機貨運效率出發(fā),以起降點綜合建設成本最低和貨物運輸時間滿意度最大為目標函數,建立無人機起降點的選址和任務分配模型,并設計遺傳算法和模擬退火(GA-SA)組合算法進行模型仿真求解,得到最優(yōu)選址方案,并對相關參數進行靈敏度分析。

1 貨運無人機起降點選址分配問題建模

1.1 問題描述

中國四川雅江縣山區(qū)存在多個貨物運輸需求點,現考慮采用貨運無人機方式進行局部貨物運輸集散。假設該地區(qū)內所有貨物均有能夠垂直起降的充電式中型旋翼無人機完成運輸任務,在具備貨物集散和無人機起降的備選起降點中,得出滿足選址模型要求的最優(yōu)選址分配方案。單架貨運無人機單次貨運任務包含往返雙程,即空載前往運輸需求點和載貨返回無人機起降點。以起降點選址建設綜合成本和運輸貨物時間滿意度為目標,研究該地區(qū)最優(yōu)選址分配方案。

為簡化計算過程,本文研究做以下假設[9]:①為方便計算,將起降中心和貨物運輸需求地區(qū)簡化為點進行討論;②僅考慮單類型貨物運輸;③所有貨運無人機速度恒定;④不考慮貨物裝卸時間和成本。

1.2 貨運無人機起降點選址模型

本文所建立的貨運無人機起降點選址模型是多約束條件下的多目標函數模型,約束條件包含物流中心選址約束和貨運無人機的性能約束兩方面,從起降點的建設綜合成本和貨物運輸時間滿意度兩方面綜合考慮,建立貨運無人機起降點選址分配模型。

1.2.1 目標函數

(1)綜合建設成本。

(1)

式(1)中:Cz綜合建設成本;I為備選起降點集合;i為備選起降點編號;j為運輸需求點編號;xi為0-1變量,表示在備選地址i處是否建立起降點;p為起降中心固定建設成本;aij為0-1變量,表示備選地址i和運輸需求點j是否發(fā)生實際的貨物運輸;Dj為運輸需求點j的運輸需求量;m為貨物在起降點的單位管理費用;dij為備選起降點i到運輸需求點j的距離;c為無人機單位空載飛行成本;n為無人機單位負載運輸成本。

(2)運輸時間滿意度。山區(qū)多為時效性較強類貨物的產地,因此對運輸時間較為敏感,此處考慮貨物對運輸時間的要求,引入運輸時間滿意度作為目標函數之一,本文研究采取線性時間滿意度函數,運輸時間滿意度隨著運輸時間增長而均勻降低,其函數圖像如圖1所示。

(2)

t為運輸時間;s(t)為運輸時間的函數值;t1和t2為分段函數s(t)的分段點

式(2)中:S為全局運輸時間滿意度;S(tij)為單次運輸任務時間滿意度隨時間變化函數;tij為備選地址i和運輸需求點j的單次運輸配送時間;fij為備選地址i和運輸需求點j運輸次數。

(3)

式(3)中:t1和t2為時間滿意度函數中的定值參數。

第二個目標函數為運輸時間滿意度最大化。根據線性運輸時間滿意度的定義,得出無人機單次運輸任務的時間滿意度計算公式,以加權運輸時間滿意度為時間滿意度目標函數。貨物運輸時間tij為

(4)

式(4)中:J為需求點集合;v為無人機的平均飛行速度。

1.2.2 約束條件

(1)點對點約束。每個運輸需求點j由且僅由一個運輸起降點i與之對應,約束條件為

(5)

(2)起降點數量約束。起降點數量不能超過備選場址數量,約束條件為

(6)

式(6)中:Z為備選無人機起降點數量。

(3)起降點容量約束。起降點負責的運輸需求點的貨物不能超過起降點的容量,約束條件為

(7)

式(7)中:Wi為備選起降點容量。

(4)配送范圍約束。所有運輸需求點均應在對應起降點的配送范圍內,約束條件為

aijdij≤Li, ?i∈I,?j∈J

(8)

式(8)中:Li為備選起降點的配送范圍。

(5)運輸時間滿意度約束。對每個運輸需求點j,運輸時間滿意度要達到最低標準,約束條件為

dij≤dmax, ?i∈I,?j∈J

(9)

式(9)中:λi為運輸需求點j的最低時間滿意度;dmax為無人機最大航程。

(6)飛行航程約束。無人機的飛行航程不能超過自身設備性能所允許的最大航程,約束條件為

dij≤dmax, ?i∈I,?j∈J

(10)

(7)無人機飛行高度約束。飛行高度要在指定空域高度內,約束條件為

Hmin≤H≤Hmax

(11)

式(11)中:Hmin和Hmax為允許無人機飛行的最小高度和最大高度。

(8)無人機載重約束。無人機單次運輸不得超大載重,約束條件為

qij≤Q, ?i∈I,?j∈J

(12)

式(12)中:Q為無人機最大載重量。

(9)空域約束。起降點與運輸需求點間的路徑處于不適航或者禁飛空域時,為空域不可達,無法執(zhí)行運輸任務,約束條件為

(13)

1.2.3 模型建立

根據1.4.1節(jié)和1.4.2節(jié)中的目標函數和約束條件的確定,即可建立物流無人機起降點選址分配模型,其模型為

(14)

(15)

s.t.

(16)

(17)

(18)

aijdij≤Li, ?i∈I,?j∈J

(19)

(20)

dij≤dmax, ?i∈I,?j∈J

(21)

Hmin≤H≤Hmax

(22)

qij≤Q, ?i∈I,?j∈J

(23)

βij=1, ?i∈I,?j∈J

(24)

在上述模型中,式(14)和式(15)為模型目標函數,式(16)～式(21)為模型約束條件,包括無人機起降點中心的約束,運輸需求點方面的約束,式(22)～式(24)為物流無人機的性能約束,相關空域是否適航由參數βij體現。

2 算法設計

根據所建立模型,對遺傳算法進行設置,具體設置如下。

2.1 編碼

所求解的問題本質上是一個選址分配問題,編碼要能夠體現每個方案的要求,因此采用符號編碼方法進行編碼。針對染色體個體,設計j+i個基因表示無人機起降點和運輸需求點之間的對應關系,每個染色的1～j個基因表示運輸需求點的編號,(j+1)～(j+i)基因表示備選起降點的編號。現假設有6個運輸需求點,最多允許4個起降點負責貨物運輸任務,那么其中一種可行的染色體表達方式為[1,2,7,3,4,8,5,9,6],其中1～6表示運輸需求點編號,7～9代表無人機起降點,其將6個需求點劃分為4段,表示4個備選起降點全部啟用。第一個起降點編號為7-6=1,表示備選起降點1負責編號1、2的運輸需求點;第二個起降點編號為8-6=2,表示備選起降點2負責編號3、4的運輸需求點;第三個起降點編號為9-6=3,表示備選起降點3負責編號5的運輸需求點,備選起降點4負責編號6的運輸需求點。

2.2 生成初始種群

通過隨機的方式,以空域是否可達為標準判斷備選起降點是否能夠被選擇,在滿足空域約束和其他約束條件的限制下,生成適當規(guī)模大小的初始種群。

2.3 適應度函數設置

由于本文建立的模型是一個多約束條件下的多目標函數,其中包括最小值規(guī)劃問題的同時,還包含了最大值問題,兩個目標函數的函數值量級差距較大,因此借鑒城區(qū)物流無人機任務分配問題,建立兩個目標函數的隸屬度函數[10]進行目標函數模型處理,原理如下。

(1)首先,在滿足選址模型所有約束條件的前提下,分別計算出兩個目標函數的最大值與最小值,并以此結果為分量構建邊界向量即Mmax=(Czmax,Smax),Mmin=(Czmin,Smin),其中Czmax、Czmin為式(1)的最大值和最小值,Smax和Smin為式(2)的最大值和最小值。

(2)其次,定義各目標函數的隸屬度函數為

(25)

(26)

式中:Czs∈[0,1]、Ss∈[0,1]分別為綜合建設成本和運輸時間滿意度目標函數轉化后的隸屬度函數。

(3)最終,將兩個目標函數的隸屬度函數通過分配不同權重轉化成模糊目標函數求解,因此適應度函數設置為

F(x)=max(α1Czs+α2Ss)

(27)

式(27)中:F(x)∈[0,1)為適應度函數;α1和α2分別為建設總成本目標函數和運輸時間滿意度函數的權重系數,α1、α2≥0且α1+α2=1。

2.4 選擇

選擇算子是算法進行迭代的一個關鍵,其本質就是從當前所有的基因池中選擇更適合下一代繁衍的子代作為下一個循環(huán)的父代,直到達到收斂條件,具體操作就是選擇適應度函數值大的,且適應度值與被選中的概率成正相關。本文研究采用輪盤賭法,計算每個個體被選擇進入下一代的概率,即

(28)

式(28)中:Fi為第i個個體的適應度函數值;N為種群規(guī)模大小;Pi為選中第i個個體基因的概率。

2.5 交叉變異

將選擇環(huán)節(jié)中選擇的優(yōu)秀個體進行交叉算子操作,將兩個染色體的基因進行交叉,從而產生基因結構更復雜、個體表現更優(yōu)良的個體,并且按照算法設置的變異概率對基因的片段進行變異操作。

交叉算子操作中,交叉的概率設置會直接對算法的收斂性產生影響,在常規(guī)的遺傳算法中交叉概率設為定值,如果該參數值設置過大會導致算法前期迭代過程收斂速度過快,迭代后期缺少新個體的產生,適應度是過于平緩,可能造成個體表現優(yōu)秀的染色體基因遭到破壞;定值設置過小會導致迭代速度緩慢,效率低下。

根據GA算法交叉的基本原理,本文研究取締傳統(tǒng)算法中交叉概率參數固定的做法,采用自適應交叉概率[11],根據算法中種群迭代過程中適應度值的變化,對交叉概率的值進行動態(tài)調整,提高全局搜索能力。

(29)

式(29)中:Fmax為當前種群個體適應度最大值;Fb為進行交叉操作的個體中的適應度較大值;Fa為每一代種群中的適應度平均值;Pc1、Pc2∈(0,1)為交叉操作的相關概率參數。

采用自適應度動態(tài)交叉概率,能夠效避免只用子代進行篩選時有可能破壞掉“父代出現了適應度很高,但后來由于交叉破壞掉其適應度形成劣勢子代”現象。

2.6 融合算法操作

首先通過改進遺傳算法進行模型的初步求解,將適應度值較高表現優(yōu)良的個體保留下來作為模擬退火算法的初始種群,如此可以提高算法的局部搜索能力。根據初始種群設置初始溫度,設置溫度衰退系數,進行模擬退火操作。初始溫度和退火函數為

(30)

Tk+1=εTk

(31)

Pa=e-ΔF/Tk

(32)

式中:T0為退火操作初始溫度;Tk為經過k次退溫操作后的溫度;ΔF為適應度函數值得極差;Pa為相對接受概率;ε為溫度衰退系數。

2.7 終止條件

達到設置的迭代次數。

3 算例分析

3.1 算例描述及參數設置

為驗證所提模型和算法的有效性,采用MATLAB R2016b進行模型仿真實驗,模擬某山區(qū)40 km×40 km×0.2 km范圍內的無人機貨運場景,現假設該區(qū)域內有50個貨運需求點和5個無人機起降點備選中心,其分布情況如圖2所示。各個需求點的需求量如表1所示。

表1 運輸需求點需求規(guī)模Table 1 Scale of demand

紅色叉號及右邊數字表示運輸需求點及其編號;綠色菱形及右邊數字表示備選無人機起降點及其編號

為盡量貼合無人機貨運中心選址和任務實際規(guī)劃過程,無人機起降點的參數設置如表2所示。

表2 無人機起降點參數設置Table 2 Landing point parameters of take-off

對比目前市場上的無人機機型,對本文研究中采用的無人機進行性能參數設置如表3所示。

表3 無人機參數設置Table 3 Parameters of UAV

有關客戶滿意度函數中的參數設置,每個運輸需求點的最低滿意度取0.5。

第二步采用模擬退火算法的相關參數設置為:初始種群規(guī)模為50,兩個目標函數的隸屬度函數所占權重分別為0.6和0.4,變異概率Pb為0.002;Pc1為0.4;Pc2為0.6;ε為0.99;迭代次數500。

3.2 結果仿真分析

基于以上仿真環(huán)境設置和參數界定,首先通過遺傳算法對模型進行仿真求解,得到一個較優(yōu)解,然后通過模擬退火算法調用遺傳算法的解作為初始解,進行第二步的仿真模擬最終得到無人機起降中心選址和任務分配結果(圖3)。

紅色叉號及右邊數字表示運輸需求點及其編號;綠色菱形及右邊數字表示備選無人機起降點及其編號

由圖3可知,當在5個備選起降中心選擇編號為2、3、4的無人機起降點時,適應度函數最優(yōu)為0.657 15,對應的起降點建設總成本為996 263.233 6元,運輸時間滿意度為0.895 17。

為分析本文采取的組合算法的優(yōu)良性,保持仿真環(huán)境和參數不變,單獨采用模擬退火算法進行模型求解,并對兩種算法的迭代過程和結果進行比較,如圖4所示,對比中能夠直觀看出,本文研究中采用的組合算法迭代結果最終的適應度函數值更高,迭代過程收斂速度更快,對模型的仿真效果更好,表明采用的GA-SA組合算法在研究無人機起降中心選址和任務分配問題,具有較好的適用性。

圖4 算法迭代過程對比Fig.4 Iterative comparison

3.3 參數靈敏度分析

在利用組合算法對模型進行仿真分析時,參數的設置會對收斂速度和最終迭代結果產生影響。本文采用控制變量法,探究空域約束和需求量變化對規(guī)劃結果的影響[12]。

3.3.1 空域約束分析

通過設置0-1矩陣來表示運輸需求點和無人機起降點備選中心的可達性,通過調整可達矩陣來實現空域條件的改變,分別增加和減少禁飛區(qū)域,圖5和圖6分別為減少和增加禁飛區(qū)域后的布局規(guī)劃方案。

圖5 減少禁飛區(qū)域Fig.5 Reduce no-fly airspace

圖6 增加禁飛區(qū)域Fig.6 Increase no-fly airspace

調整可達矩陣減少禁飛區(qū)域的情況下,選擇編號1、3、4的起降點為最優(yōu)方案,布局方案的建設成本為925 263.217元,運輸時間滿意度為0.915 11;增加禁飛區(qū)域時,選擇編號1、2、5的起降點為最優(yōu)方案,最優(yōu)布局方案的建設成本為1 119 670.093 6元,運輸時間滿意度為0.730 82。

綜上分析,不同空域約束條件下,山區(qū)無人機起降中心選址以及任務分配結果會有較大差異。當禁飛區(qū)域較多,可達矩陣的可達性較弱,無人機起降中心會負擔距離較遠的運輸需求點,飛行里程增加,導致成本升高,全局運輸時間滿意度降低;反之,整個區(qū)域可達性增強,無人機起降中心會率先負責較近的運輸需求點,飛行里程減少,成本降低,全局運輸時間滿意度提高。因此,山區(qū)的地形環(huán)境越復雜,模型中的空域約束條件增多,無人機起降中心的建設成本增加,全局運輸時間滿意度降低。

3.3.2 需求規(guī)模分析

在最初參數不變的基礎上對需求點的需求量擴大到原來的2倍和縮小至原來的1/2來對需求規(guī)模進行靈敏度分析[13]。圖7和圖8分別是增加需求規(guī)模和減少需求規(guī)模后的布局方案,經過算法模型求解,在擴大需求規(guī)模的情況下,綜合建設成本為2 011 439. 956 9元,運輸時間滿意度為0.800 059;減小需求規(guī)模的情況下,綜合建設成本為620 733.308元,運輸時間滿意度為0.935 44。

圖7 增加需求規(guī)模Fig.7 Increase the size of demand

圖8 減少需求規(guī)模Fig.8 Decrease the size of demand

當需求規(guī)模不同時選址布局方案也會發(fā)生變化,隨著需求規(guī)模擴大,起降點運輸任務量增加,綜合建設成本隨之升高,當需求規(guī)模超過一定范圍時,因為備選起降點的規(guī)模并未改變,需求點不能夠被就近的起降點滿足,導致選址分配結果較原方案會有較大改變;當需求規(guī)模縮小,建設成本會隨之降低,運輸時間滿意的也得到提升,但是備選起降點的容量過剩,且個別起降點負擔較重,整個布局并不均衡,因此備選起降點的選擇要與需求規(guī)模相匹配[14]。

4 結論

以建設總成本最小和運輸時間滿意度最大為目標函數,綜合考慮無人機的性能與空域限制等問題,構建了物流前端無人機貨運起降點的選址和任務分配模型,設計改進了遺傳算法和模擬退火算法的組合算法進行求解,并通過仿真驗證了該算法在解決此類問題具有較高的適用性和模型的合理性,并得出以下結論。

(1)空域約束條件不同的情況下,起降點的建設成本會有較大差異。山區(qū)地形環(huán)境越復雜,飛行條件越苛刻,選址模型的空域約束越多,起降點的建設成本越高。

(2)當需求量的需求規(guī)模不同時,選址布局方案也會有所不同。當需求規(guī)模過大時,備選起降點規(guī)模未改變,需求點需求難以滿足,整體時間滿意度降低;當需求規(guī)模變小時,備選點容量過剩,局部起降點負擔過重,選址布局失調,因此備選起降點要與需求點的需求規(guī)模相匹配。

隨著物流產業(yè)的不斷發(fā)展,無人機物流是大勢所趨,目前有關城區(qū)末端配送無人機應用研究有很多,但是受人口密度,空域限制等諸多因素影響,全面普及需要一定的時間,而在山區(qū)等地進行無人機貨運是無人機發(fā)展應用的新趨勢,在服務經濟等同時,還能在自然災害突發(fā)時為公共安全提供保證。