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

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

引

言近年來(lái)，全球生態(tài)環(huán)境發(fā)生急劇變化，自然災(zāi)害頻發(fā)，因此，做好災(zāi)后應(yīng)急救援，盡最大可能挽救人民群眾的生命和財(cái)產(chǎn)安全顯得尤為重要。以洪澇災(zāi)害為例，我國(guó)是世界上洪澇災(zāi)害多發(fā)頻發(fā)的國(guó)家之一，造成過(guò)極大的人員傷亡和經(jīng)濟(jì)損失。卡車(chē)因?yàn)榫哂谐休d量大、配送范圍廣的優(yōu)勢(shì)，已被廣泛應(yīng)用于災(zāi)后救援物資配送過(guò)程中，但是由于卡車(chē)自身的運(yùn)輸要求，在洪澇災(zāi)害等會(huì)對(duì)道路產(chǎn)生破壞的情況下，道路情況會(huì)對(duì)卡車(chē)配送救援物資產(chǎn)生限制，降低救援效率，因此需要尋找新的技術(shù)克服這一難題。隨著技術(shù)的不斷發(fā)展，無(wú)人機(jī)已經(jīng)被應(yīng)用于執(zhí)行救援任務(wù)，能夠明顯縮短救援時(shí)間，提高救援效率，盡可能的挽救更多人的生命。2008年汶川地震后，政府派出無(wú)人機(jī)隊(duì)伍收集災(zāi)區(qū)情況，提高搜索效率。2021年鄭州洪澇災(zāi)害中使用了無(wú)人機(jī)進(jìn)行通信指揮為群眾運(yùn)送救援物資[1]。2023年北京汛情中，政府派出無(wú)人機(jī)給被困群眾配送救援物資，以快速響應(yīng)救援需求，應(yīng)對(duì)復(fù)雜的抗洪救災(zāi)環(huán)境。隨著技術(shù)不斷成熟，無(wú)人機(jī)的應(yīng)用領(lǐng)域不斷擴(kuò)大。京東、順豐、阿里巴巴、亞馬遜等公司都已經(jīng)開(kāi)通了無(wú)人機(jī)物流配送業(yè)務(wù)，美團(tuán)也將無(wú)人機(jī)應(yīng)用在外賣(mài)配送服務(wù)中，以降低“最后一公里”帶來(lái)的高昂成本。隨著越來(lái)越多的企業(yè)將無(wú)人機(jī)應(yīng)用于實(shí)際，很多學(xué)者都開(kāi)始在無(wú)人機(jī)配送方面展開(kāi)研究。由于電池容量的限制，無(wú)人機(jī)一般只能配送距離配送中心較近的節(jié)點(diǎn)，當(dāng)存在距離配送中心較遠(yuǎn)的節(jié)點(diǎn)時(shí)，一般采用卡車(chē)和無(wú)人機(jī)協(xié)同配送的模式。Murray等[2]首先提出了兩個(gè)最后一公里交付問(wèn)題，都只涉及一輛卡車(chē)和一架無(wú)人機(jī)，且目標(biāo)函數(shù)都是最小化卡車(chē)或無(wú)人機(jī)到達(dá)倉(cāng)庫(kù)的最晚時(shí)間。FSTSP為飛行伙伴旅行商問(wèn)題，當(dāng)卡車(chē)到達(dá)客戶(hù)點(diǎn)時(shí)，無(wú)人機(jī)從卡車(chē)上起飛為另一位客戶(hù)服務(wù)，隨后在倉(cāng)庫(kù)或另一位客戶(hù)的位置返回卡車(chē)；第二個(gè)問(wèn)題為并行無(wú)人機(jī)調(diào)度旅行商問(wèn)題，這一問(wèn)題中，卡車(chē)和無(wú)人機(jī)分開(kāi)進(jìn)行配送，無(wú)人機(jī)只能從倉(cāng)庫(kù)起飛和降落。Murray等[3]對(duì)FSTSP問(wèn)題進(jìn)行了擴(kuò)展，研究了使用一輛卡車(chē)和多架無(wú)人機(jī)進(jìn)行交付的mFSTSP問(wèn)題，設(shè)定無(wú)人機(jī)只能從倉(cāng)庫(kù)或卡車(chē)發(fā)射，并且發(fā)射和降落節(jié)點(diǎn)不能為同一節(jié)點(diǎn)，使得卡車(chē)或無(wú)人機(jī)返回倉(cāng)庫(kù)的最晚時(shí)間最小。Saleu[4]等研究了多無(wú)人機(jī)多卡車(chē)的并行無(wú)人機(jī)調(diào)度問(wèn)題，問(wèn)題中使用了多架無(wú)人機(jī)和多輛卡車(chē)為客戶(hù)提供服務(wù)，但限定無(wú)人機(jī)只能在倉(cāng)庫(kù)和客戶(hù)之間往返，卡車(chē)和無(wú)人機(jī)的配送活動(dòng)相對(duì)獨(dú)立。Wang等[5]以最小化總成本為目標(biāo)，提出了多輛卡車(chē)和多架無(wú)人機(jī)的路徑優(yōu)化問(wèn)題，問(wèn)題中提出了無(wú)人機(jī)中轉(zhuǎn)節(jié)點(diǎn)用于存放和維護(hù)無(wú)人機(jī)，無(wú)人機(jī)可以從任意節(jié)點(diǎn)起飛，但只能降落在中轉(zhuǎn)節(jié)點(diǎn)或倉(cāng)庫(kù)，不能在客戶(hù)節(jié)點(diǎn)處降落。Dukkanci等[6]提出了范圍受限的最小化能量消耗的無(wú)人機(jī)交付問(wèn)題，在該問(wèn)題中卡車(chē)主要起到調(diào)度無(wú)人機(jī)的作用，不對(duì)客戶(hù)提供配送服務(wù)，卡車(chē)從倉(cāng)庫(kù)出發(fā)，將無(wú)人機(jī)和包裹運(yùn)輸?shù)綗o(wú)人機(jī)發(fā)射點(diǎn)，無(wú)人機(jī)在客戶(hù)和發(fā)射點(diǎn)之間往返，向客戶(hù)進(jìn)行最后一英里的交付，目的是使總成本最小。Dayarian等[7]研究了無(wú)人機(jī)提供補(bǔ)給的車(chē)輛路徑問(wèn)題，問(wèn)題中無(wú)人機(jī)不直接對(duì)客戶(hù)提供配送服務(wù)，而是被當(dāng)作一個(gè)向卡車(chē)補(bǔ)貨的工具，以滿足顧客最新下達(dá)的當(dāng)天送貨上門(mén)的訂單。Kuo等[8]研究了考慮碳排放的無(wú)人機(jī)車(chē)輛路徑問(wèn)題，通過(guò)卡車(chē)的行駛距離和無(wú)人機(jī)的放電過(guò)程計(jì)算總的碳排放量，通過(guò)對(duì)配送路線的設(shè)計(jì)和優(yōu)化，最小化總的完工時(shí)間和碳排放量。Yang等[9]考慮了交通情況不確定性的條件，為了減輕由于交通擁堵不能按計(jì)劃為客戶(hù)提供服務(wù)的風(fēng)險(xiǎn)，想要找到一條魯棒路徑，使得服務(wù)獲得的利潤(rùn)最大。在關(guān)于應(yīng)急救援的優(yōu)化研究方面，許鋼焱等[10]研究了單一卡車(chē)和無(wú)人機(jī)的應(yīng)急響應(yīng)策略和調(diào)度優(yōu)化，以最小化所有應(yīng)急需求的響應(yīng)時(shí)間為目標(biāo)，決策卡車(chē)與無(wú)人機(jī)的調(diào)度方案。Liu等[11]考慮了救援行動(dòng)中的投入和產(chǎn)出因素，引入了DEA模型度量救援效率，并以最大化救援效率為目標(biāo)對(duì)救援路徑問(wèn)題進(jìn)行了研究。Alinaghian等[12]以最小化到達(dá)最后一個(gè)臨時(shí)救援中心的時(shí)間為目標(biāo)，對(duì)臨時(shí)救援中心的選址和救援無(wú)人機(jī)的路徑進(jìn)行決策。Jiao等[13]將不同的救援任務(wù)根據(jù)重要性分配權(quán)重，以電車(chē)為救援車(chē)輛，研究了救援車(chē)輛如何在能量受限的情況下快速高效地執(zhí)行多個(gè)救援任務(wù)，最大化所執(zhí)行救援任務(wù)的總權(quán)重。Wang等[14]以未滿足需求的總懲罰成本和被滿足需求點(diǎn)的等待成本最小為目標(biāo)，研究了災(zāi)后應(yīng)急資源分配和車(chē)輛路徑規(guī)劃問(wèn)題?；谝陨涎芯堪l(fā)現(xiàn)，研究災(zāi)后卡車(chē)和無(wú)人機(jī)協(xié)同配送物資的問(wèn)題較少，并且與應(yīng)急救援相關(guān)研究的優(yōu)化目標(biāo)很少考慮到受災(zāi)群眾對(duì)物資送達(dá)時(shí)間的滿意程度，進(jìn)而很少有問(wèn)題將節(jié)點(diǎn)的滿意度最大作為最終的目標(biāo)。因此本文以洪澇災(zāi)害后的應(yīng)急救援為背景，提出了一個(gè)多卡車(chē)多無(wú)人機(jī)的災(zāi)后救援物資配送問(wèn)題。根據(jù)道路受損情況和受災(zāi)群眾對(duì)物資需求的緊急程度對(duì)卡車(chē)和無(wú)人機(jī)的配送路線進(jìn)行規(guī)劃，在給定時(shí)間窗口內(nèi)滿足所有受災(zāi)群眾的需求條件下，使得受災(zāi)群眾滿意度最高。在本文的問(wèn)題中，隨著配送時(shí)間的延長(zhǎng)，受災(zāi)群眾的滿意度會(huì)不斷降低，并且由于節(jié)點(diǎn)的受災(zāi)嚴(yán)重程度不同，不同的節(jié)點(diǎn)的滿意度降低速度也不同，與Yu等[15]研究中的收益遞減模式相似，因此本文參考了Yu等[15]在研究收益遞減的魯棒團(tuán)隊(duì)定向問(wèn)題時(shí)提出的隨到達(dá)時(shí)間遞減的線性函數(shù)，構(gòu)建滿意度遞減函數(shù)計(jì)算每個(gè)受災(zāi)節(jié)點(diǎn)處物資送達(dá)時(shí)的滿意度，通過(guò)合理安排卡車(chē)和無(wú)人機(jī)的配送路線，盡快將受災(zāi)物資送達(dá)各個(gè)受災(zāi)節(jié)點(diǎn)，滿足受災(zāi)群眾的救援物資需求，最大化受災(zāi)群眾的滿意度。1

