配送車與無人機(jī)的農(nóng)村物流配送路徑優(yōu)化仿真

許文鑫，張 敏，2，熊國文

(1. 西南交通大學(xué)機(jī)械工程學(xué)院，四川 成都 610031；2. 軌道交通運(yùn)維技術(shù)與裝備四川省重點(diǎn)實(shí)驗(yàn)室，四川 成都 610031)

1 引言

隨著經(jīng)濟(jì)的快速發(fā)展，物流需求加快，農(nóng)村物流市場不斷擴(kuò)大，據(jù)中國物流與采購聯(lián)合會(huì)發(fā)布數(shù)據(jù)顯示，從2015年到2019年農(nóng)村業(yè)務(wù)量指數(shù)上升了589.54。許多物流企業(yè)已開始布局農(nóng)村市場，但因我國農(nóng)村物流配送區(qū)域分散、投放難度大和配送成本較高，導(dǎo)致大多數(shù)的農(nóng)村物流配送僅局限于鄉(xiāng)鎮(zhèn)甚至是縣城，處于一級配送狀態(tài)并沒有直接面向農(nóng)村客戶，因此農(nóng)村物流總體體驗(yàn)較差。近年來，隨著我國農(nóng)村物流需求量的不斷上升，農(nóng)村物流配送末端的“最后一公里”配送問題得到越來越多的關(guān)注，探索農(nóng)村物流配送模式成為降低農(nóng)村物流配送延誤率和物流成本的關(guān)鍵方向。

隨著無人機(jī)技術(shù)的不斷發(fā)展，國內(nèi)外企業(yè)紛紛將無人機(jī)投入物流領(lǐng)域，其中包括亞馬遜的“空中倉庫”、順豐公司的“三段式”空運(yùn)以及UPS的無人機(jī)+卡車模式。他們認(rèn)為通過“運(yùn)輸工具+無人機(jī)”協(xié)同配送，能夠較好解決“最后一公里”配送的難題，以達(dá)到降低配送延誤率和成本的目的。近年來，許多國內(nèi)外專家對物流無人機(jī)的運(yùn)用進(jìn)行了一系列研究，他們分別針對各個(gè)行業(yè)對無人機(jī)的配送前景和配送系統(tǒng)進(jìn)行了討論并設(shè)計(jì)出相關(guān)優(yōu)化調(diào)度方案與路徑規(guī)劃模型，同時(shí)也對無人機(jī)物流配送的成本進(jìn)行了系統(tǒng)的分析。盡管物流無人機(jī)具有速度快、成本低和環(huán)保節(jié)能等優(yōu)點(diǎn)，但是其存在電池容量有限的不足，進(jìn)而導(dǎo)致物流無人機(jī)不能長期飛行，限制了物流無人機(jī)的配送范圍。為此，相關(guān)學(xué)者提出了一種新型配送模式即“配送車+無人機(jī)模式”，如周浪提出在農(nóng)村地區(qū)利用無人機(jī)和配送車聯(lián)合進(jìn)行物流配送，物流無人機(jī)對各個(gè)需求點(diǎn)進(jìn)行多點(diǎn)配送后返回配送中心或配送車進(jìn)行充電和補(bǔ)貨操作，配送車只需服務(wù)距配送中心較近的配送點(diǎn)，極大程度的縮短了農(nóng)村物流配送的時(shí)間和距離。但由于農(nóng)村各地區(qū)地形不同以及需求量的差異，并不是所有農(nóng)村地區(qū)都能找出合適配送車停放點(diǎn)，其勢必會(huì)影響整個(gè)運(yùn)輸過程的路徑以成本。

路徑優(yōu)化問題一直是國內(nèi)外學(xué)者研究的熱點(diǎn)，許多學(xué)者對其進(jìn)行了深入研究，欒兆亮、Xing、Cailei等分別對地鐵路線、公共交通、船舶路線等不同交通方式建立模型，并應(yīng)用相關(guān)算法進(jìn)行了求解。Xu等提出了一種改進(jìn)的多目標(biāo)粒子群優(yōu)化算法對無人機(jī)的路徑進(jìn)行優(yōu)化。楊珺等設(shè)計(jì)出禁忌搜索-改進(jìn)Clarke-Wright節(jié)省的兩階段啟發(fā)式算法來求解電動(dòng)汽車物流配送系統(tǒng)的換電站選址與配送路徑優(yōu)化問題。Ying等為了控制溫泉旅游的時(shí)間和運(yùn)輸成本，提出了一種天然溫泉旅游的沿海路線規(guī)劃模型，對關(guān)鍵路線進(jìn)行規(guī)劃。雖然許多學(xué)者已經(jīng)對無人機(jī)配送進(jìn)行了一系列研究，也將路徑優(yōu)化模型運(yùn)用到基礎(chǔ)建設(shè)、物流運(yùn)輸?shù)确矫娌⒔鉀Q了相關(guān)行業(yè)的路徑規(guī)劃問題，但針對農(nóng)村物流的無人機(jī)快遞配送的研究相對較少。

