柳伍生，李旺，周清，迭纖

（長沙理工大學(xué)，交通運(yùn)輸工程學(xué)院，長沙 410114）

0 引言

近年來，電子商務(wù)蓬勃發(fā)展，一些特殊地區(qū)，例如，農(nóng)村地區(qū)、山地城市區(qū)域等因?yàn)榈匦苇h(huán)境復(fù)雜、交通條件差等原因，物流配送經(jīng)常受到山水相阻。民用無人機(jī)的興起，為此類問題提供了新的解決方案[1]。民用無人機(jī)憑借操作方便、使用靈活、作業(yè)效率高、相對(duì)成本低等優(yōu)勢(shì)[2]發(fā)展迅速，傳統(tǒng)的配送車輛則有著載重量大，可長距離運(yùn)輸?shù)膬?yōu)勢(shì)，兩者相結(jié)合的物流配送方式已成為國內(nèi)外的研究熱點(diǎn)。

由于無人機(jī)和車輛各自配送存在諸多限制，兩者的結(jié)合，需要互相協(xié)作，這有別于有容量限制車輛路徑問題CVRP(Capacitated Vehicle Routing Problem)和多車型車輛路徑問題MTVRP(Multitypes Vehicle Routine Problem)，屬于兼具兩者特點(diǎn)的聯(lián)合配送問題。

對(duì)于此類特殊的路徑問題，研究者在進(jìn)行模型設(shè)計(jì)時(shí)，出發(fā)點(diǎn)分為兩類。一類是從TSP 出發(fā)，例如，MURRAY 等[3]提出的FSTSP(Flying Sidekick Traveling Salesman Problem)和PDSTSP(Parallel Drone Scheduling Traveling Salesman Problem)；AGATZ 等[4]提出的TSP- D(Traveling Salesman Problem with Drone)等。隨后，在此基礎(chǔ)上，YUREK 等[5]設(shè)計(jì)了求解FSTSP 的兩階段迭代算法，KITJACHAROENCHAI 等[6]改編了FSTSP，并將問題與其他場(chǎng)景進(jìn)行對(duì)比；H. AM[7]擴(kuò)展了PDSTSP，考慮到無人機(jī)能同時(shí)在倉庫或顧客點(diǎn)進(jìn)行取貨或送貨；文獻(xiàn)[8]構(gòu)造TSP-D 的混合整數(shù)模型，使其適宜解決更大規(guī)模的問題。這些研究通常假設(shè)車輛需要在固定點(diǎn)發(fā)射和回收無人機(jī)，無人機(jī)一次僅能配送一個(gè)客戶點(diǎn)。

另一類是從VRP 出發(fā)，例如，WANG 等[9]提出了VRP-D(Vehicle Routing Problem with Drone)，考慮到續(xù)航能力的限制，無人機(jī)可以從倉庫或任意客戶地點(diǎn)的車輛上進(jìn)行發(fā)射和接收；D.ORLING[10]考慮到無人機(jī)的飛行距離和載重的關(guān)系，驗(yàn)證了VRP-D 問題中無人機(jī)的能量消耗和載重呈線性關(guān)系。SCHERME等[11]為有效求解VRP-D問題，基于混合整數(shù)線性規(guī)劃，尋找最優(yōu)的無人機(jī)分配和調(diào)度方案。上述研究都是先確定車輛的行駛路徑，再分配無人機(jī)的飛行路線，而無人機(jī)相較于車輛運(yùn)輸更加低碳環(huán)保，且成本更低，無人機(jī)應(yīng)承擔(dān)更多配送任務(wù)，實(shí)現(xiàn)高效配送。

以往研究通常以時(shí)間或成本最小為目標(biāo)，而無人機(jī)飛行速度快，車輛配送中加入無人機(jī)，相當(dāng)于增加了更快速的配送工具，總配送時(shí)間應(yīng)低于傳統(tǒng)配送[3,5]；在成本上，RAFFAELLO等[2]驗(yàn)證了無人機(jī)單位配送成本低于傳統(tǒng)配送。隨著近年來技術(shù)的發(fā)展，出現(xiàn)了更多不同規(guī)格的配送無人機(jī)，需要考慮的成本計(jì)算也更加復(fù)雜，其全過程成本包括：采購、運(yùn)營、人力、燃料、維修等，以及地區(qū)間和不同環(huán)境下的成本差異，但目前還未有明確的商用無人機(jī)規(guī)范要求，同時(shí)，考慮到安全問題，需要配備自動(dòng)檢測(cè)和避障功能，會(huì)增加成本，更詳細(xì)的成本計(jì)算有待相關(guān)法規(guī)的完善。

本文基于農(nóng)村地區(qū)的聯(lián)合配送，考慮了無人機(jī)載重量和飛行距離限制，提出車輛不用在固定點(diǎn)等待無人機(jī)，無人機(jī)單次可以服務(wù)多個(gè)顧客節(jié)點(diǎn)，并構(gòu)建了一種雙層規(guī)劃模型，通過修改部分參數(shù)，模型能同時(shí)適用于多種場(chǎng)景；基于掃描法的思想，設(shè)計(jì)了一種帶末端優(yōu)化的模擬退火算法求解模型，并對(duì)考慮的無人機(jī)限制因素進(jìn)行靈敏度分析，以提高滿載率和續(xù)航利用率，充分利用無人機(jī)的配送能力。

