貨車搭載多架無人機車輛路徑問題模型及算法

劉艷秋，韓 晶

（沈陽工業(yè)大學，管理學院，沈陽 110870）

0 引 言

2019年12月，新冠疫情暴發(fā)以來，物流業(yè)面臨著前所未有的挑戰(zhàn)。首先，在整體行業(yè)運營上，復工復產(chǎn)進程受阻，原材料價格上漲，企業(yè)人工成本增加等導致物流整體成本的直線上升。其次，在貨物運輸方面，物流企業(yè)的貨量常常無法裝滿運輸車輛使得利用率大大降低。再次，在終端配送過程中，需注意避免人物接觸導致交叉感染，保障供需雙方生命安全。因此，物流行業(yè)亟須向靈活性強、成本可控、無人化物流的智能模式轉(zhuǎn)型。隨著無人機技術(shù)的成熟與規(guī)范，將其運用于物流行業(yè)成為了可能[1-2]。但受限于負載小、航程短等問題，無人機一直未能獨立執(zhí)行常規(guī)性物流運輸活動。此時，無人機與貨車聯(lián)合配送的運作模式成為了必然選擇[3]。一方面，貨車可對客戶進行貨物配送；另一方面，貨車也可作為無人機的移動倉庫和移動充電站。在這種模式下，將貨車的遠距離、大容量與無人機的高效率、低成本有效結(jié)合，既保證了復雜配送情景下的各類型配送需求，提高總體配送效率，又滿足了安全配送的要求。

最早關(guān)于貨車和無人機聯(lián)合配送的研究是在2015 年，Murry 等[4]提出了一輛貨車搭載一架無人機的飛行助手旅行商問題（Flying Sidekick Traveling Salesman Problem，F(xiàn)STSP）和并行調(diào)度旅行商問題（Parallel Drone Scheduling Traveling Salesman Problem，PDSTSP），他們以最晚返回倉庫的時間為目標函數(shù)構(gòu)建了混合整數(shù)規(guī)劃模型，設(shè)計了一種啟發(fā)式算法求解。其中兩者的區(qū)別是：前者貨車搭載無人機共同為客戶服務(wù)，后者貨車和無人機獨立為客戶服務(wù)。此后，這一問題被國內(nèi)外學者廣泛研究。

在FSTSP 擴展問題中，Agatz 等[5]在Murry 的基礎(chǔ)上首次以最小旅行成本為目標建立了整數(shù)規(guī)劃模型，并設(shè)計了路徑第一聚類第二的啟發(fā)式算法，與FSTSP 不同的是，Agatz 允許車輛在同一客戶點多次發(fā)射無人機，并將此問題擴展成為帶無人機的旅行商問題（Traveling Salesman Problem with Drone，TSPD）。Ha 等[6]進一步以最小化運營成本為目標構(gòu)建TSP-D 模型，并設(shè)計了一種混合遺傳算法求解該問題。Bouman、Poikonen 和Schermer 等[7-9]分別利用動態(tài)規(guī)劃、采用分支定界和分支切割算法求解帶無人機的旅行商問題模型。朱曉寧等[10]考慮了卡車限行和無人機禁飛等區(qū)域限制條件下的貨車和無人機聯(lián)合配送路徑優(yōu)化問題。隨后，Phan 等[11]將模型擴展到一輛貨車搭載多架無人機的情形，并指出這種配送模式更具有經(jīng)濟優(yōu)勢。Peng 等[12]提出了一種由種群管理、啟發(fā)式種群初始化和種群培養(yǎng)三個部分組成的混合遺傳算法求解一輛貨車搭載多架無人機的配送路徑優(yōu)化問題。然后，Wang 等[13]進一步將車輛與無人機協(xié)同配送問題從單一車輛擴展到多車輛，計算得出了即使在最壞情況下貨車與無人機聯(lián)合并行配送的時間都少于卡車單獨配送時間的結(jié)論。Sacramento 等[14]采用自適應(yīng)大規(guī)模鄰域搜索算法求解帶無人機的車輛路徑問題模型。