問(wèn)題建模1.1

問(wèn)題描述洪災(zāi)發(fā)生后，政府派遣卡車(chē)和無(wú)人機(jī)聯(lián)合進(jìn)行物資的配送，為多個(gè)受災(zāi)點(diǎn)提供救援物資配送服務(wù)。由于存在道路損毀問(wèn)題，卡車(chē)無(wú)法對(duì)一些受災(zāi)點(diǎn)提供服務(wù)，因此需要用無(wú)人機(jī)進(jìn)行配送?？紤]在災(zāi)后救援情況下，最重要的是能夠及時(shí)將救援物資送達(dá)，滿足受災(zāi)群眾對(duì)救援物資的需求，因此，本文將優(yōu)化目標(biāo)定為尋找最優(yōu)的卡車(chē)和無(wú)人機(jī)路徑規(guī)劃方案，使得救援物資配送獲得的受災(zāi)群眾滿意度最高。問(wèn)題考慮多輛卡車(chē)和多架無(wú)人機(jī)，包含3種類(lèi)型的節(jié)點(diǎn)：配送中心、卡車(chē)配送節(jié)點(diǎn)和無(wú)人機(jī)配送節(jié)點(diǎn)。無(wú)人機(jī)配送節(jié)點(diǎn)是由于災(zāi)后道路損壞需要由無(wú)人機(jī)配送物資，卡車(chē)配送節(jié)點(diǎn)的道路沒(méi)有被損壞，直接由卡車(chē)配送物資。在配送過(guò)程中，每輛卡車(chē)可以攜帶多架無(wú)人機(jī)從整個(gè)受災(zāi)區(qū)域的指揮中心同時(shí)出發(fā)，當(dāng)卡車(chē)到達(dá)某一需求點(diǎn)進(jìn)行配送時(shí)，無(wú)人機(jī)可以從卡車(chē)上起飛進(jìn)行救援物資的配送，由于存在續(xù)航里程的約束，無(wú)人機(jī)一次只能訪問(wèn)一個(gè)受災(zāi)點(diǎn)，與此同時(shí)，卡車(chē)可以沿著配送路徑繼續(xù)對(duì)其他受災(zāi)節(jié)點(diǎn)進(jìn)行配送。無(wú)人機(jī)完成物資配送任務(wù)后返回同一輛卡車(chē)，返回的位置必須是在受災(zāi)點(diǎn)處或指揮中心。直至所有受災(zāi)點(diǎn)的物資都配送完畢，卡車(chē)攜帶無(wú)人機(jī)一同返回指揮中心。無(wú)人機(jī)也可以直接從指揮中心起飛，為一個(gè)受災(zāi)節(jié)點(diǎn)配送物資后再返回指揮中心?？ㄜ?chē)-無(wú)人機(jī)路徑示例如圖1所示。災(zāi)后救援的情況下，受災(zāi)點(diǎn)對(duì)物資的需求更加緊急，受災(zāi)群眾的滿意度隨物資送達(dá)時(shí)間的延長(zhǎng)呈線性遞減。設(shè)定群眾的最大滿意度為，為受災(zāi)點(diǎn)處的滿意度遞減率，每個(gè)節(jié)點(diǎn)的滿意度遞減率不同，卡車(chē)或無(wú)人機(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á)。問(wèn)題假設(shè)如下。a.卡車(chē)和無(wú)人機(jī)都是同質(zhì)的；b.每輛卡車(chē)的起點(diǎn)和終點(diǎn)相同，都是指揮中心，途中不返回；c.每個(gè)受災(zāi)點(diǎn)只能由卡車(chē)或無(wú)人機(jī)配送一次；d.考慮到受災(zāi)群眾必須都要拿到物資，因此所有受災(zāi)點(diǎn)的需求都要在給定的時(shí)間窗內(nèi)得到滿足；e.每個(gè)受災(zāi)節(jié)點(diǎn)配送物資的重量均滿足無(wú)人機(jī)的載重量約束；f.每輛卡車(chē)線路上裝載的所有物資的總重量不超過(guò)卡車(chē)的最大容量；g.無(wú)人機(jī)飛出和返回卡車(chē)的地點(diǎn)均為卡車(chē)可配送的受災(zāi)點(diǎn)或指揮中心；h.卡車(chē)和無(wú)人機(jī)在受災(zāi)節(jié)點(diǎn)的服務(wù)時(shí)間忽略不計(jì)；i.各個(gè)節(jié)點(diǎn)之間的距離采用歐氏距離計(jì)算；j.無(wú)人機(jī)的飛行速度恒定，不受重力等其他因素的影響；k.無(wú)人機(jī)的最大飛行時(shí)間不受外界因素的影響；l.無(wú)人機(jī)每次起飛執(zhí)行配送任務(wù)均為滿電量，并且滿足無(wú)人機(jī)從卡車(chē)起飛到返回卡車(chē)這段路程需要的電量。1.2

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

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