1 數(shù)學(xué)模型

1.1 問題描述

對(duì)于特殊地形區(qū)域，例如，農(nóng)村地區(qū)、山地城市等，因道路彎曲、坡度大、高低起伏等原因，傳統(tǒng)車輛配送十分不便，在部分農(nóng)田和池塘環(huán)繞無路駛?cè)氲牡貐^(qū)，車輛根本無法進(jìn)行配送，而無人機(jī)配送能無視地面環(huán)境，極大的縮短配送距離，且在山水相阻車輛不能進(jìn)入的農(nóng)村地區(qū)，為實(shí)現(xiàn)“最后一公里”配送，無人機(jī)有著極大的優(yōu)勢(shì)。

聯(lián)合配送一般指無人機(jī)需從車輛上進(jìn)行取貨，送貨結(jié)束后需返回車輛，車輛可攜帶無人機(jī)進(jìn)行配送，也可在無人機(jī)取貨后同步進(jìn)行其他顧客點(diǎn)的配送，兩者依據(jù)顧客點(diǎn)的具體特征，協(xié)作完成所有顧客點(diǎn)的配送；相對(duì)的獨(dú)立配送，即非聯(lián)合配送，車輛和無人機(jī)無協(xié)作，獨(dú)立完成各自的配送任務(wù)。本文設(shè)計(jì)的兩種單無人機(jī)、單車輛配送的簡易模式如圖1所示。

圖1(a)中無人機(jī)和車輛可分別運(yùn)載貨物離開配送中心，也可由車輛攜帶無人機(jī)一起回到配送中心；車輛在無人機(jī)進(jìn)行配送時(shí)，不用原地停留等待，也可同步進(jìn)行顧客點(diǎn)的配送，無人機(jī)單次配送可以同時(shí)服務(wù)多個(gè)顧客點(diǎn)。圖1(b)中無人機(jī)和車輛分別獨(dú)立進(jìn)行配送，中途無交互協(xié)作，無人機(jī)在一定的限制范圍內(nèi)，可以服務(wù)多個(gè)客戶點(diǎn)，但每次配送結(jié)束必須返回配送中心，車輛負(fù)責(zé)其余節(jié)點(diǎn)的配送。圖1中標(biāo)記了超過無人機(jī)最大飛行距離的超遠(yuǎn)點(diǎn)和超過無人機(jī)最大載重量的超重點(diǎn)，超遠(yuǎn)顧客點(diǎn)因無人機(jī)無法長距離往返，僅可由車輛完成配送；超重顧客點(diǎn)因無人機(jī)無法負(fù)載貨物，也僅可由車輛完成配送，但聯(lián)合配送中無人機(jī)可在超重點(diǎn)進(jìn)行發(fā)射或者接收。

圖1 無人機(jī)-車輛配送簡易圖Fig.1 A simplified diagram of drone-vehicle distribution

基于上述問題，本文做如下假設(shè)：

(1)配送中心和顧客點(diǎn)的位置和需求量已知，且配送中心需求量為0；

(2)所有顧客點(diǎn)都必須得到服務(wù)，不考慮顧客點(diǎn)的時(shí)間窗限制；

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

(4)在滿足限制條件下，無人機(jī)一次可服務(wù)多個(gè)顧客點(diǎn)；

(5)不考慮車輛的載重限制和續(xù)航限制；

(6)車輛必須先于無人機(jī)到達(dá)?？奎c(diǎn)，無人機(jī)不能在?？奎c(diǎn)懸停飛行；

(7)無人機(jī)每次配送結(jié)束后，需返回車輛取貨，并進(jìn)行電池更換；

(8)不考慮顧客點(diǎn)的服務(wù)時(shí)間和無人機(jī)的取貨、電池更換時(shí)間；

(9)車輛上攜帶足夠的無人機(jī)電源。

1.2 參數(shù)說明

模型建立過程中使用的參數(shù)如下：

S1——節(jié)點(diǎn)集合，S1={1,2,…,n,n+1} ，其中，n為顧客需求點(diǎn)數(shù)，n+1為配送中心；

S2——顧客需求點(diǎn)集合，S2={1,2,…,n} ；

S3——未服務(wù)的顧客需求點(diǎn)集合，初始S3={1,2,…,n} ；

Lm——超過無人機(jī)最大載重限制的顧客需求點(diǎn)集合；

Ld——與其他顧客點(diǎn)距離均超過無人機(jī)最大飛行距離限制的顧客需求點(diǎn)集合；

C(u)——無人機(jī)配送的顧客需求點(diǎn)集合，

——第k次配送，無人機(jī)配送的顧客需求點(diǎn)集合；

