考慮多投遞的帶無人機車輛路徑規劃問題研究

馬華偉，馬 凱，郭 君

（1.合肥工業大學 管理學院，合肥 230009；2.過程優化與智能決策教育部重點實驗室，合肥 230009）

0 概述

近年來，車輛與無人機協同配送成為應急救援的重要手段，在新冠肺炎疫情下的醫療物資配送［1］、西昌瀘山森林火災救援［2］等事件中均有應用。其中，合理規劃車輛與無人機路徑對于提高應急救援的時效性至關重要，這也使得相應的路徑規劃問題成為一個備受關注的研究熱點。

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

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

1 數學模型

1.1 問題描述

在VRPD-MD 中，車輛與無人機協同完成多個受災點配送任務，無人機在任意架次中服務多個受災點，車輛在配送的同時支持無人機多次起降，目的是尋找耗時最短的配送路徑。本文所提出的車機協同模式更加貼近實際配送需求，可以充分發揮無人機的速度優勢，同時車機并行交付方式也能有效減少總體交付時間。為了建立數學模型，本文作出如下合理假設：

1）每輛車搭載一架無人機，且無人機必須從車輛起飛并返回起飛車輛。考慮車輛與無人機的容量約束，無人機電量限制其續航時長。

2）車輛與無人機行駛在歐氏空間，且只能在受災點交會。

3）車輛與無人機必須在交會位置進行時間同步，即較早到達交會節點的一方需要等待另一方。

4）有足夠的電池可供無人機替換，并且忽略電池更換和電池充電的時間。

1.2 問題建模

為便于模型描述，表1 給出建模過程中所應用的符號及其含義。

表1 符號及其含義Table 1 Symbols and their meanings

基于上述符號和變量，本文建立如下混合整數規劃模型：

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

2 基于遺傳思想的自適應算法設計

遺傳算法［19-20］是求解無人機路徑規劃問題的常用方法之一，本文考慮VRPD-MD 的特點，設計一種基于遺傳思想的自適應算法AAGM。

2.1 染色體編碼

在AAGM 算法中，一個解被表示為由多條車輛與無人機組合路線組成的染色體。本文采用自然數編碼方式，染色體表示卡車和無人機的訪問序列，每個基因位置存儲一個受災節點。如圖1 所示，車機組合1 表示一個車輛與無人機組合路徑，整條染色體包括多條組合路徑，當需要執行算子操作時對其進行解碼操作。

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

解碼操作分為兩步：第一步獲取車機組合路徑；第二步確定節點屬性。以圖1 為例，首先得到2 條車機組合路徑，組合路線中第一個重復出現的節點（如車機組合2 中的節點1）是無人機第一架次的起飛節點，第一架次的降落節點是第二個重復出現的點（如車機組合2 中的節點3）。同樣，第三和第四個重復出現的節點（節點9 和節點13）是無人機第二架次的起飛點與降落點。通過該對比選擇規則，可以識別出每個車機組合路線上的所有交會節點與非交會節點。

2.2 初始種群生成

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

步驟1利用K-means 聚類得到滿足車輛載重約束的多個受災點簇，結合旅行商問題，利用隨機規則生成各簇相應的車輛路徑。

步驟2選擇一條車輛訪問路徑，隨機選擇一個節點作為無人機第一架次的起飛節點。

步驟3判斷當前起飛節點是否為當前車輛路徑最后的訪問點，如果是，則進入步驟8；否則，進入下一步。

步驟4選擇當前車輛路徑上2 個連續受災節點加入無人機路徑，將后續節點設置為無人機降落節點，若所選節點包括最后的訪問節點，則將該最后訪問節點設置為降落節點。

步驟5判斷式（10）與式（11）是否均滿足，若是，則進入下一步；否則，撤銷當前所構建的無人機路徑，選擇當前起飛點的相鄰后續節點作為新的起飛點。

步驟6生成一條有效的無人機路徑，并將當前無人機路徑降落點的相鄰后續節點設置為下一架次的起飛節點。

步驟7判斷起飛點是否為當前車輛路徑的最終訪問節點，若是，則進入下一步；否則，返回步驟4。

步驟8返回當前車輛路徑相應的車機協同配送路徑。

步驟9判斷所有車輛路徑是否完成重構，若是，則結束；否則，返回步驟2。

2.3 遺傳算子

本文針對VRPD-MD 的特點，設計2 類內部搜索算子以生成鄰域解：訪問節點交叉算子用于對車輛訪問節點與無人機訪問節點進行交換；交會節點變異算子用于對無人機起飛節點與降落節點進行調整。

2.3.1 訪問節點交叉算子

訪問節點交叉算子基于同一車機組合路線進行內部變換，通過從車輛路徑與無人機路徑中隨機選擇不同數量的訪問節點進行交換以生成鄰域解。圖2 所示為Truck（1）-Drone（1）算子的一種操作過程，從無人機路徑中選擇節點2、車輛路徑中選擇節點5 進行交換，得到一個新的鄰域解。基于此規則，根據交換節點數量的不同，設計Truck（2）-Drone（2）、Truck（0）-Drone（1）、Truck（1）-Drone（0），加上Truck（1）-Drone（1）共4 個訪問節點交叉算子，其中數字對應選擇交換的節點數目。

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

