安子軒

摘 要：無人機因其具有不受道路條件和交通擁堵影響的特點而被應(yīng)用于物流配送，因此針對災(zāi)后道路損毀嚴(yán)重，卡車無法及時配送救援物資的問題，提出利用“卡車-無人機”協(xié)同配送的模式進行救援物資的配送。文章對多輛卡車多架無人機災(zāi)后協(xié)同配送物資的路徑規(guī)劃問題進行了研究，考慮到受災(zāi)群眾對救援物資的需求緊迫性，受災(zāi)群眾滿意度會隨著救援物資送達(dá)時間的延長而降低，因此以最大化受災(zāi)群眾滿意度為目標(biāo)建立了卡車-無人機協(xié)同物資配送模型，并使用了自適應(yīng)大鄰域搜索算法對模型進行求解。最后，通過卡車-無人機協(xié)同配送和卡車單獨配送兩種情況下的對比實驗驗證了無人機在災(zāi)后救援物資配送中的有效性。

關(guān)鍵詞：無人機；自適應(yīng)大鄰域搜索算法；路徑規(guī)劃；應(yīng)急救援

中圖分類號：F512.4；TP242文獻(xiàn)標(biāo)志碼：ADOI：10.13714/j.cnki.1002-3100.2024.10.017

Abstract： Since drones are not affected by road conditions and traffic congestion， they are applied to logistics distribution. Therefore， in view of the problem that trucks cannot deliver relief materials in time due to serious road damage after disasters， a "truck-drone" collaborative distribution mode is proposed to deliver relief materials. This paper studied the routing problem of multi-truck and multi-drone coordinated delivery of materials after disasters. Considering the urgency of the needs of the victims of a disaster for relief materials， the satisfaction of the victims of a disaster will decrease with the extension of the delivery time of relief materials， so a truck-drone collaborative material distribution model was established， and the goal was to maximize the satisfaction of the victims of a disaster. The adaptive large neighborhood search（ALNS） algorithm was used to solve the problem. Finally， the effectiveness of drones in the delivery of post-disaster relief materials was verified through the comparative experiment of truck-drone coordinated delivery and truck separate delivery.

Key words： drones; adaptive large neighborhood search algorithm（ALNS）; path planning; emergency rescue

0? ? 引? ?言

近年來，全球生態(tài)環(huán)境發(fā)生急劇變化，自然災(zāi)害頻發(fā)，因此，做好災(zāi)后應(yīng)急救援，盡最大可能挽救人民群眾的生命和財產(chǎn)安全顯得尤為重要。以洪澇災(zāi)害為例，我國是世界上洪澇災(zāi)害多發(fā)頻發(fā)的國家之一，造成過極大的人員傷亡和經(jīng)濟損失?？ㄜ囈驗榫哂谐休d量大、配送范圍廣的優(yōu)勢，已被廣泛應(yīng)用于災(zāi)后救援物資配送過程中，但是由于卡車自身的運輸要求，在洪澇災(zāi)害等會對道路產(chǎn)生破壞的情況下，道路情況會對卡車配送救援物資產(chǎn)生限制，降低救援效率，因此需要尋找新的技術(shù)克服這一難題。

隨著技術(shù)的不斷發(fā)展，無人機已經(jīng)被應(yīng)用于執(zhí)行救援任務(wù)，能夠明顯縮短救援時間，提高救援效率，盡可能的挽救更多人的生命。2008年汶川地震后，政府派出無人機隊伍收集災(zāi)區(qū)情況，提高搜索效率。2021年鄭州洪澇災(zāi)害中使用了無人機進行通信指揮為群眾運送救援物資[1]。2023年北京汛情中，政府派出無人機給被困群眾配送救援物資，以快速響應(yīng)救援需求，應(yīng)對復(fù)雜的抗洪救災(zāi)環(huán)境。隨著技術(shù)不斷成熟，無人機的應(yīng)用領(lǐng)域不斷擴大。京東、順豐、阿里巴巴、亞馬遜等公司都已經(jīng)開通了無人機物流配送業(yè)務(wù)，美團也將無人機應(yīng)用在外賣配送服務(wù)中，以降低“最后一公里”帶來的高昂成本。

