無人機與卡車多組合配送問題研究

摘 要：由于城市配送場景的復雜性，無人機開始被應用于“最后一公里”配送，但無人機配送受到其飛行距離與載重等限制，無人機與卡車組合配送得到廣泛關注。結合卡車與無人機配送特點，研究了一類考慮無人機與卡車多組合下的配送路徑優化問題；在考慮無人機的飛行范圍與載荷等因素下，建立以總配送成本最小化的整數規劃模型，并設計了結合改進K-means聚類搜索的混合變鄰域搜索算法求解該問題。算例結果驗證了所提模型的可行性和所設計算法的有效性，通過與其他配送方式相比，成本最高節約達22%，且隨著算例規模擴大，成本節約不斷增加，為實現城市地區末端物流的降本增效提供了決策參考和依據。

關鍵詞：無人機；路徑規劃；變鄰域搜索；組合配送；城市配送

中圖分類號：F252.14 文獻標志碼：A

DOI：10.13714/j.cnki.1002-3100.2024.19.003

Abstract： Due to the complexity of urban distribution scenarios， drones are beginning to be applied to the "last kilometer" distribution， but drone distribution is limited by its flight range and load， so the combination of drones and trucks for distribution has gained wide attention. Combining the characteristics of truck and UAV delivery， a delivery path optimization problem considering multiple combinations of UAVs and trucks is investigated. Under the consideration of the flight range and load of UAVs， an integer planning model is established to minimize the total delivery cost， and a hybrid variable neighborhood search algorithm combined with improved K-means clustering search is designed to solve the problem. The results verify the feasibility of the proposed model and the validity of the designed algorithm， and the cost saving is up to 22% compared with other distribution methods， and the cost saving increases with the expansion of the scale of the example， which provides decision-making references and bases for the realization of cost reduction and efficiency of the terminal logistics in urban areas.

Key words： UAV; path planning; variable neighborhood search; combinatorial distribution; urban distribution

0 引 言

隨著無人機技術越來越成熟與規范，無人機配送受到了學界和業界的廣泛關注。但無人機存在負載小、航程短等不足，這導致無人機難以較好地滿足物流運輸的需求。結合車輛的遠距離和大容量特點與無人機的高效率和低成本，可以采用無人機和車輛組合配送的方式。這種組合配送能夠滿足城市復雜場景下各種類型的配送需求，并提高總體效率，同時滿足安全配送的要求。因此，研究無人機和貨車聯合配送具有重要的理論意義和實踐價值[1-2]。

車輛與無人機組合配送可理解為旅行商問題與車輛路徑問題的擴展。同時根據無人機與車輛的數量可細分為使用單無人機的旅行商問題（Traveling Salesman Problem with a Drone，TSP-D）與使用多無人機車輛路徑問題（Vehicle Routing Problem with Drones，VRP-D）。Kang et al.[3]根據無人機飛行特性，以總配送時間最短為目標建立整數規劃模型，從而完成城市最后一公里配送任務。路世昌等[4]利用無人機與卡車協調配送對應急物流中的積水障礙問題進行研究。Agatz et al.[5]發現：與僅用卡車配送相比，小規模數量的客戶使用無人機與卡車組合配送可以節省大量費用。Paul et al.[6]基于動態規劃的精確方法，解決了大規模TSP-D的問題。Murray et al.[7]建立混合整數規劃模型，并采取多種啟發式算法求解卡車與多無人機組合配送問題。Quang et al.[2]以最小化運營成本為目標，在Murray的方法基礎上，利用貪婪自適應搜索過程對無人機的配送客戶點進行分配。曹英英等[8]基于無人機飛行范圍與載重的約束下建立混合整數模型來服務農村地區，但同樣研究的問題為TSP-D問題。季金華等[9]研究在疫情封控的背景下，以交叉感染風險與配送成本最小為目標，設計啟發式算法求解TSP-D問題。彭勇等[10]通過將顧客分成三類進行研究，通過規劃車輛與無人機路徑使總服務時間最短。

在上述研究中，主要關注單無人機與卡車組合配送的TSP-D問題。然而，在實際配送中，由于客戶點數量過多以及總需求量超過單一卡車額定載荷的限制，這種方案存在限制。因此，學者們將TSP-D問題擴展為VRP-D問題，以解決實際配送中的挑戰。

