基于GA-SA組合算法的山區(qū)復(fù)雜環(huán)境無(wú)人機(jī)起降點(diǎn)選址

李章萍, 賀亞蒙

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

隨著前端科技不斷創(chuàng)新,無(wú)人機(jī)技術(shù)不斷成熟,無(wú)人機(jī)貨運(yùn)時(shí)發(fā)展的新趨勢(shì),發(fā)展無(wú)人機(jī)貨運(yùn),起降點(diǎn)的選址分配是重點(diǎn)環(huán)節(jié),是保證高效安全運(yùn)輸?shù)年P(guān)鍵。

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

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

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

1 貨運(yùn)無(wú)人機(jī)起降點(diǎn)選址分配問(wèn)題建模

1.1 問(wèn)題描述

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

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

1.2 貨運(yùn)無(wú)人機(jī)起降點(diǎn)選址模型

本文所建立的貨運(yùn)無(wú)人機(jī)起降點(diǎn)選址模型是多約束條件下的多目標(biāo)函數(shù)模型,約束條件包含物流中心選址約束和貨運(yùn)無(wú)人機(jī)的性能約束兩方面,從起降點(diǎn)的建設(shè)綜合成本和貨物運(yùn)輸時(shí)間滿意度兩方面綜合考慮,建立貨運(yùn)無(wú)人機(jī)起降點(diǎn)選址分配模型。

1.2.1 目標(biāo)函數(shù)

(1)綜合建設(shè)成本。

(1)

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

(2)運(yùn)輸時(shí)間滿意度。山區(qū)多為時(shí)效性較強(qiáng)類(lèi)貨物的產(chǎn)地,因此對(duì)運(yùn)輸時(shí)間較為敏感,此處考慮貨物對(duì)運(yùn)輸時(shí)間的要求,引入運(yùn)輸時(shí)間滿意度作為目標(biāo)函數(shù)之一,本文研究采取線性時(shí)間滿意度函數(shù),運(yùn)輸時(shí)間滿意度隨著運(yùn)輸時(shí)間增長(zhǎng)而均勻降低,其函數(shù)圖像如圖1所示。

(2)

t為運(yùn)輸時(shí)間;s(t)為運(yùn)輸時(shí)間的函數(shù)值;t1和t2為分段函數(shù)s(t)的分段點(diǎn)

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

(3)

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

第二個(gè)目標(biāo)函數(shù)為運(yùn)輸時(shí)間滿意度最大化。根據(jù)線性運(yùn)輸時(shí)間滿意度的定義,得出無(wú)人機(jī)單次運(yùn)輸任務(wù)的時(shí)間滿意度計(jì)算公式,以加權(quán)運(yùn)輸時(shí)間滿意度為時(shí)間滿意度目標(biāo)函數(shù)。貨物運(yùn)輸時(shí)間tij為

(4)

式(4)中:J為需求點(diǎn)集合;v為無(wú)人機(jī)的平均飛行速度。

1.2.2 約束條件

(1)點(diǎn)對(duì)點(diǎn)約束。每個(gè)運(yùn)輸需求點(diǎn)j由且僅由一個(gè)運(yùn)輸起降點(diǎn)i與之對(duì)應(yīng),約束條件為

(5)

(2)起降點(diǎn)數(shù)量約束。起降點(diǎn)數(shù)量不能超過(guò)備選場(chǎng)址數(shù)量,約束條件為

(6)

式(6)中:Z為備選無(wú)人機(jī)起降點(diǎn)數(shù)量。

(3)起降點(diǎn)容量約束。起降點(diǎn)負(fù)責(zé)的運(yùn)輸需求點(diǎn)的貨物不能超過(guò)起降點(diǎn)的容量,約束條件為

(7)

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

(4)配送范圍約束。所有運(yùn)輸需求點(diǎn)均應(yīng)在對(duì)應(yīng)起降點(diǎn)的配送范圍內(nèi),約束條件為

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

(8)

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

(5)運(yùn)輸時(shí)間滿意度約束。對(duì)每個(gè)運(yùn)輸需求點(diǎn)j,運(yùn)輸時(shí)間滿意度要達(dá)到最低標(biāo)準(zhǔn),約束條件為

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

(9)

式(9)中:λi為運(yùn)輸需求點(diǎn)j的最低時(shí)間滿意度;dmax為無(wú)人機(jī)最大航程。

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

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

(10)

(7)無(wú)人機(jī)飛行高度約束。飛行高度要在指定空域高度內(nèi),約束條件為

Hmin≤H≤Hmax

(11)

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