隨著越來越多的企業(yè)將無人機應(yīng)用于實際，很多學(xué)者都開始在無人機配送方面展開研究。由于電池容量的限制，無人機一般只能配送距離配送中心較近的節(jié)點，當(dāng)存在距離配送中心較遠(yuǎn)的節(jié)點時，一般采用卡車和無人機協(xié)同配送的模式。Murray等[2]首先提出了兩個最后一公里交付問題，都只涉及一輛卡車和一架無人機，且目標(biāo)函數(shù)都是最小化卡車或無人機到達(dá)倉庫的最晚時間。FSTSP為飛行伙伴旅行商問題，當(dāng)卡車到達(dá)客戶點時，無人機從卡車上起飛為另一位客戶服務(wù)，隨后在倉庫或另一位客戶的位置返回卡車；第二個問題為并行無人機調(diào)度旅行商問題，這一問題中，卡車和無人機分開進行配送，無人機只能從倉庫起飛和降落。Murray等[3]對FSTSP問題進行了擴展，研究了使用一輛卡車和多架無人機進行交付的mFSTSP問題，設(shè)定無人機只能從倉庫或卡車發(fā)射，并且發(fā)射和降落節(jié)點不能為同一節(jié)點，使得卡車或無人機返回倉庫的最晚時間最小。Saleu[4]等研究了多無人機多卡車的并行無人機調(diào)度問題，問題中使用了多架無人機和多輛卡車為客戶提供服務(wù)，但限定無人機只能在倉庫和客戶之間往返，卡車和無人機的配送活動相對獨立。Wang等[5]以最小化總成本為目標(biāo)，提出了多輛卡車和多架無人機的路徑優(yōu)化問題，問題中提出了無人機中轉(zhuǎn)節(jié)點用于存放和維護無人機，無人機可以從任意節(jié)點起飛，但只能降落在中轉(zhuǎn)節(jié)點或倉庫，不能在客戶節(jié)點處降落。Dukkanci等[6]提出了范圍受限的最小化能量消耗的無人機交付問題，在該問題中卡車主要起到調(diào)度無人機的作用，不對客戶提供配送服務(wù)，卡車從倉庫出發(fā)，將無人機和包裹運輸?shù)綗o人機發(fā)射點，無人機在客戶和發(fā)射點之間往返，向客戶進行最后一英里的交付，目的是使總成本最小。Dayarian等[7]研究了無人機提供補給的車輛路徑問題，問題中無人機不直接對客戶提供配送服務(wù)，而是被當(dāng)作一個向卡車補貨的工具，以滿足顧客最新下達(dá)的當(dāng)天送貨上門的訂單。Kuo等[8]研究了考慮碳排放的無人機車輛路徑問題，通過卡車的行駛距離和無人機的放電過程計算總的碳排放量，通過對配送路線的設(shè)計和優(yōu)化，最小化總的完工時間和碳排放量。Yang等[9]考慮了交通情況不確定性的條件，為了減輕由于交通擁堵不能按計劃為客戶提供服務(wù)的風(fēng)險，想要找到一條魯棒路徑，使得服務(wù)獲得的利潤最大。

在關(guān)于應(yīng)急救援的優(yōu)化研究方面，許鋼焱等[10]研究了單一卡車和無人機的應(yīng)急響應(yīng)策略和調(diào)度優(yōu)化，以最小化所有應(yīng)急需求的響應(yīng)時間為目標(biāo)，決策卡車與無人機的調(diào)度方案。Liu等[11]考慮了救援行動中的投入和產(chǎn)出因素，引入了DEA模型度量救援效率，并以最大化救援效率為目標(biāo)對救援路徑問題進行了研究。Alinaghian等[12]以最小化到達(dá)最后一個臨時救援中心的時間為目標(biāo)，對臨時救援中心的選址和救援無人機的路徑進行決策。Jiao等[13]將不同的救援任務(wù)根據(jù)重要性分配權(quán)重，以電車為救援車輛，研究了救援車輛如何在能量受限的情況下快速高效地執(zhí)行多個救援任務(wù)，最大化所執(zhí)行救援任務(wù)的總權(quán)重。 Wang等[14]以未滿足需求的總懲罰成本和被滿足需求點的等待成本最小為目標(biāo)，研究了災(zāi)后應(yīng)急資源分配和車輛路徑規(guī)劃問題。

