考慮多投遞的帶無(wú)人機(jī)車輛路徑規(guī)劃問(wèn)題研究

馬華偉，馬 凱，郭 君

（1.合肥工業(yè)大學(xué) 管理學(xué)院，合肥 230009；2.過(guò)程優(yōu)化與智能決策教育部重點(diǎn)實(shí)驗(yàn)室，合肥 230009）

0 概述

近年來(lái)，車輛與無(wú)人機(jī)協(xié)同配送成為應(yīng)急救援的重要手段，在新冠肺炎疫情下的醫(yī)療物資配送［1］、西昌瀘山森林火災(zāi)救援［2］等事件中均有應(yīng)用。其中，合理規(guī)劃車輛與無(wú)人機(jī)路徑對(duì)于提高應(yīng)急救援的時(shí)效性至關(guān)重要，這也使得相應(yīng)的路徑規(guī)劃問(wèn)題成為一個(gè)備受關(guān)注的研究熱點(diǎn)。

車輛與無(wú)人機(jī)協(xié)同路徑規(guī)劃的研究尚處于起步階段，國(guó)內(nèi)外學(xué)者對(duì)該問(wèn)題的研究主要集中在帶無(wú)人機(jī)的旅行商問(wèn)題（Travelling Salesman Problem with Drone，TSPD）、帶無(wú)人機(jī)的車輛路徑問(wèn)題（Vehicle Routing Problem with Drones，VRPD）及其衍生問(wèn)題的建模與求解算法上。在對(duì)TSPD 的拓展研究中，文獻(xiàn)［3-4］分別探討了無(wú)人機(jī)與車輛在途結(jié)合問(wèn)題以及單車輛多無(wú)人機(jī)的TSPD 變體。文獻(xiàn)［5］建立高寒山地環(huán)境下的車機(jī)協(xié)同物資配送模型，并提出相應(yīng)的啟發(fā)式求解算法。文獻(xiàn)［6］提出一種車輛-無(wú)人機(jī)串聯(lián)交付系統(tǒng)優(yōu)化模型，其利用K-means算法尋找無(wú)人機(jī)發(fā)射點(diǎn)并利用遺傳算法完成車輛路徑構(gòu)造。文獻(xiàn)［7］提出帶無(wú)人機(jī)站點(diǎn)的車輛路徑規(guī)劃問(wèn)題（TSP-DS），文獻(xiàn)［8］考慮多車輛與異構(gòu)無(wú)人機(jī)并提出多車輛帶無(wú)人機(jī)旅行商問(wèn)題（mFSTSP）。在考慮車輛容量限制的情況下，TSPD 會(huì)轉(zhuǎn)化為更加一般化的VRPD。文獻(xiàn)［9-10］在最壞情況下分析VRPD 中無(wú)人機(jī)速度與數(shù)量這2 個(gè)關(guān)鍵因素。文獻(xiàn)［11-12］考慮VRPD 中的單車多無(wú)人機(jī)變體以及車機(jī)在途結(jié)合變體。文獻(xiàn)［13］介紹帶無(wú)人機(jī)和時(shí)間窗的車輛路徑問(wèn)題。文獻(xiàn)［14-15］分別考慮無(wú)人機(jī)補(bǔ)給的車輛路徑問(wèn)題與無(wú)人機(jī)取貨的車輛路徑問(wèn)題。此外，文獻(xiàn)［16］在其研究中創(chuàng)新性地提出用強(qiáng)化學(xué)習(xí)方法來(lái)解決車機(jī)組合路徑規(guī)劃問(wèn)題，這為利用人工智能技術(shù)［17-18］解決復(fù)雜車機(jī)協(xié)同問(wèn)題提供了新思路，在該問(wèn)題中，車輛為無(wú)人機(jī)提供起降與補(bǔ)給服務(wù)，但不負(fù)責(zé)配送任務(wù)。