在PDSTSP 擴展問題中，研究數(shù)量相對較少。Amico 和Saleu 等[15-16]就PDSTSP 問 題 設(shè) 計 了 不 同的啟發(fā)式算法求解。Ham 等[17]在Murry 的基礎(chǔ)上考慮了多車輛、多無人機、多配送中心的情況進行研究。Wang 和Lan[18]提出了貨車和無人機混合配送模式，即一部分客戶由多輛貨車各搭載一架無人機協(xié)同配送，剩余客戶由多架無人機往返配送中心獨立配送服務(wù)。此外，還有少部分文獻對貨車支持無人機配送和無人機支持貨車配送進行了研究[19-22]。在應(yīng)用場景方面，彭勇和楊雙鵬等[23-24]以旅行商問題為背景探究了貨車和無人機聯(lián)合配送在疫情影響下的價值。肖建華等[25]將貨車和無人機聯(lián)合配送模式應(yīng)用到農(nóng)村電商物流“最后一公里”問題。貨車和無人機聯(lián)合配送路徑優(yōu)化問題可以看作是旅行商問題或車輛路徑問題中引入了無人機配送，故在這方面也有一些值得借鑒的研究成果[26-28]。

從以上文獻可以看出，現(xiàn)有關(guān)于貨車搭載無人機配送路徑優(yōu)化問題的研究已經(jīng)擴展到了多輛貨車和多架無人機，其中大部分文獻規(guī)定車輛必須在下一節(jié)點回收無人機，且無人機單次服務(wù)一個客戶，而Othman 等[29]專門研究了不同對接點設(shè)置下的最小成本路徑選擇問題，但未從決策角度給出數(shù)學模型和相應(yīng)的計算實驗分析。其次，大部分研究集中于貨車和無人機協(xié)同配送服務(wù)，鮮少考慮混合配送模式，這樣的缺陷忽略了配送中心周圍的小需求客戶點，從而造成實際配送中這類小批量多批次的客戶配送成本較高，間接增加了配送距離。再次，對于貨車搭載無人機配送路徑優(yōu)化問題中元啟發(fā)式算法和計算實驗的研究相對較少，其中多采用精確算法求解小規(guī)模算例以得到精確解，采用啟發(fā)式算法得到滿意解，遺憾的是啟發(fā)式算法一般根據(jù)具體問題設(shè)計，故容易陷入局部最優(yōu)。因此，本文在VRPD(Vehicle Routing Problem with Drone)的基礎(chǔ)上增加了單輛貨車搭載多架無人機，單架無人機可為多個客戶服務(wù)的場景，建立“協(xié)同+并行”混合配送模式下的整數(shù)規(guī)劃模型，設(shè)計了以蟻群算法為核心的基于變維數(shù)編碼的兩階段規(guī)劃算法求解，其中變維數(shù)矩陣編碼適用于兩種運輸工具且?guī)в蟹种ЫY(jié)構(gòu)的車輛調(diào)度優(yōu)化問題。最后，通過計算實驗結(jié)果分析模型的準確性和算法的有效性。

1 問題描述與數(shù)學模型

1.1 問題描述

現(xiàn)有一個配送中心和若干個有需求的客戶分布在各個位置，每個客戶的需求量已知，配送中心和客戶之間及任意兩個客戶之間的距離已知。規(guī)定一個配送中心有多輛貨車和多架無人機，且單輛貨車可搭載多架無人機，單架無人機可給多個客戶送貨，在滿足一個客戶只能由一輛車配送貨物的前提下，配送中心派遣若干輛貨車和無人機為客戶配送貨物。每輛車都從配送中心出發(fā)，無人機可從配送中心或搭載它的貨車上出發(fā)，對若干個顧客配送貨物結(jié)束后再返回配送中心，規(guī)劃出所有車輛運營成本最小的配送方案。