Wang et al.[11]以總配送時間最短為目標，將TSP-D問題擴展為VRP-D，無人機可以從卡車或配送中心起飛。Gu et al.[12]在推廣VRP-D問題的同時，將取貨與送貨問題融合考慮，考慮了無人機的承載能力和續航能力作為限制條件，并以最大化利潤為目標，構建混合整數規劃模型進行深入研究。Tamke et al.[13]針對兩個不同的面向時間目標函數的帶無人機的車輛路徑問題（VRP-D），建立混合整數線性規劃模型。

隨著配送背景的復雜性增加，傳統的VRP-D已經不能滿足城市配送的需求。少量學者對無人機自身條件加以研究，包括無人機最大飛行時間、載重和飛行距離對續航能力的影響、道路限制對起飛點的約束等。例如，顏瑞等[14]考慮區域限制條件下卡車與無人機的組合配送。Cui et al.[15]考慮在無人機載重的約束下，提出以能耗最低為目標混合整數規劃模型。但仍然存在以下幾點考慮不足：（1）突發事件導致部分客戶點卡車無法實現配送；（2）規定車輛必須在下一節點回收無人機；（3）配送中心周圍小批量多批次的客戶使用卡車進行配送，導致配送成本較高。

鑒于此，本文在考慮無人機載重、飛行距離限制、貨車載重限制等約束下，無人機與貨車對城市某區域內多個客戶送貨時，研究如何分配客戶以及規劃車輛和無人機路徑，使配送成本最低。本文提出將獨立無人機配送方式（PDTSPHqFjVcYOoPjG+CMtyylJng==）與車載無人機與卡車聯合配送方式（FSTSP）相結合的無人機和卡車多組合配送（Hybrid Drone and Truck Delivery for Traveling Salesman Problem，HDTDTSP），它既能滿足配送范圍受限、一對一配送等特定配送需求，又能增加傳統卡車配送貨物的靈活性，降低整體的配送成本。

1 無人機與卡車多組合配送問題

1.1 問題描述

假定有一個配送中心與若干客戶，各客戶的需求量已知，配送中心到各客戶點的配送距離已知。配送中心有若干同質的貨車和多架同質的無人機，無人機包括車載無人機與獨立無人機，每輛貨車會搭載一架車載無人機。在這個配送系統中，每個客戶只能被服務一次。配送中心根據客戶的需求，靈活地派遣貨車和車載無人機、獨立無人機，以提供高效的配送服務。

圖1是卡車與無人機多組合配送的一個方案，含有1個配送中心、4輛卡車、4架車載無人機、1架獨立無人機以及17個需求點。最優配送方案如下：R1中車輛到達點為0-1-3-0，車載無人機到達點為1-2-3；R2中由獨立無人機完成需求點4的配送任務；R3中車輛到達點為0-5-6-7-8-0；R4中車輛到達點為0-9-10-12-13-0，車載無人機到達點為10-11-12；R5中車輛到達點為0-17-16-15-14-0。

本文提出的無人機和卡車多組合配送問題主要解決：（1）顧客配送方式的選擇；（2）卡車與車載無人機的路徑規劃；（3）獨立無人機的路徑規劃。

1.2 問題假設

（1）客戶點的坐標和需求已知；

（2）車載無人機或獨立無人機單次只能為單一顧客服務；

（3）卡車必須在原位置或者后續位置回收已經發射的車載無人機；

（4）無人機速度和載荷對車載或獨立無人機的續航能力不產生影響；

（5）每個客戶點只能被服務一次；

（6）獨立UAV與車載UAV同質；

（7）卡車、車載無人機和獨立無人機速度恒定，每段里程用歐式距離測量。

1.3 符號定義

無人機和卡車多組合配送問題（Hybrid Drone and Truck Delivery for Traveling Salesman Problem， HDTDTSP）可以描述為圖論問題。