綜上，車機(jī)協(xié)同路徑規(guī)劃及其衍生問(wèn)題目前已取得一定的進(jìn)展，且現(xiàn)有研究主要關(guān)注無(wú)人機(jī)每次配送單個(gè)用戶的情形。然而，隨著無(wú)人機(jī)技術(shù)的不斷發(fā)展，支持單次多用戶配送的高負(fù)載無(wú)人機(jī)開(kāi)始出現(xiàn)，這使得更加靈活的車機(jī)協(xié)同方式成為可能，亟待開(kāi)展相應(yīng)路徑規(guī)劃問(wèn)題的建模與求解工作。本文對(duì)VRPD 進(jìn)行拓展，提出一種車輛與無(wú)人機(jī)協(xié)同路徑規(guī)劃問(wèn)題，即考慮多投遞的帶無(wú)人機(jī)車輛路徑規(guī)劃問(wèn)題（Vehicle Routing Problem with Drones Considering Multi-Delivery，VRPD-MD）。在VRPD-MD 中，無(wú)人機(jī)可以在任意架次中為多個(gè)受災(zāi)區(qū)域配送物資，而車輛在配送物資的同時(shí)支持無(wú)人機(jī)完成多次起飛和降落。本文建立以最小化最大完工時(shí)間為目標(biāo)函數(shù)的混合整數(shù)規(guī)劃模型，并設(shè)計(jì)一種基于遺傳方法的自適應(yīng)算法（Adaptive Algorithm Based on Genetic Method，AAGM）對(duì)該模型進(jìn)行求解。

1 數(shù)學(xué)模型

1.1 問(wèn)題描述

在VRPD-MD 中，車輛與無(wú)人機(jī)協(xié)同完成多個(gè)受災(zāi)點(diǎn)配送任務(wù)，無(wú)人機(jī)在任意架次中服務(wù)多個(gè)受災(zāi)點(diǎn)，車輛在配送的同時(shí)支持無(wú)人機(jī)多次起降，目的是尋找耗時(shí)最短的配送路徑。本文所提出的車機(jī)協(xié)同模式更加貼近實(shí)際配送需求，可以充分發(fā)揮無(wú)人機(jī)的速度優(yōu)勢(shì)，同時(shí)車機(jī)并行交付方式也能有效減少總體交付時(shí)間。為了建立數(shù)學(xué)模型，本文作出如下合理假設(shè)：

1）每輛車搭載一架無(wú)人機(jī)，且無(wú)人機(jī)必須從車輛起飛并返回起飛車輛?？紤]車輛與無(wú)人機(jī)的容量約束，無(wú)人機(jī)電量限制其續(xù)航時(shí)長(zhǎng)。

2）車輛與無(wú)人機(jī)行駛在歐氏空間，且只能在受災(zāi)點(diǎn)交會(huì)。

3）車輛與無(wú)人機(jī)必須在交會(huì)位置進(jìn)行時(shí)間同步，即較早到達(dá)交會(huì)節(jié)點(diǎn)的一方需要等待另一方。

4）有足夠的電池可供無(wú)人機(jī)替換，并且忽略電池更換和電池充電的時(shí)間。

1.2 問(wèn)題建模

為便于模型描述，表1 給出建模過(guò)程中所應(yīng)用的符號(hào)及其含義。

表1 符號(hào)及其含義Table 1 Symbols and their meanings

基于上述符號(hào)和變量，本文建立如下混合整數(shù)規(guī)劃模型：