2.3.2 交會節點變異算子

交會節點變異算子用來對無人機起飛節點與降落節點進行調整以獲得鄰域解，包括起飛節點變異（Off-Change）與降落節點變異（Down-Change）2 類算子。圖3 所示為Off-Change 的一種操作過程。

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

在圖3 中，無人機起飛點由節點1 調整至節點2，類似地，Down-Change 可以實現降落點調整操作。需要注意的是，算子每次僅執行一個移動操作，即調整起飛點（或降落點）為其相鄰節點。

2.4 算子自適應選擇機制

為了提升算法的收斂速度與求解質量，本文設計一種算子自適應選擇機制。通過為不同算子設置不同的權重，在調用算子時根據其權重選擇當前最優算子，并根據優化結果對算子權重進行動態更新。

算子權重動態更新為自適應選擇機制的關鍵，根據所得鄰域解的質量更新算子權重：若某算子所得鄰域解優于原解，則將算子的權重增加0.7（算子初始權重為1）；若所得鄰域解為劣解，以Metropolis規則接受該解，并將算子的權重增加0.5；如果所得鄰域解被舍棄，則算子權重保持不變。

2.5 算法整體步驟

AAGM 算法的整體步驟如下：

步驟1設置控制參數，如種群規模Pnum、最大迭代次數Nmax、當前溫度Ts、降溫系數Δ、終止溫度Te等。

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

步驟3判斷Ts是否小于Te，若是，進入下一步；否則，輸出全局最優解。

步驟4判斷是否達到Nmax，若是，進入步驟10；否則，進入下一步。

步驟5執行第n（n=1,2,…）次進化，初始化算子權重為1。利用輪盤賭策略結合個體適應度（目標函數值的倒數），并根據優化個體占種群的比例挑選出進化種群。

步驟6選擇進化種群中的第j（j=1,2,…）個個體，利用輪盤賭策略結合算子權重選擇執行算子，利用算子生成當前個體的鄰域解。

步驟7若鄰域解優于全局最優解，則令鄰域解為全局最優解；若鄰域解優于當前個體，則將進化種群中的當前個體替換為鄰域解；若鄰域解為劣解，則利用Metropolis 規則接受該解，根據算子自適應選擇機制動態更新算子權重。

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

步驟9更新進化迭代次數：n=n+1。更新初始種群：從當前初始種群中隨機選擇一定數量的個體，將當前進化種群規模擴充至Pnum，并設置為新的初始種群，返回步驟4。

步驟10更新當前溫度：Ts=Ts·Δ，返回步驟3。

3 實驗結果與分析

本文利用不同的實例集進行實驗，這些實例從考慮容量限制的車輛路徑規劃標準實例集轉化而來［21］。將實例中的客戶點視為受災點，保留其原始的車輛和客戶信息，在此基礎上增加無人機信息，其中，無人機的速度是卡車的1.5 倍，其他參數設為一個合理值。算法運行環境為2.9 GHz、Intel Core i10、8 GB RAM、Windows 10、64 位系統的計算機，通過Java 編程實現。

3.1 配送模式對比實驗

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

表2 多種車機配送模式的結果對比Table 2 Comparison of results of various truck and drone distribution modes

3.2 算法性能對比實驗

為進一步驗證AAGM 算法的性能優勢，將其與已有算法進行對比。由于無人機多架次多投遞模式下的車機協同問題尚未有相關求解算法，因此無法直接進行算法比較。文獻［22］提出了求解無人機單架次多投遞模式下車機協同路徑規劃問題的大規模鄰域搜索（LNS）算法，因此，本文采用與LNS 算法相同的測試用例，在無人機單架次多投遞模式下開展算法對比實驗。基于每個實例運行10 次AAGM 算法，并記錄最優解、平均求解時間、最優解與LNS 最優解的GAP 值，具體結果如表3 所示。從表3 可以看出，AAGM 在大多數算例（8/10）中的最優解優于對比算法LNS，平均差距為-3.51%。在求解速度上，AAGM 同樣具有明顯優勢，對于大多數算例，其能夠在10 s 內完成計算，而LNS 需要的計算時間則超過1 min。

表3 AAGM 與LNS 的性能對比結果Table 3 Performance comparison results of AAGM and LNS

3.3 自適應策略性能驗證

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

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

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

4 結束語

本文研究一種考慮多點投遞的帶無人機車輛路徑規劃問題，針對該問題建立相應的混合整數規劃模型。為對模型進行求解，設計一種高效的AAGM求解算法，通過集成算子自適應選擇機制與基于Metropolis 規則的劣解接受機制，以提高算法的全局尋優性能。利用改進的CVRP 算例集進行3 組驗證實驗，結果表明，多架次多投遞車機協同模式在帶無人機的車輛路徑規劃任務中可以發揮優勢，且AAGM 算法在求解VRPD-MD 時具有可行性和有效性。多點投遞的車機協同路徑規劃研究目前尚處于起步階段，本文下一步將從2 個方面展開研究：一是探索更高效的求解算法，如設計基于車輛與無人機路徑同步生成規則的啟發式算法，利用該算法生成初始解；二是研究多種變體問題，如無人機跨車輛停靠的車機協同配送問題。