基于以上研究發(fā)現(xiàn)，研究災(zāi)后卡車和無人機協(xié)同配送物資的問題較少，并且與應(yīng)急救援相關(guān)研究的優(yōu)化目標(biāo)很少考慮到受災(zāi)群眾對物資送達(dá)時間的滿意程度，進而很少有問題將節(jié)點的滿意度最大作為最終的目標(biāo)。因此本文以洪澇災(zāi)害后的應(yīng)急救援為背景，提出了一個多卡車多無人機的災(zāi)后救援物資配送問題。根據(jù)道路受損情況和受災(zāi)群眾對物資需求的緊急程度對卡車和無人機的配送路線進行規(guī)劃，在給定時間窗口內(nèi)滿足所有受災(zāi)群眾的需求條件下，使得受災(zāi)群眾滿意度最高。

在本文的問題中，隨著配送時間的延長，受災(zāi)群眾的滿意度會不斷降低，并且由于節(jié)點的受災(zāi)嚴(yán)重程度不同，不同的節(jié)點的滿意度降低速度也不同，與 Yu等[15]研究中的收益遞減模式相似，因此本文參考了 Yu等[15]在研究收益遞減的魯棒團隊定向問題時提出的隨到達(dá)時間遞減的線性函數(shù)，構(gòu)建滿意度遞減函數(shù)計算每個受災(zāi)節(jié)點處物資送達(dá)時的滿意度，通過合理安排卡車和無人機的配送路線，盡快將受災(zāi)物資送達(dá)各個受災(zāi)節(jié)點，滿足受災(zāi)群眾的救援物資需求，最大化受災(zāi)群眾的滿意度。

1? ? 問題建模

1.1? ? 問題描述

洪災(zāi)發(fā)生后，政府派遣卡車和無人機聯(lián)合進行物資的配送，為多個受災(zāi)點提供救援物資配送服務(wù)。由于存在道路損毀問題，卡車無法對一些受災(zāi)點提供服務(wù)，因此需要用無人機進行配送?？紤]在災(zāi)后救援情況下，最重要的是能夠及時將救援物資送達(dá)，滿足受災(zāi)群眾對救援物資的需求，因此，本文將優(yōu)化目標(biāo)定為尋找最優(yōu)的卡車和無人機路徑規(guī)劃方案，使得救援物資配送獲得的受災(zāi)群眾滿意度最高。

問題考慮多輛卡車和多架無人機，包含3種類型的節(jié)點：配送中心、卡車配送節(jié)點和無人機配送節(jié)點。無人機配送節(jié)點是由于災(zāi)后道路損壞需要由無人機配送物資，卡車配送節(jié)點的道路沒有被損壞，直接由卡車配送物資。在配送過程中，每輛卡車可以攜帶多架無人機從整個受災(zāi)區(qū)域的指揮中心同時出發(fā)，當(dāng)卡車到達(dá)某一需求點進行配送時，無人機可以從卡車上起飛進行救援物資的配送，由于存在續(xù)航里程的約束，無人機一次只能訪問一個受災(zāi)點，與此同時，卡車可以沿著配送路徑繼續(xù)對其他受災(zāi)節(jié)點進行配送。無人機完成物資配送任務(wù)后返回同一輛卡車，返回的位置必須是在受災(zāi)點處或指揮中心。直至所有受災(zāi)點的物資都配送完畢，卡車攜帶無人機一同返回指揮中心。無人機也可以直接從指揮中心起飛，為一個受災(zāi)節(jié)點配送物資后再返回指揮中心?？ㄜ?無人機路徑示例如圖1所示。

災(zāi)后救援的情況下，受災(zāi)點對物資的需求更加緊急，受災(zāi)群眾的滿意度隨物資送達(dá)時間的延長呈線性遞減。設(shè)定群眾的最大滿意度為，為受災(zāi)點處的滿意度遞減率，每個節(jié)點的滿意度遞減率不同，卡車或無人機的物資送達(dá)時間為，基于以上設(shè)定構(gòu)建的滿意度模型為：fi（ai）=pi-diai，0≤ai≤Di，其中Di表示受災(zāi)點的物資最晚送達(dá)時間，所有受災(zāi)點的物資都必須要在最晚送達(dá)時間的區(qū)間內(nèi)送達(dá)。