本文將結(jié)合農(nóng)村的物流特征設(shè)計(jì)了一種擁有配送車暫時(shí)停放點(diǎn)的“配送車+無人機(jī)”路徑規(guī)劃模型以及相關(guān)物流配送策略，通過k-means算法對配送系統(tǒng)中的配送中心以及配送車暫時(shí)停放點(diǎn)的位置進(jìn)行確定，利用改進(jìn)遺傳算法實(shí)現(xiàn)無人機(jī)和配送車的路徑優(yōu)化，最后通過實(shí)例驗(yàn)證整個(gè)物流配送模式的可行性。物流企業(yè)可以根據(jù)實(shí)際情況來確定配送中心和配送車暫時(shí)停放點(diǎn)的位置以及配送車和無人機(jī)的路徑，使整個(gè)配送系統(tǒng)的成本最低。

2 問題描述

基于擁有配送車暫時(shí)停放點(diǎn)的“配送車+無人機(jī)”配送模型，假設(shè)配送中心擁有一架載重為30kg、續(xù)航30km的物流無人機(jī)與一輛載重500kg、續(xù)航50km的配送車，對某縣城農(nóng)村區(qū)域內(nèi)需求量不同的L個(gè)村落進(jìn)行快遞配送。整個(gè)系統(tǒng)包含兩種配送模式，第一種是物流無人機(jī)單獨(dú)進(jìn)行配送，物流無人機(jī)從鎮(zhèn)級配送中心A出發(fā)為各個(gè)村落固定接收點(diǎn)L進(jìn)行多點(diǎn)配送，配送完成后返回配送中心A補(bǔ)貨或充電(如圖1(a)所示)。但由于無人機(jī)載重能力以及續(xù)航能力的限制，并不能一次性完成所有村落的配送。因此提出第二種配送方式——配送車攜帶物流無人機(jī)進(jìn)行配送，首先配送車從鎮(zhèn)級配送中心A出發(fā)，按照規(guī)劃好的線路到達(dá)配送車暫時(shí)停放點(diǎn)T，然后無人機(jī)從配送車暫時(shí)停放點(diǎn)T出發(fā)按照規(guī)劃好的路線為各個(gè)村落固定接收點(diǎn)L進(jìn)行配送，配送完成后返回配送車暫時(shí)停放點(diǎn)T補(bǔ)貨或充電，“配送車+無人機(jī)”配送流程如圖1(b)所示。本文將針對農(nóng)村物流配送環(huán)境，對“配送車+無人機(jī)”配送系統(tǒng)進(jìn)行構(gòu)建，并設(shè)計(jì)擁有配送車暫時(shí)停放點(diǎn)的“配送車+無人機(jī)”路徑優(yōu)化模型，實(shí)現(xiàn)配送車和無人機(jī)的路徑優(yōu)化。

圖1 “配送車+無人機(jī)”配送模式

問題假設(shè)如下：

1)配送中心只有一輛配送車和一架無人機(jī)，整個(gè)鄉(xiāng)鎮(zhèn)級配送系統(tǒng)只有1個(gè)配送中心，多個(gè)配送車暫時(shí)停放點(diǎn)，多個(gè)村落固定接收點(diǎn)；

2) 每一個(gè)村落固定接收點(diǎn)只能進(jìn)行一次配送；

3)物流無人機(jī)可以為多個(gè)的村落固定接收點(diǎn)進(jìn)行配送，物流無人機(jī)只能返回其出發(fā)的配送車暫時(shí)停放點(diǎn)或者配送中心；

4)物流無人機(jī)可以從配送中心出發(fā)為村落固定接收點(diǎn)配送，也能在配送車達(dá)到某配送車暫時(shí)停放點(diǎn)后再為村落固定接收點(diǎn)配送；