圖1 給出了一個貨車和無人機混合配送路徑方案示例，其中包括1 個配送中心、3 輛貨車、3 架無人機和31 個客戶。在可能的路徑方案中，30 個顧客被分成R1、R2、R3 和R4 四條線路：R1 的貨車路徑為（0—1—2—6—7—0），無人機路徑為（6—5—3—4—6；7—8—9—7）；R2 的貨車路徑為（0—13—15—31—21—0），無人機路徑為（13—14—13；31—18—16—31；31—20—31；31—17—19—31）；R3 的貨車路徑為（0—29—24—10—0），無人機 路 徑 為（29—30—29；29—28—29；24—25—26—27—24；24—23—24；10—22—10）；R4 是純無人機配送路徑（0—11—12—0）。

圖1“貨車+無人機”聯(lián)合配送示例圖Fig.1 Schematic of the“truck+drone”joint distribution

搭載多架無人機的車輛路徑問題（Vehicle Routing Problem with Multiple Drones，VPR-mD）可以描述為圖論問題。令G=(V,A)為一個有向圖，其中V={0,1,2,…,n,n+1}表示節(jié)點集，節(jié)點0,n+1 表示配送中心，其余節(jié)點均表示客戶，A表示弧集。規(guī)定在有向圖G上，一條合理的配送路線必須始于節(jié)點0 終于節(jié)點n+1。Δ+(i)表示從節(jié)點i出發(fā)的弧的集合，Δ-(j)表示回到節(jié)點j的弧的集合。N=V{0,n+1}表示顧客集；Nk表示所有被貨車服務(wù)的客戶集；R表示貨車和無人機的對接點集合；NQ表示所有顧客需求點中超過無人機最大載重限制的節(jié)點集合；ND表示各對接點與其對應(yīng)的無人機客戶距離超過無人機最大續(xù)航里程的節(jié)點集合；Nu表示所有被無人機服務(wù)的客戶集；K表示配送貨車集；U表示無人機集。設(shè)d 'ij和dij分別為貨車和無人機從節(jié)點i到節(jié)點j的距離。Dmax為無人機最遠航程，由于無人機每次飛行至少為一個客戶服務(wù)，故無人機可訪問的客戶點最遠航距是Dmax2。又設(shè)qi為客戶的需求量，Qt和Qu分別為貨車和無人機的最大負載量。設(shè)a和b分別為貨車和無人機的單輛固定成本；λ和μ分別為在配送中心出發(fā)的貨車和無人機數(shù)量；Ct和Cu分別為貨車和無人機的單位運輸成本。為了更清晰地表明貨車和無人機聯(lián)合配送服務(wù)可以實現(xiàn)物流企業(yè)降本增效的目標，故選用總運營成本為目標函數(shù)。由于車輛使用數(shù)目、運輸距離和裝載量直接影響著企業(yè)總運營成本，故總運營成本主要包括三個部分：貨車和無人機的固定成本、運輸成本和超出車輛最大續(xù)航里程和裝載量的懲罰成本。

在建立數(shù)學模型之前，還需要給出一些假設(shè)：

（1）無人機只能在同一節(jié)點起飛和降落，若貨車和無人機有一方早到，則需等待另一方到達后才能再次出發(fā)；

（2）貨車和無人機均始終保持勻速行駛，無人機的速度快于貨車，且無人機遵循歐氏距離，根據(jù)道路曲折度，貨車距離可定義為d 'ij=δ·dij,δ是一個常數(shù)；

（3）不考慮速度和載重量對無人機續(xù)航時間的影響；

（4）不考慮無人機充電時間和天氣等外界因素的影響。

1.2 數(shù)學模型

根據(jù)所述問題的特點，本文定義模型變量如下：