問題假設(shè)如下。

a.卡車和無人機都是同質(zhì)的；

b.每輛卡車的起點和終點相同，都是指揮中心，途中不返回；

c.每個受災(zāi)點只能由卡車或無人機配送一次；

d.考慮到受災(zāi)群眾必須都要拿到物資，因此所有受災(zāi)點的需求都要在給定的時間窗內(nèi)得到滿足；

e.每個受災(zāi)節(jié)點配送物資的重量均滿足無人機的載重量約束；

f.每輛卡車線路上裝載的所有物資的總重量不超過卡車的最大容量；

g.無人機飛出和返回卡車的地點均為卡車可配送的受災(zāi)點或指揮中心；

h.卡車和無人機在受災(zāi)節(jié)點的服務(wù)時間忽略不計；

i.各個節(jié)點之間的距離采用歐氏距離計算；

j.無人機的飛行速度恒定，不受重力等其他因素的影響；

k.無人機的最大飛行時間不受外界因素的影響；

l.無人機每次起飛執(zhí)行配送任務(wù)均為滿電量，并且滿足無人機從卡車起飛到返回卡車這段路程需要的電量。

1.2? ? 數(shù)學(xué)模型

模型符號定義如表1所示。

根據(jù)問題描述，建立的卡車-無人機協(xié)同物資配送模型如下。

目標(biāo)函數(shù)（1）是最大化受災(zāi)群眾對政府物資配送服務(wù)的滿意度。約束（2）確保每個受災(zāi)點只能被配送一次物資。約束（3）和（4）確保每輛卡車離開、返回指揮中心僅一次。約束（5）和（6）是流量守恒約束，即當(dāng)卡車或無人機到達(dá)一個受災(zāi)節(jié)點配送物資時，卡車或無人機必須要從這個受災(zāi)節(jié)點離開。約束（7）和（8）是子環(huán)消除約束。約束（9）是卡車容量約束，即裝載到一輛卡車的無人機配送物資的重量和卡車配送物資的重量之和不能超過卡車的最大載荷。約束（10）和（11）確保卡車和無人機的初始時間為0。約束（12）是卡車時間約束，計算兩個節(jié)點之間的卡車行駛時間。約束（13）是無人機時間約束，計算兩個節(jié)點之間無人機的飛行時間。約束（14）和（15）是卡車和無人機的同步約束，確保在無人機起飛節(jié)點和降落節(jié)點處，卡車的到達(dá)時間不晚于無人機的到達(dá)時間，這兩個約束針對的是受災(zāi)節(jié)點處，當(dāng)卡車和無人機分別返回指揮中心時不需要同步。約束（16）要求無人機起飛節(jié)點處的物資必須由裝載該無人機的卡車進行配送，即如果卡車上的無人機在節(jié)點離開卡車去給受災(zāi)節(jié)點配送物資，則節(jié)點必須由卡車配送物資。約束（17）要求無人機降落節(jié)點處的物資必須由裝載該無人機的卡車進行配送，即如果卡車上的無人機在給受災(zāi)節(jié)點配送物資后在節(jié)點處返回卡車，則節(jié)點必須由卡車配送物資。約束（18）和（19）是時間窗約束，確保每個受災(zāi)點的物資在最晚時間前送達(dá)。約束（20）和（21）是對變量取值的約束。

2? ? 求解算法

本文建立的模型是一個NP難問題，很難通過傳統(tǒng)優(yōu)化方法快速有效地求解，并且精確算法在大規(guī)模算例中沒有明顯優(yōu)勢，因此本文采用了啟發(fā)式算法對問題進行求解。大鄰域搜索算法是經(jīng)典的啟發(fā)式算法，并且已經(jīng)被成功地應(yīng)用于求解多種車輛路徑問題。自適應(yīng)大鄰域搜索算法在鄰域搜索算法的基礎(chǔ)上加入了自適應(yīng)的機制，能夠根據(jù)搜索算子的歷史表現(xiàn)選擇好的鄰域搜索算子，從而提高找到質(zhì)量更高解的概率[16]。本文針對卡車-無人機協(xié)同物資配送模型，提出了改進的自適應(yīng)大鄰域搜索算法對其進行求解。算法流程如圖2所示。