5)配送車和無人機(jī)運(yùn)輸成本主要由配送距離相關(guān)的費(fèi)用構(gòu)成。

3 模型構(gòu)建

在“配送車+無人機(jī)”配送模式下，將配送系統(tǒng)的運(yùn)輸成本最低、配送的路徑總距離最短、完成所有配送任務(wù)的時(shí)間最短作為整個(gè)路徑優(yōu)化問題的目標(biāo)。配送車運(yùn)輸產(chǎn)生的相關(guān)費(fèi)用為燃料消耗成本、折舊費(fèi)用、維修費(fèi)用。無人機(jī)配送產(chǎn)生的相關(guān)費(fèi)用為無人機(jī)能耗費(fèi)用、電池維護(hù)費(fèi)用、折舊費(fèi)用、維修費(fèi)用，具體項(xiàng)目及計(jì)算方式均采用單位距離費(fèi)用*路線長度。模型參數(shù)分別代表的含義如表1所示。

表1 參數(shù)定義

針對農(nóng)村的特殊地形與村落分布情況，本文將分別對物流無人機(jī)單獨(dú)配送和配送車攜帶無人機(jī)配送兩種方式進(jìn)行建模和分析。在進(jìn)行建模計(jì)算時(shí)，首先通過運(yùn)輸方式?jīng)Q策變量l將配送點(diǎn)分為由配送車輛攜帶物流無人機(jī)進(jìn)行配送的村落固定接收點(diǎn)集合E和由物流無人機(jī)單獨(dú)進(jìn)行配送的村落固定接收點(diǎn)集合F。在整個(gè)配送過程，配送車只能從配送中心出發(fā)并且只能在配送車暫時(shí)停放點(diǎn)暫時(shí)停留，而物流無人機(jī)的出發(fā)點(diǎn)既能是配送中心也能是配送車暫時(shí)停放點(diǎn)。

E

={

i

│

l

=1，

i

∈

L

}

(1)

F

={

i

│

l

=0，

i

∈

L

}

(2)

集合H′ 表示的是通過配送車攜帶物流無人機(jī)進(jìn)行配送的物流無人機(jī)的集合：

(3)

H是從配送車暫時(shí)停點(diǎn)T出發(fā)的物流無人機(jī)集合

(4)

根據(jù)上述分析，建立擁有暫時(shí)停放點(diǎn)的“配送車+無人機(jī)”模型如下所示

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

x

=0，

i

∈

L

，?

j

，

(16)

l

=0或1，?

i

，

(17)

x

=0或1，

i

∈(

A

∪

T

)，

j

∈(

A

∪

T

)

(18)

y

=0或1，?

i

，?

j

，?

h

，

(19)

上述模型中，式(5)表示的是整個(gè)模型配送成本最小化的目標(biāo)函數(shù)。式(6)、(7)表示每個(gè)村落固定接收點(diǎn)只能由物流無人機(jī)進(jìn)行一次配送。式(8)、(9)是為了確保物流無人機(jī)配送路徑的連貫性。式(10)是為了確保配送車從配送中心出發(fā)，經(jīng)若干配送車暫時(shí)停放點(diǎn)后回到最初的配送中心。式(11)表示在物流無人機(jī)單獨(dú)進(jìn)行配送的情況下，物流無人機(jī)從配送中心站出發(fā)，經(jīng)若干村落固定接收點(diǎn)后回到出發(fā)的配送中心。式(12)表示在配送車攜帶物流無人機(jī)進(jìn)行配送時(shí)，物流無人機(jī)從配送車暫時(shí)停放點(diǎn)出發(fā)，經(jīng)若干村落固定接收點(diǎn)后回到出發(fā)的配送車暫時(shí)停放點(diǎn)。式(13)表示物流無人機(jī)的實(shí)際載重小于物流無人機(jī)的最大載重。式(14)表示配送車的實(shí)際載重小于配送車的最大載重。式(15)表示物流無人機(jī)配送路線的長度小于物流無人機(jī)的續(xù)航能力的約束。式(16)、(17)、(18)、(19)表示本模型中所有變量的取值范圍。

4 路徑優(yōu)化方法設(shè)計(jì)

基于擁有配送車暫時(shí)停放點(diǎn)的“配送車+無人機(jī)”配送模型，首先需要通過