(8)無(wú)人機(jī)載重約束。無(wú)人機(jī)單次運(yùn)輸不得超大載重,約束條件為

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

(12)

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

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

(13)

1.2.3 模型建立

根據(jù)1.4.1節(jié)和1.4.2節(jié)中的目標(biāo)函數(shù)和約束條件的確定,即可建立物流無(wú)人機(jī)起降點(diǎn)選址分配模型,其模型為

(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)為模型目標(biāo)函數(shù),式(16)～式(21)為模型約束條件,包括無(wú)人機(jī)起降點(diǎn)中心的約束,運(yùn)輸需求點(diǎn)方面的約束,式(22)～式(24)為物流無(wú)人機(jī)的性能約束,相關(guān)空域是否適航由參數(shù)βij體現(xiàn)。

2 算法設(shè)計(jì)

根據(jù)所建立模型,對(duì)遺傳算法進(jìn)行設(shè)置,具體設(shè)置如下。

2.1 編碼

所求解的問(wèn)題本質(zhì)上是一個(gè)選址分配問(wèn)題,編碼要能夠體現(xiàn)每個(gè)方案的要求,因此采用符號(hào)編碼方法進(jìn)行編碼。針對(duì)染色體個(gè)體,設(shè)計(jì)j+i個(gè)基因表示無(wú)人機(jī)起降點(diǎn)和運(yùn)輸需求點(diǎn)之間的對(duì)應(yīng)關(guān)系,每個(gè)染色的1～j個(gè)基因表示運(yùn)輸需求點(diǎn)的編號(hào),(j+1)～(j+i)基因表示備選起降點(diǎn)的編號(hào)?，F(xiàn)假設(shè)有6個(gè)運(yùn)輸需求點(diǎn),最多允許4個(gè)起降點(diǎn)負(fù)責(zé)貨物運(yùn)輸任務(wù),那么其中一種可行的染色體表達(dá)方式為[1,2,7,3,4,8,5,9,6],其中1～6表示運(yùn)輸需求點(diǎn)編號(hào),7～9代表無(wú)人機(jī)起降點(diǎn),其將6個(gè)需求點(diǎn)劃分為4段,表示4個(gè)備選起降點(diǎn)全部啟用。第一個(gè)起降點(diǎn)編號(hào)為7-6=1,表示備選起降點(diǎn)1負(fù)責(zé)編號(hào)1、2的運(yùn)輸需求點(diǎn);第二個(gè)起降點(diǎn)編號(hào)為8-6=2,表示備選起降點(diǎn)2負(fù)責(zé)編號(hào)3、4的運(yùn)輸需求點(diǎn);第三個(gè)起降點(diǎn)編號(hào)為9-6=3,表示備選起降點(diǎn)3負(fù)責(zé)編號(hào)5的運(yùn)輸需求點(diǎn),備選起降點(diǎn)4負(fù)責(zé)編號(hào)6的運(yùn)輸需求點(diǎn)。

2.2 生成初始種群

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

2.3 適應(yīng)度函數(shù)設(shè)置

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

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

(2)其次,定義各目標(biāo)函數(shù)的隸屬度函數(shù)為

(25)

(26)

式中:Czs∈[0,1]、Ss∈[0,1]分別為綜合建設(shè)成本和運(yùn)輸時(shí)間滿意度目標(biāo)函數(shù)轉(zhuǎn)化后的隸屬度函數(shù)。

(3)最終,將兩個(gè)目標(biāo)函數(shù)的隸屬度函數(shù)通過(guò)分配不同權(quán)重轉(zhuǎn)化成模糊目標(biāo)函數(shù)求解,因此適應(yīng)度函數(shù)設(shè)置為

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

(27)

式(27)中:F(x)∈[0,1)為適應(yīng)度函數(shù);α1和α2分別為建設(shè)總成本目標(biāo)函數(shù)和運(yùn)輸時(shí)間滿意度函數(shù)的權(quán)重系數(shù),α1、α2≥0且α1+α2=1。

2.4 選擇

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

(28)

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

2.5 交叉變異

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

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

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

(29)

式(29)中:Fmax為當(dāng)前種群個(gè)體適應(yīng)度最大值;Fb為進(jìn)行交叉操作的個(gè)體中的適應(yīng)度較大值;Fa為每一代種群中的適應(yīng)度平均值;Pc1、Pc2∈(0,1)為交叉操作的相關(guān)概率參數(shù)。

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

2.6 融合算法操作

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

(30)

Tk+1=εTk

(31)

Pa=e-ΔF/Tk

(32)

