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

關(guān)鍵詞：無人機(jī)；路徑規(guī)劃；變鄰域搜索；組合配送；城市配送

中圖分類號(hào)：F252.14 文獻(xiàn)標(biāo)志碼：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 引 言

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

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

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

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

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

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

1 無人機(jī)與卡車多組合配送問題

1.1 問題描述

假定有一個(gè)配送中心與若干客戶，各客戶的需求量已知，配送中心到各客戶點(diǎn)的配送距離已知。配送中心有若干同質(zhì)的貨車和多架同質(zhì)的無人機(jī)，無人機(jī)包括車載無人機(jī)與獨(dú)立無人機(jī)，每輛貨車會(huì)搭載一架車載無人機(jī)。在這個(gè)配送系統(tǒng)中，每個(gè)客戶只能被服務(wù)一次。配送中心根據(jù)客戶的需求，靈活地派遣貨車和車載無人機(jī)、獨(dú)立無人機(jī)，以提供高效的配送服務(wù)。

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

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

1.2 問題假設(shè)

（1）客戶點(diǎn)的坐標(biāo)和需求已知；

（2）車載無人機(jī)或獨(dú)立無人機(jī)單次只能為單一顧客服務(wù)；

（3）卡車必須在原位置或者后續(xù)位置回收已經(jīng)發(fā)射的車載無人機(jī)；

（4）無人機(jī)速度和載荷對(duì)車載或獨(dú)立無人機(jī)的續(xù)航能力不產(chǎn)生影響；

（5）每個(gè)客戶點(diǎn)只能被服務(wù)一次；

（6）獨(dú)立UAV與車載UAV同質(zhì)；

（7）卡車、車載無人機(jī)和獨(dú)立無人機(jī)速度恒定，每段里程用歐式距離測(cè)量。

1.3 符號(hào)定義

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

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

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

無人機(jī)和卡車多組合配送問題HDTDTSP的數(shù)學(xué)模型如下：

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

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

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

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

2.1 配送方式的選擇與卡車配送區(qū)域的確定

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

步驟2：將集合P中客戶點(diǎn)分配給卡車與車載無人機(jī)配送，集合N中客戶點(diǎn)由獨(dú)立無人機(jī)配送；

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

步驟4：在客戶點(diǎn)中隨機(jī)選擇M個(gè)對(duì)象作為初始聚類中心；

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

步驟6：根據(jù)步驟5中的M個(gè)聚類簇中心，對(duì)聚類中心信息進(jìn)行更新；

步驟7：算法迭代到設(shè)定次數(shù)，計(jì)算終止，輸出結(jié)果，否則轉(zhuǎn)步驟5。

2.2 卡車與車載無人機(jī)路徑規(guī)劃

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

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

2.3 獨(dú)立無人機(jī)的路徑規(guī)劃與全局最優(yōu)路徑搜索

步驟1：采取貪婪算法對(duì)集合N中的需求點(diǎn)進(jìn)行路徑規(guī)劃，從而確定獨(dú)立無人機(jī)的初始解；

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

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

步驟4：對(duì)集合M中客戶節(jié)約的成本進(jìn)行計(jì)算，將其從大到小進(jìn)行排列；

步驟5：依次將步驟4中客戶按節(jié)約的成本高低加入卡車路線中，在加入的同時(shí)判斷是否滿足卡車的載重，滿足則加入，不滿足則停止，并根據(jù)加入的客戶點(diǎn)重新規(guī)劃路徑。

3 算例分析

3.1 參數(shù)說明

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

假設(shè)無人機(jī)的額定載荷t=15kg，航行里程D=15km，卡車額定載荷T=200kg?？蛻舻脚渌忘c(diǎn)的最大往返直線距離D=15km?？ㄜ噯未喂潭ㄙM(fèi)用為80元，無人機(jī)單次固定費(fèi)用為20元；卡車的單位距離成本C=1.5元/km，無人機(jī)的單位距離飛行成本C=0.3元/km[17-18]。

運(yùn)行環(huán)境為Windows11操作系統(tǒng)，處理器為AMD Ryzen 7 6800H with Radeon Graphics@3.20GHz。

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

車輛與無人機(jī)的并行配送是指車輛與無人機(jī)分別獨(dú)立完成對(duì)需求點(diǎn)的配送；車輛與無人機(jī)的協(xié)調(diào)配送是指車輛搭載無人機(jī)，兩者共同對(duì)需求點(diǎn)進(jìn)行配送。本文提出的車輛與無人機(jī)的多組合配送是指協(xié)同和并行兩種配送方式相結(jié)合的混合配送，一方面車載無人機(jī)搭載車輛共同完成配送任務(wù)，另一方面獨(dú)立無人機(jī)可從配送中心直接完成配送。

為了說明組合配送的優(yōu)越性，以算例A51為例，分別采取三種配送方式進(jìn)行運(yùn)輸，比較結(jié)果如表1所示。