其中目標函數(shù)（1）由三部分組成：第一部分表示車輛的固定成本；第二部分表示車輛的運輸成本；第三部分表示超過車輛最大續(xù)航里程和裝載量時的懲罰成本。ζ1和ζ2分別是違反裝載量約束和航程約束的懲罰因子，取無限大的正數(shù)。約束（2）表示計算路徑中超出無人機最大續(xù)航里程的距離。約束（3）表示計算路徑中超出無人機最大裝載量的重量。約束（4）表示計算路徑中超出貨車最大裝載量的重量。約束（5）限制每個客戶只能被分配到一條路徑。約束（6）表示貨車從配送中心出發(fā)最后要返回配送中心。約束（7）表示貨車從某一貨車客戶進入也必須從該客戶點離開，且最多只能訪問一個客戶一次。同理，約束（8）表示允許無人機從配送中心出發(fā)服務(wù)一個或多個客戶后返回配送中心。約束（9）表示無人機進出無人機客戶的流量守恒，且最多只能訪問一個客戶一次。約束（10）表示無人機必須在同一對接點起降。約束（11）表示貨車服務(wù)的客戶中包含超重點、超遠點和對接點。約束（12）表示配送無人機u初始在配送中心的裝載量必須不大于配送無人機的最大裝載量。約束（13）表示配送貨車k初始在配送中心的裝載量必須不大于配送貨車的最大裝載量，這里的貨車初始裝載量包含其搭載無人機的裝載重量。約束（14）限制每架配送無人機u的飛行距離。約束（15）表示變量取值范圍。

2 算法設(shè)計

本文所提出的VRP-mD 屬于NP-hard 問題，優(yōu)化求解器計算效率低，精確算法求解難度大，因此多采用啟發(fā)式算法對其進行求解。啟發(fā)式算法求解VRP-mD有以下6個難點：各個客戶采用何種運輸方式？如何選擇貨車和無人機的對接點？如何確定下一個訪問點？如何構(gòu)造完整路徑，即解的編碼方式是什么？如何將完整路徑轉(zhuǎn)換為配送方案？如何評價解的質(zhì)量并更新？

蟻群算法通過螞蟻們尋找食物的過程中留下的“信息素”從而確定下一個訪問的點，循環(huán)往復，直至得到問題的最終解。現(xiàn)今蟻群算法已經(jīng)廣泛應(yīng)用于組合優(yōu)化問題的求解中，且同其他優(yōu)化算法相比，在求解性能上具有很強的魯棒性，易于搜索到較好解，具有正反饋機制和分布式計算等優(yōu)點，也易與多種優(yōu)化算法結(jié)合，從而改善算法性能。故本文針對以上6個難點，選擇蟻群算法進行求解，但傳統(tǒng)蟻群算法不能同時優(yōu)化無人機配送路徑和貨車配送路徑，為此，本文設(shè)計了一種蟻群算法與局部搜索算法結(jié)合的基于變維數(shù)矩陣編碼的兩階段規(guī)劃算法，基本思路是先用蟻群算法構(gòu)造初始解，再將其用變維數(shù)矩陣形式編碼，最后利用局部搜索算子進一步提高解的質(zhì)量。

2.1 構(gòu)造初始解

構(gòu)造初始解分為三階段進行，基本思路是：第一階段采用貪婪算法確定各個客戶的配送方式和對接點，并以每一對接點為中心將無人機客戶聚類；第二階段采用蟻群算法規(guī)劃無人機配送路徑；第三階段更新貨車客戶需求，再用蟻群算法規(guī)劃貨車配送路徑。具體步驟如下：

第一階段：確定各個客戶的配送方式和對接點。

Step 1 輸入所有客戶點位置（坐標點）和需求qi。

Step 2 初始化貨車客戶集和無人機客戶集，Nk=[],Nu=[]。

Step 3 ?i∈N,?qi≤Qu則Nu=[Nu,i]；否則Nk=[Nk,i]。

Step 4 初始化對接點集合，R=[0,Nk]。

Step 5 用貪婪算法將距離R(i)最近的無人機客戶聚集生成Ru(i,:)。

Step 6 比較Ru(i,:)中每一客戶與R(i)的距離，如果有距離超過Dmax2 的無人機客戶i，則從當前集合中移除，將其放入Nk中，轉(zhuǎn)至Step4，否則轉(zhuǎn)至Step 7。

Step 7 輸出貨車客戶集Nk、無人機客戶集Nu、對接點集R、各對接點對應(yīng)的無人機客戶集Ru。

第二階段：利用蟻群算法規(guī)劃無人機配送路徑。

