摘 要：為有效提升“最后一公里”配送效率，以總運(yùn)營成本最少為目標(biāo)函數(shù)，提出了考慮道路擁堵指數(shù)的“無人機(jī)—卡車”配送路徑優(yōu)化模型。首先，基于改進(jìn)的K-means算法確定卡車配送點(diǎn)；接著考慮道路擁堵指數(shù)，運(yùn)用節(jié)約里程法得到卡車配送路徑；然后采用改進(jìn)模擬退火算法確定無人機(jī)飛行路線；最后選取鄭州市主城區(qū)的80個(gè)小區(qū)進(jìn)行實(shí)例計(jì)算，與卡車單獨(dú)配送相比，“無人機(jī)—卡車”配送模式的配送成本降低了110元，約減少了13.78%。實(shí)例計(jì)算結(jié)果表明，“無人機(jī)—卡車”聯(lián)合配送模型可有效減少配送成本，求解算法高效，更加貼合現(xiàn)實(shí)的配送場景，為新時(shí)代物資配送問題提供了理論參考。

關(guān)鍵詞：無人機(jī)—卡車；路徑優(yōu)化；K-means算法；模擬退火算法

中圖分類號：TP18" " 文獻(xiàn)標(biāo)志碼：A" 文章編號：1007-1199（2024）02-0037-09

DOI：10.19327/j.cnki.zuaxb.1007-1199.2024.02.005

鄭州航空工業(yè)管理學(xué)院，河南 鄭州 450015

無人機(jī)因具有速度快、成本低、行駛路徑接近直線的優(yōu)勢在物流領(lǐng)域受到廣泛關(guān)注，但由于其飛行里程和載荷能力有限，故越來越多的學(xué)者開始關(guān)注卡車與無人機(jī)的混合配送，以確保其持續(xù)作業(yè)。對“無人機(jī)—卡車”配送路徑優(yōu)化模型與算法的研究不僅符合物流行業(yè)的發(fā)展，而且具有較強(qiáng)實(shí)用意義，是解決“最后一公里”配送和未來城市物資配送問題的熱門解決方案［1-3］。

針對旅行商問題，Chu和Murry（2015）[４]最早提出采用卡車和無人機(jī)對其進(jìn)行路徑規(guī)劃。韓明等（2019）［5］設(shè)計(jì)高寒山地“車輛+無人機(jī)”聯(lián)運(yùn)配送模式，以軍事效能最大、總成本最小為目標(biāo)構(gòu)建雙目標(biāo)“車輛+無人機(jī)”路徑規(guī)劃模型。Savuran等（2016）[６]考慮了基于無人機(jī)的配送系統(tǒng)，其目標(biāo)是使無人機(jī)飛行路徑最短，從而確定卡車?？奎c(diǎn)，以滿足所有客戶需求。Chang等（2018）［7］采用K-means算法及非線性規(guī)劃模型確定了卡車的?？课恢?。Wang等（2017）［8］的研究證明了卡車和無人機(jī)的配送效率始終高于卡車單獨(dú)配送。曹英英等（2022）[9]針對卡車—無人機(jī)聯(lián)合配送中無人機(jī)單次飛行配送一個(gè)包裹的問題，采用遺傳模擬退火算法進(jìn)行了路徑優(yōu)化。郭秀萍等（2021）［10］提出無人機(jī)單次飛行可攜帶多個(gè)包裹并設(shè)計(jì)了三階段規(guī)劃求解方法。孟姍姍等（2022）［11］將超出無人機(jī)承載量的包裹由卡車進(jìn)行單獨(dú)配送，卡車與無人機(jī)距離均采用歐氏距離進(jìn)行測量，并運(yùn)用變鄰域模擬退火算法進(jìn)行線路優(yōu)化，提出了兩階段求解方法對配送成本進(jìn)行優(yōu)化。柳伍生等（2021）［12］認(rèn)為采用無人機(jī)單次飛行可服務(wù)多個(gè)顧客點(diǎn)，且完成任務(wù)后無需返回卡車?？奎c(diǎn)，并基于模擬退火算法對配送路徑進(jìn)行優(yōu)化。Carlsson等（2018）［13］假設(shè)卡車可以在其行駛過程中發(fā)射無人機(jī)，無人機(jī)服務(wù)客戶后飛回正在行駛的卡車上，繼續(xù)進(jìn)行下一次服務(wù)，構(gòu)建了“卡車+無人機(jī)”動(dòng)態(tài)協(xié)同配送的馬繩路徑問題優(yōu)化模型。Agatz、Bouman等（2018）［14］假設(shè)無人機(jī)和卡車可以同時(shí)獨(dú)立送貨，在卡車服務(wù)某客戶時(shí)，無人機(jī)搭載貨物從卡車出發(fā)服務(wù)，配送完畢后無人機(jī)飛行到卡車行駛路徑的下一個(gè)節(jié)點(diǎn)與卡車匯合，以總成本最小為目標(biāo)構(gòu)建“卡車+無人機(jī)”動(dòng)態(tài)協(xié)同配送的混合整數(shù)規(guī)劃模型。此外，楊雙鵬等（2022）［15］對采用單輛卡車配送進(jìn)行了研究等。結(jié)合文獻(xiàn)研究發(fā)現(xiàn)，“無人機(jī)—卡車”配送路徑優(yōu)化主要存在以下幾個(gè)問題：

