李曉輝, 李沛帆, 于振寧, 趙 毅

1(長安大學 電子與控制工程學院, 西安 710064)

2(渤海裝備華油鋼管有限公司, 滄州 062658)

通訊作者: 李沛帆, E-mail: 2019132060@chd.edu.cn

隨著我國政府推出一系列關于智能制造和“互聯(lián)網(wǎng)+”的標準化和相關產業(yè)融合政策, 對我國物流行業(yè)的發(fā)展起到了極大的促進作用.根據(jù)劉林山[1]文中所述, 2018年618全球年中購物節(jié)的時候, 電商平臺京東1天累計下單金額達到1592億元, 天貓、蘇寧易購、國美Plus、亞馬遜中國等47家電商平臺總銷售額達到2844.7億元.因此, 擁有一套完善、現(xiàn)代的物流體系是各大電商當前最迫切需要解決的問題.

此外, 我國的物流成本近年來已經(jīng)占到我國的GDP的18%, 比發(fā)達國家要高出一倍左右.其中一個重要原因在于物流的環(huán)節(jié)過多, 而其中“最后一公里的配送”占到總成本的30%以上.基于此, 本文的研究重點在于優(yōu)化“最后一公里”的配送過程以及耗費的成本.

現(xiàn)有“最后一公里配送”之所以成本較高, 主要有以下幾點原因:

(1)運輸工具問題.快遞人員送貨的交通工具, 如電動車、自行車等, 不僅送貨速度慢, 效率低下, 而且交通事故時有發(fā)生, 快遞人員易受傷, 貨物易破損.同時, 也加劇了道路的擁擠狀況.

(2)從業(yè)人員缺少.快遞行業(yè)屬于勞動密集型行業(yè),從業(yè)人員的工作強度較大, 一旦遇上如雙十一等高峰期就會出現(xiàn)爆倉現(xiàn)象.

(3)安全問題和道德問題.隨著電子商務的不斷發(fā)展, 物流信息追蹤過程中的漏洞也逐漸暴露了出來.通?？蛻粝聠魏? 對快遞的追蹤只停留在片面的地點信息上, 當出現(xiàn)丟件, 損件的情況, 難以進行責任確定.

(4)運輸難度和成本.經(jīng)濟發(fā)展較好的城市區(qū)域,往往是客戶需求大的地區(qū).然而, 發(fā)達城市的道路交通情況往往都不容樂觀, 尤其是上下班時期.與此相對的鄉(xiāng)村地區(qū), 雖然道路車輛較少, 但是客戶比較分散, 距離配送點也較遠, 道路情況也比較復雜, 對快遞人員的安全也存在一定的影響.

針對上述問題, 一些快遞公司, 如京東、亞馬遜逐漸開始嘗試使用無人機進行“最后一公里”的配件服務.使用無人機送貨具有下面的這些優(yōu)點:

(1)使用無人機, 可以不受地面交通情況的影響,還可以在一定程度上緩解地面道路的擁擠情況.同時,配件服務無人化, 對快遞從業(yè)人員的安全也是一種保障.

(2)降低配送時間.根據(jù)文獻[2], 億航智能攜手大灰狼快運公司開通了全國首條城市內無人機物流快遞航線, 可以將該線路的單程配送時間從40 min大幅縮短至8 min.

(3)物流信息便于跟蹤.由于使用無人機, 相比于傳統(tǒng)配送, 配送路線和配送單位可以明確追溯, 在一定程度上能緩解丟件等問題.

(4)在鄉(xiāng)村地區(qū)道路情況相對較差的情況, 依然可以以相對安全的方式進行物件的配送.

在無人機逐漸應用到物流的同時, 學者做了很多工作, 希望能從技術層面上提高無人機的續(xù)航能力、安全性、穩(wěn)定性以及載重能力, 這些都是無人機送貨的局限所在.在這些現(xiàn)實約束條件下, 無人機的路徑規(guī)劃方案顯得尤為重要.下面列出了一些關于無人機應用于物流配送的相關工作.