其中：目標(biāo)函數(shù)式（1）表示最小化所有車輛返回倉(cāng)庫(kù)的運(yùn)行時(shí)間；約束條件式（2）確保每一個(gè)受災(zāi)點(diǎn)必須被車輛或無(wú)人機(jī)訪問(wèn)；約束條件式（3）為車輛在倉(cāng)庫(kù)節(jié)點(diǎn)的流量約束；約束條件式（4）保障車輛在受災(zāi)點(diǎn)的流量平衡；約束條件式（5）、式（6）分別保障無(wú)人機(jī)在起飛節(jié)點(diǎn)與降落節(jié)點(diǎn)的流量平衡；約束條件式（7）、式（8）保障無(wú)人機(jī)在提供服務(wù)的受災(zāi)點(diǎn)流量平衡；約束條件式（9）、式（10）分別為車輛容量約束與無(wú)人機(jī)架次容量約束；約束條件式（11）為無(wú)人機(jī)架次續(xù)航約束；約束條件式（12）、式（13）將車輛與無(wú)人機(jī)在起飛節(jié)點(diǎn)和降落節(jié)點(diǎn)的時(shí)間調(diào)整為一致；約束條件式（14）、式（15）為車輛與無(wú)人機(jī)的運(yùn)行時(shí)間不等式，其中，無(wú)人機(jī)的起飛和降落消耗一個(gè)單位時(shí)間，該時(shí)間分別被計(jì)算到車輛與無(wú)人機(jī)的運(yùn)行時(shí)間內(nèi)；約束條件式（16）、式（17）表示所有變量的取值約束。

2 基于遺傳思想的自適應(yīng)算法設(shè)計(jì)

遺傳算法［19-20］是求解無(wú)人機(jī)路徑規(guī)劃問(wèn)題的常用方法之一，本文考慮VRPD-MD 的特點(diǎn)，設(shè)計(jì)一種基于遺傳思想的自適應(yīng)算法AAGM。

2.1 染色體編碼

在AAGM 算法中，一個(gè)解被表示為由多條車輛與無(wú)人機(jī)組合路線組成的染色體。本文采用自然數(shù)編碼方式，染色體表示卡車和無(wú)人機(jī)的訪問(wèn)序列，每個(gè)基因位置存儲(chǔ)一個(gè)受災(zāi)節(jié)點(diǎn)。如圖1 所示，車機(jī)組合1 表示一個(gè)車輛與無(wú)人機(jī)組合路徑，整條染色體包括多條組合路徑，當(dāng)需要執(zhí)行算子操作時(shí)對(duì)其進(jìn)行解碼操作。

圖1 染色體示意圖Fig.1 Schematic diagram of chromosome

解碼操作分為兩步：第一步獲取車機(jī)組合路徑；第二步確定節(jié)點(diǎn)屬性。以圖1 為例，首先得到2 條車機(jī)組合路徑，組合路線中第一個(gè)重復(fù)出現(xiàn)的節(jié)點(diǎn)（如車機(jī)組合2 中的節(jié)點(diǎn)1）是無(wú)人機(jī)第一架次的起飛節(jié)點(diǎn)，第一架次的降落節(jié)點(diǎn)是第二個(gè)重復(fù)出現(xiàn)的點(diǎn)（如車機(jī)組合2 中的節(jié)點(diǎn)3）。同樣，第三和第四個(gè)重復(fù)出現(xiàn)的節(jié)點(diǎn)（節(jié)點(diǎn)9 和節(jié)點(diǎn)13）是無(wú)人機(jī)第二架次的起飛點(diǎn)與降落點(diǎn)。通過(guò)該對(duì)比選擇規(guī)則，可以識(shí)別出每個(gè)車機(jī)組合路線上的所有交會(huì)節(jié)點(diǎn)與非交會(huì)節(jié)點(diǎn)。

2.2 初始種群生成

本文采用先聚類后構(gòu)造路徑的思想生成初始種群中的個(gè)體，具體步驟如下：

步驟1利用K-means 聚類得到滿足車輛載重約束的多個(gè)受災(zāi)點(diǎn)簇，結(jié)合旅行商問(wèn)題，利用隨機(jī)規(guī)則生成各簇相應(yīng)的車輛路徑。

步驟2選擇一條車輛訪問(wèn)路徑，隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為無(wú)人機(jī)第一架次的起飛節(jié)點(diǎn)。

步驟3判斷當(dāng)前起飛節(jié)點(diǎn)是否為當(dāng)前車輛路徑最后的訪問(wèn)點(diǎn)，如果是，則進(jìn)入步驟8；否則，進(jìn)入下一步。