令G=S，A為一個有向圖，客戶點集合為S=0，1，2，…，n，n+1，配送中心為節點0，n+1，其余節點均表示客戶，A表示弧集。規定在有向圖G上，一條合理的配送路線必須始于節點0終于節點n+1。S表示從節點i出發的弧的集合，S表示回到節點j的弧的集合；S=S＼0，n+1表示需求點集；N表示配送貨車集；U=1，2，…，u表示車載UAV的集合；U=1，2，…，u表示獨立配送UAV集合；S表示所有顧客需求點超過無人機最大載重的集合；S表示所有顧客需求點超過無人機最大續航的集合；S和S分別表示卡車和無人機的最大負載量；D表示無人機的最大續航里程；C與C分別表示卡車與無人機的單位距離配送成本；P與P分別表示卡車與無人機的單輛固定成本；w表示客戶點i的需求量；e表示客戶點i在卡車n路徑中的序號；d表示卡車n從客戶i到客戶j的距離；d表示車載無人機u從客戶i到客戶j的距離；dd=d+d表示獨立無人機u對客戶i的配送距離。

1.4 數學模型

無人機和卡車多組合配送問題HDTDTSP的數學模型如下：

其中：公式（1）表示總成本最小化；公式（2）表示固定成本；公式（3）表示每輛卡車提供服務不能超過一次且不允許多次從配送中心出發；公式（4）表示卡車只有完成配送任務才允許返回配送中心；公式（5）表示卡車在完成需求點配送任務后必須離開；公式（6）表示需求點可以被卡車或者車載無人機或者獨立無人機提供服務；公式（7）至公式（8）表示消除卡車路徑的子回路；公式（9）至公式（10）表示若車載無人機a從點i發射，必須完成配送任務后，才可以在點k對其進行回收；公式（11）表示車載無人機的發射和回收路徑必須在卡車路徑上；公式（12）表示卡車的額定載重約束；公式（13）至公式（14）表示獨立無人機和車載無人機的電量約束；公式（15）至公式（17）是決策變量。

2 求解HDTDTSP的變鄰域搜索算法

無人機和卡車多組合配送問題HDTDTSP是比VRP更復雜的NP-hard問題，求解精確最優解的難度較大。Dhekra et al.[16]對變鄰域搜索算法（Variable Neighborhood Search， VNS）改進，使其在無人機與卡車組合問題中求解效果更好。針對HDTDTSP，本文提出了一種混合變鄰域搜索算法對其進行求解。

本文提出的變鄰域算法主要包括四個部分：（1）顧客配送方式的選擇，根據顧客的需求量以及與配送中心的距離確定顧客的初始配送方式。此外，由于每個聚類簇的配送車輛不能超過一輛，故在傳統的K-means算法中加入距離和車輛載重的限制，使得聚類簇中的總需求量小于卡車的額定載荷；（2）卡車與車載無人機的路徑規劃，首先，根據啟發式算法得到卡車與車載無人機的初始配送方案；利用領域操作對已生成的路徑進行插入和交換操作，不斷更新路徑結果；最后，采取局部搜索操作，進一步擴大解空間，不斷更新和優化路徑方案；（3）獨立無人機的路徑規劃，采用貪婪算法得到獨立無人機配送方案的初始解；（4）全局最優路徑搜索，交換不同配送方式的客戶點，對全局路徑方案進行更新。

2.1 配送方式的選擇與卡車配送區域的確定

步驟1：計算所有需求點與配送中心的距離，將需求量超過獨立無人機載重的需求點與距離大于獨立無人機飛行半徑R的需求點記錄在集合P中，其余需求點放入集合N中；

步驟2：將集合P中客戶點分配給卡車與車載無人機配送，集合N中客戶點由獨立無人機配送；

步驟3：采用手肘法確定聚類數量M；

步驟4：在客戶點中隨機選擇M個對象作為初始聚類中心；

步驟5：計算各需求點與M個初始聚類中心的距離，在不超過卡車額定載荷的情況下，將距離最近的客戶點分配至M個聚類簇中；

步驟6：根據步驟5中的M個聚類簇中心，對聚類中心信息進行更新；

步驟7：算法迭代到設定次數，計算終止，輸出結果，否則轉步驟5。

2.2 卡車與車載無人機路徑規劃