——車輛配送的顧客需求點(diǎn)集合，

——第k次配送，車輛配送的顧客需求點(diǎn)集合；

Pstart——無人機(jī)發(fā)射點(diǎn)集合；

Pend——無人機(jī)回收點(diǎn)集合；

Pnon——除無人機(jī)發(fā)射點(diǎn)和回收點(diǎn)外，非?？奎c(diǎn)集合；

K——配送總次數(shù)，K={1,2,…,k} ；

n——顧客需求點(diǎn)總數(shù)；

——第k次配送，無人機(jī)配送的顧客需求點(diǎn)數(shù)；

——第k次配送，車輛配送的顧客需求點(diǎn)數(shù)

mi——節(jié)點(diǎn)i的貨物需求量；

dij——節(jié)點(diǎn)i到節(jié)點(diǎn)j的歐式距離；

M——無人機(jī)的最大載重量；

D——無人機(jī)的最大飛行距離；

v(u)——無人機(jī)的平均飛行速度；

v(t)——車輛的平均行駛速度；

ε——道路阻抗系數(shù)；

Zk(u)——第k次配送，無人機(jī)配送的路徑距離之和；

Zk(t)——第k次配送，車輛配送的路徑距離之和；

Z——配送完所有節(jié)點(diǎn)的路徑距離總和；

1.3 模型建立

車輛路徑問題研究，較多結(jié)合節(jié)約法和聚類分析，但這兩種方法不能很好地拓展到多車型間需要?jiǎng)討B(tài)合作，且有載重限制的問題。為使無人機(jī)單次可服務(wù)多個(gè)節(jié)點(diǎn)，本文基于掃描法的思想，以總配送距離最小為目標(biāo)，按以下步驟求解。

Step 1 標(biāo)記特殊點(diǎn)。

對(duì)于所有顧客需求點(diǎn)，車輛均可以進(jìn)行配送。由于無人機(jī)單次飛行有最大載重限制和最大飛行距離限制，因此，將所有顧客需求點(diǎn)中超過無人機(jī)最大載重限制的節(jié)點(diǎn)標(biāo)記為Lm；超過無人機(jī)最大飛行距離限制的節(jié)點(diǎn)標(biāo)記為Ld。所有標(biāo)記點(diǎn)僅能由車輛完成配送，但標(biāo)記為Lm的節(jié)點(diǎn)在滿足無人機(jī)飛行距離限制的條件下，可作為無人機(jī)單次到達(dá)的終點(diǎn)。

式(1)和式(2)保證標(biāo)記點(diǎn)必定被車輛配送；式(3)和式(4)表示標(biāo)記為Ld的顧客點(diǎn)不會(huì)被無人機(jī)配送；式(5)確保若無人機(jī)飛往超重點(diǎn)，車輛必前往超重點(diǎn)；式(6)和式(7)表示無人機(jī)和車輛可分別從配送中心獨(dú)自進(jìn)出，也可由車輛攜帶無人機(jī)共同進(jìn)出；式(8)表示車輛每次配送至少服務(wù)一個(gè)顧客點(diǎn)。

Step 2 單次路徑規(guī)劃。

因無人機(jī)的電量限制，在無人機(jī)最遠(yuǎn)可達(dá)的飛行距離半徑內(nèi)，且滿足無人機(jī)最大載重限制的條件下，盡可能多的給無人機(jī)分配顧客需求點(diǎn)，以提高無人機(jī)的滿載率和續(xù)航利用率。對(duì)于給定飛行半徑內(nèi)，無人機(jī)單次配送最多可服務(wù)的顧客點(diǎn)是有限的，每次分配完成后記錄下單次到達(dá)的終點(diǎn)。無人機(jī)配送一次后需要補(bǔ)充電量，為安全考慮，不能在?？奎c(diǎn)做懸停等待，所以，車輛必須在無人機(jī)到達(dá)之前到達(dá)。以無人機(jī)單次路徑規(guī)劃記錄的終點(diǎn)為車輛此次配送的終點(diǎn)，在滿足提前到達(dá)的前提下，盡可能多的給車輛分配顧客需求點(diǎn)。因配送時(shí)間限制，車輛單次配送最多可服務(wù)的顧客點(diǎn)是有限的。

式(9)是最大化單次無人機(jī)和車輛服務(wù)的顧客節(jié)點(diǎn)數(shù)；式(10)保證單次無人機(jī)攜帶的貨物重量不超過無人機(jī)最大載重量；式(11)保證單次無人機(jī)配送總距離不超過無人機(jī)最大飛行距離；式(12)和式(13)表示在所有未被服務(wù)的顧客節(jié)點(diǎn)中，無人機(jī)進(jìn)出該節(jié)點(diǎn)不超過1 次；式(14)保證車輛必定在無人機(jī)降落前到達(dá)；式(15)和式(16)表示在所有未被服務(wù)的顧客節(jié)點(diǎn)中，車輛進(jìn)出該節(jié)點(diǎn)不超過1 次；式(17)保證每次分配完單次服務(wù)的顧客節(jié)點(diǎn)后，將其從前1次未服務(wù)顧客節(jié)點(diǎn)集合中除去。

