基于無人機(jī)運(yùn)輸?shù)膽?yīng)急物流路徑優(yōu)化研究

摘 要：世界各地?zé)o時(shí)無刻不在發(fā)生著應(yīng)急事件。在應(yīng)急事件中，最關(guān)鍵的問題就是物流救援。而在應(yīng)急物流中，車輛路徑問題又是一個(gè)棘手問題，因此優(yōu)化應(yīng)急物流路徑已迫在眉睫。文章以時(shí)間最短化為目標(biāo)，考慮配送中心約束，客戶點(diǎn)流量平衡，客戶點(diǎn)服務(wù)約束，無人機(jī)重量約束，無人機(jī)航行距離約束，所需無人機(jī)數(shù)量約束等條件構(gòu)建數(shù)學(xué)模型，引入模擬退火算法進(jìn)行分析，旨在提高應(yīng)急物流反應(yīng)速度和運(yùn)輸效率，加強(qiáng)應(yīng)急響應(yīng)能力，降低應(yīng)急物流成本，增強(qiáng)應(yīng)急物流的安全性，同時(shí)探索新型應(yīng)急物流運(yùn)輸方式，促進(jìn)應(yīng)急物流的優(yōu)化和升級(jí)。最后通過案例仿真分析結(jié)果，證明文中所建模型及設(shè)計(jì)的算法對(duì)解決該類問題的有效性。

關(guān)鍵詞：無人機(jī)；路徑規(guī)劃；應(yīng)急物流；模擬退火算法；車輛路徑問題

中圖分類號(hào)：F252 文獻(xiàn)標(biāo)志碼：A DOI：10.13714/j.cnki.1002-3100.2024.18.016

Abstract： The world is constantly experiencing emergency events， and in these situations， the most critical issue is emergency logistics and rescue operations. Within emergency logistics， vehicle routing issues poses a challenging problem， making emergency logistics path optimization an urgent necessity. This article aims to minimize response time， while considering constraints such as distribution center limitations， customer demand balancing， customer service constraints， UAV’s weight limitations， UAV’s flight distance constraints， and the required number of UAVs. A mathematical model is constructed to address these challenges. To achieve the optimization， a simulated annealing algorithm is introduced for analysis. The goal is to enhance the speed and efficiency of emergency logistics response， strengthen emergency response capabilities， reduce logistics costs， improve the safety of emergency logistics， and explore new modes of emergency transport. This research intends to promote the optimization and advancement of emergency logistics. Finally， the effectiveness of the proposed model and algorithm is demonstrated through case-based simulations， affirming their suitability for effectively solving this class of problems.

Key words： UAV; path planning; e1Zy760AIKBcYD191agQ22A==mergency logistics; simulated annealing algorithm; vehicle routing issues

0 引 言