2.1? ? 解的描述和初始解生成

卡車-無人機協(xié)同物資配送模型的解由卡車路徑和無人機路徑兩部分組成。如圖3所示，卡車路徑部分，每條卡車路徑的起點和終點都是指揮中心，中間從左到右依次為卡車配送的受災(zāi)節(jié)點；無人機路徑部分，每條無人機路徑由每輛卡車上每架無人機的路徑組合而成，每架無人機的路徑都依次包含3個節(jié)點：無人機起飛節(jié)點、無人機配送節(jié)點和無人機降落節(jié)點，其中無人機起飛節(jié)點和無人機降落節(jié)點都是對應(yīng)卡車路徑中的卡車配送節(jié)點或指揮中心。

針對初始解生成，本文采用了隨機生成的方法分兩階段生成初始路徑。第一階段針對由卡車配送物資的受災(zāi)點建立卡車路徑解決方案；第二階段在第一階段生成的卡車路線的基礎(chǔ)上，針對由無人機配送物資的受災(zāi)節(jié)點，確定每架無人機的起飛節(jié)點和降落節(jié)點，生成無人機路徑。

2.2? ? 鄰域搜索算子

本文使用了3個破壞算子和3個修復(fù)算子構(gòu)造鄰域解，在每次迭代時使用輪盤賭的方式選擇使用的破壞算子和修復(fù)算子。

2.2.1? ? 隨機破壞算子

該算子從當(dāng)前解決方案中隨機移除2個卡車節(jié)點和2個無人機節(jié)點，其中對無人機節(jié)點進行移除時，要在無人機路徑中同時移除與該無人機節(jié)點相關(guān)聯(lián)的起飛節(jié)點和降落節(jié)點。

2.2.2? ? 貪婪破壞算子

該算子將當(dāng)前解決方案路徑中的所有受災(zāi)節(jié)點依次移除、插入，并記錄使受災(zāi)群眾滿意度變化最大（即增加最多）的節(jié)點。依次找到2個卡車節(jié)點和2個無人機節(jié)點并移除。對無人機節(jié)點進行移除時，要在無人機路徑中同時移除與該無人機節(jié)點相關(guān)聯(lián)的起飛節(jié)點和降落節(jié)點。

2.2.3? ? 相關(guān)性破壞算子

該算子首先從當(dāng)前解決方案中隨機選擇1個卡車節(jié)點移除，之后根據(jù)其他受災(zāi)節(jié)點與該節(jié)點的相關(guān)性，選擇與該節(jié)點相關(guān)性最強的1個卡車配送節(jié)點和2個無人機配送節(jié)點移除。對無人機節(jié)點進行移除時，要在無人機路徑中同時移除與無人機節(jié)點相關(guān)聯(lián)的起飛節(jié)點和降落節(jié)點。

2.2.4? ? 隨機修復(fù)算子

對于每一個移除的卡車節(jié)點，該算子隨機選擇一條卡車路線，在滿足卡車載荷約束和時間窗約束的條件下，將該移除節(jié)點插入此卡車路線中；對于每一個移除的無人機節(jié)點，該算子也隨機選擇一條卡車路線，在滿足卡車載荷約束和時間窗約束的條件下，找到并確定與該無人機節(jié)點相關(guān)聯(lián)的起飛節(jié)點和降落節(jié)點，并將起飛節(jié)點、受災(zāi)節(jié)點和降落節(jié)點插入到對應(yīng)的無人機路線中。

2.2.5? ? 貪婪修復(fù)算子