許衛(wèi)衛(wèi)等人[3]在A*算法的基礎上考慮了低空規(guī)劃區(qū)域、物理性能等內外限制, 設計了一種改進的A*算法用來快速求解路徑.其仿真實驗結果也表明此算法能夠快速規(guī)劃出危險程度小、能耗小的避障運輸路徑.任新惠等人[4]主要論述了車輛和無人機組合運行的4種模式.另外還探討了目前無人機和車輛組合路徑規(guī)劃的一些現(xiàn)實因素, 如無人機電池電量、運送包裹數(shù)量和時間窗等.常波等人[5]針對無人機的三維航跡規(guī)劃問題提出了一種基于幾何法的航跡規(guī)劃算法,研究了無人機最大過載系數(shù)、最大平飛速度、升限等性能與航跡可行性的關系, 并得出了生成最優(yōu)航跡的限定條件.楊玉等人[6]針對無人機的航跡規(guī)劃問題提出了一種融合簡化稀疏A*算法與模擬退火算法的航跡規(guī)劃方法, 其實驗結果表明相比于稀疏A*算法內存占有量少了兩個量級, 與模擬退火算法相比其所得航跡的綜合代價平均減少了35%左右.王琪等人[7]根據(jù)遺傳算法與動態(tài)的稀疏A*搜索算法各自的特點, 提出了一種新的組合優(yōu)化算法來解決不確定環(huán)境下的自適應航跡規(guī)劃, 仿真實驗結果表明該組合算法不但能生成近似最優(yōu)解而且能夠滿足在線實時應用的要求.

從這些相關文獻可以看出, 當今學者在解決無人機的路徑規(guī)劃時大多使用的是元啟發(fā)算法, 如遺傳算法等智能算法.使用這些啟發(fā)式算法可以高效的解決無人機的路徑規(guī)劃問題, 然而這些方法本身也存在一些問題, 如容易陷入局部最優(yōu)、收斂時間過長等.本文使用的自適應大鄰域搜索算法則可以通過一些優(yōu)良的鄰域搜索算子來跳出局部最優(yōu)以及保證算法能夠快速的收斂到全局最優(yōu).此外借鑒于當前學者的一些啟發(fā)式算法, 在本文中我們使用了啟發(fā)式的方法來進行鄰域搜索算子的選擇從而進一步提高了算法的搜索效率.

1 問題描述

在使用無人機進行“最后一公里”的物流配送過程中, 無人機必須從倉庫點出發(fā)并最終返回倉庫點, 所有的顧客的貨件只能被一個無人機送達且只能送達一次.另外, 由于無人機本身的載重和電量限制, 所以我們在規(guī)劃路徑的時候, 需要保證其載重量不能超過其最大載重量以及保證無人機能夠返回倉庫點.另外, 顧客通常會要求貨件在規(guī)定的時間內到達, 因此除了需要考慮路線長度還需要將因為送貨時間超過顧客的規(guī)定最晚時間導致顧客的滿意度下降所帶來的損失考慮在內.下面將給出該問題的數(shù)學模型.

C表示所有需要服務的顧客集合, 0表示倉庫點,S表示需要服務的顧客點和倉庫點的集合,A表示使用的無人機集合.Xija為0-1整數(shù)變量, 等于1時表示無人機a從點i到達點j, 其他情況則為0.Wi為第i個顧客所需貨物的重量,N為無人機的最大載重量.U(a,b)為無人機在當前載重量為b時行駛a距離所耗費的電量,Q為無人機的電池容量,Wai為無人機a在到達顧客點i時的載重量.Ti為到達顧客i的時間,sij為無人機從點i到點j所花費的時間.

目標值如式(1)所示由兩部分組成,TD表示所有路線的總長度, 第二部分中的Arrive(i)表示到達顧客點i的時間,T(i)表示顧客i所要求的最晚送達時間,β表示懲罰系數(shù).其意義為我們在最小化路線長度的同時要盡可能避免不能按時服務顧客的情況發(fā)生:

約束(2)表示所有的無人機需要從倉庫點出發(fā):

約束(3)保證了所有點的出度和入度相等:

約束(4)限制了所有的顧客點均被訪問一次且僅被訪問一次:

約束(5)保證了所配送的貨物總重量不會超過無人機的最大載重量:

約束(6)為無人機的電量約束:

約束(7)和約束(8)為時間約束:

2 算法描述

自適應大鄰域搜索(ALNS)算法是由Ropke與Pisinger[8]在2006年提出的一種元啟發(fā)式方法, 該方法在鄰域搜索算法的基礎上加入了自適應的機制, 能夠根據(jù)搜索算子的歷史表現(xiàn)來自動選擇好的鄰域搜索算子, 從而能夠增加找到更高質量解的幾率.該方法屬于鄰域搜索算法變種方法之一.在鄰域搜索方法的變種方法中, 有的算法可以只使用一種鄰域搜索算法, 如模擬退化算法, 遺傳算法等.該類算法的鄰域搜索部分僅搜索了解空間的一小部分, 找到全局最優(yōu)的概率較小,這類算法的優(yōu)勢之一可以避免陷入局部最優(yōu).而有的算法可以使用多種算子, 如變鄰域搜索算法, 該算法通過對當前解進行多個鄰域中搜索從而可以以更高的概率找到全局最優(yōu)解.但是經(jīng)典的變鄰域搜索算法在選擇搜索算子的時候過于隨機, 缺乏了一些啟發(fā)式信息的指導.自適應大鄰域搜索算法就彌補了這種不足, 該算法通過搜索算子的歷史表現(xiàn)與使用次數(shù)來選擇下一次迭代使用的算子, 通過這種啟發(fā)式的搜索可以有較大概率找到更好的解.自適應大鄰域搜索算法的步驟如算法1所示: (1) 生成初始解; (2)根據(jù)鄰域搜索算子的分數(shù), 使用輪盤賭來選擇鄰域搜索算子.然后對當前解使用該鄰域搜索算子進行改進.最后更新該鄰域搜索算子的分數(shù); (3)重復步驟(2)直到達到最大迭代次數(shù), 返回找到的最優(yōu)解并退出程序.