隨著社會(huì)經(jīng)濟(jì)的發(fā)展和人口的不斷增長，各種自然災(zāi)害和突發(fā)事件頻繁發(fā)生，給物流運(yùn)輸帶來了巨大的挑戰(zhàn)。作為一種全新的物流運(yùn)輸方式，無人機(jī)運(yùn)輸在應(yīng)急物流中的應(yīng)用受到了廣泛的關(guān)注。無人機(jī)運(yùn)輸具有快速、高效、靈活、機(jī)動(dòng)等優(yōu)勢，可以在短時(shí)間內(nèi)將緊急物資送達(dá)受災(zāi)區(qū)域，有效提高應(yīng)急物流的效率，減輕災(zāi)民的痛苦[1-2]。無人機(jī)運(yùn)輸在應(yīng)急物流中有廣泛的應(yīng)用場景。然而，無人機(jī)運(yùn)輸在應(yīng)急物流中的應(yīng)用還面臨著一系列的問題和挑戰(zhàn)。例如無人機(jī)運(yùn)輸需要滿足快速響應(yīng)和高效運(yùn)輸?shù)囊?，但無人機(jī)當(dāng)前的飛行高度、飛行速度、續(xù)航能力等仍有一定的局限。因此，對(duì)于無人機(jī)運(yùn)輸?shù)膽?yīng)急物流路徑規(guī)劃研究顯得尤為重要，它能夠?yàn)闊o人機(jī)運(yùn)輸提供科學(xué)的理論基礎(chǔ)和技術(shù)支持，使其能夠更好地應(yīng)用于應(yīng)急物流中，提高救援效率和救援質(zhì)量，為災(zāi)民的生命和財(cái)產(chǎn)安全保駕護(hù)航[3-4]。本文所構(gòu)建的模型及算法能有效地解決應(yīng)急物流下的無人機(jī)運(yùn)輸路線問題，并且通過分析了解了最大載重量、最大航行距離以及時(shí)間窗懲罰系數(shù)對(duì)最優(yōu)解的影響。為應(yīng)急條件下無人機(jī)的運(yùn)輸路徑優(yōu)化問題研究提供了參考方向。本文的主要貢獻(xiàn)：相比于傳統(tǒng)的VRP問題，本文是基于無人機(jī)的運(yùn)輸，在運(yùn)輸條件上增加了無人機(jī)的續(xù)航這個(gè)約束條件以保證整個(gè)任務(wù)的順利實(shí)施；在應(yīng)急背景下，優(yōu)化目標(biāo)由傳統(tǒng)VRP問題的成本最低轉(zhuǎn)變?yōu)榭紤]人民生命財(cái)產(chǎn)安全的時(shí)間最短，并根據(jù)受災(zāi)情況的嚴(yán)重程度設(shè)置了配送節(jié)點(diǎn)的優(yōu)先級(jí)。

1909年美國成功試飛無人機(jī)，一戰(zhàn)期間，歐洲部分國家開始在相關(guān)技術(shù)領(lǐng)域取得突破，20世紀(jì)60年代美國開始將無人機(jī)用于軍事用途，而在民用領(lǐng)域則稍晚一些，1983年，日本首先研發(fā)出了農(nóng)用的噴灑型無人機(jī)，到現(xiàn)在經(jīng)過幾十年的發(fā)展，日本已在世界上農(nóng)用無人機(jī)領(lǐng)域處于領(lǐng)先地位。2013年，亞馬遜創(chuàng)始人提出了無人機(jī)物流送貨的概念，隨后谷歌、Facebook等互聯(lián)網(wǎng)企業(yè)也相繼提出無人機(jī)物流的發(fā)展意向及規(guī)劃，但是由于美國對(duì)航空器領(lǐng)域的政策管控非常嚴(yán)，很多公司的發(fā)展方向遭受限制，只能在澳大利亞等國家進(jìn)行試驗(yàn)。歐洲等一些國家隨后相繼提出了無人機(jī)物流的發(fā)展概念，隨著時(shí)間的推移，目前歐洲在無人機(jī)領(lǐng)域也處于領(lǐng)先地位。在無人機(jī)運(yùn)輸中，路徑規(guī)劃是最重要的一環(huán)，剛開始的路徑規(guī)劃都是由人工完成，但隨著環(huán)境的變遷和國家政策的逐步正規(guī)化，傳統(tǒng)的路徑規(guī)劃技術(shù)已經(jīng)滿足不了現(xiàn)實(shí)情況的需求，計(jì)算機(jī)算法以及數(shù)學(xué)建模等熱點(diǎn)模式逐漸被國際學(xué)者關(guān)注，取得了較多的研究性成果。如基于激素的生物啟發(fā)式無人機(jī)路徑規(guī)劃算法研究、分布式多機(jī)器人路徑規(guī)劃算法研究等。在協(xié)調(diào)控制技術(shù)研究方面，國外無人機(jī)研究人員也取得了不少成果，為多機(jī)無人機(jī)協(xié)同路徑規(guī)劃提供了可靠的技術(shù)保障。在視覺計(jì)算技術(shù)研究領(lǐng)域，國外研究者通過利用基于視覺的無人機(jī)路徑規(guī)劃方法，實(shí)現(xiàn)了無人機(jī)在復(fù)雜環(huán)境中的智能化操作。其中國外Alraslan 等指出路徑規(guī)劃算法的目標(biāo)是尋找從源位置到目標(biāo)位置的最優(yōu)路徑，并提出了一種基于遺傳算法的無人機(jī)實(shí)時(shí)路徑規(guī)劃器[5]。此方法不識(shí)別障礙物之外或障礙物之間的任何特定點(diǎn)，以解決無形路徑的問題。此外，該方法不使用遺傳算法中的額外步驟來處理由障礙物內(nèi)部生成點(diǎn)或與障礙物相交的路徑段產(chǎn)生的問題。Zammit等提出了針對(duì)復(fù)雜室內(nèi)環(huán)境下的3D無人機(jī)路徑規(guī)劃問題，比較分析了兩種最常用的基于圖和基于采樣的算法及其變體[6]。該分析的結(jié)果概述了方法的可用性，可以幫助未來的無人機(jī)路徑規(guī)劃設(shè)計(jì)者選擇與具體應(yīng)用相關(guān)的最佳參數(shù)配置的最佳算法。該項(xiàng)工作解決了A*和RRT標(biāo)準(zhǔn)算法的缺點(diǎn)，開發(fā)了一種新的A*紋波減少算法，一種新的RRT變體和一個(gè)專門設(shè)計(jì)的平滑算法。

