基于集群的卡車與無人機聯(lián)合配送調(diào)度研究

曹英英，陳淮莉

上海海事大學(xué) 物流科學(xué)與工程研究院，上海 201306

近年來，隨著互聯(lián)網(wǎng)在農(nóng)村的不斷滲透，農(nóng)村網(wǎng)購熱潮不斷興起，在國家和企業(yè)的雙重支持下，2020年中國農(nóng)村電商市場規(guī)模為31 533億元，同比增長37.7%，農(nóng)村電商迅猛發(fā)展[1]。然而，除了國營企業(yè)郵政速遞，大部分民營物流公司所構(gòu)建的配送網(wǎng)絡(luò)最多由縣級下沉到人口聚集、交通相對便捷的鄉(xiāng)鎮(zhèn)，尚未往下延伸到各個村落，更不用說直接面向消費者，大部分快遞仍需消費者自取，自行解決從村到站點的交通問題，導(dǎo)致物流時效性大大降低[2]。如何改變傳統(tǒng)的物流配送方式以打通農(nóng)村物流“最后一公里”，讓消費者獲得更高效的服務(wù)，是亟需解決的難點。隨著無人機在物流領(lǐng)域受到越來越多的關(guān)注，多家企業(yè)和學(xué)者推出一種新的配送模式，即卡車與無人機聯(lián)合配送，來取代傳統(tǒng)的卡車運輸。

目前Amazon、UPS、DHL等大公司開始將無人機應(yīng)用于物流業(yè)務(wù)中[3]，國內(nèi)企業(yè)以京東和順豐等也緊跟其后，在全國各地著手布局無人機配送體系[4]。同時，關(guān)于在配送過程中使用無人機的研究受到學(xué)者們極大的關(guān)注。一些研究考慮通過搭建充電站網(wǎng)絡(luò)使無人機直接從倉庫交付貨物[5]，或建立靠近客戶的無人機站單獨為無人機提供儲存貨物和充電服務(wù)[6]，以克服飛行距離限制。為了規(guī)避這些站點的投資成本，許多研究[7-17]又考慮將無人機加入到現(xiàn)有的卡車配送模式中協(xié)同配送。雖然無人機憑借著配送速率快、無視地形影響等優(yōu)點，能有效節(jié)約時間和減少交付成本，但無人機載荷和續(xù)航能力有限，傳統(tǒng)卡車可以彌補這一技術(shù)限制。在這些研究中，卡車攜帶無人機和所有訂單從配送中心出發(fā)，需要在一些客戶點處停留完成交付任務(wù)，同時無人機從客戶點起飛對附近一定范圍內(nèi)的其他客戶配送小型包裹。以此循環(huán)，直到所有訂單配送完成。相比城市配送和其他應(yīng)用場景[7-9]，農(nóng)村地區(qū)由于禁飛政策相對寬松、安全性相對較好等因素能夠很好地發(fā)揮出卡車與無人機聯(lián)合配送新模式的作用。

關(guān)于卡車與無人機聯(lián)合配送的研究主要集中于帶無人機的旅行商問題（traveling salesman problem with drone，TSP-D）和多卡車多無人機路徑問題（vehicle routing problem with drones，VRPD）。2015年，Murray等[10]首次提出卡車搭載無人機聯(lián)合配送理論，開發(fā)混合整數(shù)線性規(guī)劃模型和簡單的啟發(fā)式算法，可解決小規(guī)模案例。Agatz等[11]在Murray的研究基礎(chǔ)上基于局部搜索和動態(tài)規(guī)劃設(shè)計出兩階段啟發(fā)式算法。Ha等[12]針對TSP-D問題，在最小化總運營成本中加入了等待時間所產(chǎn)生的罰金，提出貪婪隨機化自適應(yīng)搜索算法來求解更大規(guī)模實例。Ferrandez等[13]使用K-means算法將配送網(wǎng)絡(luò)劃分為集群，集群質(zhì)心充當(dāng)無人機調(diào)度的卡車?？空?，并使用遺傳算法優(yōu)化卡車路線。