步驟4選擇當(dāng)前車輛路徑上2 個(gè)連續(xù)受災(zāi)節(jié)點(diǎn)加入無(wú)人機(jī)路徑，將后續(xù)節(jié)點(diǎn)設(shè)置為無(wú)人機(jī)降落節(jié)點(diǎn)，若所選節(jié)點(diǎn)包括最后的訪問(wèn)節(jié)點(diǎn)，則將該最后訪問(wèn)節(jié)點(diǎn)設(shè)置為降落節(jié)點(diǎn)。

步驟5判斷式（10）與式（11）是否均滿足，若是，則進(jìn)入下一步；否則，撤銷當(dāng)前所構(gòu)建的無(wú)人機(jī)路徑，選擇當(dāng)前起飛點(diǎn)的相鄰后續(xù)節(jié)點(diǎn)作為新的起飛點(diǎn)。

步驟6生成一條有效的無(wú)人機(jī)路徑，并將當(dāng)前無(wú)人機(jī)路徑降落點(diǎn)的相鄰后續(xù)節(jié)點(diǎn)設(shè)置為下一架次的起飛節(jié)點(diǎn)。

步驟7判斷起飛點(diǎn)是否為當(dāng)前車輛路徑的最終訪問(wèn)節(jié)點(diǎn)，若是，則進(jìn)入下一步；否則，返回步驟4。

步驟8返回當(dāng)前車輛路徑相應(yīng)的車機(jī)協(xié)同配送路徑。

步驟9判斷所有車輛路徑是否完成重構(gòu)，若是，則結(jié)束；否則，返回步驟2。

2.3 遺傳算子

本文針對(duì)VRPD-MD 的特點(diǎn)，設(shè)計(jì)2 類內(nèi)部搜索算子以生成鄰域解：訪問(wèn)節(jié)點(diǎn)交叉算子用于對(duì)車輛訪問(wèn)節(jié)點(diǎn)與無(wú)人機(jī)訪問(wèn)節(jié)點(diǎn)進(jìn)行交換；交會(huì)節(jié)點(diǎn)變異算子用于對(duì)無(wú)人機(jī)起飛節(jié)點(diǎn)與降落節(jié)點(diǎn)進(jìn)行調(diào)整。

2.3.1 訪問(wèn)節(jié)點(diǎn)交叉算子

訪問(wèn)節(jié)點(diǎn)交叉算子基于同一車機(jī)組合路線進(jìn)行內(nèi)部變換，通過(guò)從車輛路徑與無(wú)人機(jī)路徑中隨機(jī)選擇不同數(shù)量的訪問(wèn)節(jié)點(diǎn)進(jìn)行交換以生成鄰域解。圖2 所示為T(mén)ruck（1）-Drone（1）算子的一種操作過(guò)程，從無(wú)人機(jī)路徑中選擇節(jié)點(diǎn)2、車輛路徑中選擇節(jié)點(diǎn)5 進(jìn)行交換，得到一個(gè)新的鄰域解。基于此規(guī)則，根據(jù)交換節(jié)點(diǎn)數(shù)量的不同，設(shè)計(jì)Truck（2）-Drone（2）、Truck（0）-Drone（1）、Truck（1）-Drone（0），加上Truck（1）-Drone（1）共4 個(gè)訪問(wèn)節(jié)點(diǎn)交叉算子，其中數(shù)字對(duì)應(yīng)選擇交換的節(jié)點(diǎn)數(shù)目。

圖2 Truck（1）-Drone（1）算子操作示意圖Fig.2 Operation diagram of Truck（1）-Drone（1）operator

2.3.2 交會(huì)節(jié)點(diǎn)變異算子

交會(huì)節(jié)點(diǎn)變異算子用來(lái)對(duì)無(wú)人機(jī)起飛節(jié)點(diǎn)與降落節(jié)點(diǎn)進(jìn)行調(diào)整以獲得鄰域解，包括起飛節(jié)點(diǎn)變異（Off-Change）與降落節(jié)點(diǎn)變異（Down-Change）2 類算子。圖3 所示為Off-Change 的一種操作過(guò)程。

圖3 Off-Change 算子操作示意圖Fig.3 Operation diagram of Off-Change operator