國內(nèi)的無人機(jī)領(lǐng)域研究則起步更晚，從某一方面來說，無人機(jī)產(chǎn)業(yè)目前在國內(nèi)的蓬勃發(fā)展，與中國制造和中國的現(xiàn)代經(jīng)濟(jì)發(fā)展有著很大的聯(lián)系，中國目前的民用無人機(jī)規(guī)模逐年上升，爆發(fā)式增長，尤其是在物流領(lǐng)域的應(yīng)用，成為無人機(jī)的重點(diǎn)發(fā)展方向，其中大疆、京東、順豐等無人機(jī)與物流企業(yè)走在國內(nèi)發(fā)展前列，而對(duì)于無人機(jī)路徑優(yōu)化的研究，國內(nèi)學(xué)者也做了許多研究，提出了許多新穎的見解和解決方案[7-9]。如基于M-GA的多無人機(jī)協(xié)同任務(wù)分配問題優(yōu)化研究、基于強(qiáng)化學(xué)習(xí)的無人機(jī)路徑規(guī)劃算法研究等。在仿真技術(shù)領(lǐng)域，我國學(xué)者也取得了較大進(jìn)展，如利用模糊邏輯控制和遺傳算法對(duì)無人機(jī)路徑規(guī)劃進(jìn)行仿真等。在飛行控制技術(shù)研究領(lǐng)域，我國無人機(jī)研究人員對(duì)飛行控制技術(shù)進(jìn)行了深入研究，為無人機(jī)路徑規(guī)劃提供了可靠的技術(shù)保障。其中段聰（2022）提出了關(guān)于帶有取送貨的車輛路徑問題，通過分析無人機(jī)調(diào)度的相關(guān)研究，結(jié)合無人機(jī)與卡車各自的特點(diǎn)， 選取了卡車作為無人機(jī)著陸和起飛平臺(tái)的配送模式，探索了醫(yī)藥物流路徑優(yōu)化相關(guān)問題[10]。其主要思想是構(gòu)建一個(gè)混合的整數(shù)模型，并以最短的配送時(shí)間為目標(biāo)，在這個(gè)模型中，作者加入了車輛載量以及客戶需求等約束條件，然后設(shè)計(jì)了無人機(jī)回收端鄰域搜索算法并進(jìn)行求解結(jié)果。作者還對(duì)一般傳統(tǒng)的配送模式以及無人機(jī)配送模式進(jìn)行了實(shí)驗(yàn)對(duì)比， 并且通過設(shè)計(jì)的模型去驗(yàn)證了算法。最后作者依據(jù)實(shí)際情況，選用了實(shí)際的數(shù)據(jù)，并選擇了最短配送時(shí)間的目標(biāo)參數(shù)，運(yùn)用無人機(jī)回收端鄰域搜索算法進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果表明，此算法確實(shí)有一定可靠性和合理性，為物流企業(yè)提供了發(fā)展借鑒的方向。魯熙今（2022）提出的關(guān)于卡車-無人機(jī)協(xié)同配送路徑優(yōu)化問題是不同于傳統(tǒng)車輛路徑優(yōu)化問題的一個(gè)新問題，它不是簡單地著眼于卡車行駛路徑，而是如何合理協(xié)調(diào)兩種載運(yùn)工具，使其實(shí)現(xiàn)降本增效的目標(biāo)[11]。特別是在無人機(jī)可以在多個(gè)客戶點(diǎn)起降、無人機(jī)飛行距離受到載重影響的現(xiàn)實(shí)條件下， 其復(fù)雜程度遠(yuǎn)遠(yuǎn)高于僅使用卡車進(jìn)行物流配送的車輛路徑問題。于是建立了以配送時(shí)間最短為目標(biāo)，考慮無人機(jī)飛行距離受載重影響的混合整數(shù)規(guī)劃模型，為卡車支持無人機(jī)配送問題（Carrier-Vehicle Problem with Drone，CVP-D）設(shè)計(jì)了以K-Means++聚類算法為基礎(chǔ)的三階段求解算法， 為飛行伙伴旅行商問題（Flying Side-kick Travelling Salesman Problem，F(xiàn)STSP）設(shè)計(jì)了兩階段改進(jìn)模擬退火算法， 利用車輛路徑問題標(biāo)準(zhǔn)算例分別進(jìn)行求解， 通過與單卡車配送進(jìn)行對(duì)比， 驗(yàn)證了模型的有效性。最后，引入真實(shí)案例進(jìn)行仿真實(shí)驗(yàn)， 驗(yàn)證兩種配送模式在現(xiàn)實(shí)生活中的可行性， 定量分析了兩種配送模式帶來的實(shí)際效益，并通過靈敏度分析， 總結(jié)了兩種配送模式分別適用的物流配送場景，對(duì)于提升卡車-無人機(jī)協(xié)同配送效果具有一定的參考價(jià)值。陳存糧（2021）提出在低密度人口地區(qū)， 如貧困鄉(xiāng)鎮(zhèn)或偏遠(yuǎn)山區(qū)，對(duì)相關(guān)配送問題求解[12]。