Step 3 整體路徑優(yōu)化。

以單次配送路徑記錄的終點(diǎn)為下次配送路徑的起點(diǎn)，重復(fù)Step 2，直到所有顧客需求點(diǎn)全部配送完畢。將車輛和無人機(jī)的配送距離相加，以總配送距離最短為目標(biāo)函數(shù)，優(yōu)化每次配送的路徑選擇。

目標(biāo)函數(shù)式(18)為最小化無人機(jī)和車輛的總配送距離；式(19)和式(20)表示所有非停靠的顧客節(jié)點(diǎn)僅被無人機(jī)或車輛配送一次；式(21)和式(22)表示無人機(jī)收發(fā)節(jié)點(diǎn)車輛僅進(jìn)出一次；式(23)表示無人機(jī)發(fā)射節(jié)點(diǎn)無人機(jī)僅飛出一次；式(24)表示無人機(jī)回收節(jié)點(diǎn)無人機(jī)僅降落一次；式(25)和式(26)保證所有節(jié)點(diǎn)全部分配完畢，無人機(jī)的發(fā)射和回收點(diǎn)可為同一節(jié)點(diǎn)；式(27)保證無人機(jī)對(duì)于非?？奎c(diǎn)出入流量守恒；式(28)確保車輛對(duì)于所有節(jié)點(diǎn)出入流量守恒；式(29)和式(30)給出了參數(shù)的取值范圍。式(6)、式(7)、式(21)～式(24)共同給出了當(dāng)配送中心作為無人機(jī)收發(fā)點(diǎn)或非?？奎c(diǎn)時(shí)的進(jìn)出規(guī)則，無人機(jī)可從配送中心發(fā)射回收，也可由車輛攜帶進(jìn)出，中途無人機(jī)和車輛均不會(huì)再次訪問配送中心。

2 方法

由于設(shè)計(jì)的聯(lián)合配送模型屬于NP-hard 問題，問題會(huì)隨節(jié)點(diǎn)的增多而成指數(shù)級(jí)增長，當(dāng)節(jié)點(diǎn)超過10 個(gè)時(shí)，使用精確算法需要花費(fèi)大量時(shí)間，還無法求解出結(jié)果，而啟發(fā)式算法能在較短時(shí)間內(nèi)求解出很好的結(jié)果。所以本文針對(duì)聯(lián)合配送案例特征，采用啟發(fā)式算法求解問題。

2.1 求解算法

模擬退火算法通過設(shè)置不同的控制參數(shù)，能有效求解本文所提問題。

(1)控制參數(shù)的設(shè)置

通過設(shè)置不同的控制參數(shù)，可以控制模型的降溫速率，更好地逼近全局最優(yōu)解。需要設(shè)置的主要控制參數(shù)：降溫速率q=0.9；鏈長L=2000；初始溫度Tstart=1000；結(jié)束溫度Tend=0.001。

(2)初始解的生成和編碼

采用整數(shù)排列的編碼方法，隨機(jī)生成由1～n個(gè)整數(shù)構(gòu)成的初始解，每個(gè)整數(shù)對(duì)應(yīng)1～n個(gè)顧客需求點(diǎn)，配送中心為n+1。初始解可劃分為幾個(gè)不同的部分，每個(gè)部分，即不同配送趟次的無人機(jī)和車輛路徑集合。各數(shù)字的排列順序決定對(duì)應(yīng)節(jié)點(diǎn)的配送順序，從配送中心開始，按排列順序依次將各節(jié)點(diǎn)加入到無人機(jī)和車輛的配送路徑，每加入1個(gè)節(jié)點(diǎn)，計(jì)算是否滿足約束條件，未超出條件，則繼續(xù)加入下1 個(gè)節(jié)點(diǎn)，直到超出約束范圍，進(jìn)入下一趟次的顧客點(diǎn)分配。重復(fù)分配k次，得到所有趟次的配送路徑，每趟次配送路徑的順序結(jié)合，即總的配送路徑。結(jié)合式(9)～式(17)，單次路徑規(guī)劃的偽代碼如算法1所示。

(3)解的變換

通過對(duì)當(dāng)前解進(jìn)行變換，生成新的路徑組合，更新當(dāng)前解。本文主要采用交換規(guī)則有單點(diǎn)交叉和2-opt 變換。單點(diǎn)交叉即隨機(jī)產(chǎn)生[1,n]區(qū)間內(nèi)的兩個(gè)整數(shù)，將當(dāng)前解中兩個(gè)整數(shù)對(duì)應(yīng)位置的節(jié)點(diǎn)進(jìn)行對(duì)換。2-opt 即隨機(jī)產(chǎn)生[1,n]區(qū)間內(nèi)的兩個(gè)整數(shù)，將當(dāng)前解中兩個(gè)整數(shù)對(duì)應(yīng)位置中間部分的節(jié)點(diǎn)進(jìn)行轉(zhuǎn)置。以1～10 為例，假設(shè)隨機(jī)產(chǎn)生的兩個(gè)整數(shù)為4 和7，單點(diǎn)交叉和2-opt 的交換示意如圖2所示。