在圖3 中，無(wú)人機(jī)起飛點(diǎn)由節(jié)點(diǎn)1 調(diào)整至節(jié)點(diǎn)2，類似地，Down-Change 可以實(shí)現(xiàn)降落點(diǎn)調(diào)整操作。需要注意的是，算子每次僅執(zhí)行一個(gè)移動(dòng)操作，即調(diào)整起飛點(diǎn)（或降落點(diǎn)）為其相鄰節(jié)點(diǎn)。

2.4 算子自適應(yīng)選擇機(jī)制

為了提升算法的收斂速度與求解質(zhì)量，本文設(shè)計(jì)一種算子自適應(yīng)選擇機(jī)制。通過(guò)為不同算子設(shè)置不同的權(quán)重，在調(diào)用算子時(shí)根據(jù)其權(quán)重選擇當(dāng)前最優(yōu)算子，并根據(jù)優(yōu)化結(jié)果對(duì)算子權(quán)重進(jìn)行動(dòng)態(tài)更新。

算子權(quán)重動(dòng)態(tài)更新為自適應(yīng)選擇機(jī)制的關(guān)鍵，根據(jù)所得鄰域解的質(zhì)量更新算子權(quán)重：若某算子所得鄰域解優(yōu)于原解，則將算子的權(quán)重增加0.7（算子初始權(quán)重為1）；若所得鄰域解為劣解，以Metropolis規(guī)則接受該解，并將算子的權(quán)重增加0.5；如果所得鄰域解被舍棄，則算子權(quán)重保持不變。

2.5 算法整體步驟

AAGM 算法的整體步驟如下：

步驟1設(shè)置控制參數(shù)，如種群規(guī)模Pnum、最大迭代次數(shù)Nmax、當(dāng)前溫度Ts、降溫系數(shù)Δ、終止溫度Te等。

步驟2生成算法初始化種群，令種群最優(yōu)解為全局最優(yōu)解。

步驟3判斷Ts是否小于Te，若是，進(jìn)入下一步；否則，輸出全局最優(yōu)解。

步驟4判斷是否達(dá)到Nmax，若是，進(jìn)入步驟10；否則，進(jìn)入下一步。

步驟5執(zhí)行第n（n=1,2,…）次進(jìn)化，初始化算子權(quán)重為1。利用輪盤(pán)賭策略結(jié)合個(gè)體適應(yīng)度（目標(biāo)函數(shù)值的倒數(shù)），并根據(jù)優(yōu)化個(gè)體占種群的比例挑選出進(jìn)化種群。

步驟6選擇進(jìn)化種群中的第j（j=1,2,…）個(gè)個(gè)體，利用輪盤(pán)賭策略結(jié)合算子權(quán)重選擇執(zhí)行算子，利用算子生成當(dāng)前個(gè)體的鄰域解。

步驟7若鄰域解優(yōu)于全局最優(yōu)解，則令鄰域解為全局最優(yōu)解；若鄰域解優(yōu)于當(dāng)前個(gè)體，則將進(jìn)化種群中的當(dāng)前個(gè)體替換為鄰域解；若鄰域解為劣解，則利用Metropolis 規(guī)則接受該解，根據(jù)算子自適應(yīng)選擇機(jī)制動(dòng)態(tài)更新算子權(quán)重。

步驟8判斷進(jìn)化種群中所有個(gè)體是否都完成進(jìn)化，若是，進(jìn)入下一步；否則，j=j+1，返回步驟6。

步驟9更新進(jìn)化迭代次數(shù)：n=n+1。更新初始種群：從當(dāng)前初始種群中隨機(jī)選擇一定數(shù)量的個(gè)體，將當(dāng)前進(jìn)化種群規(guī)模擴(kuò)充至Pnum，并設(shè)置為新的初始種群，返回步驟4。

步驟10更新當(dāng)前溫度：Ts=Ts·Δ，返回步驟3。

3 實(shí)驗(yàn)結(jié)果與分析

