卡車-無人機協(xié)同救災物資避障配送問題研究

路世昌，邵旭倫，李 丹

遼寧工程技術(shù)大學 工商管理學院，遼寧 葫蘆島125105

2021年7月，中國多省出現(xiàn)強降雨現(xiàn)象導致多地發(fā)生洪澇災害，造成了人員與財產(chǎn)的損失。在發(fā)生大規(guī)模災害后，迅速、有效地配送應(yīng)急物資，是保障人民安全和救災工作順利進行的關(guān)鍵因素。國內(nèi)外學者對自然災害的應(yīng)急物資配送做出了眾多研究，例如，Mollah等[1]建立了一個成本優(yōu)化模型進行救災物資分配，并提出了基于混合整數(shù)規(guī)劃和遺傳算法進行求解。Sarma等[2]針對緊急情況下的人道主義救援建立了以總成本和總時間最小的、覆蓋人口最大為目標的多目標災后救助物流模型，利用LINGO 13.0優(yōu)化求解器進行求解。Sabouhi等[3]提出了一個綜合的疏散和分配物流系統(tǒng)，并提出了一種模因算法（memetic algorithm，MA）進行大規(guī)模的分配問題。Wei等[4]開發(fā)了一種混合蟻群算法對目標為開庫成本、車輛固定成本和運輸成本組成的總運營成本以及違反時間窗懲罰成本進行求解，以保證在應(yīng)急物流總倉庫位置和車輛路線的選擇中做出快速正確的判斷。

無人機的快速發(fā)展在運輸物流、安全，災害管理領(lǐng)域中同樣發(fā)揮著重要作用，國內(nèi)外各大公司也在積極推進無人機網(wǎng)絡(luò)的構(gòu)建，例如亞馬遜于2016年公開測試Prime空運服務(wù)無人機、2021年7月DHL擬在歐洲使用4 000架貨運無人機執(zhí)行中程送貨服務(wù)，以及順豐2020年8月試飛的大型載貨無人機、京東在上海亞洲消費電子展（CESAsia）期間展示的載貨無人機，無不證實物流行業(yè)對無人機發(fā)展的重視。在研究領(lǐng)域，Liu等[5]建立了一種多旋翼無人機系統(tǒng)的功率消耗理論模型。Kirschstein[6]提出了一種用以描述無人機在不同環(huán)境條件和飛行模式下的能源消耗模型。Song等[7]提出了一個混合整數(shù)線性規(guī)劃（MILP）公式來推導無人機的持續(xù)交付問題并開發(fā)了一種后退地平線任務(wù)分配（receding horizon task assignment，RHTA）啟發(fā)式算法。袁建華等[8]設(shè)計了一種基于改進粒子群與滾動策略相結(jié)合的無人機路徑規(guī)劃與避障方法以解決無人機在三維環(huán)境中的避障與路徑優(yōu)化問題。范葉滿等[9]設(shè)計了一種模擬退火算法對無人機三維運動的能效系數(shù)進行分析并找出山地作業(yè)情況下的能耗最優(yōu)路徑。Cheng等[10]針對多行程無人機路徑問題，建立了一個考慮載荷量和飛行距離的非線性函數(shù)并提出分支-切割精確算法進行求解。