（1）現(xiàn)有文獻(xiàn)在確定卡車配送點(diǎn)時(shí)多采用傳統(tǒng)的K-means算法，未考慮無人機(jī)配送的航程和容量限制，致使無法充分利用無人機(jī)的運(yùn)力，致使配送效率降低。

（2）現(xiàn)有文獻(xiàn)在對卡車進(jìn)行路徑優(yōu)化時(shí)，直接采用歐氏距離或者曼哈頓距離來測量卡車行駛距離，然而，實(shí)際配送過程中不同城市的道路交通情況可能存在較大差異，需對行駛距離進(jìn)行修正。

（3）優(yōu)化無人機(jī)飛行路徑時(shí)，現(xiàn)有文獻(xiàn)多采用傳統(tǒng)的模擬退火算法。傳統(tǒng)的模擬退火算法一般采取隨機(jī)生成或貪婪算法，從而導(dǎo)致初始解太過隨機(jī)，雖然能夠較好地?cái)[脫局部最優(yōu)解的限制，但無法在較少迭代次數(shù)下快速得出全局最優(yōu)解。

為了解決上述問題，結(jié)合無人機(jī)短程運(yùn)送成本明顯低于卡車運(yùn)送成本，本文采用將多輛卡車作為動(dòng)態(tài)“倉庫”，負(fù)責(zé)攜帶物品、搭載無人機(jī)，以及為無人機(jī)提供“消菌殺毒”、充電或更換電池的場地，無人機(jī)單次服務(wù)可配送多個(gè)客戶點(diǎn)的方案，以提高無人機(jī)的利用效率；在確定卡車配送點(diǎn)時(shí)，考慮無人機(jī)配送的航程和容量限制約束，基于改進(jìn)的K-means算法進(jìn)行聚類分析，得到合理的卡車配送點(diǎn)；在卡車路徑優(yōu)化過程中考慮道路擁堵指數(shù)，可以根據(jù)各地的道路交通情況做出相應(yīng)調(diào)整。同時(shí)支持多輛卡車同時(shí)派送，以提高配送效率以及擴(kuò)大配送中心的服務(wù)范圍；在無人機(jī)進(jìn)行路徑規(guī)劃時(shí)，采用“尾部客戶判斷法”［15］用以構(gòu)造初始解，不僅兼顧無人機(jī)的最大運(yùn)輸能力，使得無人機(jī)得到充分利用，并且可以極大程度上降低模擬退火算法的迭代次數(shù)，減少求解時(shí)間，使得最終優(yōu)化成果更加貼合實(shí)際，更具現(xiàn)實(shí)意義。

1 模型構(gòu)建

1.1 問題描述

圖1為“無人機(jī)—卡車”聯(lián)合配送示意圖。

為便于定量研究，特將問題簡化，并作出以下假設(shè)：

（1）配送中心需求為0；

（2）必須滿足所有客戶點(diǎn)需求；

（3）已知無人機(jī)的最大續(xù)航里程和最大載荷；

（4）當(dāng)滿足限制時(shí)，無人機(jī)單次飛行可服務(wù)多個(gè)客戶點(diǎn)；

（5）卡車數(shù)量、里程限制已知，且車輛上攜帶足夠的無人機(jī)電源；

（6）無人機(jī)配送完成后，需要返回卡車配送點(diǎn)更換電池，取貨后再進(jìn)行下一次配送；

（7）無人機(jī)無法在不同的卡車配送點(diǎn)之間隨意釋放和收回；

（8）每個(gè)客戶點(diǎn)的需求量不大于無人機(jī)單次配送的最大載荷。

1.2 符號說明

U：所有節(jié)點(diǎn)集合，U=B∪C；

B：卡車配送點(diǎn)的集合，B=｛b|b=1，2，3，…，K｝；

C：所有客戶點(diǎn)集合，C=｛c|c=1，2，3，…，M｝；

F：F=｛f|f=1，2，3，…，N｝為無人機(jī)集合；

K：卡車配送點(diǎn)個(gè)數(shù)；

M：客戶點(diǎn)個(gè)數(shù)；

N：無人機(jī)個(gè)數(shù)；

m：可調(diào)度的卡車車輛總數(shù)；

u：卡車編號；

L：卡車最大行駛距離；

q：道路擁堵指數(shù)；

S：卡車行駛總路程；

CQc：客戶點(diǎn)c的需求量；

Fm：卡車單位距離行駛成本；

W1：無人機(jī)配送成本；

Bm：卡車調(diào)用成本；

dhj：從配送點(diǎn)h到配送點(diǎn)j的距離；

FQf：無人機(jī)容量；

FLf：無人機(jī)航程；

BFf：無人機(jī)派遣準(zhǔn)備成本；

Wf：無人機(jī)裝卸成本；

Ff：無人機(jī)單位距離運(yùn)輸成本；

zhju：值為0或1，0表示卡車從配送點(diǎn)j到配送點(diǎn)h，1表示卡車從配送點(diǎn)h到配送點(diǎn)j；

lhu：值為0或1，0表示卡車配送點(diǎn)h的物品不是由卡車u進(jìn)行配送的，1表示卡車配送點(diǎn)h的物品是由卡車u進(jìn)行配送的；

xf=1表示無人機(jī)f投入使用，否則xf=0；

ycb=1表示需求點(diǎn)c被配送點(diǎn)b服務(wù)，否則ycb=0;

zijf=1表示無人機(jī)f從配送點(diǎn)i飛往配送點(diǎn)j，否則zijf=0。

1.3 模型建立

1.3.1確定卡車配送點(diǎn)

為確保無人機(jī)可有效抵達(dá)客戶點(diǎn)，要求無人機(jī)的最大續(xù)航里程必須大于卡車配送點(diǎn)至客戶點(diǎn)的往返距離，并可以此為依據(jù)對客戶點(diǎn)進(jìn)行聚類得到卡車配送點(diǎn)。

1.3.2卡車路徑優(yōu)化

通過改進(jìn)的K-means算法確定卡車配送點(diǎn)后，卡車從配送中心出發(fā)。為了提高配送效率，并結(jié)合實(shí)際情況，本文采用多輛卡車一起參與配送，分別以各自路線前往不同的配送點(diǎn)。結(jié)合道路擁堵指數(shù)并基于節(jié)約里程法對其行駛路線進(jìn)行優(yōu)化，以最小行駛路徑作為目標(biāo)函數(shù)，進(jìn)行建模求解。

設(shè)配送中心為P，從配送中心同時(shí)向k個(gè)卡車配送點(diǎn)進(jìn)行配送服務(wù)，已知配送中心共有m輛卡車可以用于配送，求解以最短路程S為最終目標(biāo)。

構(gòu)建目標(biāo)函數(shù)如下：

[minS=θh=0kj=0ku=1kdhjzhju] （1）

s.t.[u=1mlhu=1，=m，" " " h=1，2，…，kh=0" ] （2）

[θh=0kj=1kdhjzhju≤L] （3）

[h=1kzhju=lju" " " "j=0，1，2，…，k] （4）

[j=1kzhju=lhu] （5）

在上述配送路線優(yōu)化模型中，式（1）為總路程最小的目標(biāo)函數(shù)。約束條件式（2）表示該配送中心共有可配送卡車數(shù)量為m時(shí)，任意一個(gè)卡車配送點(diǎn)僅能由m輛卡車中的一輛來完成。式（3）表示每條卡車配送路徑的總里程數(shù)不得超過卡車的里程限制。式（4）、式（5）為消除卡車配送點(diǎn)間的子回路。

1.3.3無人機(jī)路徑優(yōu)化

以無人機(jī)配送成本最小為目標(biāo)，構(gòu)建如下目標(biāo)函數(shù)：

[minW1=f∈FxfBFf+i∈Uj∈Uzijfdij?Ff+Wf] （6）

s.t.[b∈Bycb=1 ， ?c∈C] （7）

[i∈Uj=CzijfCQj≤FQf ， ?f∈F] （8）

[i∈Uj∈Uzijfdij≤FLf ， ?f∈F] （9）

[i∈Uzijf-i∈Uzjif=0 ， ?j∈U ， f∈F] （10）

[i∈Uf∈Fzijf=1 ， ?j∈C] （11）

[f∈Fi∈Bj∈Bzijf=0 ， i≠j] （12）

目標(biāo)函數(shù)式（6）表示無人機(jī)配送的最小成本，由準(zhǔn)備成本和實(shí)際的運(yùn)輸成本組成；約束條件式（7）表示任意一客戶點(diǎn)只能對應(yīng)一個(gè)配送點(diǎn)；式（8）為限制無人機(jī)最大載荷；式（9）為限制無人機(jī)最大續(xù)航里程；式（10）為確保無人機(jī)配送服務(wù)路線為閉環(huán)；式（11）為確保每一個(gè)客戶點(diǎn)有且僅有一架無人機(jī)進(jìn)行配送服務(wù)；式（12）表示無人機(jī)不能在卡車配送點(diǎn)間飛行。

1.3.4無人機(jī)+卡車聯(lián)合配送目標(biāo)函數(shù)

[minW=SFm+W1+mBm] （13）

式（13）表示以無人機(jī)和卡車總配送成本最少為最終目標(biāo)，由卡車配送成本、無人機(jī)配送成本以及卡車調(diào)度成本組成。

2 算法設(shè)計(jì)

2.1 確定卡車配送點(diǎn)

針對卡車配送點(diǎn)問題，傳統(tǒng)K-means算法在求解過程中，首先選取k個(gè)點(diǎn)作為聚類中心，接著按照每個(gè)客戶點(diǎn)與聚類中心的距離選擇其歸屬聚類，而后計(jì)算新的聚類中心，再次劃分樣本，重復(fù)前面的過程，迭代到聚類中心不再變化。故k值的選取對于樣本的劃分非常重要。k值太小，可能會因某些客戶點(diǎn)距聚類中心過遠(yuǎn)以致超出無人機(jī)最大續(xù)航里程，導(dǎo)致無法配送；k值過大，則易造成配送成本增加。故在考慮無人機(jī)配送的航程和容量限制約束下，對傳統(tǒng)的K-means算法進(jìn)行了改進(jìn)，如圖2所示。

設(shè)Hmax為判別值，且Hmax稍小于FLf，可依據(jù)Hmax調(diào)整k值大小。改進(jìn)的K-means聚類算法能夠自適應(yīng)地確定聚類數(shù)以獲取適合問題的k值，改進(jìn)后的算法具體流程如下：

步驟1：任意選取k個(gè)客戶點(diǎn)作為初始聚類中心；

步驟2；計(jì)算客戶點(diǎn)與各聚類中心的距離，按照就近原則得到k個(gè)聚類簇；

步驟3：計(jì)算新的聚類中心，再次劃分樣本；

步驟4：重復(fù)步驟2和步驟3，直到聚類中心不再變化；

步驟5：計(jì)算各個(gè)簇內(nèi)所包含樣本與聚類中心的距離，并判斷該距離是否大于Hmax/2，若大于轉(zhuǎn)至步驟6，若小于轉(zhuǎn)至步驟7；

步驟6：使k=k+1，轉(zhuǎn)至步驟1；

步驟7：輸出結(jié)果。

2.2 考慮道路擁堵指數(shù)對多輛卡車行駛路徑進(jìn)行優(yōu)化

擁堵指數(shù)指卡車的行程時(shí)間與暢通行程時(shí)間的比值，擁堵指數(shù)越小，擁堵程度越低，道路越通暢；反之，則代表道路越擁堵。通過百度地圖交通出行大數(shù)據(jù)平臺可以查閱到主要城市地區(qū)的實(shí)時(shí)道路擁堵指數(shù)。結(jié)合本算法模型卡車勻速行駛，將擁堵指數(shù)轉(zhuǎn)換成相應(yīng)的里程來彌補(bǔ)卡車路徑規(guī)劃時(shí)采用歐氏距離計(jì)算造成的偏差，使其行駛距離進(jìn)一步貼合實(shí)際。

接著運(yùn)用節(jié)約里程法將所有站點(diǎn)兩兩組合，計(jì)算各個(gè)組合中，兩節(jié)點(diǎn)合并為一條線路時(shí)節(jié)約的里程數(shù)，并降序排列，合并線路后即可得到卡車配送路徑。

2.3 基于改進(jìn)的模擬退火算法確定無人機(jī)飛行路線

本文采用“尾部客戶判斷法”來構(gòu)建初始解，對模擬退火算法進(jìn)行改進(jìn)。改進(jìn)后的算法既兼顧了無人機(jī)的最大運(yùn)輸能力，同時(shí)還能極大程度上降低求解迭代次數(shù)，減少求解時(shí)間。

“尾部客戶判斷法”如圖3所示，a，b，c，…，f表示兩點(diǎn)間的距離，無人機(jī)起飛后，首先前往距離最近的客戶點(diǎn)1進(jìn)行配送，然后依據(jù)無人機(jī)所剩航程和容量判斷無人機(jī)服務(wù)距離客戶點(diǎn)1最近的客戶點(diǎn)2的可能性，如果滿足條件，則選擇繼續(xù)前往客戶點(diǎn)2進(jìn)行配送，否則直接返回卡車配送點(diǎn)，以此類推，即可構(gòu)建出初始解。改進(jìn)后的模擬退火算法如圖4所示。

3 實(shí)例計(jì)算

3.1 實(shí)例介紹

本文選取了河南省鄭州市主城區(qū)的80個(gè)小區(qū)來對“無人機(jī)—卡車”聯(lián)合配送模式進(jìn)行實(shí)例計(jì)算，如圖5所示。

通過百度地圖拾取各小區(qū)的經(jīng)緯度坐標(biāo)，單位為度，屬于地理坐標(biāo)系，需將其轉(zhuǎn)換成單位為米的投影坐標(biāo)系。本文基于高斯克呂格投影原理［16］，利用ArcGIS軟件，以經(jīng)緯度為初始坐標(biāo)輸入，通過投影變換工具將地理坐標(biāo)系轉(zhuǎn)換到北京54投影坐標(biāo)系。實(shí)施坐標(biāo)轉(zhuǎn)換后，可得到各研究點(diǎn)的平面直角坐標(biāo)，如表1所示。假設(shè)本區(qū)域內(nèi)共有兩輛卡車，每輛卡車配備3架無人機(jī)，客戶點(diǎn)的需求隨機(jī)生成，客戶位置及需求信息如表1所示，車輛和無人機(jī)的相關(guān)參數(shù)如表2所示。

3.2 確定卡車配送點(diǎn)

首先對客戶點(diǎn)進(jìn)行聚類，令k=2，Hmax=20km，求解結(jié)果如圖6所示。

接著，運(yùn)用傳統(tǒng)K-means算法對表1所示客戶點(diǎn)進(jìn)行聚類劃分，進(jìn)行對比分析。傳統(tǒng)K-means算法需要不斷手動(dòng)調(diào)節(jié)k值，才能使聚類結(jié)果滿足范圍約束。最終聚類結(jié)果如圖7所示。

通過對比分析發(fā)現(xiàn)，改進(jìn)后的K-means算法可以快速得到合適的k值，并使每個(gè)簇的半徑均在無人機(jī)續(xù)航里程內(nèi)。而傳統(tǒng)K-means算法則需要進(jìn)行多次嘗試，且得到的k值往往偏大。

3.3 優(yōu)化多輛卡車行駛路徑

為避免實(shí)時(shí)數(shù)據(jù)存在較大偶然性，本文選取2021年鄭州市的年平均擁堵指數(shù)，即q=1.597帶入計(jì)算。

通過節(jié)約里程法對1.3.2所建模型進(jìn)行求解，計(jì)算步驟如下：

（1）數(shù)據(jù)初始化，將各個(gè)聚類中心的橫縱坐標(biāo)以及各個(gè)聚類中心的物資總量進(jìn)行數(shù)據(jù)處理。

（2）計(jì)算各站點(diǎn)間距離，得到各聚類中心間距離作為后續(xù)計(jì)算的數(shù)據(jù)基礎(chǔ)，如表4所示。

（3）計(jì)算每兩個(gè)聚類中心的節(jié)約里程，按距離降序排列，通過判斷行駛里程是否超過60km來進(jìn)行合并或增加路徑。得到的卡車行駛路徑及各路徑具體里程數(shù)如表5所示。

3.4 確定無人機(jī)飛行路線

根據(jù)2.3.3模型，將表6配送區(qū)b1客戶點(diǎn)坐標(biāo)及其需求量的數(shù)據(jù)輸入Python中，設(shè)置初始溫度為路徑最大偏差的20倍，溫度的下降系數(shù)為0.99。分別帶入未改進(jìn)的模擬退火算法和“尾部客戶判斷法”改進(jìn)的模擬退火算法中，與配送區(qū)b1所求結(jié)果進(jìn)行對比分析，路徑示意圖分別如圖8、圖9所示，具體數(shù)據(jù)見表7。

由配送區(qū)b1無人機(jī)飛行路徑優(yōu)化實(shí)驗(yàn)對比分析可得，運(yùn)用“尾部客戶判斷法”改進(jìn)的模擬退火算法比未改進(jìn)的模擬退火算法減少了20.61 km行駛里程，優(yōu)化提升了17.82%。

接著運(yùn)用改進(jìn)后的模擬退火算法分別對配送區(qū)b2到b5進(jìn)行無人機(jī)路徑優(yōu)化，結(jié)果如圖10至圖13所示。

3.5 配送成本對比分析

運(yùn)用節(jié)約里程法計(jì)算出卡車單獨(dú)配送的總里程為478.68km，成本為798.02元，“無人機(jī)—卡車”聯(lián)合配送模式總里程為577.69km，成本為688.02元。相較于卡車單獨(dú)配送成本降低了110元，約減少了13.78%。

結(jié)果對比分析如圖14所示。

4 結(jié) 論

結(jié)合無人機(jī)短程運(yùn)送成本明顯低于卡車運(yùn)送成本，本文以總運(yùn)營成本最少為目標(biāo)函數(shù)，提出了考慮道路擁堵指數(shù)的“無人機(jī)—卡車”配送路徑優(yōu)化模型。首先基于改進(jìn)的K-means算法確定卡車配送點(diǎn)，接著基于節(jié)約里程法考慮道路擁堵指數(shù)優(yōu)化卡車的行駛路徑，然后運(yùn)用改進(jìn)的模擬退火算法對無人機(jī)單次服務(wù)可配送多個(gè)客戶點(diǎn)的路徑進(jìn)行優(yōu)化，提高了無人機(jī)的利用效率，得到了以下結(jié)論：

（1）采用改進(jìn)的K-means算法，同時(shí)考慮無人機(jī)配送的航程和容量限制，能夠快速精準(zhǔn)地確定卡車的合理配送點(diǎn)，提升配送效率。

（2）根據(jù)不同的城市擁堵情況，結(jié)合道路擁堵指數(shù)優(yōu)化卡車的行駛路徑，使之更加貼合實(shí)際的配送場景。

（3）本文采用改進(jìn)的模擬退火算法在求解過程中能夠在較少迭代次數(shù)下快速得出全局最優(yōu)解，有效降低無人機(jī)的飛行里程，降低配送成本。

后續(xù)，可進(jìn)一步將道路避障和時(shí)間窗等約束條件深度融入所述的無人機(jī)—卡車配送模型中，得到更加合理的優(yōu)化路徑。

參考文獻(xiàn)：

［1］AGGARWAL S，KUMAR N.Path planning techniques for unmanned aerial vehicles：A review，solutions，and challenges［J］.Computer Communications，2020（149）：270-299.

［2］CHUNG S，SAH B，LEE J.Optimization for drone and drone-truck combined operations：A review of the state of the art and future directions［J］.Computers amp; Operations Research，2020（104）：307-317.

［3］彭勇，黎元鈞.考慮疫情影響的卡車無人機(jī)協(xié)同配送路徑優(yōu)化［J］.中國公路學(xué)報(bào)，2020（11）：73-82.

［4］MURRAY C，CHU A.The flying sidekick traveling salesman problem：Optimization of drone-assisted parcel delivery［J］. Transportation Research Part C-emerging Technologies，2015（54）：86-109.

［5］韓明，王亞彬，丁連永，等.基于CTDEA算法的車輛+UAV配送路徑優(yōu)化［J］.兵器裝備工程學(xué)報(bào)，2019，40（11）：149-154.

［6］SAVURAN H，KARAKAYA M.Efficient route planning for an unmanned air vehicle deployed on a moving carrier［J］. Soft Computing，2016（20）：2905-2920.

［7］CHANG Y，LEE H.Optimal delivery routing with wider drone-delivery areas along a shorter truck-route［J］.Expert Systems With Applications，2018（104）：307-317.

［8］WANG X，POIKONEN S，GOLDEN B.The vehicle routing problem with drones：several worst-case results[J].Optimization Letters，2017（11）：679-697.

［9］曹英英，陳淮莉.基于集群的卡車與無人機(jī)聯(lián)合配送調(diào)度研究［J］.計(jì)算機(jī)工程與應(yīng)用，2022，58（11）：287-294.

［10］郭秀萍，胡運(yùn)霞.卡車與無人機(jī)聯(lián)合配送模式下物流調(diào)度的優(yōu)化研究［J］.工業(yè)工程與管理，2021，26（1）：1-8.

［11］孟姍姍，郭秀萍.卡車—無人機(jī)混合配送的兩階段求解方法［J］.工業(yè)工程與管理，2022，27（5）：60-68.

［12］柳伍生，李旺，周清，等.“無人機(jī)—車輛”配送路徑優(yōu)化模型與算法［J］.交通運(yùn)輸系統(tǒng)工程與信息，2021，21（6）：176-186.

［13］CARLSSON J，SONG S.Coordinated Logistics with a Truck and a Drone［J］.Management Science，2018（64）：4052-4069.

［14］AGATZ N，BOUMAN P，SCHMID M.Optimization Approaches for the Traveling Salesman Problem with Drone［J］.Transportation Science，2018（52）：965-981.

［15］楊雙鵬，郭秀萍，高嬌嬌.無接觸式“卡車+無人機(jī)”聯(lián)合配送問題研究［J］.工業(yè)工程與管理，2022，27（1）：184-194.

［16］劉梟華.地理信息系統(tǒng)工程坐標(biāo)系統(tǒng)研究［J］.測繪通報(bào)，2020（11）：158-162.

責(zé)任編校：張 靜，杜寶花

Research on Optimization of “UAV-Truck”Distribution Path

YAN Qiong，LIU Chang-chang，ZHANG Hai-jun

（Zhengzhou University of Aeronautics，Zhengzhou 450015，China）

Abstract：In order to effectively improve the “l(fā)ast mile” distribution efficiency，a joint “UAV-truck” delivery model considering road congestion index is proposed.Firstly，the truck delivery points are selected by categorizing the customer points with the improved K-means algorithm.Then the road congestion index is considered and the multi-truck delivery path is optimized based on the mileage saving method.Then the UAV flight route is determined by the improved simulated annealing algorithm.Finally，take 80 residential areas in Zhengzhou for example，compared with truck distribution alone，the distribution cost decreased by 110 yuan，or about 13.78%。The results show that the joint UAV-truck distribution model can effectively reduce the distribution cost，and the solution algorithm is efficient and more suitable for realistic distribution scenarios，which provides a theoretical reference for the distribution of materials during the new era.

Key words：UAV-Truck；path optimization；K-means algorithm；simulated annealing algorithm