本文利用不同的實(shí)例集進(jìn)行實(shí)驗(yàn)，這些實(shí)例從考慮容量限制的車輛路徑規(guī)劃標(biāo)準(zhǔn)實(shí)例集轉(zhuǎn)化而來(lái)［21］。將實(shí)例中的客戶點(diǎn)視為受災(zāi)點(diǎn)，保留其原始的車輛和客戶信息，在此基礎(chǔ)上增加無(wú)人機(jī)信息，其中，無(wú)人機(jī)的速度是卡車的1.5 倍，其他參數(shù)設(shè)為一個(gè)合理值。算法運(yùn)行環(huán)境為2.9 GHz、Intel Core i10、8 GB RAM、Windows 10、64 位系統(tǒng)的計(jì)算機(jī)，通過(guò)Java 編程實(shí)現(xiàn)。

3.1 配送模式對(duì)比實(shí)驗(yàn)

本組實(shí)驗(yàn)一方面驗(yàn)證車機(jī)協(xié)同配送模式相比純車輛配送模式的優(yōu)勢(shì)，另一方面通過(guò)比較幾種不同的車機(jī)協(xié)同模式證明本文所提多架次多投遞無(wú)人機(jī)配送模式的有效性。通過(guò)修改初始解生成策略，本文增加無(wú)人機(jī)多架次單投遞、無(wú)人機(jī)單架次多投遞2 種常見(jiàn)車機(jī)協(xié)同模式。從CVRP 算例中選擇不同問(wèn)題規(guī)模的15 個(gè)實(shí)例，在不同模式下基于每個(gè)實(shí)例運(yùn)行10 次AAGM 算法，并記錄最優(yōu)解、平均解、平均求解時(shí)間、平均解與CVRP 最優(yōu)解的GAP 值，具體結(jié)果如表2 所示，其中，n表示節(jié)點(diǎn)數(shù)，k表示所需車輛數(shù)。從表2 可以看出，3 種車機(jī)協(xié)同模式下平均目標(biāo)值在大多數(shù)實(shí)例中均優(yōu)于CVRP 最優(yōu)解，其中，多架次多投遞模式下的車機(jī)協(xié)同取得最佳結(jié)果。對(duì)比多架次單投遞與多架次多投遞模式，可以看出，具有多點(diǎn)投遞能力的無(wú)人機(jī)配送模式配送效率提升明顯。多架次單投遞與單架次多投遞模式的對(duì)比結(jié)果顯示，在本文實(shí)驗(yàn)案例規(guī)模下，增加無(wú)人機(jī)單架次投遞節(jié)點(diǎn)數(shù)優(yōu)于增加無(wú)人機(jī)架次數(shù)。當(dāng)擴(kuò)展到更大規(guī)模的問(wèn)題時(shí)，多架次多投遞模式相較單架次多投遞可能具有更大的優(yōu)勢(shì)。

表2 多種車機(jī)配送模式的結(jié)果對(duì)比Table 2 Comparison of results of various truck and drone distribution modes

3.2 算法性能對(duì)比實(shí)驗(yàn)

為進(jìn)一步驗(yàn)證AAGM 算法的性能優(yōu)勢(shì)，將其與已有算法進(jìn)行對(duì)比。由于無(wú)人機(jī)多架次多投遞模式下的車機(jī)協(xié)同問(wèn)題尚未有相關(guān)求解算法，因此無(wú)法直接進(jìn)行算法比較。文獻(xiàn)［22］提出了求解無(wú)人機(jī)單架次多投遞模式下車機(jī)協(xié)同路徑規(guī)劃問(wèn)題的大規(guī)模鄰域搜索（LNS）算法，因此，本文采用與LNS 算法相同的測(cè)試用例，在無(wú)人機(jī)單架次多投遞模式下開(kāi)展算法對(duì)比實(shí)驗(yàn)?；诿總€(gè)實(shí)例運(yùn)行10 次AAGM 算法，并記錄最優(yōu)解、平均求解時(shí)間、最優(yōu)解與LNS 最優(yōu)解的GAP 值，具體結(jié)果如表3 所示。從表3 可以看出，AAGM 在大多數(shù)算例（8/10）中的最優(yōu)解優(yōu)于對(duì)比算法LNS，平均差距為-3.51%。在求解速度上，AAGM 同樣具有明顯優(yōu)勢(shì)，對(duì)于大多數(shù)算例，其能夠在10 s 內(nèi)完成計(jì)算，而LNS 需要的計(jì)算時(shí)間則超過(guò)1 min。