雖然無人機具有機動性、靈活性、低成本等明顯優(yōu)勢，但由于飛行時間、載荷量等方面的限制，在大范圍運輸中難以應(yīng)用?？朔@種障礙的一種方法是使用大型地面運載工具組成混合運載系統(tǒng)，相對于其他傳統(tǒng)大型地面運載工具，卡車-無人機協(xié)同運輸具有顯著優(yōu)勢，可以有效解決單無人機配送問題中無人機行程不足，運貨量過小及單卡車配送問題中因道路或天氣原因造成的無法面對面交接的情況，三種運輸方式效果圖如圖1所示。Jeong[11]等考慮了包裹重量對無人機能量消耗的影響和存在禁飛區(qū)時無人機最后一公里運輸問題，并提出了一個兩階段的搜索啟發(fā)式算法以解決卡車-無人機混合運輸路線。Othman等[12]將ALSD、NW-ALSDP、LSDP和NWLSDP四種模型作為尋找特殊結(jié)構(gòu)的最小成本路徑問題，用以解決卡車-無人機最后一公里配送問題。Yu等[13]對無人機配送后降落在無人車進行充電的路徑問題進行了研究，并提出了GTSP-BASED算法解決客戶訪問順序及尋找無人車進行充電的時間及地點問題。Murray等[14]建立了兩種數(shù)學規(guī)劃模型，并通過兩種啟發(fā)式算法進行求解，以解決大規(guī)?？ㄜ?無人機配送問題。郭秀萍等[15]設(shè)計了一種三階段的規(guī)劃求解方法，對卡車-無人機聯(lián)合配送模式的物流調(diào)度問題進行探究。彭勇等[16]提出通過卡車-無人機協(xié)同配送模式對新冠疫情嚴重地區(qū)進行配送，并設(shè)計嵌入簡單啟發(fā)式算法的混合鄰域算法進行求解。Ponza[17]設(shè)計了一種模擬退火元啟發(fā)式算法來解決卡車-無人機在最后一英里的配送問題。Moshref-Javadi等[18]針對貨車與無人機聯(lián)合作業(yè)的多模式運輸系統(tǒng)，提出了運輸路線優(yōu)化規(guī)劃的數(shù)學公式和啟發(fā)式求解方法。

圖1 三種運輸方式效果圖Fig.1 Effect of three transportation methods

綜上可知，卡車-無人機協(xié)同運輸對于解決存在障礙區(qū)的最后一公里配送問題有著明顯的優(yōu)勢，本文研究洪澇災害應(yīng)急物資配送過程中，存在的大量積水導致傳統(tǒng)卡車運輸或無人機運輸無法有效完成應(yīng)急物資的配送問題。將整個配送過程分為兩個階段，第一階段設(shè)計改進k-means算法將需求節(jié)點進行聚類劃分，在有效避免存在極值使算法陷入局部最優(yōu)解的同時確定卡車可到，且各需求點位置處于無人機配送范圍內(nèi)的卡車等待點。第二階段提出階段性規(guī)劃算法，將改進A*算法與改進的非線性收斂因子的模擬退火鯨魚算法進行結(jié)合，在保證運輸車輛安全的同時，以最短運輸時間將救災物資安全且快速地運送至各需求點，為救災物資配送問題的探究提出了一種新的思路。

1 問題分析

1.1 問題描述

已知若干位于積水障礙區(qū)內(nèi)的需求節(jié)點需求量，且卡車無法獨立完成運輸。卡車載貨物及多架無人機進行救災物資配送，首先確定各貨車等待點具體位置，待卡車停至等待點后，所載多架無人機攜帶物資進行同時配送，完成配送后返回等待點卡車內(nèi)進行充電或換電池操作?？ㄜ囕d無人機依此途經(jīng)各等待點，確保各需求點都被服務(wù)一次，需求都被滿足的情況下使總配送時間最短，卡車-無人機協(xié)同救災配送路徑示意圖如圖2所示。

圖2 卡車-無人機協(xié)同救災配送路徑示意圖Fig.2 Schematic diagram of truck-drone coordinated disaster relief distribution path

問題假設(shè)如下：

（1）各需求點需求已知，且都會得到服務(wù)；

（2）卡車載重足夠滿足所有需求點需求；

（3）卡車只能停在等待點發(fā)射無人機；

（4）無人機以穩(wěn)定的速度飛行，假設(shè)空氣和重力的流體密度是固定的；

（5）無人機充電及電池更換時間包括載卡車運輸中；

（6）每架無人機每次只能為一個需求點服務(wù)；

（7）無人機飛行范圍有限制，且飛行距離受實時荷載量影響；

（8）所有需求點距最近等待點歐氏距離小于無人機最大航程一半；