求解思路主要是將人口密度較低的地區(qū)劃分為若干個(gè)配送區(qū)域，每個(gè)區(qū)域內(nèi)的配送距離相對(duì)較短且配送點(diǎn)數(shù)量較少，利用無人機(jī)進(jìn)行配送。在這個(gè)過程中，他主要采用以下思路：第一，采用多點(diǎn)依次配送策略：將一個(gè)配送區(qū)域內(nèi)的多個(gè)客戶點(diǎn)按照距離遠(yuǎn)近排序，然后依次使用無人機(jī)進(jìn)行配送。這種策略可以有效地減少每次配送的距離和時(shí)間，提高無人機(jī)的配送效率。第二，使用混合整數(shù)規(guī)劃模型優(yōu)化配送路徑：針對(duì)多點(diǎn)依次配送策略，建立混合整數(shù)規(guī)劃模型，通過對(duì)無人機(jī)配送路徑的優(yōu)化，進(jìn)一步降低配送時(shí)間和成本。第三，使用無人機(jī)-卡車協(xié)同配送模式：對(duì)于人口密度較低的地區(qū)，采用無人機(jī)進(jìn)行配送。而對(duì)于周邊密度適中的地區(qū)，則采用卡車進(jìn)行中轉(zhuǎn)，實(shí)現(xiàn)無人機(jī)和卡車的協(xié)同配送。這種配送模式可以在提高配送效率的同時(shí)，保證配送的及時(shí)性和準(zhǔn)確性。第四，利用配送網(wǎng)絡(luò)進(jìn)行路徑優(yōu)化：建立基于高精度地圖的配送網(wǎng)絡(luò)，通過對(duì)網(wǎng)絡(luò)優(yōu)化算法的應(yīng)用，實(shí)現(xiàn)無人機(jī)路徑的優(yōu)化和配送的實(shí)時(shí)監(jiān)控，提高配送效率、準(zhǔn)確性和安全性。以上思路的綜合應(yīng)用可以有效地解決低密度人口地區(qū)的相關(guān)配送問題，提高無人機(jī)配送的效率和效益。謝關(guān)淑（2021）提出關(guān)于應(yīng)急物流下的無人機(jī)與卡車協(xié)同配送路徑優(yōu)化問題[13]。

