考慮交通受限的卡車無人機協(xié)同配送路徑優(yōu)化研究

摘" 要：隨著城市化進程的加速，交通擁堵已成為城市生活中不可忽視的問題，許多城市采取了車牌限行等措施來緩解交通壓力。同時，為了確保飛行安全和維護城市秩序，一些城市也通過設定禁飛區(qū)等對無人機飛行進行限制。這些政策給城市物流配送帶來了很大的挑戰(zhàn)。文章提出了一種基于卡車無人機協(xié)同配送的解決方案，并采用單親遺傳算法對模型進行求解，實驗結(jié)果表明，相比傳統(tǒng)的卡車配送方式，協(xié)同方案可以縮短配送時間，能夠在一定程度上避免交通擁堵和無人機飛行安全帶來的不確定性，提高配送效率和準確性。

" 關(guān)鍵詞：卡車；無人機；協(xié)同配送；遺傳算法

" 中圖分類號：F252.14" " 文獻標志碼：A" " DOI：10.13714/j.cnki.1002-3100.2025.05.006

Abstract： With the acceleration of urbanization， traffic congestion has become a non-negligible problem in urban life. Many cities have taken measures such as license plate restrictions to alleviate traffic pressure. At the same time， in order to ensure flight safety and maintain urban order， some cities have also restricted drone flights by setting no-fly zones and other measures. These policies bring great challenges to urban logistics and distribution. This paper proposes a solution based on the collaborative delivery of truck-drone， and uses the single parent genetic algorithm to solve the model. The experimental results show that compared with the traditional truck delivery method， the collaborative solution can shorten the delivery time， avoid the uncertainty caused by traffic congestion and drone flight safety to a certain extent， and improve the efficiency and accuracy of delivery.

Key words： truck; UAV; collaborative distribution; genetic algorithm

0" 引" 言

" 物流行業(yè)迫切需要跟上迅速變化的需求和供應條件。一方面，城市擁堵對新興的物流服務提出了巨大的挑戰(zhàn)。當客戶需求發(fā)生在高峰通勤時間，僅通過卡車來滿足這些需求就會有困難和不確定性的準時交貨。這種情況在有嚴格及時性要求的后勤服務中很明顯，例如醫(yī)療物資（如人體器官、血液）的運輸[1]。另一方面，城市急于采取卡車交通限制政策，以保護城市的流動性和環(huán)境，從而限制了物流業(yè)務的協(xié)調(diào)。因此，在有限的城市物流資源條件下及時滿足客戶需求已成為城市物流中的一個關(guān)鍵問題。

" 無人機已經(jīng)成為解決這個問題最有效的工具。使用無人機進行配送包裹有兩個好處。首先，無人機不依賴于交通基礎(chǔ)設施，因此，無人機能夠抵御交通系統(tǒng)中的干擾。其次，無人機性能可靠，飛行速度快。這些技術(shù)優(yōu)勢和無人機使用的廣闊市場前景促使各種公司，如亞馬遜，谷歌和其他物流巨頭，在他們的配送系統(tǒng)中使用無人機。

" 但是，只使用無人機配送也有局限性。首先，無人機的巡航距離很短，有的客戶點距離最近的物流倉庫都超過了這個距離，因此無人機無法從這樣的倉庫起飛。其次，無人機的貨運能力有限，這個限制會影響一架無人機可以攜帶貨物的類型和數(shù)量，以及每架無人機可以服務的客戶數(shù)量。最后，飛行限制限制了無人機的使用。在一些城市的禁飛區(qū)，許多無人機無法進入。在一些大城市，密集的高層建筑也給無人機的操作帶來了挑戰(zhàn)?？紤]到這些限制，利用無人機和卡車協(xié)調(diào)配送預計將成為未來城市物流配送的一種常見方式。

" 無人機的技術(shù)進步使卡車-無人機混合模式能夠?qū)a(chǎn)品從倉庫運送到客戶手中，從而提高了城市物流配送網(wǎng)絡的效率。對于卡車無人機協(xié)同配送，Chase et al.[2]最早提出了兩種模型，一個是FSTSP，另外一個是PDSTSP。陳添博等[3]證明了市區(qū)內(nèi)卡車無人機協(xié)同配送的高效性。季金華等[4]以無人機載貨重量限制及生活物資時效性要求等為約束條件，建立混合整數(shù)規(guī)劃模型。目前卡車無人機協(xié)同送貨存在以下幾點考慮不足：（1）交通擁堵導致部分客戶點卡車無法實現(xiàn)配送；（2）禁飛區(qū)對于無人機配送的影響尚未得到充分考慮；（3）卡車和無人機都可以獨立服務客戶，并且無人機可以在同一個客戶點起飛回收，也可以在不同的客戶點起飛回收。