對于每一個移除的卡車節(jié)點，該算子將每個移除的卡車節(jié)點循環(huán)放入卡車路徑中的所有位置，并記錄使受災(zāi)群眾滿意度變化最好（即增加最多）的位置，最后將移除的卡車節(jié)點插入貪婪修復(fù)算子計算得到的最好的位置；對于移除的無人機節(jié)點，該算子循環(huán)將每條卡車路徑中無人機能夠起飛的節(jié)點作為起飛節(jié)點，將無人機節(jié)點插入，記錄使受災(zāi)群眾滿意度減少最小的位置，并確定與該位置相關(guān)聯(lián)的無人機起飛節(jié)點和降落節(jié)點，最后將移除的無人機節(jié)點及相關(guān)聯(lián)的起飛節(jié)點和降落節(jié)點插入貪婪修復(fù)算子計算得到的最好的無人機路徑中。

2.2.6? ? 后悔修復(fù)算子

該算子依次循環(huán)計算每個移除節(jié)點的后悔值，找到卡車配送節(jié)點和無人機配送節(jié)點一共4個移除節(jié)點中后悔值最大的節(jié)點，將其插入到路徑中，并更新滿意度。再重新循環(huán)計算剩余移除節(jié)點的后悔值，找到后悔值最大的節(jié)點并插入。重復(fù)該步驟，直至所有的移除節(jié)點都被重新插入到路徑中為止。

2.3? ? 算子選擇

在算法迭代過程中，采用了輪盤賭的方法選擇使用的破壞算子和修復(fù)算子。每個算子被選中的概率為該算子的權(quán)重占所有算子權(quán)重之和的比例，因此在迭代過程中，算法根據(jù)算子的表現(xiàn)動態(tài)地調(diào)整算子的權(quán)重，使表現(xiàn)更好的算子占的比重更大，以獲得質(zhì)量更高的解。

迭代開始前將每個算子的權(quán)重均設(shè)為1，在后續(xù)迭代過程中，按照如下的規(guī)則對算子的權(quán)重進行更新：如果選擇的破壞算子和修復(fù)算子產(chǎn)生的新解好于當(dāng)前解，則對應(yīng)破壞算子和修復(fù)算子的權(quán)重加；如果選擇的破壞和修復(fù)算子產(chǎn)生的新解好于全局最優(yōu)解，則對應(yīng)破壞算子和修復(fù)算子的權(quán)重再加；如果選擇的破壞算子和修復(fù)算子產(chǎn)生的新解比當(dāng)前解差，但根據(jù)模擬退火算法的以概率接受準(zhǔn)則被接受，則對應(yīng)破壞算子和修復(fù)算子的權(quán)重加；否則，對應(yīng)破環(huán)算子和修復(fù)算子的權(quán)重不變。在每次破壞和修復(fù)操作之后，都按照以上的規(guī)則計算更新算子的權(quán)重。

2.4? ? 停止和接受準(zhǔn)則

為了防止鄰域搜索時陷入局部最優(yōu)，引入了模擬退火算法以概率接受準(zhǔn)則。如果在迭代過程中獲得的新解比當(dāng)前解差，則以概率接受，其中表示新解，表示當(dāng)前解，表示目標(biāo)函數(shù)值，表示當(dāng)前溫度，隨著迭代次數(shù)的不斷增加，以的降溫速度不斷降低，其中。當(dāng)算法達(dá)到最大迭代次數(shù)或者連續(xù)迭代Imax次沒有得到更好的解時，算法直接結(jié)束，接受當(dāng)前的全局最優(yōu)解為最優(yōu)解并輸出。

3? ? 計算實驗

由于本文所研究的問題還沒有公開的測試算例可用，為了驗證本文卡車-無人機協(xié)同物資配送模型和自適應(yīng)大鄰域搜索算法的有效性和可行性，本文參考了來自于文獻(xiàn)[17]中修改后的Solomon數(shù)據(jù)集，將其在Solomon數(shù)據(jù)集中增加的每個節(jié)點的收益遞減率對應(yīng)本文中受災(zāi)點處的滿意度遞減率，并根據(jù)本文所研究的問題對數(shù)據(jù)集進行了適當(dāng)?shù)母木帲糠謹(jǐn)?shù)據(jù)示例見表2。本文中提出的算法由Java實現(xiàn)，實驗的運行環(huán)境為Intel（R） Core（TM） i5-13500H 2.60 GHz處理器，16.0 GB內(nèi)存。

3.1? ? 參數(shù)設(shè)置