圖2 交換規(guī)則示意Fig.2 Schematic diagram of exchange rules

(4)Metropolis準(zhǔn)則

對(duì)于目標(biāo)函數(shù)Z，假設(shè)當(dāng)前解a1的路徑長度為Z（a1），新解a2的路徑長度為Z（a2），路徑差Z′的計(jì)算式為

Metropolis準(zhǔn)則為

如果Z′＜0，則以概率1 接受新的路徑；否則，以概率exp(-Z′T)接受新的路徑。

(5)單次路徑末端優(yōu)化

以總配送路徑距離最小為目標(biāo)函數(shù)，考慮到車輛不用在原地等待無人機(jī)返回，可以對(duì)部分聯(lián)合配送路徑進(jìn)行末端優(yōu)化。

為減少不必要的回路，結(jié)合式(33)，當(dāng)無人機(jī)負(fù)責(zé)配送1個(gè)及以上節(jié)點(diǎn)，而車輛僅配送1個(gè)節(jié)點(diǎn)(此節(jié)點(diǎn)為無人機(jī)回收節(jié)點(diǎn)，可包括配送中心)，其2 種路徑方案如圖3所示。為使路徑距離最小，無人機(jī)單次路徑距離計(jì)算如式(34)所示，車輛單次路徑距離計(jì)算如式(35)所示。當(dāng)(Zk(u)+Zk(t))≤εZk(u)時(shí)，采用如圖3(a)所示方案；當(dāng)(Zk(u)+Zk(t))＞εZk(u)時(shí)，采用如圖3(b)所示方案。

圖3 末端配送路徑方案Fig.3 Terminal distribution route scheme

算法1：單次路徑規(guī)劃1 Input：S3={1,2,…,n} ,Ld,dij,mi,M,D 2 Output：C(k u),C(k t)3 temp_C(k t )←?,temp_C(k u )←?,m ←0,Zk( u )←0,Zk( t)←0;4 for i,j ∈S3 do 5Pstart ←Pstart ?{i};6if i,j ∈Ld then 7 continue;89 else在集合S3 中尋找Zk( u )+dij ≤D;10m ←m+mi;11Zk( u )←Zk( u )+dij;12temp_C(k u )←temp_C(k u )?{i};13temp_n(k u)←temp_n(k u)+1;14if mj ≥M or constraint Zk( u )+dj,j+1 ≥D then 15Pend ←Pend ?{j};16break;17else i ←j;18j ←j+1;19 for l ∈(S3-temp_C(k u))do 20temp_C(k t )←temp_C(k t )?Pstart ?Pend;22 12起Zk( t點(diǎn))←和Z終k( t)點(diǎn)+d已t_st確art,l定+d的l,t_eTnd S;P路徑尋優(yōu)23temp_C(k t )←temp_C(k t )?{l} ;22 45 tief mvpε(t_ )Zn(kk( t t))←≤v t1e(u m )Zpk(_ u)nt(k th)+e n 1;26break;22 78重if復(fù)tem遍p歷_n所(k u)+有te的m節(jié)p_點(diǎn)n(k t)n≥;n(k u)+n(k t)then 29C(k u)←temp_C(k u);30C(k t )←temp_C(k t );31 S3 ←S3-C(k u)-C(k t);32 return C(k u ),C(k t );

偽代碼如算法2所示。

(6)降溫

利用降溫速率q按照

進(jìn)行降溫，若當(dāng)前溫度T小于結(jié)束溫度，則停止迭代，并輸出當(dāng)前最優(yōu)解的結(jié)果；否則，繼續(xù)迭代。

2.2 場(chǎng)景設(shè)計(jì)

為驗(yàn)證所提出路徑優(yōu)化模型的有效性，設(shè)計(jì)了車輛單獨(dú)配送、無人機(jī)-車輛獨(dú)立配送和無人機(jī)-車輛聯(lián)合配送3種場(chǎng)景，并結(jié)合模擬退火算法(SA)和末端優(yōu)化對(duì)設(shè)計(jì)的場(chǎng)景進(jìn)行求解。

(1)場(chǎng)景1 車輛單獨(dú)配送

即傳統(tǒng)配送問題(SA+TSP)，車輛無載重和續(xù)航能力限制，考慮道路阻抗的影響，車輛從配送中心出發(fā)，完成所有顧客需求點(diǎn)的配送后，再返回配送中心。

為使模型能求解此問題，設(shè)置無人機(jī)最大載重量M=0，或無人機(jī)最大飛行距離D=0，限制無人機(jī)的配送，本文所設(shè)計(jì)的聯(lián)合配送模型即轉(zhuǎn)變?yōu)檐囕v單獨(dú)配送模型。

(2)場(chǎng)景2 無人機(jī)-車輛獨(dú)立配送

