無(wú)人機(jī)與卡車(chē)多組合配送問(wèn)題研究

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

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

中圖分類(lèi)號(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 引 言

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

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

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

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

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

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

1 無(wú)人機(jī)與卡車(chē)多組合配送問(wèn)題

1.1 問(wèn)題描述

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

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

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

1.2 問(wèn)題假設(shè)

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

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

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

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

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

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

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

1.3 符號(hào)定義

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

令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表示配送貨車(chē)集；U=1，2，…，u表示車(chē)載UAV的集合；U=1，2，…，u表示獨(dú)立配送UAV集合；S表示所有顧客需求點(diǎn)超過(guò)無(wú)人機(jī)最大載重的集合；S表示所有顧客需求點(diǎn)超過(guò)無(wú)人機(jī)最大續(xù)航的集合；S和S分別表示卡車(chē)和無(wú)人機(jī)的最大負(fù)載量；D表示無(wú)人機(jī)的最大續(xù)航里程；C與C分別表示卡車(chē)與無(wú)人機(jī)的單位距離配送成本；P與P分別表示卡車(chē)與無(wú)人機(jī)的單輛固定成本；w表示客戶點(diǎn)i的需求量；e表示客戶點(diǎn)i在卡車(chē)n路徑中的序號(hào)；d表示卡車(chē)n從客戶i到客戶j的距離；d表示車(chē)載無(wú)人機(jī)u從客戶i到客戶j的距離；dd=d+d表示獨(dú)立無(wú)人機(jī)u對(duì)客戶i的配送距離。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 算例分析

3.1 參數(shù)說(shuō)明

在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，基于卡車(chē)-無(wú)人機(jī)組合配送背景要求，對(duì)標(biāo)準(zhǔn)算例數(shù)據(jù)進(jìn)行一定的處理，分別包含一個(gè)配送中心和16、32、40、51、76、101個(gè)客戶。此外，對(duì)客戶需求量進(jìn)行調(diào)整，以確保車(chē)載或獨(dú)立無(wú)人機(jī)可以完成配送任務(wù)。

假設(shè)無(wú)人機(jī)的額定載荷t=15kg，航行里程D=15km，卡車(chē)額定載荷T=200kg。客戶到配送點(diǎn)的最大往返直線距離D=15km?？ㄜ?chē)單次固定費(fèi)用為80元，無(wú)人機(jī)單次固定費(fèi)用為20元；卡車(chē)的單位距離成本C=1.5元/km，無(wú)人機(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 不同配送方式的總配送成本

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

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

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

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

3.3 算法的有效性分析

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

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

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

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

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

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

為了進(jìn)一步驗(yàn)證變鄰域算法在解決HDTDTSP問(wèn)題方面的性能優(yōu)勢(shì)，我們選取了文獻(xiàn)[20]中的大規(guī)模鄰域搜索（LNS）作為對(duì)照。根據(jù)表3的數(shù)據(jù)，變鄰域算法在解決A16、A32、A51、A76和A101這五個(gè)問(wèn)題實(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問(wèn)題上顯示出更高效的求解能力，能夠在短時(shí)間內(nèi)獲得最優(yōu)解決方案。

3.4 敏感性分析

3.4.1 飛行范圍的敏感性分析

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

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

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

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

從圖8可知：在無(wú)人機(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)無(wú)人機(jī)載荷能力在15kg～20kg范圍內(nèi)變動(dòng)時(shí)，總配送成本變動(dòng)較大。主要是因?yàn)榭蛻酎c(diǎn)的需求量在15kg～20kg。無(wú)人機(jī)的載荷能力從25kg增加至30kg時(shí)，三組數(shù)據(jù)成本降低不明顯，由于無(wú)人機(jī)飛行范圍的限制，增加載重不能進(jìn)一步降低配送成本。

4 結(jié) 論

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

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

參考文獻(xiàn)：

[1] 任璇，黃輝，于少偉，等. 車(chē)輛與無(wú)人機(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] 路世昌，邵旭倫，李丹. 卡車(chē)-無(wú)人機(jī)協(xié)同救災(zāi)物資避障配送問(wèn)題研究[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] 曹英英，陳淮莉. 基于集群的卡車(chē)與無(wú)人機(jī)聯(lián)合配送調(diào)度研究[J]. 計(jì)算機(jī)工程與應(yīng)用，2022，58（11）：287-294.

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

[10] 彭勇，黎元鈞. 考慮疫情影響的卡車(chē)無(wú)人機(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ū)域限制的卡車(chē)搭載無(wú)人機(jī)車(chē)輛路徑問(wèn)題研究[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)霞. 卡車(chē)與無(wú)人機(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.