表3 AAGM 與LNS 的性能對(duì)比結(jié)果Table 3 Performance comparison results of AAGM and LNS

3.3 自適應(yīng)策略性能驗(yàn)證

本組實(shí)驗(yàn)的目的：一是通過(guò)靈敏度分析進(jìn)行算法參數(shù)調(diào)優(yōu)；二是研究自適應(yīng)策略對(duì)于AAGM 算法性能的影響。對(duì)比最優(yōu)參數(shù)配置的非自適應(yīng)算法（None-Adaptive Algorithm Based on Genetic Method，NAAGM）與非最優(yōu)參數(shù)配置的AAGM 算法在求解質(zhì)量與求解速度上的差異。在參數(shù)調(diào)優(yōu)環(huán)節(jié)，首先根據(jù)經(jīng)驗(yàn)確定參數(shù)的測(cè)試區(qū)間，通過(guò)選取不同規(guī)模算例更改參數(shù)組合以進(jìn)行多組測(cè)試，得到最佳參數(shù)配置如表4 所示。分別在15 個(gè)測(cè)試用例上運(yùn)行AAGM 與NAAGM 各10 次，記錄平均運(yùn)行時(shí)間與最優(yōu)解。圖4（a）展示AAGM 與NAAGM 在求解時(shí)間上的對(duì)比，可以看出，在所有測(cè)試算例上，增加自適應(yīng)策略后的算法求解時(shí)效性明顯提升，求解時(shí)間平均節(jié)省30%。圖4（b）展示自適應(yīng)策略對(duì)于算法求解質(zhì)量的影響，從中可以看出，在大多數(shù)算例（11/15）中，AAGM 算法的最優(yōu)解優(yōu)于NAAGM 算法，求解質(zhì)量平均提升1.83%。

表4 AAGM 算法的最佳參數(shù)配置Table 4 Optimal parameters configuration of AAGM algorithm

圖4 2 種算法的求解速度與求解質(zhì)量對(duì)比Fig.4 Comparison of solution speed and quality between the two algorithms

4 結(jié)束語(yǔ)

本文研究一種考慮多點(diǎn)投遞的帶無(wú)人機(jī)車輛路徑規(guī)劃問(wèn)題，針對(duì)該問(wèn)題建立相應(yīng)的混合整數(shù)規(guī)劃模型。為對(duì)模型進(jìn)行求解，設(shè)計(jì)一種高效的AAGM求解算法，通過(guò)集成算子自適應(yīng)選擇機(jī)制與基于Metropolis 規(guī)則的劣解接受機(jī)制，以提高算法的全局尋優(yōu)性能。利用改進(jìn)的CVRP 算例集進(jìn)行3 組驗(yàn)證實(shí)驗(yàn)，結(jié)果表明，多架次多投遞車機(jī)協(xié)同模式在帶無(wú)人機(jī)的車輛路徑規(guī)劃任務(wù)中可以發(fā)揮優(yōu)勢(shì)，且AAGM 算法在求解VRPD-MD 時(shí)具有可行性和有效性。多點(diǎn)投遞的車機(jī)協(xié)同路徑規(guī)劃研究目前尚處于起步階段，本文下一步將從2 個(gè)方面展開(kāi)研究：一是探索更高效的求解算法，如設(shè)計(jì)基于車輛與無(wú)人機(jī)路徑同步生成規(guī)則的啟發(fā)式算法，利用該算法生成初始解；二是研究多種變體問(wèn)題，如無(wú)人機(jī)跨車輛?？康能嚈C(jī)協(xié)同配送問(wèn)題。