（9）所有需求點需求小于無人機荷載量上限。

1.2 積水障礙區(qū)二維化處理

積水障礙區(qū)內(nèi)各需求點由無人機進行空中配送，無人機飛行分為四個階段：起飛、水平飛行、懸停、降落，無人機交付理想飛行模式如圖3所示。即無人機在水平飛行過程中，可將建筑物等三維物體進行二維化處理。同時，考慮卡車最短路問題及積水障礙區(qū)避障問題，將目標區(qū)域進行方形網(wǎng)格化處理。由于積水障礙區(qū)多屬不規(guī)則圖形，這對求解避障最短路徑問題提出難題，故此，本研究將在目標區(qū)域方形網(wǎng)格化處理的基礎(chǔ)上提出不規(guī)則圖形網(wǎng)格化處理方式。

圖3 無人機配送飛行模式Fig.3 Drones delivery flight mode

首先確定目標區(qū)域位置，本文參考面積內(nèi)插模型[19]進行積水障礙區(qū)不規(guī)則圖形的方形網(wǎng)格化處理，處理圖如圖4所示，具體步驟如下。

圖4 積水障礙區(qū)方形網(wǎng)格化處理圖Fig.4 Square grid treatment of waterlogged obstacle area

步驟1確定所選取不規(guī)則圖形所處方形網(wǎng)格。

步驟2確定各方形網(wǎng)格內(nèi)不規(guī)則圖形所占網(wǎng)格面積比重。

步驟3按照不規(guī)則圖形占方形網(wǎng)格面積比重確定選取方形網(wǎng)格的橫/縱坐標。當面積比重低于30%，則選取橫/縱坐標小的方形網(wǎng)格，當面積比重大于30%小于50%時，選取中點坐標，當面積比重大于50%，則選取橫/縱坐標大的方形網(wǎng)格。

步驟4考慮或存在積水面積大于不規(guī)則圖形網(wǎng)格化后的方形網(wǎng)格以及為可能存在的短時間高強度降水做出預留量，將步驟3完成后所有方形網(wǎng)格坐標擴大0.5，以保證配送任務(wù)的順利完成。

2 模型參數(shù)及變量分析

2.1 符號說明

為更直觀表述模型，設(shè)置參數(shù)及變量表如表1所示。

表1 參數(shù)及變量符號說明表Table 1 Parameter and variable symbol description table

2.2 符號說明

3 優(yōu)化模型

可建立如下數(shù)學模型：

其中，式（1）表示卡車載無人機返回倉庫最小時間；式（2）表示由一輛卡車完成任務(wù)，卡車自倉庫出發(fā)并返回倉庫；式（3）表示卡車流量平衡；式（4）、式（5）表示各需求點有且只有一架無人機進行配送服務(wù)；式（6）表示無人機只能從卡車等待區(qū)起飛進行配送；式（7）表示無人機i不允許直接飛回倉庫；式（8）表示無人機i不能直接自倉庫起飛配送；式（9）表示無人機荷載量約束；式（10）表示無人機從等待區(qū)w發(fā)射的最大飛行距離；式（11）表示卡車離開倉庫的時間為0；式（12）表示卡車到達等待區(qū)i的時間；式（13）表示卡車離開等待區(qū)i的時間；式（14）和式（15）表示消去不完整無人機回路；式（16）和式（17）表示消去卡車不完整行車路線；式（18）～（20）為0-1變量約束。

4 算法設(shè)計

無人機-卡車協(xié)同配送問題作為傳統(tǒng)TSP（traveling salesman problem，TSP）[20]問題的延伸，顯然也屬于NPhard問題，針對NP-hard大規(guī)模求解問題，啟發(fā)式算法具有更強的優(yōu)越性，故此，本文提出一種兩階段啟發(fā)式算法，對于卡車-無人機協(xié)同救災物資避障配送問題進行求解。第一階段，考慮受災地區(qū)交通網(wǎng)線分布情況及需求點分布情況，將積水障礙區(qū)二維化，設(shè)計改進k-means聚類算法，將眾多需求點分成不同簇類，并確定貨車等待區(qū)具體位置。第二階段提出階段性規(guī)劃算法，結(jié)合A*算法的避障性與改進模擬退火鯨魚算法的全局快速尋優(yōu)性確定最優(yōu)配送路線，以保證救災物資避障配送流程的安全且快速完成。