以上研究均假設(shè)一輛卡車僅攜帶一架無人機，隨著研究的深入，可考慮單輛或多輛卡車攜帶多架無人機[14-17]。其中，Kitjacharoenchai等[15]提出帶無人機的兩級車輛路徑問題，設(shè)計無人機卡車路徑構(gòu)建算法和大鄰域搜索算法來解決該問題。Chang等[16]在初始K-means聚類和TSP建模后通過增加移動權(quán)重將卡車?？奎c向倉庫靠近，以進一步縮短交貨完成時間。Salama等[17]將無監(jiān)督機器學(xué)習(xí)K-means算法分為三步得到修正后的最優(yōu)卡車路徑。

上述研究大多選擇客戶點來作為無人機的發(fā)射和回收位置，傳統(tǒng)的K-means算法只是將聚類出的質(zhì)心移動到離質(zhì)心最近的客戶位置處，該過程沒有考慮卡車和無人機配送成本。對此，本文對K-means算法進行改進，考慮無人機續(xù)航和數(shù)量限制，通過修改聚類以適應(yīng)本文所提出的特定客戶點和普通客戶點，來選出最佳卡車?？奎c集合，并提出遺傳模擬退火算法加快收斂速度，用以優(yōu)化卡車與無人機聯(lián)合配送路線，從而找出總運營成本最小的配送方案。同時，以上文獻均未將時間窗納入考慮范疇進行深入探索，而時間窗的設(shè)定可以提高消費者的服務(wù)體驗。本文增加時間窗限制，若卡車或無人機配送未在規(guī)定時間內(nèi)送達(dá)則會產(chǎn)生相應(yīng)的懲罰成本。

綜上，本文針對農(nóng)村地區(qū)送貨上門難的問題提出基于集群的卡車與無人機聯(lián)合配送問題，以總運營成本最小為目標(biāo)，結(jié)合無人機的特點，構(gòu)建帶有時間窗的混合整數(shù)規(guī)劃模型，并通過改進后的K-means聚類算法和遺傳模擬退火算法對模型求解，結(jié)果表明本文所采用的方法能有效降低配送成本，且算法效率較高。

1 模型構(gòu)建

1.1 問題描述

在一個農(nóng)村地區(qū)的鄉(xiāng)鎮(zhèn)級配送網(wǎng)點中，需要該網(wǎng)點的運輸工具在規(guī)定時間內(nèi)向周邊相鄰的多個客戶點投遞包裹。傳統(tǒng)卡車單獨配送如圖1（a）所示，卡車與無人機聯(lián)合配送模式如圖1（b）所示。一輛卡車搭載著多架無人機和總需求前往每個集群內(nèi)依次進行配送。將卡車配送點統(tǒng)稱為卡車?？奎c，集群是指以卡車?？奎c為中心并包含作業(yè)半徑限制內(nèi)客戶節(jié)點的集合。卡車需要在每個?？奎c停留一段時間，首先對該客戶點服務(wù)，然后讓無人機從?？奎c起飛對集群內(nèi)的普通客戶點配送，最后返回到?？奎c處的卡車上完成裝貨和更換電池操作為下一次停靠做準(zhǔn)備。以此循環(huán)完成所有配送，最后一同回到配送網(wǎng)點。由于部分貨物的重量或體積超過無人機載荷限制，或需客戶當(dāng)面簽名驗收等原因，這些貨物無法由無人機配送只能特別指定卡車來服務(wù)。本文稱這些客戶點為特定客戶點，其他客戶點為普通客戶點，可隨機由卡車或無人機來完成服務(wù)。為方便統(tǒng)計，本文簡單地考慮貨物重量來區(qū)分客戶種類。

圖1 配送模式對比Fig.1 Comparison of distribution modes

為方便進行定量化研究，對問題進行簡化，做出如下假設(shè)：

（1）所有客戶點位置、需求、服務(wù)時間及時間窗已知。

（2）無人機有容量和最大飛行半徑限制，卡車一次出行有足夠的容量和燃料供應(yīng)。

（3）無人機裝貨和更換電池時間較短忽略不計。