Step 1 輸入對接點R與對接點對應(yīng)的無人機客戶集Ru。

Step 2 初始化螞蟻數(shù)目m、迭代次數(shù)MAXGEN、信息素重要程度因子α、啟發(fā)函數(shù)重要程度因子β、信息素揮發(fā)因子ρ、更新信息素濃度的常數(shù)Q、信息素矩陣τ、螞蟻路徑記錄表Table、計數(shù)器gen=1。

Step 3 如果gen≤MAXGEN，轉(zhuǎn)至Step4，否則轉(zhuǎn)至Step 12。

Step 4 初始化i= 1。

Step 5 如果i≤m，轉(zhuǎn)至Step 6，否則轉(zhuǎn)至Step 8。

Step 6 確定允許訪問的客戶集allowj，該集合不包括已經(jīng)訪問的客戶和違反裝載量與航程約束的客戶。

Step 7 根據(jù)轉(zhuǎn)移概率計算公式Pn ij和輪盤賭法求出第i只螞蟻下一個訪問的客戶j。螞蟻n從i點轉(zhuǎn)移到j(luò)點的概率計算公式如下：

式中：τij為i點到j(luò)點這條線段上的“信息素”濃度；ηij= 1dij為i點到j(luò)點這條線段距離的倒數(shù)，又被稱為能見度函數(shù)；allowj為螞蟻從i點出發(fā)允許訪問的無人機客戶集合；α為τij的重要程度；β為ηij的重要程度。

Step 8 更新路徑記錄表Table(k,i)=j，i=i+1，轉(zhuǎn)至Step 5。

Step 9 比較m只螞蟻所規(guī)劃的行走方案，找到無人機配送成本最小的一個行走方案，配送成本計算公式如下：

式（17）為無人機的飛行距離與違反裝載量和航程約束成本之和，加入違反約束成本是為了避免出現(xiàn)不可行解，若存在不可行解，則配送成本會變得非常大，否則配送成本等于飛行距離。

Step 10 更新“信息素”矩陣，這里本文選擇更新最佳行走方案所包含線段上的“信息素”，更新公式如下：式中：τnewij為更新后的i點與j點之間的“信息素”濃度；τoldij為更新前的i點與j點之間的“信息素”濃度；ρ為“信息素”濃度揮發(fā)因子，取0～1 的一個數(shù)字；Δτij為這只螞蟻在i點與j點之間釋放的“信息素”濃度；Q為常數(shù)，表示螞蟻構(gòu)建一次完整路徑所釋放的“信息素”總量；TD為這只螞蟻構(gòu)建的完整路徑所對應(yīng)的配送方案的車輛行駛總距離。

Step 11 清空路徑記錄表，轉(zhuǎn)至Step 3。

Step 12 輸出對接點R(i)的無人機配送路徑。

Step 13 依次循環(huán)Ru的每一行，得到全部無人機配送路徑，記錄每一對接點對應(yīng)無人機客戶總需求。

第三階段：規(guī)劃貨車配送路徑。

Step 1 輸入配送中心0與貨車客戶Nk。

Step3 同理利用ACO 算法規(guī)劃出貨車配送路徑，稍有不同的是貨車配送成本計算公式變?yōu)椋?/p>

2.2 局部搜索操作

本文局部搜索操作選擇交換算子，但用交換算子必須存在可以將完整路徑表現(xiàn)出來的編碼方式。現(xiàn)有車輛路徑優(yōu)化問題通常采用自然數(shù)編碼，但在VRP-mD 問題中存在同一個對接點被多次選擇的情形，例如圖2 中的客戶7 被兩架無人機同時選擇，因此路徑結(jié)構(gòu)中出現(xiàn)了帶有分支結(jié)構(gòu)的哈密頓路行駛。由于計算機編碼輸入條件的限制和局部搜索操作對編碼結(jié)構(gòu)生成和處理方式的特點，這種分支路徑結(jié)構(gòu)無法直接編譯表達，因此需要將這種分支路徑結(jié)構(gòu)寫成多維數(shù)組形式。為此，本文介紹變維數(shù)矩陣的路徑編碼方式。

