曹英英，陳淮莉

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

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

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

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

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

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

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

1 模型構(gòu)建

1.1 問(wèn)題描述

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

圖1 配送模式對(duì)比Fig.1 Comparison of distribution modes

為方便進(jìn)行定量化研究，對(duì)問(wèn)題進(jìn)行簡(jiǎn)化，做出如下假設(shè)：

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

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

（3）無(wú)人機(jī)裝貨和更換電池時(shí)間較短忽略不計(jì)。

（4）無(wú)人機(jī)一次只能配送一個(gè)包裹，完成任務(wù)后只能返回卡車?？奎c(diǎn)，在每個(gè)集群內(nèi)只進(jìn)行一次飛行。

（5）每個(gè)客戶點(diǎn)只能由一輛卡車或一架無(wú)人機(jī)一次配送完成。

（6）卡車和無(wú)人機(jī)均勻速行駛和飛行。

1.2 符號(hào)說(shuō)明

1.3 建立模型

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

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

2 算法設(shè)計(jì)

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

2.1 獲取卡車?？奎c(diǎn)集合

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

步驟1對(duì)普通點(diǎn)進(jìn)行K-means聚類，得到k個(gè)聚類中心。

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

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

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

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

步驟6輸出優(yōu)化后的卡車?？奎c(diǎn)集合。

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

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

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

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

（2）生成初始種群：卡車停靠點(diǎn)編號(hào)為順序?qū)條染色體編碼，隨機(jī)生成N條長(zhǎng)度為k的染色體（k為卡車?？奎c(diǎn)數(shù)）。

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

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

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

（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ù)值實(shí)驗(yàn)

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

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

3.1 模型與算法的驗(yàn)證分析

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

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

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

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

3.2 案例分析

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

圖3 客戶點(diǎn)分布Fig.3 Customer points distribution

每個(gè)客戶點(diǎn)的需求和時(shí)間窗隨機(jī)生成，如表2所示，其中1、3、4這3位客戶的需求超過(guò)無(wú)人機(jī)載重限制，為特定客戶點(diǎn)，其他客戶點(diǎn)均為普通客戶點(diǎn)。

表2 客戶點(diǎn)信息Table 2 Customer points information

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

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

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

圖5 收斂性能對(duì)比圖Fig.5 Convergence performance comparison chart

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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