即帶容量限制的多車型路徑問題(SA+CVRP+MTVRP)，獨(dú)立配送為非聯(lián)合配送，屬于PDSTSP的變種問題，車輛和無人機(jī)負(fù)責(zé)各自的顧客點(diǎn)，沒有協(xié)作，無人機(jī)單次配送需返回配送中心進(jìn)行取貨和更換電源。

為使模型能求解此問題，將無人機(jī)的發(fā)射和接收點(diǎn)設(shè)置為Pstart=Pend=n+1，無人機(jī)收發(fā)操作固定在配送中心進(jìn)行，除式(14)、式(23)和式(24)，車輛不必等待無人機(jī)，無人機(jī)出入配送中心不受次數(shù)限制，結(jié)合其余公式，本文所設(shè)計(jì)的聯(lián)合配送模型即轉(zhuǎn)變?yōu)闊o人機(jī)-車輛獨(dú)立配送模型。

(3)場(chǎng)景3 無人機(jī)-車輛聯(lián)合配送

即本文所提的路徑優(yōu)化問題(SA+VRP-D)，無人機(jī)和車輛需要密切合作，共同完成所有顧客點(diǎn)的配送任務(wù)。

3 算例分析

為求解本文設(shè)計(jì)的路徑優(yōu)化模型，使用MATLAB R2019a 編程，在一臺(tái)處理器為Intel(R)Core(TM)i7-8550U、8 G內(nèi)存，操作系統(tǒng)為Win10 64位的計(jì)算機(jī)上運(yùn)行。模型各參數(shù)設(shè)置如表1所示。

表1 模型參數(shù)Table 1 Model parameters

3.1 案例仿真

考慮到農(nóng)村地區(qū)的位置特點(diǎn)，依據(jù)Solomon實(shí)例數(shù)據(jù)集中RC208 的數(shù)據(jù)，在50 km×50 km 的空間范圍內(nèi)，隨機(jī)生成包含35個(gè)節(jié)點(diǎn)的仿真案例，修改部分顧客需求點(diǎn)的貨物需求量，加入2個(gè)超重點(diǎn)和2個(gè)超遠(yuǎn)點(diǎn)，各節(jié)點(diǎn)的具體數(shù)據(jù)如表2所示。

表2 節(jié)點(diǎn)數(shù)據(jù)Table 2 Node data

以路徑距離最小為目標(biāo)，輸入數(shù)據(jù)參數(shù)，求解上述3個(gè)場(chǎng)景，統(tǒng)計(jì)運(yùn)算結(jié)果。不同場(chǎng)景下的配送結(jié)果如圖4所示。

車輛單獨(dú)配送的結(jié)果如圖4(a)所示，車輛從配送中心出發(fā)，順次完成所有顧客需求點(diǎn)的配送后返回配送中心；無人機(jī)-車輛獨(dú)立配送的結(jié)果如圖4(b)所示，無人機(jī)單次能服務(wù)多個(gè)顧客需求，但受無人機(jī)最大飛行距離限制，而農(nóng)村節(jié)點(diǎn)較為分散，且離配送中心相距很遠(yuǎn)，無人機(jī)僅服務(wù)了4個(gè)顧客需求點(diǎn)，其余節(jié)點(diǎn)由車輛負(fù)責(zé)配送；無人機(jī)-車輛聯(lián)合配送的配送結(jié)果如圖4(c)所示，車輛和無人機(jī)分別從配送中心出發(fā)，無人機(jī)同樣服務(wù)多個(gè)顧客需求點(diǎn)，超重點(diǎn)和超遠(yuǎn)點(diǎn)僅能由車輛進(jìn)行配送，但超重點(diǎn)可以作為車輛配送的中間節(jié)點(diǎn)，也能作為無人機(jī)飛行的收、發(fā)節(jié)點(diǎn)，無人機(jī)和車輛相互協(xié)作，服務(wù)所有顧客需求點(diǎn)后共同回到配送中心。

圖4 不同場(chǎng)景下的配送結(jié)果Fig.4 Delivery results in different scenarios

對(duì)每個(gè)場(chǎng)景獨(dú)立運(yùn)行程序30 次，每次的運(yùn)行結(jié)果如圖5所示。不同場(chǎng)景下的統(tǒng)計(jì)結(jié)果，以及場(chǎng)景3相對(duì)其他場(chǎng)景的變動(dòng)比例如表3所示。

圖5 不同場(chǎng)景的運(yùn)行結(jié)果Fig.5 Diagram of running results of different scenarios

表3中，場(chǎng)景3 的最小值在所有場(chǎng)景中結(jié)果最小，相對(duì)場(chǎng)景1下降2.81%，相對(duì)場(chǎng)景2下降1.91%，場(chǎng)景2的最小值結(jié)果也小于場(chǎng)景1。說明無人機(jī)和車輛的獨(dú)立配送和聯(lián)合配送均優(yōu)于車輛單獨(dú)配送，無人機(jī)的加入，可以減少總的配送距離，證明了本文設(shè)計(jì)模型的可行性，3 種場(chǎng)景均可以視為設(shè)計(jì)模型在不同參數(shù)下的特例。此外，場(chǎng)景2、場(chǎng)景3的最大值均大于場(chǎng)景1，場(chǎng)景1的仿真結(jié)果差距最小。