4.1 確定卡車等待區(qū)位置

救災物資配送問題常見于城市居民樓簇或村莊村落，相對于傳統(tǒng)TSP問題中客戶節(jié)點的無序分布，救災物資需求點分布更加規(guī)整化，同時，無人機運輸在中高空飛行時不能利用地形因素進行避讓，且飛行高度在一次任務(wù)中變化不大，航跡規(guī)劃可以簡化成二維網(wǎng)格圖，二維網(wǎng)格圖最常用的距離規(guī)劃方法之一是曼哈頓距離[21]，其更接近實際距離，故此，各需求點位置間距的確定使用曼哈頓距離，需求點配送模式區(qū)別圖如圖5所示。

圖5 需求點配送模式區(qū)別圖Fig.5 Demand point distribution model difference diagram

相對于傳統(tǒng)的k-means聚類算法每次選出簇內(nèi)平均值作為聚類中心而導致可能會存在某個極值點使算法陷入局部最優(yōu)解的情況，本研究所提出的改進k-means聚類算法，選取簇內(nèi)中心點作為聚類中心，并設(shè)立值f(f≤(1/2)F)在解決算法遇極值易陷最優(yōu)解的同時確保各需求點都在某架無人機服務(wù)范圍內(nèi)，具體卡車等待點確定過程如下。

步驟1將積水障礙區(qū)二維化處理。

步驟2選定n個簇內(nèi)中心點作為初始聚類中心，簇內(nèi)中心個數(shù)n為：

步驟3計算各需求點到聚類中心距離，將各需求點分配至最近聚類中心。

步驟4更新聚類中心根據(jù)各需求點位置以及需求量，確定客戶節(jié)點是否穩(wěn)定。

步驟5計算當前需求點離最近網(wǎng)格距離，并設(shè)定該網(wǎng)格上點為預等待點。

步驟6計算預等待點與各需求點距離是否小于等于f，若大于f則將該需求點更換至次近聚類，轉(zhuǎn)入步驟4，若都小于等于f，則轉(zhuǎn)入步驟7。

步驟7將預等待點更改為等待點，并輸出優(yōu)化后聚類結(jié)果。

具體算法流程圖，如圖6所示。

圖6 改進k-means算法流程圖Fig.6 Flow chart of improved k-means algorithm

4.2 階段性規(guī)劃算法避障路徑確定

鯨魚算法（whale optimization algorithm，WOA）是2016年由Mirjalili等提出的一種模仿自然界中鯨魚捕食行為的新型群體智能優(yōu)化算法，其具有易于實現(xiàn)，調(diào)整參數(shù)少以及魯棒性強等優(yōu)點，將改進A*算法與改進非線性收斂因子的模擬退火鯨魚算法優(yōu)點相結(jié)合，以實現(xiàn)全局高效避障路徑優(yōu)化。

4.2.1 改進A＊算法設(shè)置

A*算法作為最受歡迎的尋路算法之一，具有很強的靈活性，已被廣泛應(yīng)用于智能尋路、無人機突防等領(lǐng)域中。在算法搜索過程中，需構(gòu)造open list與closelist兩表，其中，open list用于記錄已被計算但未被拓展節(jié)點，close list用于記錄已被拓展節(jié)點，首先選擇open list中代價最小節(jié)點，將其放入close list中進行拓展及分析，之后對open list與close list進行更新。賦予評估節(jié)點i權(quán)重，并選擇代價最少的節(jié)點作為下一位置，重復此過程直至到達最終節(jié)點，其公式表達為：

