基于集群的卡車與無人機聯合配送調度研究

曹英英，陳淮莉

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

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

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

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

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

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

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

1 模型構建

1.1 問題描述

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

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

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

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

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

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

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

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

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

1.2 符號說明

1.3 建立模型

根據問題描述和參數定義，可構建以下模型：

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

2 算法設計

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

2.1 獲取卡車停靠點集合

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

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

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

步驟3超過無人機數量限制時選擇客戶遵循優先滿足離配送網點最遠距離原則，未被選上的普通點加入停靠點集合。

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

步驟5含有α個普通點的集群嘗試與最近的集群合并，見公式（18）。以滿足兩個約束條件為前提，停靠點為普通點的集群并入停靠點為特定點或配送網點的集群，停靠點到配送網點較遠的集群并入停靠點到配送網點近的集群中。

步驟6輸出優化后的卡車停靠點集合。

帶約束的改進K-means聚類算法既滿足了無人機續航和數量限制，還能不斷調整卡車停靠點移動到合適的客戶點處。與傳統的K-means聚類算法相比，不需要考慮初始值的選取對聚類結果的影響。

2.2 優化聯合配送路線

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

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

（2）生成初始種群：卡車停靠點編號為順序對N條染色體編碼，隨機生成N條長度為k的染色體（k為卡車停靠點數）。

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

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

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

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

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

3 數值實驗

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

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

3.1 模型與算法的驗證分析

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

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

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

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

3.2 案例分析

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

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

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

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

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

圖4 卡車與無人機聯合配送結果Fig.4 Results of joint distribution of trucks and drones

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

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

為了體現卡車與無人機聯合配送的優越性，本文對單獨使用卡車運輸的方式進行求解，結果如表3所示，最低總成本為309.4元。聯合配送模式的最終結果與僅卡車配送模式的最終結果相比降低了14.89%，這表明無人機在物流運輸方面還是有一定的優勢，卡車與無人機聯合配送的運輸方式可有效降低物流運輸成本。

表3 卡車單獨配送結果Table 3 Individual truck delivery results

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

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

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

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

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

4 結束語

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