該編碼由一個p×q維矩陣結(jié)構(gòu)進行編碼，其中p=l+k+1，l表示貨車客戶節(jié)點總數(shù)，k表示使用貨車數(shù)量；q=max(r(i))+d+1，其中r(i)表示第i個對接點對應(yīng)的無人機客戶的數(shù)量，d表示第i個無人機路徑內(nèi)使用無人機數(shù)量。針對圖2（a）中的路徑結(jié)構(gòu)，變維數(shù)矩陣編碼如圖2（b）所示。

圖2 變維數(shù)矩陣編碼示例圖Fig.2 Schematic of the variable dimension matrix coding

圖2（b）中編碼由多層結(jié)構(gòu)體表示。第一層為貨車層，表示所有貨車的訪問節(jié)點順序。除第一層外的其他層為無人機層，表示所有無人機選擇的對接點及訪問節(jié)點順序。在無人機層內(nèi)多架無人機可選擇同一個節(jié)點進行對接，通過這種編碼方式解決了現(xiàn)有算法中編碼不能夠有效表達分支路徑結(jié)構(gòu)的問題。圖2（b）中編碼表示客戶1、3由貨車1 提供配送服務(wù)，客戶7 由貨車2 提供配送服務(wù)；客戶2 選擇客戶1 作為對接位置，并由無人機1 提供配送服務(wù)，客戶4、5、6 共同選擇客戶7 作為對接位置，并由無人機2 和無人機3 提供配送服務(wù)。由此可見，變維數(shù)矩陣編碼方式可以清晰地展示多輛貨車和多架無人機的配送路徑，且進行交換等局部搜索操作時可有效減少不可行解的數(shù)量，從而提高運算效率。這種編碼方式還可以拓展到其他具有分支結(jié)構(gòu)的組合優(yōu)化問題研究中。

在初始解構(gòu)造完成后，此時為使解的目標函數(shù)值向著更小的方向進化，需要改變個體的“基因”。針對無人機路徑優(yōu)化設(shè)計有兩種改變個體“基因”的操作：類內(nèi)交換操作與類間交換操作，交換算子示意圖見圖3。

圖3 交換算子示意圖Fig.3 Schematic of the exchange operator

（1）類內(nèi)交換：在同一對接點集合內(nèi)隨機選擇兩個位置交換。如圖3（a）中的3 與4 交換。也就是說，當一條無人機路徑中存在交叉結(jié)構(gòu)時，便采用類內(nèi)交換操作。

（2）類間交換：在相鄰對接點集合中隨機選擇兩個位置交換。如圖3（b）中的（1231）（45）變?yōu)椋?234）（5）。也就是說，當選擇對接點R1 的無人機客戶距離另一對接點R2 更近時，便采用類間操作。

綜合以上策略，本文整體算法流程見圖4。

圖4 算法流程圖Fig.4 Algorithm flow chart

3 算例分析

算法將通過Matlab 2018b 進行編程，所有測試均在同一臺電腦上進行，運行環(huán)境為Windows 10 操作系統(tǒng)，處理器為Intel(R) Core(TM)i5-10200H CPU @ 2.40GHz 2.40GHz。經(jīng)過多次測試，設(shè)置算法參數(shù)為：螞蟻數(shù)目為50，最大迭代次數(shù)為200，信息素重要程度因子α= 1、啟發(fā)函數(shù)重要程度因子β= 5、信息素揮發(fā)因子ρ= 0.85、更新信息素濃度的常數(shù)Q= 5、初始信息素矩陣為單位陣。