表3 不同場(chǎng)景下的結(jié)果及變動(dòng)比例Table 3 Results and change ratios in different scenarios

由圖5中可知，場(chǎng)景1中30次的運(yùn)行結(jié)果波動(dòng)幅度最平緩，另外2 種場(chǎng)景的波動(dòng)幅度較大，特別是場(chǎng)景2，由于無人機(jī)的發(fā)射和接收點(diǎn)均限制為配送中心，且受最大載重量和最大飛行距離限制，無人機(jī)能服務(wù)的顧客點(diǎn)十分有限，部分單一節(jié)點(diǎn)分配給無人機(jī)進(jìn)行配送后，導(dǎo)致總配送距離增大。在3種場(chǎng)景中，場(chǎng)景3 的結(jié)果均值依然最小，無人機(jī)和車輛的聯(lián)合配送有著更大優(yōu)勢(shì)，合理分配無人機(jī)和車輛的配送路徑，兩者相互協(xié)調(diào)，可以更高效地完成所有節(jié)點(diǎn)的配送任務(wù)。

3.2 靈敏度分析

為驗(yàn)證在不同載重和飛行距離限制下，無人機(jī)是否能很好地完成農(nóng)村地區(qū)的物流配送任務(wù)，使用表2的顧客點(diǎn)數(shù)據(jù)，對(duì)無人機(jī)最大載重和最大飛行距離進(jìn)行靈敏度分析，其余參數(shù)保持不變，每組結(jié)果獨(dú)立運(yùn)行20次后取最小值。保持無人機(jī)最大載重不變，不同飛行距離限制下，3種場(chǎng)景的配送結(jié)果如圖6所示。

圖6 不同最大飛行距離下配送結(jié)果Fig.6 Delivery results under different maximum flight distances

圖6中，場(chǎng)景1因?yàn)閮H使用車輛進(jìn)行配送，而車輛無配送距離限制，無人機(jī)最大飛行距離的變化，不會(huì)影響其配送結(jié)果。以場(chǎng)景1為參考，隨著無人機(jī)最大飛行距離的提高，無人機(jī)的運(yùn)載能力得到充分發(fā)揮，場(chǎng)景2的配送距離逐漸低于場(chǎng)景1，在飛行距離取20 km 時(shí)達(dá)到最低，明顯優(yōu)于其他場(chǎng)景，但繼續(xù)增大無人機(jī)的最大飛行距離，場(chǎng)景2的配送距離反而增大，因?yàn)?，此時(shí)無人機(jī)的飛行直徑已經(jīng)接近空間范圍的1/2，無人機(jī)存在遠(yuǎn)距離往返，在每次完成配送后，需要折返回配送中心，導(dǎo)致配送距離增加。而場(chǎng)景3因?yàn)橛熊囕v的支持，在較低飛行距離時(shí)，已經(jīng)能很好地發(fā)揮無人機(jī)的運(yùn)載能力，其配送結(jié)果優(yōu)于另外2個(gè)場(chǎng)景，但隨著無人機(jī)飛行距離的增加，場(chǎng)景3 的配送距離同樣在增大，這是受數(shù)據(jù)節(jié)點(diǎn)位置分散的影響，無人機(jī)在完成附近顧客點(diǎn)的配送時(shí)，還會(huì)飛往較遠(yuǎn)顧客點(diǎn)，車輛也因此增大了行駛距離。

保持無人機(jī)的最大飛行距離不變，不同載重量限制下，3種場(chǎng)景的配送結(jié)果如圖7所示。

圖7 不同最大載重量下配送結(jié)果Fig.7 Delivery results under different maximum load capacities

仍然以場(chǎng)景1 為參照，由圖7可知，場(chǎng)景2 中，無人機(jī)在較小載重量時(shí)，已優(yōu)于場(chǎng)景1，但因無人機(jī)最大飛行距離固定，無人機(jī)只能在配送中心一定范圍內(nèi)飛行，其最大載重量兩端(0 kg 和5 kg)均無法很好地利用無人機(jī)的配送能力，結(jié)果陷入局部最優(yōu)。而場(chǎng)景3 中，車輛可以攜帶無人機(jī)，無人機(jī)因此能夠前往更遠(yuǎn)的節(jié)點(diǎn)，當(dāng)周圍顧客需求點(diǎn)分布較為密集，無人機(jī)載重量越大，越能發(fā)揮其配送優(yōu)勢(shì)，減少總的配送距離。值得注意的是，當(dāng)無人機(jī)最大載重量超過4 kg 時(shí)，節(jié)點(diǎn)中已經(jīng)不存在超重點(diǎn)，在可達(dá)的情況下，無人機(jī)能配送所有節(jié)點(diǎn)，但無法同時(shí)配送超重點(diǎn)和其他節(jié)點(diǎn)，無人機(jī)的配送能力受到限制。