算法1.自適應大鄰域搜索算法輸入: 顧客的訂單信息以及無人機的相關參數(shù)輸出: 滿足約束條件下的最優(yōu)解Begin生成初始解T記錄當前最優(yōu)解S=T While 當前迭代次數(shù)小于最大迭代次數(shù):根據(jù)當前鄰域搜索算子的各自分數(shù)選擇一個鄰域搜索算子O將解T應用鄰域搜索算子O, 獲得改進解I If f(I) ＜ f(T):更新鄰域搜索算子O的分數(shù)T = I EndIf更新當前最優(yōu)解S, 將當前迭代次數(shù)加1

End返回最優(yōu)解S End

2.1 初始解的生成

本文采取了逐點選擇的方法來構造初始解.首先,我們初始化一個當前可訪問列表.然后, 我們考慮所有未被訪問過的顧客點, 如果能夠滿足如下條件就將其放入可訪問列表里面: (1)該顧客的貨件重量不超過當前無人機的最大載重量.(2)當前無人機的電量可以支持無人機從當前點出發(fā)到達該點并能夠返回倉庫點.當?shù)玫娇稍L問列表后, 我們根據(jù)列表內的顧客點距離當前點的距離來進行選擇, 即距離當前點越近的顧客被選擇的概率就越大.例如: 當前點為0, 可訪問列表為[2,5,6], 點0距離可訪問列表內各點的距離為[10,8,5], 那么我們就以其距離的倒數(shù)歸一化之后的值作為選擇該點的概率, 即得到選擇2的概率為0.24, 選擇5的概率為0.29, 選擇6的概率為0.47.然后我們將當前點更新為該步驟選擇得到的點, 并重復上述步驟, 直至所有顧客點均被服務過.需要注意的是, 如果計算得到的訪問列表為空的話, 表明當前路線已經(jīng)構造完成,那么無人機就執(zhí)行返回倉庫點的操作, 并重新從倉庫點出發(fā), 計算新的服務路線.最終獲得的初始解的形式類似于[[0,1,2,3,0], [0,4,5,6,0]], 這表明我們總共需要兩個無人機完成送貨任務, 第1個無人機從倉庫點出發(fā)依次服務顧客1,2,3并返回倉庫點, 第2個無人機從倉庫點出發(fā)依次服務顧客4,5,6并訪問倉庫點.

2.2 鄰域搜索算子

本文使用了來自文獻[4]的5種鄰域搜索算子.

(1) 2-opt.選擇一條路線的部分顧客, 逆序其訪問順序.

(2) Swap(1,1).交換兩條路線的顧客點.

(3) Shift(1,0).將一條路線的顧客點, 插入到其他路線.

(4) CrossOver.選擇兩條路線, 然后將其分為兩部分將第1條路線的前部分和第2條路線的后部分進行組合, 第2條路線的前部分和第1條路線的后部分進行組合.

(5) Exchange.選擇一條路線, 交換其中兩個顧客點的服務順序.

本文在執(zhí)行上述鄰域搜索的時候, 只選擇對當前解有改進的操作, 如果存在多個操作可以改善當前解的質量, 則只選擇其中改善程度最大的操作進行當前解的更新.

2.3 自適應鄰域算法選擇

在本文中, 每個算子的分數(shù)由兩部分組成: (1)該算子的歷史表現(xiàn); (2)該算子的使用次數(shù), 然后將這兩部分進行加權求和作為該算子的最后分數(shù).具體如式(9)所示, 其中score表示算子的最終分數(shù),history表示算子的歷史表現(xiàn),cnt表示該算子的使用次數(shù), α表示權重系數(shù).

其中, 算子的歷史表現(xiàn)更新量, 按照式(10)進行更新,f為式(1)用來計算目標值,old為當前解,new為進行鄰域搜索后的解.如果執(zhí)行該鄰域搜索后, 解的質量沒有改進, 則當前算子歷史表現(xiàn)的更新量為0即保持不變, 如果有改進的話, 則更新其歷史表現(xiàn)分數(shù).第一部分為使用該算子所導致的提升量, θ則是固定提升量.另外, 無論是否改進, 該算子的使用次數(shù)都增加1.