解的描述和初始解生成卡車(chē)-無(wú)人機(jī)協(xié)同物資配送模型的解由卡車(chē)路徑和無(wú)人機(jī)路徑兩部分組成。如圖3所示，卡車(chē)路徑部分，每條卡車(chē)路徑的起點(diǎn)和終點(diǎn)都是指揮中心，中間從左到右依次為卡車(chē)配送的受災(zāi)節(jié)點(diǎn)；無(wú)人機(jī)路徑部分，每條無(wú)人機(jī)路徑由每輛卡車(chē)上每架無(wú)人機(jī)的路徑組合而成，每架無(wú)人機(jī)的路徑都依次包含3個(gè)節(jié)點(diǎn)：無(wú)人機(jī)起飛節(jié)點(diǎn)、無(wú)人機(jī)配送節(jié)點(diǎn)和無(wú)人機(jī)降落節(jié)點(diǎn)，其中無(wú)人機(jī)起飛節(jié)點(diǎn)和無(wú)人機(jī)降落節(jié)點(diǎn)都是對(duì)應(yīng)卡車(chē)路徑中的卡車(chē)配送節(jié)點(diǎn)或指揮中心。針對(duì)初始解生成，本文采用了隨機(jī)生成的方法分兩階段生成初始路徑。第一階段針對(duì)由卡車(chē)配送物資的受災(zāi)點(diǎn)建立卡車(chē)路徑解決方案；第二階段在第一階段生成的卡車(chē)路線的基礎(chǔ)上，針對(duì)由無(wú)人機(jī)配送物資的受災(zāi)節(jié)點(diǎn)，確定每架無(wú)人機(jī)的起飛節(jié)點(diǎn)和降落節(jié)點(diǎn)，生成無(wú)人機(jī)路徑。2.2

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

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

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