求解思路主要是將無人機(jī)和卡車進(jìn)行協(xié)同配送，以提高應(yīng)急物流的配送效率和應(yīng)對(duì)突發(fā)事件。具體思路如下。第一，建立綜合配送模型：設(shè)計(jì)基于混合整數(shù)規(guī)劃的綜合配送模型，將無人機(jī)與卡車進(jìn)行協(xié)同配送，以最小化總配送成本為目標(biāo)。第二，采用模擬退火算法進(jìn)行路徑規(guī)劃：建立無人機(jī)和卡車的路徑規(guī)劃模型，并采用模擬退火算法進(jìn)行路徑優(yōu)化。該算法可以在保證較好解的質(zhì)量的前提下，避免陷入局部最優(yōu)解。第三，考慮配送路徑的實(shí)時(shí)變化：在實(shí)際應(yīng)急物流場景下，配送路徑會(huì)因?yàn)椴粩嘧兓氖录l(fā)生調(diào)整。因此，需要在模型中考慮路徑的實(shí)時(shí)變化，以保證路徑的穩(wěn)定性和可靠性。第四，針對(duì)不同應(yīng)急事件制定不同應(yīng)對(duì)方案：在不同應(yīng)急事件下，無人機(jī)和卡車的協(xié)同配送方案也需要發(fā)生改變。因此需要根據(jù)不同的應(yīng)急事件制定不同的應(yīng)對(duì)方案，以提高應(yīng)急響應(yīng)能力。以上思路的應(yīng)用可以有效提高應(yīng)急物流配送的效率和效益，同時(shí)也可以應(yīng)對(duì)突發(fā)事件，提高應(yīng)急物流的快速響應(yīng)和迅速解決問題的能力。

1 應(yīng)急物流路徑優(yōu)化問題數(shù)學(xué)模型

構(gòu)建基于無人機(jī)運(yùn)輸?shù)膽?yīng)急物流路徑優(yōu)化模型。

1.1 問題描述

在某場突發(fā)事件（如地震、山洪、火災(zāi)等）發(fā)生后，需要盡快將必要的物資和救援隊(duì)伍送往事故現(xiàn)場進(jìn)行救援。假設(shè)有一批無人機(jī)可以用于貨運(yùn)運(yùn)輸，每架無人機(jī)擁有相同的貨運(yùn)能力、速度、續(xù)航能力等特點(diǎn)?，F(xiàn)在需要確定合適的無人機(jī)運(yùn)輸路徑，保證救援物資和隊(duì)伍能夠在最短的時(shí)間內(nèi)到達(dá)事故現(xiàn)場[14]。假設(shè)航空交通擁堵和天氣等因素不會(huì)對(duì)無人機(jī)運(yùn)輸路徑造成太大的影響，現(xiàn)在需要設(shè)計(jì)一個(gè)基于無人機(jī)運(yùn)輸?shù)膽?yīng)急物流路徑優(yōu)化問題的模型。要求如下。

確定無人機(jī)運(yùn)輸路線，使得時(shí)間最短；根據(jù)貨運(yùn)能力確定無人機(jī)任務(wù)分配的策略，使得貨物能夠得到最大化的使用；保證無人機(jī)能夠在有限的續(xù)航范圍內(nèi)完成運(yùn)輸任務(wù)；避免無人機(jī)碰撞，以及其他安全問題；保證受災(zāi)嚴(yán)重的地區(qū)優(yōu)先得到物資配送。

問題中需要確定以下內(nèi)容。

解決思路可以采用模擬退火算法對(duì)運(yùn)輸路徑進(jìn)行優(yōu)化設(shè)計(jì)，通過設(shè)定初始參數(shù)，調(diào)整搜索范圍，降低溫度等一系列策略，一步步優(yōu)化無人機(jī)的運(yùn)輸路徑。同時(shí)，還需要考慮無人機(jī)的負(fù)載均衡問題、貨運(yùn)安全問題以及調(diào)度算法的復(fù)雜度問題等。