（4）無人機一次只能配送一個包裹，完成任務(wù)后只能返回卡車停靠點，在每個集群內(nèi)只進行一次飛行。

（5）每個客戶點只能由一輛卡車或一架無人機一次配送完成。

（6）卡車和無人機均勻速行駛和飛行。

1.2 符號說明

1.3 建立模型

根據(jù)問題描述和參數(shù)定義，可構(gòu)建以下模型：

其中，目標(biāo)函數(shù)（1）為總運營成本最小化，總運營成本由無人機的固定成本、總行駛成本和時間懲罰成本構(gòu)成；約束（2）表示每個客戶節(jié)點只能被卡車或無人機訪問一次；約束（3）確保卡車恰好離開和返回配送網(wǎng)點一次；約束（4）表示卡車對每一客戶點進出度相同；約束（5）表示無人機對每一客戶點進出度相同；約束（6）表示每架無人機對卡車停靠點進出度相同且只訪問一次；約束（7）表示集群作業(yè)半徑限制；約束（8）表示每個集群內(nèi)需要無人機服務(wù)的客戶點數(shù)不超過所攜帶的無人機數(shù)量；約束（9）表示無人機在集群內(nèi)的配送時間為它的飛行時間加上在客戶點的服務(wù)時間；約束（10）表示卡車的等待時間為無人機在集群內(nèi)配送的最長時間；約束（11）表示當(dāng)卡車到達(dá)j點時，其消耗的時間包括卡車到達(dá)i點的總時間，加上i處的服務(wù)時間和等待時間以及卡車從i到j(luò)所花費的行駛時間；約束（12）表示無人機配送滿足客戶時間約束；約束（13）為消除卡車路徑子回路；約束（14）至（17）為變量取值范圍。

2 算法設(shè)計

本文的問題屬于NP-Hard問題，傳統(tǒng)優(yōu)化方法很難求解，因此本研究設(shè)計一個兩階段優(yōu)化算法。首先利用帶約束的改進K-means算法對普通客戶點進行聚類，選出卡車?？奎c；然后利用遺傳模擬退火算法求得卡車與無人機聯(lián)合配送最佳路線，從而求得卡車與無人機聯(lián)合配送最小總運營成本。

2.1 獲取卡車?？奎c集合

K-means算法是一種基于劃分的聚類算法，它以k為參數(shù)把數(shù)據(jù)對象分成k個簇，將相似度高的對象聚為一類，而簇間對象彼此相似度盡量低。傳統(tǒng)的K-means算法事先給定聚類數(shù)k，該點為各簇中樣本點的平均值。在本研究中，將對普通客戶進行聚類，k的最大值高達(dá)N F，最小值為N F/(g+1)，即每(g+1)個點就會形成一個集群和一個卡車?？奎c，是最理想的狀態(tài)。需要對聚類算法進行改進，修改聚類來滿足所有類型客戶的配送需求。本文將k值設(shè)為N F/(g+1)，初始卡車停靠點集合中含有配送網(wǎng)點和特定客戶點。具體實現(xiàn)過程如下：

步驟1對普通點進行K-means聚類，得到k個聚類中心。

步驟2將每個聚類中心移至最近的節(jié)點處作為卡車?？奎c，首先考慮約束（7）進行篩選，超過里程限制的普通點加入停靠點集合。若簇內(nèi)的普通點滿足約束（8），轉(zhuǎn)步驟4，不滿足轉(zhuǎn)步驟3。

步驟3超過無人機數(shù)量限制時選擇客戶遵循優(yōu)先滿足離配送網(wǎng)點最遠(yuǎn)距離原則，未被選上的普通點加入?？奎c集合。

步驟4將每個集群內(nèi)的卡車停靠點移至最近的配送網(wǎng)點或特定點處，同時考慮約束（7）和（8）。集群內(nèi)的普通點沒有減少，則將該集群的停靠點轉(zhuǎn)移到配送網(wǎng)點或特定點處，不滿足則不轉(zhuǎn)移保持現(xiàn)狀。