k

-

means

算法將村落固定接收點(diǎn)分為無人機(jī)單獨(dú)配送和配送車攜帶無人機(jī)進(jìn)行配送兩種類型并對配送中心和配送車暫時(shí)停放點(diǎn)的位置進(jìn)行確定。其次，通過遺傳算法分別對配送車和無人機(jī)的配送路線進(jìn)行規(guī)劃，模型的具體流程如下圖2所示。

圖2 “配送車+無人機(jī)”路徑規(guī)劃模型步驟

由于

k

-

means

算法在解決聚類問題上簡單、快捷，處理大型數(shù)據(jù)集具有可收縮性和高效性，因此將用其確定配送中心和配送車暫時(shí)停放點(diǎn)的位置以及對村落固定接收點(diǎn)進(jìn)行分類。其中在計(jì)算對象之間的距離時(shí)選取歐式距離，

d

(，)越小二者越相似，計(jì)算公式如(20)所示。

(20)

在聚類結(jié)束后將運(yùn)用平方誤差準(zhǔn)則函數(shù)對聚類后的性能進(jìn)行評估，E表示所有對象的平方誤差和。計(jì)算公式如(21)所示。

(21)

其中簇中心的計(jì)算公式如(22)所示。

(22)

關(guān)于農(nóng)村“配送車+無人機(jī)”路徑規(guī)劃問題，本文將運(yùn)用遺傳算法對配送車與無人機(jī)的路徑進(jìn)行求解。它的具體步驟有交叉、變異、進(jìn)化、分裂一系列操作。其中變異操作是隨機(jī)選取兩點(diǎn)對換其位置，通過產(chǎn)生隨機(jī)的兩個(gè)數(shù)，如m=4，m=7，將其對換，具體過程如下圖3所示。

圖3 變異操作

交叉操作采用部分映射的方式來進(jìn)行，將父代分成A、B兩組，每一組重復(fù)以下過程：產(chǎn)生兩個(gè)隨機(jī)數(shù)m=4，m=7，對兩個(gè)位置中間的部分進(jìn)行交叉，交叉后有沖突的位置采用部分映射的方式進(jìn)行消除，其過程如下圖4所示。

圖4 交叉操作

分裂操作是為了使無人機(jī)與配送車的路徑更貼合現(xiàn)實(shí)，通過分裂無人機(jī)和配送車能夠從固定點(diǎn)出發(fā)返回固定點(diǎn)并在貨物配送完后返回對應(yīng)的地點(diǎn)進(jìn)行補(bǔ)給，如在m=4，m=7時(shí)進(jìn)行補(bǔ)給，具體步驟如下：首先從初始種群提取路徑數(shù)據(jù)，然后通過計(jì)算確定代插入的村落固定接收點(diǎn)插入返回點(diǎn)形成新的種群。過程如下圖所示，圖5中1為返回點(diǎn)。

圖5 分裂操作

5 實(shí)際算例分析

以四川省某鄉(xiāng)鎮(zhèn)為例，對農(nóng)村“配送車+無人機(jī)”配送問題的實(shí)際情況進(jìn)行分析，并在收集的數(shù)據(jù)基礎(chǔ)上進(jìn)行路徑規(guī)劃的應(yīng)用。本文選取的鄉(xiāng)鎮(zhèn)共有12個(gè)村落，地形多為山地丘陵地帶，將其作為研究對象具有一定的代表性。為了方便計(jì)算，下面將以北緯32°10′26

.

89″，東經(jīng)106°18′34

.

93″ 的碾子梁作為坐標(biāo)原點(diǎn)，碾子梁以北為

Y

軸以東為

X

坐標(biāo)建立坐標(biāo)系，以下各個(gè)坐標(biāo)圖均以此為參照。為了確定配送中心和配送車暫時(shí)停放點(diǎn)的位置，分別在

k

=1、

k

=2、

k

=3、

k

=4時(shí)運(yùn)行

K

-

means

算法，求解出

k

=1時(shí)配送中心的坐標(biāo)為(7

.

3463，8

.

2584)如圖6所示，以及在

k

=4時(shí)配送車暫時(shí)停放點(diǎn)的坐標(biāo)分別為(10

.

7892，9

.

2454)、(4

.

4560，3

.

8244)、(6

.

3156，7

.

8939)、(7

.

8243，12

.

0698)如圖7所示。