根據配送方式與聚類的結果，首先利用動態規劃法得到卡車的行駛方案，然后將距離無人機配送客戶點最近的兩個點選為起落點，從而得到初始組合配送方案。局部搜索與插入操作、交換操作的設計可以進一步提高求解效率與精確性。如圖2所示，將某路徑中的某個客戶插入到另一條路徑中為插入操作。無人機起飛或回收點被選中時則順延到下一點。如圖3所示，交換操作是在交換后總需求量不大于卡車額定載荷前提下，對子路徑中的客戶點進行交替更換，若被選中的客戶點為無人機的起落點，則將無人機的發射或者收回點設置為該客戶點鄰近點。

在子路徑的局部過程尋找更優方案的過程就是局部搜索。即在某條子路徑中隨機交換兩個客戶點并更新路徑，若被選擇的客戶點是無人機的發射或者收回點，則將無人機的發射或者收回點設置為該客戶點鄰近點，若出現無人機的發射和收回點與卡車行進方向沖突，則將發射與回收的順序調換。路徑更新的前提是原配送方案劣于新配送方案。子路徑局部搜索如圖4所示。

2.3 獨立無人機的路徑規劃與全局最優路徑搜索

步驟1：采取貪婪算法對集合N中的需求點進行路徑規劃，從而確定獨立無人機的初始解；

步驟2：對圈內所有客戶點進行遍歷，判斷客戶點的需求量加入是否會超過聚類J集合中的一條線路卡車的載重，如果小于則轉Step3，大于則算法結束；

步驟3：比較將客戶點加入卡車配送路線增加的成本與無人機單獨配送的成本，如果無人機單獨配送的成本高于加入卡車路線的成本則將其加入集合M，否則跳過；

步驟4：對集合M中客戶節約的成本進行計算，將其從大到小進行排列；

步驟5：依次將步驟4中客戶按節約的成本高低加入卡車路線中，在加入的同時判斷是否滿足卡車的載重，滿足則加入，不滿足則停止，并根據加入的客戶點重新規劃路徑。

3 算例分析

3.1 參數說明

在VRP Web獲取CVRP的相關標準算例P-n16-k8、A-n32-k5、P-n40-k5、E-n51-k5、E-n76-k8以及E-n101-k8為基礎數據，并將其命名為A16、A32、A40、A51、A76、A101，基于卡車-無人機組合配送背景要求，對標準算例數據進行一定的處理，分別包含一個配送中心和16、32、40、51、76、101個客戶。此外，對客戶需求量進行調整，以確保車載或獨立無人機可以完成配送任務。

假設無人機的額定載荷t=15kg，航行里程D=15km，卡車額定載荷T=200kg。客戶到配送點的最大往返直線距離D=15km?？ㄜ噯未喂潭ㄙM用為80元，無人機單次固定費用為20元；卡車的單位距離成本C=1.5元/km，無人機的單位距離飛行成本C=0.3元/km[17-18]。

運行環境為Windows11操作系統，處理器為AMD Ryzen 7 6800H with Radeon Graphics@3.20GHz。

3.2 不同配送方式的總配送成本

車輛與無人機的并行配送是指車輛與無人機分別獨立完成對需求點的配送；車輛與無人機的協調配送是指車輛搭載無人機，兩者共同對需求點進行配送。本文提出的車輛與無人機的多組合配送是指協同和并行兩種配送方式相結合的混合配送，一方面車載無人機搭載車輛共同完成配送任務，另一方面獨立無人機可從配送中心直接完成配送。

為了說明組合配送的優越性，以算例A51為例，分別采取三種配送方式進行運輸，比較結果如表1所示。

由表1可知：針對城市末端配送的復雜場景需求，結合無人機和卡車的多組合配送方式，可以同時實現協同和并行的優勢。這種配送方式不僅能有效降低無人機使用頻率和總配送距離，還能減少物流系統運營成本。圖6為算例A51的最優配送路線。

由于在最后一公里配送時經常出現交叉感染等現象，故本文考慮無人機在實施配送服務時僅對客戶進行一對一配送，即車載和獨立無人機單次僅配送一次客戶便返回卡車或配送中心進行二次配送準備。由表2可以得出傳統配送模式的固定成本占比為15.86%，但是車輛與無人機的組合配送方式在配送成本降低方面較明顯，同時總成本比傳統配送模式降低了12%，且隨著規模的增加，成本的下降幅度更大。