3 實驗驗證

本文使用的數(shù)據(jù)集來自于文獻[9]中的Solomon數(shù)據(jù)集.該數(shù)據(jù)集的顧客規(guī)模分別為25, 50, 100.數(shù)據(jù)類型分為R型, C型和RC型.R型數(shù)據(jù)表明顧客的數(shù)據(jù)分布全部為隨機生成的, C型數(shù)據(jù)意味著顧客的分布是通過聚類操作之后生成的, 即分布區(qū)域較為集中,RC類型則是混合這兩種數(shù)據(jù)分布類型的.其中RC類型分布的數(shù)據(jù)如圖1所示.

圖1 顧客分布

3.1 參數(shù)設置

根據(jù)Song等人在文獻[10]中的研究表明, 無人機的耗電量公式如式(11)所示, 其中Q為無人機最大載重,e為空載時無人機的耗電量其值為20 mAh/s,v為無人機的飛行速度其值為10單位每秒.另外所使用樣例中兩點之間的最大距離設置為1500單位, 其他點距離按照同比例縮放.無人機的最大載重量來自與具體的數(shù)據(jù)集文件所給出的數(shù)值.自適應大鄰域搜索的最大鄰域搜索次數(shù)為5, 最大迭代次數(shù)為100.α值為1,β值為0.2, γ值為0.9, θ為1.

3.2 實驗結果

圖2為該算法在樣例RC101中得到的結果, 從圖中可以看出路線之間幾乎沒有交叉的情況且把位置相近的顧客分配給同一輛無人機進行配送, 這樣可以最大程度地節(jié)省無人機資源.

圖2 配送路線

其具體數(shù)據(jù)如表1所示, Problem表示了測試的樣例名稱, Std, Mean, Best, Worst, CT分別表示的為程序運行10次的標準差, 平均值, 最好值, 最壞值以及程序的平均運行時間(s).從表1可以看出, 程序運行結果的標準差在數(shù)據(jù)規(guī)模為25和50的時候基本在0.001左右, 隨著問題規(guī)模的增加至100的時候, 標準差保持在相當小的值0.3以下, 這體現(xiàn)了本文所設計的算法不僅在小規(guī)模樣例上具有很強的穩(wěn)定性, 隨著問題規(guī)模的增加算法的穩(wěn)定性依然能夠保證.另外從表1可以看出算法在問題規(guī)模為25的運行時間為2 s左右, 問題規(guī)模為50時運行時間為10 s左右, 問題規(guī)模為100時運行時間在30-50 s之間.算法的運行時間和問題規(guī)模基本是呈線性關系的, 這說明本文提出的算法能夠在有限的時間內對大規(guī)模問題進行求解.為了進一步驗證本文設計算法的有效性, 本文設計了和GA (遺傳算法)[11], DPSO (離散粒子群算法)[12]的對比實驗, 各算法得到的目標值如表2所示, 其中加粗字體為3個算法所獲得的最好結果.根據(jù)表2中的數(shù)據(jù)可以看出本文提出的ALNS算法在總共18個樣例上均得到了最好的結果.這表明了本文提出的算法相比于經(jīng)典的遺傳算法和離散粒子群算法可以進一步地節(jié)省無人機進行物流運輸?shù)木C合代價.本文ALNS算法還具有非常強的擴展性和提升潛力比如說可以通過增加鄰域搜索算子的方式來進一步地提升所獲得的解的質量.

表1 實驗結果

表1和表2實驗結果表明, 本文與同類工作相比主要具有3點優(yōu)勢: (1)求解的效率更高, 能得到更高質量的解; (2) 具有很強的擴展性; (3)能夠應用于大規(guī)模的問題的求解.

表2 對比實驗

4 總結

本文探討了使用無人機來進行“最后一公里”的物流配送的現(xiàn)狀和實際應用價值以及設計了自適應大鄰域搜索算法成功地解決了在具體配送過程中的路徑規(guī)劃問題.首先, 我們將算法應用到經(jīng)典數(shù)據(jù)集上來驗證了我們算法的穩(wěn)定性和魯棒性.然后我們又設計了和經(jīng)典的遺傳算法以及離散粒子群算法的對比實驗證明了本文提出的算法對于該問題的求解是十分有效的.接下來, 我們將研究在更復雜的環(huán)境下的路徑規(guī)劃, 如含有禁飛區(qū)的約束條件下進行無人機的路徑規(guī)劃.除此之外, 還將嘗試設計一些更加高效的鄰域搜索算子來進一步提升解的質量.