其中，Gi表示從初始等待點s到指定方格的移動消耗，Hi表示從指定方格移動到下一等待點e的預計消耗。（Hi消耗使用曼哈頓距離計算）。

傳統(tǒng)A*算法雖然計算速度快，但是在移動過程中，存在過多不必要的拐點以及冗余節(jié)點，影響算法整體速度，為降低計算復雜度，消除不滿足路徑規(guī)劃約束子節(jié)點，本文設(shè)定方格搜索范圍為朝向下一到達節(jié)點的最大轉(zhuǎn)角小于等于90°的方格，即將可選擇的8個方格縮減至5個，方格選擇圖如圖7所示。

圖7 方格選擇圖Fig.7 Grid selection chart

具體算法流程如下：

步驟1設(shè)立open list，從初始等待點s開始，將s點放入open list。

步驟2獲取方向朝向下一等待點e的最大轉(zhuǎn)角小于等于90°的方格，將它們放入open list，設(shè)置它們的父方格為s。

步驟3設(shè)立open list，從open list中刪除初始等待點s，將s放入close list。

步驟4計算每個選定周圍方格的F值。

步驟5從open list中選擇F值最低的方格k，將其從open list中刪除，移至close list中。

步驟6獲取方格k朝向下一等待點e的最大轉(zhuǎn)角小于等于90°的方格，其中，障礙方格（unwalkable node）和處于close list中的方格不予考慮，若考慮方格不在open list中，將它們加入open list中，并設(shè)置方格k為父方格。若選中相鄰方格p到方格e的新路徑，且該路徑經(jīng)過k節(jié)點，并進行判斷。

（1）新路徑G值更低，則修改父方格為方格k，重新計算F值，H值不變。

（2）新路徑G值更高，說明新路徑消耗高，則G值不變。

步驟7繼續(xù)從open list中找出最小F值方格，將其從open list中刪除，添加至open list中，如此循環(huán)。

步驟8目標路徑已經(jīng)在open list中，最優(yōu)路徑被找到。

4.2.2 改進鯨魚算法設(shè)置

（1）非線性收斂因子

傳統(tǒng)收斂因子α在WOA算法中會隨著迭代次數(shù)的增加從2至0線性遞減，在求解復雜優(yōu)化問題時存在迭代前期搜索獵物不徹底，迭代后期種群個體多樣性減少，陷入局部最優(yōu)解的問題，因此，設(shè)計了一種非線性收斂因子α，使算法在迭代前期速度放慢，提高全局搜索能力，在迭代后期速度加快，對提高局部搜索的準確性，防止陷入局部最優(yōu)，非線性收斂因子公式如下：

非線性收斂因子迭代圖如圖8所示。

圖8 收斂因子迭代圖Fig.8 Convergence factor iteration diagram

且鯨魚個體Xi在最佳鯨魚個體Xd的影響下的下一位置的計算公式如下：

（2）編碼與解碼

根據(jù)車輛路徑常規(guī)編碼分析，設(shè)計了一種M×M矩陣結(jié)構(gòu)，將矩陣行設(shè)置為配送順序，矩陣列設(shè)置為等待點排列，生成[0，1]矩陣。

卡車配送路徑為1->3->2->7->6->4->5，則通過矩陣轉(zhuǎn)化為整數(shù)編碼為（0，1，3，2，7，6，4，5，0），其中0為出發(fā)倉庫，表示卡車自倉庫出發(fā)進行配送，最終返回倉庫。

（3）種群初始化

鯨魚個體適應(yīng)度由總配送時間決定，故配送時間越小，鯨魚體適應(yīng)度越大。

其中，fi為鯨魚個體Xi的適應(yīng)度，zi為鯨魚個體Xi的目標函數(shù)值。

（4）選擇操作

為提高鯨群算法的精確度，采用精英保留策略與剩余隨機抽樣相結(jié)合，首先計算鯨群中每個鯨魚個體在下一代的期望值ei。

其中，m為種群大小，fi為第i個鯨魚個體的適應(yīng)度。