本文所使用數(shù)據(jù)集中受災(zāi)節(jié)點規(guī)模分別為50，75，100，數(shù)據(jù)類型分為C型和R型兩類，C類數(shù)據(jù)中節(jié)點分布比較集中，R類數(shù)據(jù)中節(jié)點分布比較隨機。設(shè)定每個算例中由卡車配送的受災(zāi)節(jié)點占80%，由無人機配送的受災(zāi)節(jié)點占20%。指揮中心使用卡車和無人機作為物資配送工具，其中，卡車容量為200，每個受災(zāi)節(jié)點需求物資的重量都在無人機的承載范圍之內(nèi)，卡車和無人機的速度分別為30km/h和50km/h。自適應(yīng)大鄰域搜索算法的最大迭代次數(shù)為100。

3.2? ? 實驗結(jié)果

根據(jù)本文使用的改編后的Solomon數(shù)據(jù)集和設(shè)定的卡車、無人機相關(guān)參數(shù)，結(jié)合本文構(gòu)建的卡車-無人機協(xié)同物資配送模型，在卡車-無人機協(xié)同配送和卡車單獨配送兩種情景下，使用改進的自適應(yīng)大鄰域搜索算法進行求解，每個算例求解10次，記錄每次的目標(biāo)函數(shù)值并取平均值，結(jié)果對比如表3所示。

為了驗證無人機在應(yīng)急救援物資配送中的有效性，本文將卡車-無人機協(xié)同配送物資和只有卡車配送物資兩種模式下求得的受災(zāi)群眾滿意度進行了對比，對于3種不同規(guī)模的算例，本文使用改進的自適應(yīng)大鄰域搜索算法都能在較短的時間內(nèi)進行求解。從表3和表4的實驗結(jié)果中可以看出，相同規(guī)模的問題中，用卡車-無人機協(xié)同配送物資的滿意度明顯高于卡車單獨配送物資的滿意度，說明卡車-無人機協(xié)同配送物資能夠更快的將物資送到受災(zāi)點，提高救援效率。

實驗證明，將無人機和卡車協(xié)同應(yīng)用于災(zāi)后應(yīng)急救援物資的配送能夠同時發(fā)揮出卡車和無人機自身配送物資的優(yōu)勢，相互彌補在運輸速度和載重量方面的劣勢，進而顯著減少物資配送時間，能夠更加及時地將救援物資送達(dá)到受災(zāi)點處，降低由于道路損壞對卡車配送物資產(chǎn)生的影響，進而提高災(zāi)民的存活率以及對政府配送救援物資的滿意度，為以后政府在救災(zāi)中的救援物資配送方案打開了一個新的思路。

4? ? 總? ? 結(jié)

當(dāng)洪澇災(zāi)害等對道路損毀嚴(yán)重時，往往會影響到卡車配送救援物資的效率，進而錯過災(zāi)后救援的最佳時機。因此，本文考慮將無人機應(yīng)用于災(zāi)后救援物資配送的場景中，研究了卡車-無人機協(xié)同物資配送問題，以最大化與物資送達(dá)時間相關(guān)的受災(zāi)群眾的滿意度為目標(biāo)，構(gòu)建了卡車-無人機協(xié)同物資配送模型，使用了自適應(yīng)大鄰域搜索算法成功對模型進行求解，并利用模擬退火算法防止算法陷入局部最優(yōu)。通過實驗對比卡車單獨配送物資和卡車-無人機協(xié)同配送物資兩種情況下受災(zāi)群眾的滿意度，證明了無人機在應(yīng)急救援物資配送中的有效性，有助于深化無人機在應(yīng)急救援場景中的應(yīng)用，在面臨實際救援物資配送問題時及時提供可行的解決方案，進一步提高應(yīng)急救援的效率。

本文構(gòu)建的卡車-無人機協(xié)同配送模型也可擴展應(yīng)用于其他場景，例如物流最后一公里配送等，能夠有效地縮短配送時間，提高物流配送效率。但由于本文所構(gòu)建的模型主要針對災(zāi)后應(yīng)急救援的場景，因此沒有考慮取送貨、無人機在配送途中充電等比較復(fù)雜的約束條件，將來在研究無人機在物流配送場景中的實際應(yīng)用時可以進一步將這些復(fù)雜約束考慮在內(nèi)。