由表1可知：針對(duì)城市末端配送的復(fù)雜場(chǎng)景需求，結(jié)合無人機(jī)和卡車的多組合配送方式，可以同時(shí)實(shí)現(xiàn)協(xié)同和并行的優(yōu)勢(shì)。這種配送方式不僅能有效降低無人機(jī)使用頻率和總配送距離，還能減少物流系統(tǒng)運(yùn)營(yíng)成本。圖6為算例A51的最優(yōu)配送路線。

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

3.3 算法的有效性分析

3.3.1 算法規(guī)模性分析

選取6種不同規(guī)模的數(shù)據(jù)，分別使用三種配送方式進(jìn)行計(jì)算，F(xiàn)為無人機(jī)配送成本，F(xiàn)為卡車配送成本，F(xiàn)為運(yùn)營(yíng)總成本。

由表2可以看出，隨著客戶規(guī)模的增加，傳統(tǒng)配送的總成本遠(yuǎn)遠(yuǎn)高于其他兩種配送方式。與協(xié)同配送相比，組合配送在配送中規(guī)模的客戶時(shí)總成本降低5%，在配送小規(guī)模與大規(guī)模客戶，總成本降低8%。

與傳統(tǒng)配送相比較，本文采用的組合配送由于無人機(jī)的參與，組合配送方式下的卡車?yán)锍虦p少近40%，且隨著客戶點(diǎn)的增加而增幅較緩。同時(shí)，為進(jìn)一步對(duì)比配送方法的優(yōu)劣，選取三種配送方式進(jìn)行配送。經(jīng)過三階段算法優(yōu)化，組合配送的總成本與傳統(tǒng)卡車配送成本相比分別節(jié)約17.26%、12.68%、14.24%、23.78%、31.47%和33.22%，可以看出：組合配送與傳統(tǒng)卡車相比，隨著客戶點(diǎn)規(guī)模的增多，節(jié)約的成本比例不斷增加，說明該配送方法是有效的。

與并行配送相比，組合配送分別節(jié)約12.5%、2.24%、3.67%、6.89%、20.93%和13.91%?？梢钥闯?，組合配送方式與并行配送方式相比也降低了成本，進(jìn)一步說明配送方法的有效性。

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

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

3.4 敏感性分析

3.4.1 飛行范圍的敏感性分析

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

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

3.4.2 無人機(jī)載重的敏感性分析

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

從圖8可知：在無人機(jī)的載荷能力等差變動(dòng)的情況下，載荷能力越大，總配送成本越低。然而，不同組數(shù)據(jù)的綜合成本變動(dòng)范圍和變動(dòng)間隔存在差異。A2組的客戶需求量大多集中在15kg～30kg，同時(shí)由于飛行范圍的限制，綜合成本變動(dòng)較小，并且細(xì)微的變動(dòng)主要集中在15kg～25kg之間。對(duì)于C2組的數(shù)據(jù)集，當(dāng)無人機(jī)載荷能力在15kg～20kg范圍內(nèi)變動(dòng)時(shí)，總配送成本變動(dòng)較大。主要是因?yàn)榭蛻酎c(diǎn)的需求量在15kg～20kg。無人機(jī)的載荷能力從25kg增加至30kg時(shí)，三組數(shù)據(jù)成本降低不明顯，由于無人機(jī)飛行范圍的限制，增加載重不能進(jìn)一步降低配送成本。

4 結(jié) 論

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

考慮無人機(jī)與卡車多組合配送的實(shí)用性和有效性，接下來可進(jìn)一步研究更有效的啟發(fā)式算法，拓展并應(yīng)用到城市地區(qū)更復(fù)雜的配送場(chǎng)景，考慮交通情況、時(shí)間窗等實(shí)際約束。

參考文獻(xiàn)：

[1] 任璇，黃輝，于少偉，等. 車輛與無人機(jī)組合配送研究綜述[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ī)協(xié)同救災(zāi)物資避障配送問題研究[J]. 計(jì)算機(jī)工程與應(yīng)用，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ī)聯(lián)合配送調(diào)度研究[J]. 計(jì)算機(jī)工程與應(yīng)用，2022，58（11）：287-294.

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

[10] 彭勇，黎元鈞. 考慮疫情影響的卡車無人機(jī)協(xié)同配送路徑優(yōu)化[J]. 中國(guó)公路學(xué)報(bào)，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] 顏瑞，陳立雙，朱曉寧，等. 考慮區(qū)域限制的卡車搭載無人機(jī)車輛路徑問題研究[J]. 中國(guó)管理科學(xué)，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] 郭秀萍，胡運(yùn)霞. 卡車與無人機(jī)聯(lián)合配送模式下物流調(diào)度的優(yōu)化研究[J]. 工業(yè)工程與管理，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.