1.2 模型假設(shè)

第一，假設(shè)使用的載物無人機(jī)之間具有相同的最大安全航行距離，并且在整個(gè)航行過程中保持速度不變，不考慮氣候、國家政策等禁飛約束。 第二，無人機(jī)從配送中心出發(fā)去服務(wù)目標(biāo)點(diǎn)，配送任務(wù)結(jié)束后回到起始點(diǎn)。第三，每個(gè)客戶的包裹只能由一架無人機(jī)運(yùn)送一次完成配送。 第四，無人機(jī)可以一次對(duì)多個(gè)顧客節(jié)點(diǎn)進(jìn)行送貨，且每一次飛行都需要滿足無人機(jī)的載重和最遠(yuǎn)飛行距離的限制。第五，無人機(jī)的使用數(shù)量沒有限制。 第六，所有無人機(jī)的型號(hào)一樣，不考慮交通堵塞。

1.3 模型中符號(hào)和決策變量（見表1）

1.4 模型建立

2 模型求解

本文模型是基于模擬退火算法進(jìn)行，算法通過一系列的迭代過程來搜索更優(yōu)的解。在每一次迭代中，根據(jù)當(dāng)前溫度和鄰域解的差異程度，決定是否接受新的解。這一步是模擬“退火”的過程，隨著溫度的降低，算法更趨向于接受使目標(biāo)函數(shù)減小的解，但也有可能接受使目標(biāo)函數(shù)增大的解，以避免陷入局部最優(yōu)解。隨著迭代的進(jìn)行，溫度逐漸降低，搜索空間逐漸縮小，最終在一定條件下終止迭代過程。最終得到的解是算法在搜索過程中找到的最優(yōu)或次優(yōu)解。

模擬退火算法（Simulated Annealing Algorithm）是一種啟發(fā)式優(yōu)化算法，用于尋找非全局最優(yōu)解的復(fù)雜優(yōu)化問題。它最初由Kirkpatrick、Gelatt和Vecchi在1983年提出，后進(jìn)行了進(jìn)一步的研究和改進(jìn)。模擬退火算法模擬了冶金中物質(zhì)從高溫狀態(tài)到低溫狀態(tài)的冷卻過程，利用隨機(jī)性和概率接受策略來跳出局部最小值，并最終找到全局最優(yōu)解[16-17]。圖1為退火算法的工作流程圖。

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)計(jì)

3.2 影響參數(shù)分析

由上述實(shí)驗(yàn)可知，模擬退火算法能有效求解模型，且不同參數(shù)對(duì)于結(jié)果的影響較大，下面我們通過對(duì)無人機(jī)載重量、無人機(jī)最大航行距離以及違反最晚時(shí)間窗約束的懲罰函數(shù)系數(shù)來分析不同參數(shù)對(duì)實(shí)驗(yàn)結(jié)果的影響。

無人機(jī)載重量：保持其他參數(shù)不變，設(shè)立不同的無人機(jī)載重量。結(jié)果表明，隨著無人機(jī)載重量變大，每輛無人機(jī)的裝載率會(huì)顯著變小。當(dāng)無人機(jī)的最大載重量小于路徑上所有客戶需求量總和時(shí)，每輛無人機(jī)的裝載率已經(jīng)大于100%，說明無人機(jī)已經(jīng)無法完成配送任務(wù)，而最終的總成本變化趨勢圖也表明，總成本沒有收斂到最小，優(yōu)化目標(biāo)無法完成。而當(dāng)無人機(jī)的最大載重量遠(yuǎn)大于路徑上的所有客戶點(diǎn)需求量總和時(shí)，大部分無人機(jī)的裝載率還沒到50%，過大的無人機(jī)載重量會(huì)導(dǎo)致無人機(jī)性能的浪費(fèi)，造成經(jīng)濟(jì)效益偏低，實(shí)驗(yàn)得到的數(shù)據(jù)見表4。