然后將期望值ei的整數(shù)部分作為個體i在下一代的存活數(shù)，因此可以確定下一代e個體。

（5）鯨魚個體位置更新

采用線性順序交叉策略[22]，選擇鯨魚個體Xi當前位置信息，將其復制到鯨魚個體Xi預位置，將預位置串中存在問題（元素相同）的基因進行修復，使預位置信息合法，鯨魚個體位置更新圖如圖9所示。

圖9 鯨魚個體位置更新圖Fig.9 Whale individual location update figure

（6）局部搜索操作

為了提高算法的精確性以及解的質(zhì)量，采用逆轉(zhuǎn)操作和插入操作以提高算法精度，將鯨魚個體Xi上兩個位置之間所有元素排列進行逆轉(zhuǎn)，設(shè)N為配送節(jié)點數(shù)目。即鯨魚W可表示為：

選擇逆轉(zhuǎn)位置為i和j(i≠j,i≥1,j≤N)，則將第i個和第j個位置之間所有元素逆轉(zhuǎn)后的解可表示為：

執(zhí)行插入操作，將第一個位置上選擇的元素插入第二個位置上選擇的元素后，則鯨魚個體W可表示為：

若選擇插入的位置為i和j，那么將第i個位置上的元素插入第j個位置上的元素后的解為：

（7）最優(yōu)解選取策略

當前大多數(shù)群優(yōu)化算法在求解復雜優(yōu)化問題時，存在迭代后期種群個體多樣性減少，陷入局部最優(yōu)解問題，因此，本研究將模擬退火算法中的Metropolis抽樣穩(wěn)定準則與鯨魚算法進行結(jié)合，以一定概率接受較差鯨魚位置，從而提高算法跳出局部最優(yōu)解的能力。

首先計算更新解前后差值Δf,Δf=f(xj)-f(xi)，若Δf≤0則接受新解并且替代當前解，若Δf＞0則需要計算該點接受概率，通過計算目標函數(shù)的差值對比當前概率。

其中，t代表當前溫度，并產(chǎn)生一偽隨機數(shù)c，符合區(qū)間[0，1]之間的均勻分布，若P(Δf)≤s，則使用當前新解，否則，棄用新解仍使用原點進行下一次的Metropolis過程。

階段性規(guī)劃算法流程圖如圖10所示。

圖10 階段性規(guī)劃算法流程圖Fig.10 Stage planning algorithm flow chart

5 求解實例與分析

為驗證所提出兩階段啟發(fā)式算法的有效性，本文采用兩個2021年7月國內(nèi)受災區(qū)域?qū)嶋H地理位置數(shù)據(jù)，結(jié)合當?shù)氐雀呔€、俯拍圖等，選取兩個區(qū)域6個居住集群中50個節(jié)點作為救災物資配送需求點?？ㄜ囕d5架無人機自倉庫出發(fā)，由于天氣、積水原因，卡車行駛速度為30 km/h，無人機飛行速度恒定為30 km/h，無人機服務(wù)半徑為15 km且無人機懸停取貨時間為20 min。需求點分布圖如圖11所示。

圖11 需求點分布圖Fig.11 Demand point distribution map

5.1 卡車等待點確定

將需求點分布圖二維網(wǎng)格化，按照1方格邊長=150 m的換算比例將網(wǎng)格化后的需求點分布圖置于110×100的網(wǎng)格圖中，并將需求點網(wǎng)格圖進行簡化處理，確定倉庫及各需求點具體位置，倉庫編號設(shè)置為0，二維方形網(wǎng)格化流程圖如圖12所示，倉庫及需求點坐標如表2所示。

表2 倉庫及需求點坐標表Table 2 Coordinate list of warehouse and demand point

圖12 需求點二維網(wǎng)格化圖Fig.12 Two-dimensional gridding map of demand points

通過需求節(jié)點的改進k-means聚類操作，按卡車等待點確定步驟確定10個卡車等待點及其所服務(wù)的需求點如表3所示，完成算法第一階段。