步驟5含有α個普通點的集群嘗試與最近的集群合并，見公式（18）。以滿足兩個約束條件為前提，?？奎c為普通點的集群并入?？奎c為特定點或配送網(wǎng)點的集群，?？奎c到配送網(wǎng)點較遠(yuǎn)的集群并入?？奎c到配送網(wǎng)點近的集群中。

步驟6輸出優(yōu)化后的卡車停靠點集合。

帶約束的改進K-means聚類算法既滿足了無人機續(xù)航和數(shù)量限制，還能不斷調(diào)整卡車?？奎c移動到合適的客戶點處。與傳統(tǒng)的K-means聚類算法相比，不需要考慮初始值的選取對聚類結(jié)果的影響。

2.2 優(yōu)化聯(lián)合配送路線

遺傳算法的基本思想是借鑒自然界中“物競天擇、適者生存”的法則，應(yīng)用適應(yīng)度對個體進行評估篩選來尋找問題的滿意解，是具有自適應(yīng)能力的、全局性的概率搜索算法。因其尋優(yōu)能力強，可靠性較高，已被用于求解許多車輛路徑問題。同時遺傳算法容易出現(xiàn)過早收斂的問題，在進化后期搜索效率較低，不易得到最優(yōu)解。模擬退火算法是以單個個體為對象，基于上一代個體進行迭代，局部收斂特性良好，但全局搜索能力不太強。因此，本文將這兩種算法相結(jié)合可以優(yōu)勢互補，設(shè)計遺傳模擬退火算法來優(yōu)化卡車與無人機聯(lián)合配送路徑問題，提高求解效率。遺傳模擬退火算法具體操作步驟如下。

（1）設(shè)置初始化參數(shù)：種群規(guī)模N、最大迭代次數(shù)M、交叉概率pc、變異概率pm、初始溫度T、溫度冷卻系數(shù)λ。

（2）生成初始種群：卡車?？奎c編號為順序?qū)條染色體編碼，隨機生成N條長度為k的染色體（k為卡車?？奎c數(shù)）。

（3）計算個體適應(yīng)度：適應(yīng)度函數(shù)是用來度量群體中染色體的優(yōu)良程度，適配值越大則個體越優(yōu)。本文的目標(biāo)函數(shù)是求成本最小化，所以根據(jù)公式（1）計算出每種卡車與無人機聯(lián)合配送方案的總運營成本，以其倒數(shù)作為適應(yīng)度f i。

（4）遺傳算子：為選擇算子、交叉算子和變異算子。本文采用輪盤賭的方法選擇出當(dāng)前種群中適應(yīng)度高的個體，以pc的概率利用單點交叉方式生成子代。為了維持種群的多樣性，本文按pm概率對個體進行變異。經(jīng)過選擇、交叉和變異操作后生成新種群，并計算新種群中個體的適應(yīng)度f i+1。

（5）模擬退火操作：根據(jù)模擬退火中Metropolis接受準(zhǔn)則，對新種群中的個體進行退火操作來實現(xiàn)新舊種群的替換，若f i+1＞f i，新個體將替換舊個體，否則的話就以p=exp((f i-f i+1)/T)的概率接受新個體。

（6）判斷終止條件：若迭代次數(shù)達(dá)到M，則停止循環(huán)輸出最優(yōu)解，否則按照T i+1=λTi降溫轉(zhuǎn)（3）。根據(jù)上述步驟，遺傳模擬退火算法流程圖如圖2所示。

圖2 遺傳模擬退火算法流程圖Fig.2 Genetic simulated annealing algorithm flow chart

3 數(shù)值實驗

算法采用Python編程來實現(xiàn)，在一臺CPU型號為AMD Ryzen 5、12 GB內(nèi)存、Windows 10操作系統(tǒng)的計算機上運行。遺傳模擬退火算法中種群規(guī)模設(shè)為50，最大迭代次數(shù)設(shè)為200，交叉概率為0.9，變異概率為0.1，初始溫度為100，降溫系數(shù)為0.98。