3.3 算法的有效性分析

3.3.1 算法規模性分析

選取6種不同規模的數據，分別使用三種配送方式進行計算，F為無人機配送成本，F為卡車配送成本，F為運營總成本。

由表2可以看出，隨著客戶規模的增加，傳統配送的總成本遠遠高于其他兩種配送方式。與協同配送相比，組合配送在配送中規模的客戶時總成本降低5%，在配送小規模與大規?？蛻?，總成本降低8%。

與傳統配送相比較，本文采用的組合配送由于無人機的參與，組合配送方式下的卡車里程減少近40%，且隨著客戶點的增加而增幅較緩。同時，為進一步對比配送方法的優劣，選取三種配送方式進行配送。經過三階段算法優化，組合配送的總成本與傳統卡車配送成本相比分別節約17.26%、12.68%、14.24%、23.78%、31.47%和33.22%，可以看出：組合配送與傳統卡車相比，隨著客戶點規模的增多，節約的成本比例不斷增加，說明該配送方法是有效的。

與并行配送相比，組合配送分別節約12.5%、2.24%、3.67%、6.89%、20.93%和13.91%。可以看出，組合配送方式與并行配送方式相比也降低了成本，進一步說明配送方法的有效性。

3.3.2 算法性能對比實驗

為了進一步驗證變鄰域算法在解決HDTDTSP問題方面的性能優勢，我們選取了文獻[20]中的大規模鄰域搜索（LNS）作為對照。根據表3的數據，變鄰域算法在解決A16、A32、A51、A76和A101這五個問題實例時，都獲得了比LNS算法更優的最優解。此外，變鄰域算法在求解時間方面也表現出了明顯的優勢，其求解時間較傳統算法短得多，求解時間不到LNS算法的十分之一。同時，變鄰域算法在解決表3中所列算例中的大多數最優解都優于LNS，平均差距為4.86%。綜上所述，變鄰域算法在解決HDTDTSP問題上顯示出更高效的求解能力，能夠在短時間內獲得最優解決方案。

3.4 敏感性分析

3.4.1 飛行范圍的敏感性分析

隨機選擇A40、A51和A76客戶點數為40點的算例（即A2組、B2組和C2組），將無人機的載重設置為15kg，同時將無人機的續航能力設置分別為15km、20km、25km和30km，并進行靈敏度分析以發現飛行范圍與總配送成本之間的關系。圖7為A2、B2、C2三組數據的對比圖，自變量為無人機的飛行范圍，因變量為綜合成本。

從圖7可知：無人機飛行范圍從15km變化至20km時，總配送成本變化明顯；當飛行成本從20km增加至25km，以及從25km增加至30km時，總配送成本變動較小。在無人機飛行范圍較小時，難以滿足城市的配送需求，從而導致總成本變動不明顯，因此在組合配送模式中發揮作用較小。但是，隨著無人機飛行范圍即無人機的可支配飛行空間增加，所發揮的效用也在增加，配送成本也進一步降低。當無人機的載重和飛行范圍配比達到一個標準以后，飛行范圍的增加并不能有效降低綜合成本。

3.4.2 無人機載重的敏感性分析

在A40、A51和A76中隨機選擇客戶數為40的算例，設置無人機的飛行范圍為15km，同時將無人機的載荷能力分別設置為15kg、20kg、25kg和30kg，并進行靈敏度分析以發現不同載重范圍對總配送成本的影響。圖8為三個數據集的求解結果，縱軸為總配送成本，橫軸為無人機載荷能力。

從圖8可知：在無人機的載荷能力等差變動的情況下，載荷能力越大，總配送成本越低。然而，不同組數據的綜合成本變動范圍和變動間隔存在差異。A2組的客戶需求量大多集中在15kg～30kg，同時由于飛行范圍的限制，綜合成本變動較小，并且細微的變動主要集中在15kg～25kg之間。對于C2組的數據集，當無人機載荷能力在15kg～20kg范圍內變動時，總配送成本變動較大。主要是因為客戶點的需求量在15kg～20kg。無人機的載荷能力從25kg增加至30kg時，三組數據成本降低不明顯，由于無人機飛行范圍的限制，增加載重不能進一步降低配送成本。

