配送車與無人機的農村物流配送路徑優化仿真

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

(1. 西南交通大學機械工程學院，四川 成都 610031；2. 軌道交通運維技術與裝備四川省重點實驗室，四川 成都 610031)

1 引言

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

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

路徑優化問題一直是國內外學者研究的熱點，許多學者對其進行了深入研究，欒兆亮、Xing、Cailei等分別對地鐵路線、公共交通、船舶路線等不同交通方式建立模型，并應用相關算法進行了求解。Xu等提出了一種改進的多目標粒子群優化算法對無人機的路徑進行優化。楊珺等設計出禁忌搜索-改進Clarke-Wright節省的兩階段啟發式算法來求解電動汽車物流配送系統的換電站選址與配送路徑優化問題。Ying等為了控制溫泉旅游的時間和運輸成本，提出了一種天然溫泉旅游的沿海路線規劃模型，對關鍵路線進行規劃。雖然許多學者已經對無人機配送進行了一系列研究，也將路徑優化模型運用到基礎建設、物流運輸等方面并解決了相關行業的路徑規劃問題，但針對農村物流的無人機快遞配送的研究相對較少。

本文將結合農村的物流特征設計了一種擁有配送車暫時停放點的“配送車+無人機”路徑規劃模型以及相關物流配送策略，通過k-means算法對配送系統中的配送中心以及配送車暫時停放點的位置進行確定，利用改進遺傳算法實現無人機和配送車的路徑優化，最后通過實例驗證整個物流配送模式的可行性。物流企業可以根據實際情況來確定配送中心和配送車暫時停放點的位置以及配送車和無人機的路徑，使整個配送系統的成本最低。

2 問題描述

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

圖1 “配送車+無人機”配送模式

問題假設如下：

1)配送中心只有一輛配送車和一架無人機，整個鄉鎮級配送系統只有1個配送中心，多個配送車暫時停放點，多個村落固定接收點；

2) 每一個村落固定接收點只能進行一次配送；

3)物流無人機可以為多個的村落固定接收點進行配送，物流無人機只能返回其出發的配送車暫時停放點或者配送中心；

4)物流無人機可以從配送中心出發為村落固定接收點配送，也能在配送車達到某配送車暫時停放點后再為村落固定接收點配送；

5)配送車和無人機運輸成本主要由配送距離相關的費用構成。

3 模型構建

在“配送車+無人機”配送模式下，將配送系統的運輸成本最低、配送的路徑總距離最短、完成所有配送任務的時間最短作為整個路徑優化問題的目標。配送車運輸產生的相關費用為燃料消耗成本、折舊費用、維修費用。無人機配送產生的相關費用為無人機能耗費用、電池維護費用、折舊費用、維修費用，具體項目及計算方式均采用單位距離費用*路線長度。模型參數分別代表的含義如表1所示。

表1 參數定義

針對農村的特殊地形與村落分布情況，本文將分別對物流無人機單獨配送和配送車攜帶無人機配送兩種方式進行建模和分析。在進行建模計算時，首先通過運輸方式決策變量l將配送點分為由配送車輛攜帶物流無人機進行配送的村落固定接收點集合E和由物流無人機單獨進行配送的村落固定接收點集合F。在整個配送過程，配送車只能從配送中心出發并且只能在配送車暫時停放點暫時停留，而物流無人機的出發點既能是配送中心也能是配送車暫時停放點。

E

={

i

│

l

=1，

i

∈

L

}

(1)

F

={

i

│

l

=0，

i

∈

L

}

(2)

集合H′ 表示的是通過配送車攜帶物流無人機進行配送的物流無人機的集合：

(3)

H是從配送車暫時停點T出發的物流無人機集合

(4)

根據上述分析，建立擁有暫時停放點的“配送車+無人機”模型如下所示

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

4 路徑優化方法設計

基于擁有配送車暫時停放點的“配送車+無人機”配送模型，首先需要通過

k

-

means

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

圖2 “配送車+無人機”路徑規劃模型步驟

由于

k

-

means

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

d

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

(20)

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

(21)

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

(22)

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

圖3 變異操作

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

圖4 交叉操作

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

圖5 分裂操作

5 實際算例分析

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

.

89″，東經106°18′34

.

93″ 的碾子梁作為坐標原點，碾子梁以北為

Y

軸以東為

X

坐標建立坐標系，以下各個坐標圖均以此為參照。為了確定配送中心和配送車暫時停放點的位置，分別在

k

=1、

k

=2、

k

=3、

k

=4時運行

K

-

means

算法，求解出

k

=1時配送中心的坐標為(7

.

3463，8

.

2584)如圖6所示，以及在

k

=4時配送車暫時停放點的坐標分別為(10

.

7892，9

.

2454)、(4

.

4560，3

.

8244)、(6

.

3156，7

.

8939)、(7

.

8243，12

.

0698)如圖7所示。

圖6 配送中心求解

圖7 配送車暫時停放點求解

通過

Google

地圖，本文將求解出的結果與實際路線相結合，并對配送車暫時停放點和配送中心的位置進行整合，將(6

.

9273，8

.

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

表2 配送車暫時停放點分類

表3 配送車公路距離

表4 無人機航線距離

在整個“配送車+無人機”配送系統，配送車的作用是將貨物與無人機運輸到配送車暫時停放點，無人機的作用是對分布在暫時停放點周圍的小貨件物品進行配送。下面將通過遺傳算法對配送車和無人機的路徑進行求解。在整個過程中，假設各個配送車暫時停放點貨物重量分別為300kg、200kg、150kg，假設各個村落固定接收點貨物重量如表5所示，計算出配送車和無人機的路徑如圖8、9所示。

圖8 配送車路徑圖

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

圖9 無人機路徑圖

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

表6 無人機路徑求解

6 結論

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