" 本文綜合考慮以上幾點，研究車輛搭載無人機對某區(qū)域內(nèi)多個客戶送貨時，如何分配客戶以及規(guī)劃車輛和無人機路徑，使總服務時間最短的問題。并與單獨使用卡車的配送時間進行比較，進而對比分析證明卡車與無人機協(xié)同配送的高效性。該問題的解決方案能提高物流配送系統(tǒng)的能力，滿足客戶及時交貨的需求，提高總體的配送效率。

1" 問題建模

1.1" 問題描述

J公司在城市配送過程中經(jīng)常遇到一些問題，如交通擁堵、道路限行等不可控因素，導致無法承接更多的加急單任務，從而失去了一大批潛在客戶。為了解決這個問題，J公司進行了大量的研發(fā)工作，投入了時間、資金和精力，使其在無人機領(lǐng)域取得了相當成熟的技術(shù)。目前，J公司已經(jīng)獲得了相關(guān)部門的許可，可以試運營無人機配送服務。然而，僅僅依靠無人機進行配送也存在一些問題，比如無人機有禁飛區(qū)域。因此，為了兼顧安全和效率，J公司制定了一項新的配送策略，即卡車與無人機協(xié)同配送。

" 在這種協(xié)同配送模式下，由于有的客戶需求服務不能用無人機來提供（例如，有禁飛限制，需求量超過無人機的最大載重等），因此這樣的客戶只能用卡車來提供服務。有的客戶點區(qū)域?qū)嵭薪煌ü苤疲缆贩忾]，卡車不能駛?cè)?，只能由無人機來提供服務。此外，還有一些客戶配送不受限制，卡車和無人機都可以為其提供服務。

為了方便研究，對問題進行簡化，根據(jù)配送過程中可能存在的問題進行假設：

（1）倉庫和所有客戶需求點已知，且所有客戶點只能訪問一次；

" （2）無人機飛出后一次只能服務一個客戶點；

（3）無人機有最大飛行時間限制；

（4）無人機不能在卡車行駛途中發(fā)射，即無人機只能在卡車到達客戶點時飛出；

" （5）無人機不能在倉庫飛出，也不能獨自飛回倉庫；

" （6）無人機充電采用換電模式，且換電時間忽略不計；

" （7）無人機發(fā)射和回收的時間忽略不計，裝卸包裹的時間也不計；

" （8）卡車和無人機都勻速行駛，速度不受載重影響。

1.2" 模型建立

" 式（2）表示卡車從倉庫出發(fā)一次。式（3）表示卡車從客戶點返回倉庫，且只有一次。式（4）表示卡車在提供服務過程中的路徑連續(xù)性，式（2）、式（3）、式（4）共同表示車輛流量平衡。式（5）表示每個客戶只能由一架無人機服務或一輛卡車服務。式（6）表示無人機起飛后必須服務一個客戶且只能服務一個。式（7）表示無人機不能從倉庫起飛，即只能在卡車行駛到某一個客戶點之后起飛。式（8）表示無人機不能在倉庫降落，即無人機不能單獨飛回倉庫，必須由卡車搭載回倉庫。式（9）表示若無人機從客戶點i起飛到客戶點j之后又返回到客戶點k時，卡車必須要經(jīng)過客戶點i和客戶點j。式（10）表示無人機流量平衡。式（11）、式（12）表示卡車去子環(huán)約束，確?？ㄜ囆旭偮肪€正確。式（13）表示如果無人機從客戶點i飛出，最后又返回到客戶點k，那么卡車必須到達客戶點k之前先到達客戶點i。式（14）表示無人機要離開某個客戶點時，要先為該客戶點提供完服務才能離開。式（15）表示若無人機飛出提供服務，那么卡車在離開某個客戶點之前無人機必須達到該客戶點，若無人機沒有飛出，就一直搭載在卡車上。式（16）表示卡車為某個客戶點提供完服務后無人機才能起飛去執(zhí)行下一個配送任務。式（17）、式（18）表示無人機飛行滿足最大飛行時間限制。式（19）表示卡車不能去只能由無人機提供服務的客戶點。式（20）表示無人機不能去只能由卡車提供服務的客戶點。式（21）表示卡車離開倉庫的時間記為0。式（22）、式（23）是0～1變量約束。