參考文獻(xiàn)：

[1] WANG Desheng，HU Peng，DU Jingxuan，et al．Routing and scheduling for hybrid truck-drone collaborative parcel delivery? with independent and truck-carried drones[J]．IEEE Internet of Things Journal，2019，6（6）：10483-10495．

[2] MURRAY C C，CHU A G．The flying sidekick traveling salesman problem： Optimization of drone-assisted parcel delivery[J].? Transportation Research Part C： Emerging Technologies，2015，54：86–109．

[3] MURRAY C C，RAJ R．The multiple flying sidekicks traveling salesman problem： Parcel delivery with multiple drones[J].? Transportation Research Part C： Emerging Technologies，2020，110：368–398．

[4] SALEU R G M，DEROUSSI L，F(xiàn)EILLET D，et al．The parallel drone scheduling problem with multiple drones and vehicles[J].? ?European Journal of Operational Research，2022，300（2）：571-589．

[5] WANG Zheng，SHEU Jiuh-biing．Vehicle routing problem with drones[J]．Transportation Research Part B： Methodological，? ?2019，122：350–364．

[6] DUKKANCI O，KARA B Y，BEKTAS T．Minimizing energy and cost in range-limited drone deliveries with speed optimization[J/OL].? ?Transportation Research Part C： Emerging Technologies，2021，125.[2023-08-25].https：//doi.org/10.1016/j.trc.2021.102985.

[7] DAYARIAN I，SAVELSBERGH M，CLARKE J-P．Same-day delivery with drone resupply[J].Transportation Science，2020，54（1）： 229-249.

[8] KUO R J，EDBERT E，ZULVIA F E，et al．Applying NSGA-II to vehicle routing problem with drones considering makespan and carbon?? emission[J/OL]．Expert Systems with Applications，2023，221.[2023-08-27].https：//doi.org/10.1016/j.eswa.2023.119777．

[9] YANG Yu，YAN Chiwei，CAO Yufeng Cao，et al．Planning robust drone-truck delivery routes under road traffic uncertainty[J]．?European Journal of Operational Research，2023，309（3）： 1145-1160．

[10] 許鋼焱，龍玉瑩，王欣悅，等.考慮貨車-無人機協(xié)同的災(zāi)后應(yīng)急響應(yīng)策略及調(diào)度優(yōu)化[J]．安全與環(huán)境學(xué)報，2023，23（5）：1587-1595.

[11] LIU Bingsheng，SHEU Jiuh-biing，ZHAO Xue，et al．Decision making on post-disaster rescue routing problems from the rescue efficiency? ?perspective[J]．European Journal of Operational Research，2020，286（1）：321-335．

[12] ALINAGHIAN M，AHGAIE M，SABBAGH M S．A mathematical model for location of temporary relief centers and dynamic routing of?? aerial rescue vehicles[J].Computers & Industrial Engineering，2019，131：227-241．

[13] JIAO Lei，PENG Zhihong，XI Lele，et al．A multi-stage heuristic algorithm based on task grouping for vehicle routing problem with energy?? ?constraint in disasters[J/OL]．Expert Systems with Applications，2023，212.[2023-08-30]．https：//doi.org/10.1016/j.eswa.2022.118740.

[14] WANG Weiqiao，TANG Kai，YANG Lixing，et al．Distributionally robust chance-constrained programming for multi-period emergency resource?? ?allocation and vehicle routing in disaster response operations[J/OL].Omega，2023，120.[2023-09-05].https：//doi.org/10.1016/j.omega.2023.102915.

[15] YU Qinxiao，CHENG Chun，ZHU Ning．Robust team orienteering problem with decreasing profits[J]．INFORMS Journal on?? ? ?Computing，2022，34（6）： 3215-3233．

[16] GENDREAU M，POTVIN J-Y．Handbook of metaheuristics（2nd edition）[M]．New York： Springer，2010：99-127．

[17] YU Qinxiao，ADULYASAK Y，ROUSSEAU L-M，et al．Team orienteering with time-varying profit[J]．INFORMS Journal on? ? Computing，2022，34（1）：262-280．