4 結 論

本文研究了無人機與卡車多組合配送問題，以最小化配送總成本為目標建立模型，并設計了求解該問題的變鄰域搜索算法，具體包括：首先，對客戶的配送方式進行選擇；其次，以卡車最大載荷為約束，使用K-means算法確定聚類并運用迭代最近點算法給出初始路徑；最后，采用混合變鄰域算法優化初始路徑，最終得到總成本最低的路徑方案。算例結果驗證了本文所設計算法能有效求解所提問題，同時分析了無人機的飛行范圍以及載重對最優方案產生影響。

考慮無人機與卡車多組合配送的實用性和有效性，接下來可進一步研究更有效的啟發式算法，拓展并應用到城市地區更復雜的配送場景，考慮交通情況、時間窗等實際約束。

參考文獻：

[1] 任璇，黃輝，于少偉，等. 車輛與無人機組合配送研究綜述[J]. 控制與決策，2021，36（10）：2313-2327.

[2] QUANG M H， YVES D， QUANG D P， et al. On the min-cost traveling salesman problem with drone[J]. Transportation Research Part C， 2018，86：597-621.

[3] KANG M J， LEE C， et al. An exact algorithm for heterogeneous drone-truck routing problem[J]. Transportation Science， 2021，55（5）：1088-1112.

[4] 路世昌，邵旭倫，李丹. 卡車-無人機協同救災物資避障配送問題研究[J]. 計算機工程與應用，2023，59（2）：289-298.

[5] AGATZ N， PAUL B， SCHMIDT M， et al. Optimization approaches for the traveling salesman problem with drone[J]. Transportation Science， 2018，52（4）：965-981.

[6] PUAL B， AGATZ N， SCHMIDT M， et al. Dynamic programming approaches for the traveling salesman problem with drone[J]. Networks， 2018，72（4）：528-542.

[7] MURRAY C C， RITWIK R， et al. The multiple flying sidekicks traveling salesman problem： Parcel delivery with multiple drones[J]. Transportation Research Part C， 2020，110：368-398.

[8] 曹英英，陳淮莉. 基于集群的卡車與無人機聯合配送調度研究[J]. 計算機工程與應用，2022，58（11）：287-294.

[9] 季金華，劉亞君，別一鳴，等. 基于無人機與卡車協作的封控社區生活物資配送方法[J]. 交通運輸系統工程與信息，2022，22（5）：264-272.

[10] 彭勇，黎元鈞. 考慮疫情影響的卡車無人機協同配送路徑優化[J]. 中國公路學報，2020，33（11）：73-82.

[11] WANG X Y， POIKONEN S， GOLDEN B， et al. The vehicle routing problem with drones： Several worst-case results[J]. Optimization Letters， 2017，11（4）：679-697.

[12] GU R X， LIU Y， MARK P， et al. Dynamic truck-drone routing problem for scheduled deliveries and on-demand pickups with time-related constraints[J]. Transportation Research Part C， 2023，151：1-19.

[13] TAMKE F， BUSHERU. A branch-and-cut algorithm for the vehicle routing problem with drones[J]. Transportation Research Part B， 2021，144：174-203.

[14] 顏瑞，陳立雙，朱曉寧，等. 考慮區域限制的卡車搭載無人機車輛路徑問題研究[J]. 中國管理科學，2022，30（5）：144-155.

[15] CUI S X， SUN Q， ZHANG Q， et al. A time-dependent vehicle routing problem for instant delivery based on memetic algorithm[Z]. 2022.

[16] DHEKRA R， JOUHAINA C S， WASSILA A M， et al. Application of a variable neighborhood search algorithm to a fleet size and mix vehicle routing problem with electric modular vehicles[J]. Computers & Industrial Engineering， 2019，130：537-550.

[17] 郭秀萍，胡運霞. 卡車與無人機聯合配送模式下物流調度的優化研究[J]. 工業工程與管理，2021，26（1）：1-8.

[18] KITJACHAROENCHAI P， MIN B C， LEE S， et al. Two echelon vehicle routing problem with drones in last mile delivery[J]. International Journal of Production Economics， 2020，225：107598.