本文選擇三種算例進行測試：隨機生成客戶點、文獻[19]中B-n32-k5 算例和文獻[4]中的FSTSP-10、PDSTSP-10 算例。文獻[19]中假設(shè)單輛車的固定費用（折舊費等）為80 元，單架無人機的固定費用為20元，車輛單位距離成本為1.5元/km，無人機的單位距離飛行成本為0.3 元/km，但其客戶需求設(shè)置全部不超過無人機載重量。根據(jù)亞馬遜公司公布的調(diào)查數(shù)據(jù)和順豐科技有限公司提供的Ark 方舟無人機參數(shù)[30]，本文設(shè)定無人機最大載重量為12 kg，無人機最大續(xù)航里程為20 km，貨車最大載重量為100 kg，且86%的客戶需求重量為3 kg及以下，其余客戶為3 kg以上。

3.1 基于不同配送方式的總配送成本比較

如果僅使用貨車配送，該問題就被稱為傳統(tǒng)貨運；如果貨車和無人機獨立服務(wù)客戶，該問題就被稱為貨車和無人機并行配送模式；如果無人機必須從貨車處出發(fā)并返回貨車，該問題就被稱為貨車和無人機協(xié)同配送問題。本文提出的貨車和無人機聯(lián)合配送是指結(jié)合協(xié)同和并行兩種模式的混合配送模式，簡單來說，無人機可以從配送中心或貨車處出發(fā)，既可以單獨服務(wù)客戶又可以乘坐貨車服務(wù)客戶。為了進一步說明聯(lián)合配送的優(yōu)越性，以算例B-n32-k5 為例，分別采用傳統(tǒng)貨車配送、并行配送方式和聯(lián)合配送方式進行運輸，比較結(jié)果見表1。

表1 不同配送模式下的成本分析Tab.1 Cost analysis under different distribution modes

通過表1 的比較分析可知，在使用貨車和無人機兩種運輸工具的路徑優(yōu)化問題中，同時考慮協(xié)同和并行的聯(lián)合配送模式下建立的數(shù)學模型更加符合最后一公里配送所面臨的實際背景。同時靈活的配送模式有效地減少了無人機的使用和總配送距離，達到了降低物流系統(tǒng)運營總成本的目標。

為了進一步分析該算法相對于其他優(yōu)化算法在處理此類研究問題中的優(yōu)勢，本文在相同規(guī)模問題中將其與文獻[19]的算法性能進行比較分析，最優(yōu)配送方案路線如圖5 所示，仿真運算結(jié)果如表2 所示。可以看到本文設(shè)計的基于變維數(shù)矩陣的兩階段規(guī)劃算法能夠在可接受的時間內(nèi)在解空間搜索到問題的滿意解甚至是最優(yōu)解，求解效率高。

圖5 B-n32-k5最優(yōu)配送方案路線圖Fig.5 Roadmap for the B-n32-k5 optimal distribution scheme

表2 不同算法求解的聯(lián)合配送成本比較Tab.2 Comparison of the joint distribution cost using different algorithms

3.2 算法的驗證分析

為了評估模型的準確性與算法的有效性，本文比較了商業(yè)軟件CPLEX 與基于變維數(shù)編碼的兩階段規(guī)劃算法的計算結(jié)果。為了保證實驗的一般性，隨機選取文獻[4]中10 個FSTSP-10 算例、5個PDSTSP-10 算例，由于文獻[4]中未設(shè)置成本參數(shù)，故本文對配送距離和運行時間進行對比，測試結(jié)果見表3。

表3 算例計算結(jié)果對比Tab.3 Comparison of the calculation results for the solved examples

續(xù)表3

從表3 可以看出，在15 個算例中，基于變維數(shù)矩陣編碼的兩階段算法找到了4個算例的最優(yōu)解，11 個算例的滿意解，說明該算法的計算精度較為一般。從計算時間上看，CPLEX 平均求解時間需要21.2991 s，而基于變維數(shù)矩陣編碼的兩階段算法需要7.5862 s，說明該算法具有較快的計算速度。從計算結(jié)果上看，客戶點的分布與配送距離有直接關(guān)系，當全部無人機客戶距離配送中心不超過Dmax2 時，選擇貨車和無人機并行配送模式更節(jié)省配送距離，除此之外，選擇貨車和無人機聯(lián)合配送模式更節(jié)省配送距離。

3.3 靈敏度分析

