災(zāi)后應(yīng)急救援背景下卡車-無人機(jī)協(xié)同配送路徑規(guī)劃

安子軒

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

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

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

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

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

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

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

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

1? ? 問題建模

1.1? ? 問題描述

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

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

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

問題假設(shè)如下。

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

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

c.每個(gè)受災(zāi)點(diǎn)只能由卡車或無人機(jī)配送一次；

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

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

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

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

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

i.各個(gè)節(jié)點(diǎn)之間的距離采用歐氏距離計(jì)算；

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

k.無人機(jī)的最大飛行時(shí)間不受外界因素的影響；

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

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

模型符號(hào)定義如表1所示。

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

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

2? ? 求解算法

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

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

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

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

2.2? ? 鄰域搜索算子

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

2.2.1? ? 隨機(jī)破壞算子

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

2.2.2? ? 貪婪破壞算子

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

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

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

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

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

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

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

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

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

2.3? ? 算子選擇

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

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

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

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

3? ? 計(jì)算實(shí)驗(yàn)

由于本文所研究的問題還沒有公開的測(cè)試算例可用，為了驗(yàn)證本文卡車-無人機(jī)協(xié)同物資配送模型和自適應(yīng)大鄰域搜索算法的有效性和可行性，本文參考了來自于文獻(xiàn)[17]中修改后的Solomon數(shù)據(jù)集，將其在Solomon數(shù)據(jù)集中增加的每個(gè)節(jié)點(diǎn)的收益遞減率對(duì)應(yīng)本文中受災(zāi)點(diǎn)處的滿意度遞減率，并根據(jù)本文所研究的問題對(duì)數(shù)據(jù)集進(jìn)行了適當(dāng)?shù)母木帲糠謹(jǐn)?shù)據(jù)示例見表2。本文中提出的算法由Java實(shí)現(xiàn)，實(shí)驗(yàn)的運(yù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é)點(diǎn)規(guī)模分別為50，75，100，數(shù)據(jù)類型分為C型和R型兩類，C類數(shù)據(jù)中節(jié)點(diǎn)分布比較集中，R類數(shù)據(jù)中節(jié)點(diǎn)分布比較隨機(jī)。設(shè)定每個(gè)算例中由卡車配送的受災(zāi)節(jié)點(diǎn)占80%，由無人機(jī)配送的受災(zāi)節(jié)點(diǎn)占20%。指揮中心使用卡車和無人機(jī)作為物資配送工具，其中，卡車容量為200，每個(gè)受災(zāi)節(jié)點(diǎn)需求物資的重量都在無人機(jī)的承載范圍之內(nèi)，卡車和無人機(jī)的速度分別為30km/h和50km/h。自適應(yīng)大鄰域搜索算法的最大迭代次數(shù)為100。

3.2? ? 實(shí)驗(yàn)結(jié)果

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

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

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

4? ? 總? ? 結(jié)

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

本文構(gòu)建的卡車-無人機(jī)協(xié)同配送模型也可擴(kuò)展應(yīng)用于其他場(chǎng)景，例如物流最后一公里配送等，能夠有效地縮短配送時(shí)間，提高物流配送效率。但由于本文所構(gòu)建的模型主要針對(duì)災(zāi)后應(yīng)急救援的場(chǎng)景，因此沒有考慮取送貨、無人機(jī)在配送途中充電等比較復(fù)雜的約束條件，將來在研究無人機(jī)在物流配送場(chǎng)景中的實(shí)際應(yīng)用時(shí)可以進(jìn)一步將這些復(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] 許鋼焱，龍玉瑩，王欣悅，等.考慮貨車-無人機(jī)協(xié)同的災(zāi)后應(yīng)急響應(yīng)策略及調(diào)度優(yōu)化[J]．安全與環(huán)境學(xué)報(bào)，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．