表3 卡車等待區(qū)服務(wù)表Table 3 Truck waiting area service table

5.2 避障路徑確定

依據(jù)所提出的階段性規(guī)劃算法，進行避障路徑確定，將10個等待點及倉庫位置信息帶入算法，應(yīng)用Matlab2016a進行求解，所得最優(yōu)結(jié)果如表4所示。

表4 救災物資避障配送優(yōu)化結(jié)果表Table 4 Disaster relief supplies avoidance distribution optimization results table 單位：min

卡車自倉庫出發(fā)，按照0-10-4-3-1-2-5-6-7-8-9-0的順序一次行駛至各等待點進行無人機配送，最后返回倉庫，卡車共計行駛52.643 km，其中部分等待路徑優(yōu)化圖，如圖13所示。

圖13 部分等待點避障路徑優(yōu)化圖Fig.13 Part of waiting point obstacle avoidance path optimization map

5.3 算法對比

為進一步驗證本研究所提出算法有效性，針對本文實例，采用：（1）本研究所提出兩階段啟發(fā)式算法求得最優(yōu)路徑；（2）k-means聚類算法與遺傳算法計算最優(yōu)路徑；（3）k-means聚類算法與Dijkstra算法計算最優(yōu)路徑；（4）本研究第一階段聚類算法與遺傳算法計算最優(yōu)路徑；（5）本研究第一階段聚類算法與Dijkstra算法計算最優(yōu)路徑進行對比，實驗對比結(jié)果如表5所示。

表5 五算法對比表Table 5 Five-algorithm comparison table單位：min

圖13

從卡車最短配送時間、無人機最短配送時間與最小配送總時間三個方面及對五種算法進行對比，算法對比圖如圖14。

圖14 五算法對比圖Fig.14 Five-algorithm comparison chart

從實驗結(jié)果看，本研究所提出的兩階段啟發(fā)式算法在求解救災物資避障配送路徑優(yōu)化問題時能力最優(yōu)，對比（2）、（3）、（4）、（5）算法，所提出算法最小配送總時間方面分別優(yōu)化4.76%、4.26%、3.14%和2.61%?？砂l(fā)現(xiàn)所提出兩階段啟發(fā)式算法綜合了改進A*算法避障性與改進鯨魚算法快速全局精確搜索的優(yōu)勢，在保證配送安全的前提下，快速運輸救災物資，使災區(qū)群眾生命安全在第一時間得到保障。

6 結(jié)束語

為保障災區(qū)人民生命安全，快速將急需物資運送至處于積水區(qū)、大型載貨工具無法運至需求點的問題，本研究采用卡車-無人機協(xié)同運輸?shù)姆绞竭M行救災物資的避障配送，建立了以總配送時間最短為目標函數(shù)的優(yōu)化模型，并提出了一種兩階段啟發(fā)式算法解決此問題。首先將積水障礙區(qū)、倉庫及各需求點進行二維網(wǎng)格化處理，運用改進k-means算法將所有需求點以無人機數(shù)量，無人機飛行半徑為約束進行聚類，并確定各卡車等待點具體位置，創(chuàng)建階段性規(guī)劃算法，設(shè)計改進A*算法，規(guī)定搜索方向性有效提升A*算法速度，同時設(shè)計非線性收斂因子的模擬退火鯨魚算法，使算法在迭代前期速度放慢，提高全局搜索能力，在迭代后期速度加快，提高局部搜索的準確性，同時加入Metropolis準則，以一定概率接受較差鯨魚位置，防止算法陷入局部最優(yōu)的困境。有效減少卡車及無人機運輸時間，通過實例仿真可以看出，所提出的兩階段啟發(fā)式算法在選定等待點及優(yōu)化避障配送路徑方面都具有優(yōu)勢，為解決救災物資的避障配送問題提出了新的思路。

在后續(xù)研究中，會進一步考慮不同風向及風力等級差異對無人機飛行距離產(chǎn)生的影響以及在實時運輸中需求點需求量突增導致的二次配送等問題。