隨機生成14、31、43、52、100 個客戶算例，實驗中采用控制變量法分別對無人機續(xù)航里程、無人機載重量兩個參數(shù)進行靈敏度分析，探討無人機性能對結(jié)果的影響。設(shè)置無人機最大續(xù)航里程是20 km，最大裝載量是12 kg，隨著無人機技術(shù)的發(fā)展，其性能也將會慢慢提高，將無人機最大續(xù)航里程分別設(shè)定為20 km、30 km 和M（足夠大的正整數(shù)，即允許無人機給任意一個客戶送貨），測試結(jié)果見表4。將無人機最大裝載量設(shè)定為12 kg、20 kg和30 kg，測試結(jié)果見表5。

表4 無人機續(xù)航里程靈敏度分析Tab.4 UAV range sensitivity analysis

表5 無人機裝載量靈敏度分析Tab.5 UAV loading capacity sensitivity analysis

從表4和表5可以看出，在100個客戶規(guī)模內(nèi)，隨著數(shù)據(jù)規(guī)模的增加，基于變維數(shù)矩陣編碼的兩階段規(guī)劃算法具有較高的穩(wěn)定性，優(yōu)化效果更加明顯。無人機續(xù)航里程的增加使得無人機使用數(shù)量減少，單架無人機配送距離不斷上漲，這說明無人機性能的提高增加了無人機的利用率，從而使配送成本和運營成本下降，提升了運輸效率，但可以觀察到配送距離變化率較小，這說明無人機加入配送過程在配送距離上表現(xiàn)不明顯，其在總運營成本和配送完成時間上體現(xiàn)更明顯。結(jié)合表1和表5 可知，當無人機載重量較小時，獲得的距離和成本節(jié)省很低。原因在于，當無人機載重量較小時，無人機一次飛行訪問需求點較少，所以同樣行程使用的無人機數(shù)量較多，從而成本節(jié)約較小。隨著無人機載重量的增加使得無人機服務(wù)的客戶增多，但單架無人機實載率較低，即無人機續(xù)航里程嚴重制約了無人機服務(wù)范圍，所以單純增加無人機裝載量并沒有使得配送成本和運營成本下降。由此可見，企業(yè)在研發(fā)物流配送無人機時不能一味追求續(xù)航里程或裝載量單方面的優(yōu)化，而需將續(xù)航里程和載重量同時進行考慮，且需要重點考慮無人機續(xù)航里程的影響。

4 結(jié)論

本文研究了貨車搭載多架無人機的車輛路徑問題，進一步考慮了無人機容量和不同配送模式的影響，構(gòu)建了以總運營成本最小為目標的混合整數(shù)規(guī)劃模型，并設(shè)計了基于變維數(shù)矩陣編碼的兩階段啟發(fā)式算法。第一階段：首先根據(jù)需求量對客戶進行分類，然后基于蟻群算法分別規(guī)劃無人機路徑和貨車路徑，其中貨車路徑要根據(jù)無人機路徑進行更新需求后再規(guī)劃路徑；第二階段：將完整路徑采用變維數(shù)矩陣編碼，再利用交換算子進行局部搜索優(yōu)化。仿真結(jié)果表明，本文提出的算法可有效解決兩種運輸工具的路徑規(guī)劃問題，具有計算時間短、求解效率高的優(yōu)勢。貨車和無人機聯(lián)合配送策略可以真正實現(xiàn)降本增效的目標。同時本文的工作保證了在最后一公里問題中實現(xiàn)無接觸安全配送，解決了因新冠疫情導致的空載率高、配送成本高的現(xiàn)實難題，也為未來實現(xiàn)“貨車+無人機”聯(lián)合配送常態(tài)化發(fā)展提供了理論支持。

未來的研究中，考慮根據(jù)不同的物流問題，在問題模型方面加入其他約束或目標函數(shù)，例如不同停靠地點、時間窗、同時取送貨約束以及貨車和無人機的同步成本等。在算法方面將繼續(xù)研究計算精度更高的算法框架和算法策略，并結(jié)合更符合實際路網(wǎng)情況的算例開展計算實驗。