無人機(jī)最大航行距離：保持其他參數(shù)不變，設(shè)置不同的無人機(jī)最大航行距離。結(jié)果表明，隨著無人機(jī)最大航行距離的變大，無人機(jī)的裝載率以及航行距離都會(huì)受到影響。當(dāng)無人機(jī)最大航行距離小于路徑長度時(shí)，必須增大一部分無人機(jī)的裝載量以及路徑長度以滿足任務(wù)需求。而此時(shí)部分無人機(jī)的實(shí)際航行距離已經(jīng)大于最大航行距離，所以無法完成優(yōu)化目標(biāo)。當(dāng)無人機(jī)最大航行距離遠(yuǎn)大于路徑長度時(shí)，無人機(jī)的裝載率以及航行距離基本不受影響，但會(huì)浪費(fèi)無人機(jī)性能，造成經(jīng)濟(jì)效益偏低。結(jié)果見表5。

違反最晚時(shí)間窗約束的懲罰函數(shù)系數(shù)：保持其他參數(shù)不變，設(shè)置不同的違反最晚時(shí)間窗約束的懲罰函數(shù)系數(shù)。結(jié)果表明，當(dāng)違反最晚時(shí)間窗約束的懲罰函數(shù)系數(shù)小于違反容量和距離約束的懲罰函數(shù)系數(shù)時(shí)，相當(dāng)于容量和距離約束更重要。其優(yōu)化目標(biāo)更偏向于容量和距離約束，最優(yōu)路徑基本變化不大，在實(shí)際情況中可能會(huì)造成部分受災(zāi)嚴(yán)重的災(zāi)民無法得到及時(shí)的救援。當(dāng)違反最晚時(shí)間窗約束的懲罰函數(shù)系數(shù)大于違反容量和距離約束的懲罰函數(shù)系數(shù)時(shí)，相當(dāng)于最晚時(shí)間窗約束更重要，優(yōu)化目標(biāo)更偏向于時(shí)間窗約束，最優(yōu)路徑會(huì)更偏向于節(jié)點(diǎn)優(yōu)先級(jí)。實(shí)驗(yàn)結(jié)果如表6所示。

所得的全局最優(yōu)解表格說明，最終配送路徑均滿足約束條件，全局最優(yōu)解總成本變化趨勢圖說明，本文所設(shè)計(jì)的算法能有效達(dá)到優(yōu)化目標(biāo)，降低成本（此成本是指最后一輛無人機(jī)回到配送中心時(shí)間和違反時(shí)間窗所產(chǎn)生的懲罰成本之和），通過對(duì)無人機(jī)最大載重量、最大航行距離的約束，保證了無人機(jī)的載重量以及續(xù)航時(shí)間，通過對(duì)配送節(jié)點(diǎn)優(yōu)先級(jí)設(shè)置時(shí)間窗懲罰成本，保證了受災(zāi)嚴(yán)重的地區(qū)優(yōu)先得到配送，且收斂速度較快（整個(gè)計(jì)算所用時(shí)間大約為13.54s），驗(yàn)證了算法的有效性。

4 結(jié) 論

本文得到的主要結(jié)論如下。

首先，相比于傳統(tǒng)的VRP問題，本文是基于無人機(jī)的運(yùn)輸，在運(yùn)輸條件上增加了無人機(jī)續(xù)航這個(gè)約束條件以保證整個(gè)任務(wù)的順利實(shí)施。

其次，在應(yīng)急背景下，優(yōu)化目標(biāo)由傳統(tǒng)VRP問題的成本最低轉(zhuǎn)變?yōu)榭紤]人民生命財(cái)產(chǎn)安全的時(shí)間最短，并根據(jù)受災(zāi)情況嚴(yán)重程度設(shè)置了配送節(jié)點(diǎn)的優(yōu)先級(jí)。