式中:T0為退火操作初始溫度;Tk為經(jīng)過(guò)k次退溫操作后的溫度;ΔF為適應(yīng)度函數(shù)值得極差;Pa為相對(duì)接受概率;ε為溫度衰退系數(shù)。

2.7 終止條件

達(dá)到設(shè)置的迭代次數(shù)。

3 算例分析

3.1 算例描述及參數(shù)設(shè)置

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

表1 運(yùn)輸需求點(diǎn)需求規(guī)模Table 1 Scale of demand

紅色叉號(hào)及右邊數(shù)字表示運(yùn)輸需求點(diǎn)及其編號(hào);綠色菱形及右邊數(shù)字表示備選無(wú)人機(jī)起降點(diǎn)及其編號(hào)

為盡量貼合無(wú)人機(jī)貨運(yùn)中心選址和任務(wù)實(shí)際規(guī)劃過(guò)程,無(wú)人機(jī)起降點(diǎn)的參數(shù)設(shè)置如表2所示。

表2 無(wú)人機(jī)起降點(diǎn)參數(shù)設(shè)置Table 2 Landing point parameters of take-off

對(duì)比目前市場(chǎng)上的無(wú)人機(jī)機(jī)型,對(duì)本文研究中采用的無(wú)人機(jī)進(jìn)行性能參數(shù)設(shè)置如表3所示。

表3 無(wú)人機(jī)參數(shù)設(shè)置Table 3 Parameters of UAV

有關(guān)客戶滿意度函數(shù)中的參數(shù)設(shè)置,每個(gè)運(yùn)輸需求點(diǎn)的最低滿意度取0.5。

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

3.2 結(jié)果仿真分析

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

紅色叉號(hào)及右邊數(shù)字表示運(yùn)輸需求點(diǎn)及其編號(hào);綠色菱形及右邊數(shù)字表示備選無(wú)人機(jī)起降點(diǎn)及其編號(hào)

由圖3可知,當(dāng)在5個(gè)備選起降中心選擇編號(hào)為2、3、4的無(wú)人機(jī)起降點(diǎn)時(shí),適應(yīng)度函數(shù)最優(yōu)為0.657 15,對(duì)應(yīng)的起降點(diǎn)建設(shè)總成本為996 263.233 6元,運(yùn)輸時(shí)間滿意度為0.895 17。

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

圖4 算法迭代過(guò)程對(duì)比Fig.4 Iterative comparison

3.3 參數(shù)靈敏度分析

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

3.3.1 空域約束分析

通過(guò)設(shè)置0-1矩陣來(lái)表示運(yùn)輸需求點(diǎn)和無(wú)人機(jī)起降點(diǎn)備選中心的可達(dá)性,通過(guò)調(diào)整可達(dá)矩陣來(lái)實(shí)現(xiàn)空域條件的改變,分別增加和減少禁飛區(qū)域,圖5和圖6分別為減少和增加禁飛區(qū)域后的布局規(guī)劃方案。

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

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

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

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

3.3.2 需求規(guī)模分析

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

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

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

當(dāng)需求規(guī)模不同時(shí)選址布局方案也會(huì)發(fā)生變化,隨著需求規(guī)模擴(kuò)大,起降點(diǎn)運(yùn)輸任務(wù)量增加,綜合建設(shè)成本隨之升高,當(dāng)需求規(guī)模超過(guò)一定范圍時(shí),因?yàn)閭溥x起降點(diǎn)的規(guī)模并未改變,需求點(diǎn)不能夠被就近的起降點(diǎn)滿足,導(dǎo)致選址分配結(jié)果較原方案會(huì)有較大改變;當(dāng)需求規(guī)?？s小,建設(shè)成本會(huì)隨之降低,運(yùn)輸時(shí)間滿意的也得到提升,但是備選起降點(diǎn)的容量過(guò)剩,且個(gè)別起降點(diǎn)負(fù)擔(dān)較重,整個(gè)布局并不均衡,因此備選起降點(diǎn)的選擇要與需求規(guī)模相匹配[14]。

4 結(jié)論

以建設(shè)總成本最小和運(yùn)輸時(shí)間滿意度最大為目標(biāo)函數(shù),綜合考慮無(wú)人機(jī)的性能與空域限制等問(wèn)題,構(gòu)建了物流前端無(wú)人機(jī)貨運(yùn)起降點(diǎn)的選址和任務(wù)分配模型,設(shè)計(jì)改進(jìn)了遺傳算法和模擬退火算法的組合算法進(jìn)行求解,并通過(guò)仿真驗(yàn)證了該算法在解決此類(lèi)問(wèn)題具有較高的適用性和模型的合理性,并得出以下結(jié)論。

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

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

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