圖6 配送中心求解

圖7 配送車暫時(shí)停放點(diǎn)求解

通過

Google

地圖，本文將求解出的結(jié)果與實(shí)際路線相結(jié)合，并對配送車暫時(shí)停放點(diǎn)和配送中心的位置進(jìn)行整合，將(6

.

9273，8

.

8970)確定為配送中心并取消暫時(shí)停放點(diǎn)4。配送車暫時(shí)停放點(diǎn)的分類如下表2所示。此外還計(jì)算出各個(gè)點(diǎn)之間的距離，暫時(shí)停放點(diǎn)之間配送車的公路距離如表3所示，村落固定接收點(diǎn)之間無人機(jī)的航線距離如表4所示。

表2 配送車暫時(shí)停放點(diǎn)分類

表3 配送車公路距離

表4 無人機(jī)航線距離

在整個(gè)“配送車+無人機(jī)”配送系統(tǒng)，配送車的作用是將貨物與無人機(jī)運(yùn)輸?shù)脚渌蛙嚂簳r(shí)停放點(diǎn)，無人機(jī)的作用是對分布在暫時(shí)停放點(diǎn)周圍的小貨件物品進(jìn)行配送。下面將通過遺傳算法對配送車和無人機(jī)的路徑進(jìn)行求解。在整個(gè)過程中，假設(shè)各個(gè)配送車暫時(shí)停放點(diǎn)貨物重量分別為300kg、200kg、150kg，假設(shè)各個(gè)村落固定接收點(diǎn)貨物重量如表5所示，計(jì)算出配送車和無人機(jī)的路徑如圖8、9所示。

圖8 配送車路徑圖

從圖8可以看出配送車的路線為：1—>3—>4—>1—>2—>1，即配送中心—>配送車暫時(shí)停放點(diǎn)3—>配送車暫時(shí)停放點(diǎn)2—>配送中心—>配送車暫時(shí)停放點(diǎn)1—>配送中心，總路程為28.78km，配送總成本為22.4484元。從圖9可以看出，在整個(gè)配送過程，無人機(jī)分別從1、5、9、13這些點(diǎn)出發(fā)(其中5為配送中心其余點(diǎn)均為配送車暫時(shí)停放點(diǎn))，根據(jù)聚類的結(jié)果與求解的路徑進(jìn)行配送，最后返回對應(yīng)的配送車暫時(shí)停放點(diǎn)，具體計(jì)算結(jié)果如表6所示，無人機(jī)飛行總路程33.9623km，總成本15.9623元。

圖9 無人機(jī)路徑圖

表5 假設(shè)各村落需求量表(單位：kg)

表6 無人機(jī)路徑求解

6 結(jié)論

農(nóng)村物流配送一直是物流企業(yè)面臨的一大難題。本文通過對農(nóng)村現(xiàn)有的物流配送模式進(jìn)行分析，在傳統(tǒng)配送網(wǎng)絡(luò)的基礎(chǔ)上考慮了物流無人機(jī)的載重能力和續(xù)航能力，將無人機(jī)與配送車有效結(jié)合，提出了擁有配送車暫時(shí)停放點(diǎn)的“配送車+無人機(jī)”農(nóng)村物流配送模式，并設(shè)計(jì)出無人機(jī)單獨(dú)配送和配送車攜帶無人機(jī)進(jìn)行配送兩種模式，能夠有效解決農(nóng)村“最后一公里”配送難題。在整個(gè)路徑規(guī)劃模型中，首先通過k-means算法分別對配送車暫時(shí)停放點(diǎn)和配送中心的位置進(jìn)行確定并將村落固定接收點(diǎn)進(jìn)行分類處理；然后通過遺傳算法分別對配送車的路徑以及物流無人機(jī)的路徑進(jìn)行規(guī)劃，使整個(gè)系統(tǒng)的成本最低；最后通過實(shí)際算例驗(yàn)證了本模型的可行性。本文的物流模型并沒有考慮無人機(jī)在飛行過程中的風(fēng)速影響，以及惡劣天氣的應(yīng)急處理方式，為使整個(gè)配送模式在應(yīng)用中更加具有實(shí)際意義，在今后的研究中會(huì)考慮風(fēng)速等自然條件的影響，設(shè)計(jì)出更加符合實(shí)際的配送模式。