假設(shè)有四架無人機，無人機的固定成本為10元/架，載重為10 kg，平均飛行速度為80 km/h，最大飛行距離為12 km，卡車平均行駛速度為60 km/h。另一方面，將卡車單位行駛成本設(shè)為1.5元/km，無人機單位飛行成本設(shè)為0.18元/km，早到的時間懲罰成本為0.4元/min，晚到的時間懲罰成本為0.8元/min，每個客戶的平均服務(wù)時間為1.5 min。為方便計算，各點之間的卡車行駛距離采用曼哈頓距離，各點之間的無人機飛行距離采用直線距離。

3.1 模型與算法的驗證分析

目前，沒有針對該問題的標(biāo)準(zhǔn)測試數(shù)據(jù)，本文以Solomon算例集中的C和R為基礎(chǔ)數(shù)據(jù)，在10 km、20 km和30 km的地圖范圍內(nèi)從兩個算例中分別選擇前10、20和30個顧客節(jié)點構(gòu)成小規(guī)模算例，并對數(shù)據(jù)做適當(dāng)調(diào)整，來適應(yīng)地圖的大小。其中，確保有δ=10%的客戶需求超過無人機的載重，剩余客戶均可由無人機服務(wù)。在此對時間窗放寬限制，避免最終結(jié)果受時間懲罰成本影響較大。

為了評估本文模型的準(zhǔn)確性和兩階段算法的有效性，選用文獻[17]中的方法進行對比。首先將聚類數(shù)定為N F/(g+1)，采用傳統(tǒng)的K-means算法求出各集群的質(zhì)心，然后將質(zhì)心移動至最近的卡車服務(wù)點，從而得到卡車停靠點集合，同時考慮無人機數(shù)量和里程限制，超過限制的點由卡車配送。最后使用CPLEX求解標(biāo)準(zhǔn)的TSP模型。將結(jié)果與本文所提出的兩階段算法的計算結(jié)果進行比較，測試結(jié)果如表1所示。

通過表1可知，兩階段算法求出的結(jié)果均小于文獻[17]所采用的方法。對K-means算法進行改進加入選擇客戶優(yōu)先滿足離中心最遠(yuǎn)距離原則和合并操作可得到優(yōu)化后的卡車?？奎c集合，有效減少總運營成本。

表1 傳統(tǒng)K-means+CPLEX與兩階段算法結(jié)果對比Table 1 Comparison of results between traditional K-means+CPLEX and two-stage algorithm

3.2 案例分析

綜上分析，本文所提出的兩階段算法對卡車與無人機聯(lián)合配送優(yōu)化問題具有較好的求解性能，接下來，選取江蘇省宿遷某農(nóng)村地區(qū)來對卡車與無人機聯(lián)合配送模式進行仿真模擬。本區(qū)域有一輛卡車和四架無人機，為30個客戶提供送貨服務(wù)，具體位置分布如圖3所示。

圖3 客戶點分布Fig.3 Customer points distribution

每個客戶點的需求和時間窗隨機生成，如表2所示，其中1、3、4這3位客戶的需求超過無人機載重限制，為特定客戶點，其他客戶點均為普通客戶點。

表2 客戶點信息Table 2 Customer points information

遺傳模擬退火算法迭代到52次時算法收斂。經(jīng)過多次程序的運行，最終方案如圖4所示，最低總運營成本為263.35元，其中運輸成本為218.75元，時間懲罰成本為4.6元，大部分服務(wù)時間都在客戶要求的時間窗范圍內(nèi)，極大地提升了客戶服務(wù)水平。以上結(jié)果表明卡車與無人機聯(lián)合配送模式能夠在農(nóng)村地區(qū)有效完成配送任務(wù)。

圖4 卡車與無人機聯(lián)合配送結(jié)果Fig.4 Results of joint distribution of trucks and drones