最后，設(shè)計(jì)了仿真實(shí)驗(yàn)以驗(yàn)證算法的有效性，有效解決了基于無人機(jī)運(yùn)輸?shù)膽?yīng)急物流路徑優(yōu)化問題，并對(duì)影響參數(shù)進(jìn)行了研究，分析了最大載重量、最大航行距離以及違反時(shí)間窗懲罰成本函數(shù)系數(shù)對(duì)最優(yōu)解的影響，對(duì)實(shí)際情況中具體參數(shù)的設(shè)計(jì)以及無人機(jī)的實(shí)際選擇具有一定借鑒意義。

參考文獻(xiàn)：

[1] 費(fèi)毓晗，張洪海，張連東，等．城市物流無人機(jī)運(yùn)輸路徑規(guī)劃[J].武漢理工大學(xué)學(xué)報(bào)（交通科學(xué)與工程版），2023，47（1）：79-84，89.

[2] 谷金蔚，劉旭．無人機(jī)物流分析與應(yīng)用研究[J]．科技資訊，2018，16（18）：11-123.

[3] 王琳璘．H物流公司車輛路徑優(yōu)化問題研究[D]．廣州：廣東工業(yè)大學(xué)，2022.

[4] 孫亞強(qiáng)．H企業(yè)物流配送中心選址及路徑優(yōu)化問題研究[D]．濟(jì)南：山東財(cái)經(jīng)大學(xué)，2022.

[5] ALRASLAN M，ALKURDI A H．UAV path planning using genetic algorithm with parallel implementation[J]．InternationalJournal of Computational Science and Information Technology，2022，10（2）：1-15.

[6] ZAMMIT C，VAN KAMPEN E．Comparison between A*and RRT algorithms for 3D UAV path planning[J]．UnmannedSystems，2021，10：129-146.

[7] 陳亮．農(nóng)村地區(qū)無人機(jī)配送選址及路徑規(guī)劃研究[D]．北京：北京信息科技大學(xué)，2022.

[8] 郭文靜．多目標(biāo)粒子群算法的研究與應(yīng)用[D]．東莞：東莞理工學(xué)院，2022.

[9] 張碩航．基于改進(jìn)蟻群混合算法的末端物流路徑優(yōu)化研究[D]．呼和浩特：內(nèi)蒙古師范大學(xué)，2022.

[10] 段聰．基于無人機(jī)與卡車聯(lián)合配送的醫(yī)藥物流路徑優(yōu)化研究[D]．沈陽：沈陽工業(yè)大學(xué)，2022.

[11] 魯熙今．卡車-無人機(jī)協(xié)同配送路徑優(yōu)化模型與算法[D]．蘭州：蘭州交通大學(xué)，2022.

[12] 陳存糧．無人機(jī)末端物流配送算法研究[D]．西安：西安電子科技大學(xué)，2021.

[13] 謝關(guān)淑．考慮應(yīng)急物流需求等級(jí)的無人機(jī)與卡車協(xié)同配送路徑優(yōu)化問題研究[D]．成都：西南交通大學(xué)，2021.

[14] 黎聰，謝莉．物流無人機(jī)技術(shù)在廣西農(nóng)村配送的可行性研究及實(shí)際應(yīng)用[J]．物流工程與管理，2022，44（9）：31-33.

[15] 林巧珍．帶時(shí)間窗約束的醫(yī)藥協(xié)同配送路徑優(yōu)化研究[D]．廈門：廈門理工學(xué)院，2022.

[16] 苗苗．具有禁飛區(qū)條件的無人機(jī)群路徑規(guī)劃研究[D]．西安：長安大學(xué)，2021.

[17] 許衛(wèi)衛(wèi)．復(fù)雜低空物流無人機(jī)路徑規(guī)劃技術(shù)研究[D]．南京：南京航空航天大學(xué)，2020.

[18] 楊沙．考慮動(dòng)態(tài)需求的冷鏈物流配送路徑優(yōu)化研究[D]．沈陽：沈陽工業(yè)大學(xué)，2022.

[19] 羅娟．物流末端“車輛-無人機(jī)”協(xié)同配送路徑優(yōu)化研究[D]．重慶：重慶郵電大學(xué)，2022.

[20] 王家杰．基于時(shí)間窗的M公司生鮮產(chǎn)品物流配送路徑優(yōu)化研究[D]．上海：東華大學(xué)，2022.