“無(wú)人機(jī)—卡車(chē)”配送路徑優(yōu)化研究

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

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

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

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

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

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

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

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

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

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

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

1 模型構(gòu)建

1.1 問(wèn)題描述

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

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

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

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

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

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

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

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

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

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

1.2 符號(hào)說(shuō)明

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

B：卡車(chē)配送點(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｝為無(wú)人機(jī)集合；

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

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

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

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

u：卡車(chē)編號(hào)；

L：卡車(chē)最大行駛距離；

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

S：卡車(chē)行駛總路程；

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

Fm：卡車(chē)單位距離行駛成本；

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3 模型建立

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

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

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

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

設(shè)配送中心為P，從配送中心同時(shí)向k個(gè)卡車(chē)配送點(diǎn)進(jìn)行配送服務(wù)，已知配送中心共有m輛卡車(chē)可以用于配送，求解以最短路程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）表示該配送中心共有可配送卡車(chē)數(shù)量為m時(shí)，任意一個(gè)卡車(chē)配送點(diǎn)僅能由m輛卡車(chē)中的一輛來(lái)完成。式（3）表示每條卡車(chē)配送路徑的總里程數(shù)不得超過(guò)卡車(chē)的里程限制。式（4）、式（5）為消除卡車(chē)配送點(diǎn)間的子回路。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 實(shí)例介紹

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

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

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

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

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

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

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

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

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

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

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

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

3.4 確定無(wú)人機(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)行對(duì)比分析，路徑示意圖分別如圖8、圖9所示，具體數(shù)據(jù)見(jiàn)表7。

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

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

3.5 配送成本對(duì)比分析

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

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

4 結(jié) 論

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

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

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

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

后續(xù)，可進(jìn)一步將道路避障和時(shí)間窗等約束條件深度融入所述的無(wú)人機(jī)—卡車(chē)配送模型中，得到更加合理的優(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］彭勇，黎元鈞.考慮疫情影響的卡車(chē)無(wú)人機(jī)協(xié)同配送路徑優(yōu)化［J］.中國(guó)公路學(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算法的車(chē)輛+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］曹英英，陳淮莉.基于集群的卡車(chē)與無(wú)人機(jī)聯(lián)合配送調(diào)度研究［J］.計(jì)算機(jī)工程與應(yīng)用，2022，58（11）：287-294.

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

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

［12］柳伍生，李旺，周清，等.“無(wú)人機(jī)—車(chē)輛”配送路徑優(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］楊雙鵬，郭秀萍，高嬌嬌.無(wú)接觸式“卡車(chē)+無(wú)人機(jī)”聯(lián)合配送問(wèn)題研究［J］.工業(yè)工程與管理，2022，27（1）：184-194.

［16］劉梟華.地理信息系統(tǒng)工程坐標(biāo)系統(tǒng)研究［J］.測(cè)繪通報(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