隨機(jī)修復(fù)算子對(duì)于每一個(gè)移除的卡車(chē)節(jié)點(diǎn)，該算子隨機(jī)選擇一條卡車(chē)路線，在滿足卡車(chē)載荷約束和時(shí)間窗約束的條件下，將該移除節(jié)點(diǎn)插入此卡車(chē)路線中；對(duì)于每一個(gè)移除的無(wú)人機(jī)節(jié)點(diǎn)，該算子也隨機(jī)選擇一條卡車(chē)路線，在滿足卡車(chē)載荷約束和時(shí)間窗約束的條件下，找到并確定與該無(wú)人機(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)的無(wú)人機(jī)路線中。2.2.5

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

后悔修復(fù)算子該算子依次循環(huán)計(jì)算每個(gè)移除節(jié)點(diǎn)的后悔值，找到卡車(chē)配送節(jié)點(diǎn)和無(wú)人機(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

算子選擇在算法迭代過(guò)程中，采用了輪盤(pán)賭的方法選擇使用的破壞算子和修復(fù)算子。每個(gè)算子被選中的概率為該算子的權(quán)重占所有算子權(quán)重之和的比例，因此在迭代過(guò)程中，算法根據(jù)算子的表現(xiàn)動(dòng)態(tài)地調(diào)整算子的權(quán)重，使表現(xiàn)更好的算子占的比重更大，以獲得質(zhì)量更高的解。迭代開(kāi)始前將每個(gè)算子的權(quán)重均設(shè)為1，在后續(xù)迭代過(guò)程中，按照如下的規(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)則。如果在迭代過(guò)程中獲得的新解比當(dāng)前解差，則以概率接受，其中表示新解，表示當(dāng)前解，表示目標(biāo)函數(shù)值，表示當(dāng)前溫度，隨著迭代次數(shù)的不斷增加，以的降溫速度不斷降低，其中。當(dāng)算法達(dá)到最大迭代次數(shù)或者連續(xù)迭代Imax次沒(méi)有得到更好的解時(shí)，算法直接結(jié)束，接受當(dāng)前的全局最優(yōu)解為最優(yōu)解并輸出。3

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

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

實(shí)驗(yàn)結(jié)果根據(jù)本文使用的改編后的Solomon數(shù)據(jù)集和設(shè)定的卡車(chē)、無(wú)人機(jī)相關(guān)參數(shù)，結(jié)合本文構(gòu)建的卡車(chē)-無(wú)人機(jī)協(xié)同物資配送模型，在卡車(chē)-無(wú)人機(jī)協(xié)同配送和卡車(chē)單獨(dú)配送兩種情景下，使用改進(jìn)的自適應(yīng)大鄰域搜索算法進(jìn)行求解，每個(gè)算例求解10次，記錄每次的目標(biāo)函數(shù)值并取平均值，結(jié)果對(duì)比如表3所示。為了驗(yàn)證無(wú)人機(jī)在應(yīng)急救援物資配送中的有效性，本文將卡車(chē)-無(wú)人機(jī)協(xié)同配送物資和只有卡車(chē)配送物資兩種模式下求得的受災(zāi)群眾滿意度