2" 數(shù)據(jù)處理

J公司需要向某區(qū)域內(nèi)的17個客戶進行配送。己知客戶點、倉庫的實際坐標，為方便計算，已將實際坐標數(shù)據(jù)轉(zhuǎn)化為直角坐標系中相對位置坐標，數(shù)據(jù)如表2所示。其中序號1表示倉庫，序號2～4表示只能由卡車提供服務的客戶點，序號5～9表示只能由無人機提供服務的客戶點，序號10～18表示卡車和無人機都可以提供服務的客戶點。倉庫和客戶點相對位置圖如圖1所示。

3" 實驗結(jié)果分析

本文所研究的卡車與無人機協(xié)同配送問題屬于NP難問題，因此采用單親遺傳算法進行求解。單親遺傳算法是一種簡化版的遺傳算法，它僅包括選擇和變異兩種遺傳算子，沒有交叉算子。相對于傳統(tǒng)遺傳算法，單親遺傳算法更加高效，通過選擇操作篩選出適應度較高的個體，并通過變異操作引入新的基因變異，從而不斷搜索解空間。時間最短的最優(yōu)解如圖2所示。

卡車路徑先從倉庫1出發(fā)，先后經(jīng)過15-2-13-18-16-3-14-4-11-12，最后返回倉庫。無人機在卡車到達客戶點2時起飛服務客戶點5，隨后返回到客戶點2，接著再從客戶點2起飛服務客戶點6，隨后返回客戶點2，再從客戶點2起飛服務客戶點7，此時卡車正前往客戶點13，無人機這次返回到客戶點13。之后無人機和卡車一起到客戶點18，然后無人機起飛服務客戶點17并返回到客戶點16。再從客戶點16起飛服務客戶點8并返回到客戶點14。再從客戶點14起飛服務客戶點9返回到客戶點4。最后從客戶點11起飛服務客戶點10并返回到客戶點12。

卡車無人機協(xié)同配送時，卡車行駛速度為50km/h，無人機飛行速度是30km/h，無人機服務客戶點時間為1分鐘，卡車服務客戶點時間為4分鐘，經(jīng)過計算服務完所有客戶點所需時間為2.45h。如若不考慮交通限制，只用卡車單獨配送，服務完所有客戶點所需時間為3.8h。

通過對比，卡車無人機協(xié)同配送將部分配送任務交給無人機進行，減少了卡車的行駛路程，從而降低了行駛時間和靈活處理時間。整體配送任務的總時間得到了大幅節(jié)省，相比于傳統(tǒng)只有卡車配送的方案，節(jié)省了1.35小時的時間。這符合預期，有效提高了配送效率和服務質(zhì)量。

4" 結(jié)" 論

本文在考慮道路受限情況下卡車無人機協(xié)同配送路徑優(yōu)化，通過構(gòu)建數(shù)學模型，并采用單親遺傳算法進行求解，結(jié)果表明卡車無人機協(xié)同配送相較于傳統(tǒng)卡車配送更加節(jié)約時間?？傊ㄜ嚐o人機協(xié)同配送是一種前景廣闊的解決方案，在城市貨運領(lǐng)域具有巨大潛力。然而，還需要進一步研究和解決一些問題，例如考慮無人機的速度變化，客戶時間窗等，讓問題更加貼合實際。

參考文獻：

[1] 劉子齊，牛新源. 無人機配送的血液供應鏈管理探討[J]. 管理觀察，2018（1）：190-192.

[2]" CHASE C MURRAY， AMANDA G CHU. The flying sidekick traveling salesman problem： Optimization of drone-assisted parcel delivery[J]. Transportation Research Part C： Emerging Technologies， 2015，54：86-109.

[3] 陳添博，謝寶玲. 市區(qū)內(nèi)卡車與無人機協(xié)同配送路徑優(yōu)化研究[J]. 物流科技，2023，46（1）：19-22.

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