為了驗證遺傳模擬退火算法的優(yōu)劣，采用傳統(tǒng)的遺傳算法對模型求解，參數(shù)設(shè)置不變，結(jié)果對比如圖5所示。從圖5可知傳統(tǒng)遺傳算法相較于遺傳模擬退火算法有著更多的平均迭代次數(shù)，這意味著遺傳模擬退火算法在每個生成解的范圍內(nèi)有著更好的搜索精度，搜索效率更佳。而且遺傳模擬退火算法求出的解優(yōu)于傳統(tǒng)遺傳算法，這表明遺傳模擬退火算法收斂到全局最優(yōu)，沒有陷入局部最優(yōu)解中，因此遺傳模擬退火算法較傳統(tǒng)的遺傳算法有著更好的求解性能，尋優(yōu)能力更強，穩(wěn)定性更好。

圖5 收斂性能對比圖Fig.5 Convergence performance comparison chart

為了體現(xiàn)卡車與無人機聯(lián)合配送的優(yōu)越性，本文對單獨使用卡車運輸?shù)姆绞竭M行求解，結(jié)果如表3所示，最低總成本為309.4元。聯(lián)合配送模式的最終結(jié)果與僅卡車配送模式的最終結(jié)果相比降低了14.89%，這表明無人機在物流運輸方面還是有一定的優(yōu)勢，卡車與無人機聯(lián)合配送的運輸方式可有效降低物流運輸成本。

表3 卡車單獨配送結(jié)果Table 3 Individual truck delivery results

與此同時，研究特定客戶占比因子和攜帶的無人機數(shù)量對最終結(jié)果的影響，分別在有時間窗和沒有時間窗約束的情況下運行，最優(yōu)值變化如圖6、圖7所示。

通過圖6和圖7可知，特定客戶占比因子和攜帶的無人機數(shù)量均會對配送路徑目標(biāo)產(chǎn)生影響。圖6和圖7中的（a）顯示，所有貨物都可以由無人機服務(wù)時成本最少。當(dāng)δ為10%以上時成本急速上升，因此理想的做法是將特定客戶占比限制為較小的值，盡量將貨物交予無人機配送。在現(xiàn)實配送中，物流公司應(yīng)選擇能承載更重貨物的無人機來進行末端配送，減少卡車配送的幾率。

圖6 不考慮時間窗時的最優(yōu)值變化Fig.6 Optimal value change without considering time window

圖7 考慮時間窗時的最優(yōu)值變化Fig.7 Optimal value change when considering time window

圖6和圖7中的（b）顯示，不考慮時間窗時，UAV數(shù)量為2架時總運營成本最小，相較于純卡車配送成本降低11.07%；而總運營成本加入時間懲罰成本時，UAV數(shù)量為3架時最小，相較于純卡車配送總成本降低17.41%。因此，物流公司在配送規(guī)劃時應(yīng)根據(jù)不同農(nóng)村地區(qū)對時間窗的容忍度來考慮是否將時間罰金納入總運營成本中。同時，物流公司還需要根據(jù)客戶分布情況來選擇攜帶的UAV架數(shù)，而不是攜帶得越多越好，這會增加無人機成本，導(dǎo)致總運營成本的上升。

4 結(jié)束語

本文基于集群提出卡車與無人機聯(lián)合配送模式來解決農(nóng)村電商物流末端配送難題，并對問題進行定義，建立帶時間窗的混合整數(shù)規(guī)劃模型，目標(biāo)是盡可能降低總運營成本。根據(jù)問題特性，提出兩階段算法，首先對K-means算法改進求出最佳卡車停靠點，然后采用遺傳模擬退火算法優(yōu)化卡車與無人機聯(lián)合配送路線，將其與傳統(tǒng)K-means算法加CPLEX結(jié)果對比，驗證了模型的可行性和兩階段算法的有效性。仿真結(jié)果表明，遺傳模擬退火算法相比傳統(tǒng)的遺傳算法有著更好的求解性能。同時，卡車與無人機聯(lián)合配送模式與傳統(tǒng)的純卡車運輸模式相比可有效降低總運營成本，這為解決農(nóng)村地區(qū)的配送難題提供了指導(dǎo)性建議。本文只是考慮了將卡車?？奎c限制在客戶位置上，未來可以放松這一限制擴大搜索范圍找到更合適的?？奎c位置，還可以考慮卡車與無人機的其他合作模式來靈活應(yīng)對不同的場景。