為進(jìn)一步了解無人機(jī)的特性，取無人機(jī)最大載重1～3 kg、最大飛行距離9～21 km，構(gòu)成25 組配送能力組合，運(yùn)算結(jié)果如表4所示。

表4中，隨著無人機(jī)配送能力的上升，無人機(jī)配送的節(jié)點(diǎn)數(shù)不斷增多，有利于發(fā)揮無人機(jī)無視路況、速度快的優(yōu)勢(shì)。而僅提升一項(xiàng)能力，雖然可以增加無人機(jī)配送節(jié)點(diǎn)，但因需要同時(shí)提高滿載率和續(xù)航利用率，總配送距離會(huì)有所上升。從配送距離在310 km以下的幾組(編號(hào)為：7、12、18、24)可以發(fā)現(xiàn)，無人機(jī)的最大載重量和飛行距離以一定比例同步提升，能更好地發(fā)揮無人機(jī)的配送能力，在配送距離上更優(yōu)。

表4 無人機(jī)不同能力組合下場(chǎng)景3配送結(jié)果Table 4 Scenario 3 delivery results under different combinations of drone capabilities

3.3 實(shí)例求解

以湖南省瀏陽市為例，隨機(jī)選取下屬5個(gè)鄉(xiāng)鎮(zhèn)范圍內(nèi)的30個(gè)節(jié)點(diǎn)，使用百度地圖標(biāo)記各點(diǎn)，無人機(jī)飛行距離取兩點(diǎn)間歐式距離，車輛行駛距離取推薦的最短車行距離。道路阻抗系數(shù)取1，假設(shè)道路情況良好，車輛可以送達(dá)所有包裹，無人機(jī)最大載重量為2 kg，最大飛行距離10 km，平均飛行速度80 km·h-1，車輛平均行駛速度50 km·h-1。節(jié)點(diǎn)位置及配送結(jié)果如圖8所示。

聯(lián)合配送相比于傳統(tǒng)配送，在配送距離上最大優(yōu)勢(shì)在于可以無視地形直線飛行，而部分農(nóng)村節(jié)點(diǎn)靠近河流、山區(qū)，離公路距離較遠(yuǎn)，車輛進(jìn)出十分不便，例如，節(jié)點(diǎn)13和節(jié)點(diǎn)16，因?yàn)楹恿髯钃?，車輛行駛需要繞行，其推薦路程(6.6 km)是直線路程(1.5 km)的4.4倍。

采用設(shè)計(jì)算法對(duì)3種場(chǎng)景進(jìn)行求解，求解結(jié)果分別為：106.69，106.99，106.09 km，其中，場(chǎng)景3 距離最短。3 種場(chǎng)景的配送距離差距并不大，主要是因?yàn)楣?jié)點(diǎn)較為分散，無人機(jī)配送受到嚴(yán)格的限制，圖8中無人機(jī)僅服務(wù)了5 個(gè)節(jié)點(diǎn)，大部分節(jié)點(diǎn)依然由車輛完成配送。在不考慮道路阻抗的情況下，無人機(jī)的距離優(yōu)勢(shì)并不明顯，但無人機(jī)所分擔(dān)的距離，可以減小車輛行駛距離，降低燃油消耗。此外，相比于單純?cè)黾訜o人機(jī)配送節(jié)點(diǎn)，設(shè)計(jì)的聯(lián)合配送可以提高無人機(jī)的能量利用率，使運(yùn)輸更節(jié)能環(huán)保。

圖8 節(jié)點(diǎn)位置及配送結(jié)果Fig.8 Node location and delivery result

4 結(jié)論

本文提出一種新的無人機(jī)-車輛聯(lián)合配送模式，以總配送距離最小為目標(biāo)，采用3 步驟路徑分配方法，優(yōu)先分配無人機(jī)的路徑。無人機(jī)單次可以服務(wù)多個(gè)顧客需求點(diǎn)，且車輛不用在固定點(diǎn)等待無人機(jī)，兩者聯(lián)合協(xié)作，共同完成配送任務(wù)。此外，設(shè)計(jì)了3 種配送場(chǎng)景，通過修改部分參數(shù)，本文模型能同時(shí)適用于3種場(chǎng)景。由于問題求解的復(fù)雜性，使用了模擬退火算法，并結(jié)合單次路徑末端優(yōu)化求解模型。

考慮到一些特殊地區(qū)需求點(diǎn)較為分散的特點(diǎn)，采用包括特殊點(diǎn)在內(nèi)的案例數(shù)據(jù)進(jìn)行分析，結(jié)果證實(shí)了模型的可行性。并對(duì)無人機(jī)的最大載重量和飛行距離進(jìn)行了敏感性分析，結(jié)果表明：單獨(dú)提升其中一項(xiàng)能力，超過一定范圍后，并不能減少總的配送距離，需要兩者協(xié)調(diào)，才能充分發(fā)揮無人機(jī)的配送能力。