趙強柱，盧福強，王雷震，王素欣

1.東北大學(xué) 信息科學(xué)與工程學(xué)院，沈陽 110004

2.東北大學(xué)秦皇島分校，河北 秦皇島 066004

3.燕山大學(xué) 經(jīng)濟管理學(xué)院，河北 秦皇島 066004

近年來，隨著移動互聯(lián)網(wǎng)的普及和餐飲O2O的快速發(fā)展，陸續(xù)出現(xiàn)了餓了么、美團外賣等第三方外賣平臺，外賣點餐早已成為有別于傳統(tǒng)堂食的另一種餐飲消費模式[1-2]。外賣配送作為外賣業(yè)務(wù)從線上到線下的關(guān)鍵環(huán)節(jié)，配送路徑的規(guī)劃不僅直接決定餐品的準(zhǔn)時送達(dá)與否，而且對商家的外賣運作成本和利潤有著重要影響[3]。騎手送餐是現(xiàn)階段主要的外賣送餐方式，騎手通過騎摩托車或電動車將餐品送到消費者手中，但這種方式存在很多弊端：在交通高峰期，城市道路擁堵，導(dǎo)致送餐到達(dá)時間延誤，顧客滿意度降低；騎手配送服務(wù)范圍有限，對稍遠(yuǎn)顧客的訂單不能夠及時送達(dá)，或因超出騎手配送范圍，商家不得不拒絕接受此類訂單，導(dǎo)致顧客數(shù)量減少[4-5]。因此，如何提高餐品準(zhǔn)時送達(dá)率，減少配送成本，是外賣行業(yè)亟待解決的問題。

為適應(yīng)行業(yè)發(fā)展，餓了么、美團等外賣平臺開始逐漸將無人機應(yīng)用于外賣配送領(lǐng)域中，使無人機與騎手共同完成配送任務(wù)。2018年5月29日，餓了么宣布獲準(zhǔn)開通中國第一批無人機即時送餐航線，并在上海舉行無人機商業(yè)飛行發(fā)布會[6]，送餐無人機正式投入商業(yè)運營。目前餓了么投入使用的無人機最高飛行速度為65 km/h，最大載重可達(dá)10 kg，滿載續(xù)航距離最遠(yuǎn)為20 km。配送過程中，無人機主要承擔(dān)集散點A到B的干線運輸，兩名騎手則分別負(fù)責(zé)將外賣餐品裝運上飛機和將餐品送達(dá)消費者手中。因此，無人機騎手聯(lián)合外賣配送的路徑優(yōu)化問題研究具有非?，F(xiàn)實的研究背景和十分重要的研究意義。

目前，雖然沒有對無人機騎手聯(lián)合外賣配送的模式的研究，但國內(nèi)外學(xué)者對外賣配送路徑優(yōu)化問題的研究不少。翟勁松等[7]在單配送中心情景中以總行駛時間最小為目標(biāo)進行帶有硬時間窗的外賣配送研究；Liao等[8]研究了一種將外賣配送與車輛路徑問題相結(jié)合的綠色配送路徑問題，提出了以最大顧客滿意度、最優(yōu)騎手平衡利用率、最少碳排放為目標(biāo)的多目標(biāo)綠色配送路徑模型；Naccache等[9]構(gòu)建了考慮時間窗的多個取送貨點車輛路徑問題模型，分別使用改進的自適應(yīng)大鄰域搜索算法（ALNS）與精確算法分支定界法對算例求解；Ulmer等[10]考慮顧客下單時間的不確定性和餐品出餐時間的不確定性，研究隨機動態(tài)取送貨問題；陳萍等[11]以時間滿意度為目標(biāo)，考慮外賣的取送貨次序約束，并據(jù)此設(shè)計遺傳算法，最終實驗得出統(tǒng)一取貨再集中配送的優(yōu)化結(jié)果；李桃迎等[12]以外賣配送成本增量總和為目標(biāo)，以聚類為手段，將多配送員外賣配送問題轉(zhuǎn)化為單配送員問題，并依托遺傳算法實現(xiàn)問題求解；張力婭等[13]基于O2O外賣平臺的配送現(xiàn)狀分析，引入外賣平臺顧客優(yōu)先級概念，從顧客滿意度和配送成本兩個角度出發(fā)，建立了考慮客戶優(yōu)先級的、帶時間窗的、動態(tài)的、多車場多目標(biāo)取送貨車輛路徑模型，采用加權(quán)法將多目標(biāo)轉(zhuǎn)化成單目標(biāo)，并設(shè)計改進的迭代局部搜索算法對模型進行求解。

綜上，雖然現(xiàn)有文獻對外賣配送路徑優(yōu)化問題從不同的考慮因素上均有研究，但這些文獻的研究背景都是僅騎手配送的單一配送模式。結(jié)合實際商業(yè)案例，考慮到國內(nèi)外賣的應(yīng)用場景和城市建筑物密集復(fù)雜、不具備無人機入戶定點投放等特點，本文以最小化送餐成本為目標(biāo)建立了無人機騎手聯(lián)合外賣配送的路徑優(yōu)化模型，并設(shè)計了一種引入時空距離的兩階段啟發(fā)式算法進行求解。在第一階段，基于時空距離的度量，運用結(jié)合K-means算法的遺傳算法對顧客聚類，得到騎手的初始路徑；第二階段，以最小送餐成本為目標(biāo)對騎手送餐路徑和無人機送餐航跡優(yōu)化。

1 問題描述及假設(shè)

傳統(tǒng)的僅騎手外賣配送模式如圖1（a）所示，騎手在商家取餐后直接送至顧客手中。在送餐時，由于騎手往往憑借經(jīng)驗對顧客逐個配送，通常不能實現(xiàn)最短路徑的配送方案；另一方面，騎手在憑借經(jīng)驗規(guī)劃路徑時大多只考慮了顧客的地理位置，而忽略了訂單的下單時間，產(chǎn)生的配送方案有可能對時間窗寬松、距離商家較近的顧客先行配送，而對時間窗緊迫、距離商家較遠(yuǎn)的顧客稍后配送進而導(dǎo)致餐品不能準(zhǔn)時送達(dá)。

圖1 僅騎手配送模式和無人機騎手聯(lián)合送餐模式圖Fig.1 Schematic diagram of riders only delivery mode and drones and riders joint delivery mode

本文研究的無人機騎手聯(lián)合外賣配送如圖1（b）所示，商家在某一時段接收顧客訂單，出餐后統(tǒng)一將多份餐品送至無人機上，無人機避開障礙物將餐品送至某個顧客點附近（無人機降落點），騎手取出餐品后按照預(yù)先規(guī)劃好的路徑將餐品送至各個顧客手中。

根據(jù)無人機騎手聯(lián)合外賣配送的實際案例，本文做出如下假設(shè)：

（1）由于電動車行駛距離約為50 km，遠(yuǎn)大于一次送餐的行駛距離，故不考慮電動車的續(xù)航問題。

（2）由于無人機滿載續(xù)航約為20 km，足夠飛行往返完成一次送餐任務(wù)，故不考慮無人機的續(xù)航問題。

（3）無人機的飛行速度、電動車的行駛速度恒定。

（4）將每份餐品的質(zhì)量與體積視為單位固定值。

（5）對每個顧客的送餐服務(wù)時間視為固定值。

（6）在騎手在送餐過程中，不考慮天氣時況、交通狀況或其他意外事件。

（7）送餐電動車和無人機均有容量限制，且無人機最大容量等于電動車最大容量。

2 模型構(gòu)建

符號定義如下：

K={k1,k2,…,k m}：騎手所駕駛的電動車的集合；

V={v0,v1,…,v n}：商家與顧客的集合，其中v0表示商家，v1,v2,…,v n表示n個顧客；

G={g1,g2,…,g m}：無人機?？奎c集合，G?V；

t i：騎手騎行電動車到達(dá)顧客i時的時間；

t s：對每個顧客的送餐服務(wù)時間；

d ij：顧客i與顧客j之間的空間距離；

s：騎手所駕駛電動車的平均速度；

t ijk：表示騎手k從顧客點i到顧客點j之間所用時間；

qi：顧客i下單的外賣量；

[0,T i]：顧客i的時間窗，T i表示顧客i的預(yù)期送達(dá)時間；

Q：單個送餐無人機的最大裝載量；

a：騎手所駕駛電動車的單位距離運輸成本；

b：無人機送餐時的單位距離運輸成本；

xijk：決策變量，若騎手k從顧客點i到顧客點j時為1，否則為0。

本文以最小化送餐成本作為目標(biāo)函數(shù)建立模型，送餐成本包括三部分，即電動車運輸成本、無人機運輸成本以及懲罰成本。其中懲罰成本P i表示如下：

本文采用分階段懲罰函數(shù)來刻畫懲罰成本。當(dāng)騎手在顧客i的時間窗內(nèi)到達(dá)顧客i時，即t i≤T i時，無懲罰成本；當(dāng)騎手超過預(yù)期送達(dá)時間到達(dá)顧客i時，顧客的滿意度會下降，因此出現(xiàn)了懲罰成本，c1為此階段的單位時間懲罰成本；設(shè)定一個最遲送達(dá)時間T i′，令T i′＞T i，當(dāng)?shù)竭_(dá)時間超過最遲送達(dá)時間Ti′，顧客滿意度會急劇下降，懲罰成本急劇增加，c2為此階段的單位時間懲罰成本，c2＞c1＞0。外賣送達(dá)時間t i與懲罰成本Pi關(guān)系如圖2所示。

圖2 懲罰成本函數(shù)Fig.2 Punishment cost function

最小化送餐成本的目標(biāo)函數(shù)如式（2），等式右邊三項分別為送餐時電動車的運輸成本、無人機運輸成本和懲罰成本。

式（3）和式（4）共同表示一個顧客只能由一個騎手進行一次送餐服務(wù)；式（5）表示騎手不能由無人機?？奎c直接開往另一個無人機?？奎c；式（6）表示所有的騎手必須從無人機?？奎c出發(fā)；式（7）確保騎手在起始點和結(jié)束點之間的路徑是連續(xù)的：式（8）表示送餐時的載貨量約束；式（9）為簡單圈約束，消除路徑中的子回路。將約束（6）改寫為表示騎手須從商家出發(fā)最終回到商家，上述模型即為僅騎手配送模式下的騎手路徑模型。

3 兩階段啟發(fā)式算法設(shè)計

針對無人機騎手聯(lián)合外賣配送場景下的路徑優(yōu)化問題，本文設(shè)計了一種兩階段啟發(fā)式算法進行求解。第一階段構(gòu)造騎手初始路徑，先對顧客點基于時空距離進行度量，在此基礎(chǔ)上采用結(jié)合K-means算法的遺傳算法對顧客訂單聚類，根據(jù)時空距離遠(yuǎn)近構(gòu)造騎手初始路徑。第二階段路優(yōu)化騎手路徑和無人機航跡，考慮到變鄰域搜索算法在求解大規(guī)模組合優(yōu)化問題時具有求解快速和易實現(xiàn)的特點，本文在傳統(tǒng)鄰域算子的基礎(chǔ)上，針對外賣配送的特點設(shè)計了幾種鄰域算子，用于優(yōu)化騎手路徑；A*算法是一種靜態(tài)路網(wǎng)中常用的有向圖啟發(fā)式搜索算法，因為具有計算效率高、易實現(xiàn)、內(nèi)存需求少、靈活性高等優(yōu)點，被廣泛應(yīng)用在航跡規(guī)劃和圖搜索領(lǐng)域中，本文根據(jù)無人機避障問題的特點對A*算法加以改進，用于送餐無人機的航跡規(guī)劃。兩階段算法框架如圖3所示。

圖3 兩階段算法框架Fig.3 Two-stage algorithm framework

3.1 構(gòu)造考慮時空距離的初始路徑

3.1.1 時空距離的定義

絕大多數(shù)的聚類算法在對顧客或配送點進行聚類時，通常只考慮了顧客點之間的地理位置這一因素，而并未將顧客點間的服務(wù)時間窗的差異考慮在內(nèi)。然而在實際配送過程中，如果只考慮顧客的空間分布，將位置距離近的顧客安排在同一條路徑上進行配送，當(dāng)顧客點的服務(wù)時間窗差異較大時，則可能造成餐品不能準(zhǔn)時送達(dá)；同理，如果只考慮顧客的時間窗，將時間窗相似的顧客安排在同一條路徑上進行配送，當(dāng)顧客空間距離相隔較遠(yuǎn)時，則可能無法達(dá)到最優(yōu)解甚至可行解?；诖耍疚脑跇?gòu)造騎手送餐的初始路徑時，同時考慮了顧客點的時間屬性和空間屬性。由于時間距離和空間距離的量綱不一致，本文基于文獻[14]的研究構(gòu)造時空距離，公式如下：

（1）若l i′＜e j，即騎手從顧客點i行駛至顧客點j后需要等待才能開始對顧客j的送餐服務(wù)，則顧客i與顧客j的時間距離可表示為行駛時間與平均等待時間之和，即

圖4 顧客點間的時間窗關(guān)系示意圖Fig.4 Schematic diagram of time window relationship between customer points

（2）若ei′＜e j≤l i′，即騎手有可能提前到達(dá)顧客點j，也有可能在顧客j的服務(wù)時間窗內(nèi)到達(dá)，參考（1）的度量方法，顧客點i與顧客點j的時間距離可表示為

（3）若e j≤ei′且l i′≤l j，即騎手到達(dá)顧客點i的時刻完全位于顧客j的服務(wù)時間窗內(nèi)，則將顧客點i與顧客點j的時間距離設(shè)為從顧客點i到顧客點j的行駛時間，即

（5）若l j＜ei′，即騎手從顧客點i行駛至顧客點j的時間完全晚于顧客j的預(yù)期最遲送達(dá)時間，這表明將該顧客點i與顧客點j安排在同一條路徑上進行配送是不可行的，則將顧客點i與顧客點j的時間距離設(shè)為無窮大。

綜上，時間距離的計算公式如下所示：

3.1.2 顧客聚類

聚類即將特征屬性相似的個體劃歸為一組，使得組內(nèi)個體的特征屬性相似度盡可能大，而組間的盡可能小。由于K-means算法在對數(shù)據(jù)進行聚類時具有穩(wěn)健快速等特點，故K-means算法是一種常用的數(shù)據(jù)聚類方法，但由于初始聚類中心的隨機選取對聚類結(jié)果影響較大，本文采用結(jié)合K-means算法的遺傳算法對顧客聚類，目標(biāo)函數(shù)如式（12）所示，目的是使對所有的聚類簇，其他顧客點到聚類中心的時空距離之和最小。式中k為聚類數(shù)，即無人機的數(shù)量，z i為第i個聚類里的所有顧客點。

（2）根據(jù)式（11）計算顧客點間的時空距離。

（3）初始化種群。對種群中個體采用自然整數(shù)的十進制編碼，個體的長度設(shè)為k，個體的每一位代表聚類中心，根據(jù)K-means算法的思想，當(dāng)簇的中心確定時，可以根據(jù)就近原則對所有顧客分類。

（4）計算種群中個體的目標(biāo)函數(shù)值，并將其作為個體的適應(yīng)度值。

（5）種群進化。通過對個體的選擇、交叉與變異來優(yōu)化種群。

（6）判斷是否滿足終止條件。是，結(jié)束；否，返回（1）。

將時空距離替度量換為空間距離度量即為不考慮時空距離的顧客聚類。

3.1.3 騎手初始路徑的構(gòu)造

對顧客點完成聚類之后，以無人機的最大裝載量作為約束，對顧客點按照離聚類中心時空距離最近的原則（或按照離商家空間距離最近的原則）進行配送，并對超過無人機最大裝載量約束的顧客點重新分配，對每個聚類簇的初始路徑構(gòu)造如下：

（1）選取離聚類中心時空距離最近的顧客點并將其配送任務(wù)指派給騎手。

（2）以無人機最大裝載量為限制條件對剩余顧客點按時空距離由小到大依次進行指派，對違反無人機裝載量約束限制的顧客點執(zhí)行步驟（3）。

（3）按照該顧客點與其余無人機?？奎c時空距離由小到大的順序，依次檢測其他聚類簇的無人機剩余裝載量是否滿足該顧客點的送餐量需求，若滿足，則將顧客點指派給該聚類簇；否則，令k=k+1，并將該顧客點劃歸到一個新的聚類簇中。

（4）檢測是否還有未進行指派的訂單，若有，則返回（1）；若無，結(jié)束并輸出初始路徑。

如對顧客點按照離商家空間距離最近的原則進行配送，即為不考慮時空距離時僅騎手配送模式下的騎手初始路徑構(gòu)造。

3.2 騎手路徑優(yōu)化

3.2.1 變鄰域搜索算法

變鄰域搜索算法是一種基于局部搜索的元啟發(fā)式算法，其基本思想是在搜索過程中系統(tǒng)地改變當(dāng)前解的鄰域結(jié)構(gòu)以擴展搜索范圍，接著通過局部搜索求得局部最優(yōu)解，基于此局部最優(yōu)解重復(fù)上述過程，經(jīng)過若干次迭代之后最終達(dá)到收斂的目的。本文在傳統(tǒng)的變鄰域搜索算法的基礎(chǔ)上，結(jié)合外賣配送過程中顧客位置臨近、送餐時間窗相似等特點，對傳統(tǒng)鄰域結(jié)構(gòu)和局部搜索算子進行改進。圖5描述了變鄰域算法的基本流程，其中x b表示當(dāng)前時刻的最優(yōu)解，F(xiàn)(x)表示任意解x的目標(biāo)函數(shù)值。本文在求解過程中，通過以一定概率接受較差解的方法擴大解空間，從而提升算法跳出局部最優(yōu)解的能力。

圖5 變鄰域搜索算法流程Fig.5 Flow chart of VNS

3.2.2 鄰域構(gòu)造

為了擴展當(dāng)前解的搜索空間，擴大解的多樣性，減少算法陷入局部最優(yōu)的可能性，本文采用Relocate和Exchange兩種鄰域結(jié)構(gòu)。Relocate表示在某條路徑上選取一個或幾個連續(xù)的節(jié)點，從當(dāng)前路徑隨機轉(zhuǎn)移到另一條路徑中；Exchange表示在任意兩條路徑上交換數(shù)量相同的連續(xù)節(jié)點。兩種鄰域結(jié)構(gòu)分別如圖6所示。

圖6 兩種鄰域結(jié)構(gòu)Fig.6 Two neighborhood structures

3.2.3 局部搜索

在鄰域結(jié)構(gòu)抖動后，運用局部搜索對產(chǎn)生的新的路徑進行優(yōu)化，求得局部最優(yōu)解。本文采用Insert、2-opt和Reverse三種局部搜索算子，Insert表示把一個或幾個連續(xù)的節(jié)點插入到這條路徑上的其他位置，2-opt表示在同一條路徑上選取任意兩點位置互換，Reverse表示在一條路徑選取幾個連續(xù)的節(jié)點進行倒序。三種局部搜索算子如圖7所示。

圖7 三種局部搜索算子Fig.7 Three local search operators

3.2.4 新解的接受策略

為了進一步提升算法跳出局部最優(yōu)的能力，本文借鑒模擬退火算法的解的接受規(guī)則，以一定的概率接受較差解，避免算法過早地陷入局部最優(yōu)。令x表示當(dāng)前解，x2為x經(jīng)過鄰域抖動和局部搜索之后的局部最優(yōu)解，令ΔF=F(x2)-F(x)，若ΔF≤0則進一步比較F(x2)與F(xb)的大小關(guān)系；若ΔF＞0，則以一定的概率p=e-ΔF/T接受x2并更新當(dāng)前解x至x2。為了使算法在迭代初期跳出局部最優(yōu)的能力較強而在迭代末期算法趨于穩(wěn)定，本文令溫度T線性變化，迭代第r次后，T=Tmax(1-r R)，其中Tmax為初始溫度，R為最大迭代次數(shù)。

3.3 送餐無人機避障航跡規(guī)劃

在無人機越來越多地應(yīng)用于送餐、航拍等民用領(lǐng)域的同時，相關(guān)部門也制定了若干無人機飛行管理規(guī)定，考慮到城市建筑物高度可能大于無人機飛行高度等情況，規(guī)避障礙物成為了無人機路徑規(guī)劃中十分重要的一個方面。無人機在巡航時要與規(guī)避對象保持一定的安全距離，即留有安全裕度l。由于城市中的高樓形狀規(guī)則，因此為了簡化飛行環(huán)境，可以在立體平面中取飛行平面，在二維平面中進行無人機航跡規(guī)劃。A*算法是一種靜態(tài)路網(wǎng)中常用的有向圖啟發(fā)式搜索算法，因為它計算效率高、易實現(xiàn)、內(nèi)存需求少、靈活性高以及對不同路況超強的適應(yīng)能力，A*算法被廣泛應(yīng)用在航跡規(guī)劃和圖搜索鄰域中。

3.3.1 A＊算法

A*算法通過搜索當(dāng)前位置的臨近節(jié)點，選取代價值最小的節(jié)點作為擴展節(jié)點加入搜索空間，新加入的節(jié)點又能產(chǎn)生新的可擴展節(jié)點，直到目標(biāo)點被選作擴展節(jié)點，再從目標(biāo)節(jié)點逆向溯源，找到從起始點到目標(biāo)點代價最小的路徑。A*算法中節(jié)點n的代價函數(shù)為：

其中，f(n)為待擴展節(jié)點的評估函數(shù)，表示從起始點經(jīng)節(jié)點n到達(dá)目標(biāo)點的估計代價，g(n)為從起始點到當(dāng)前節(jié)點n的實際代價，h(n)表示從當(dāng)前節(jié)點n到目標(biāo)點的代價估值。A*算法擴展下一節(jié)點時，從待選節(jié)點中選擇估計代價值f(n)最小的節(jié)點插入到路徑鏈表中。

針對二維平面無人機避障航跡規(guī)劃問題，本文對A*算法做如下設(shè)計。設(shè)置無人機的起飛點S和降落點G和各障礙區(qū)域的節(jié)點信息，建立兩個存儲節(jié)點信息的空列表OPEN LIST和CLOSE LIST。由于目標(biāo)是使無人機飛行距離最小，故式（13）中考慮的代價是無人機的航程，g(n)表示從起飛點S到節(jié)點n避過障礙物的已飛航程，h(n)表示不考慮障礙區(qū)域從當(dāng)前節(jié)點n到降落點G的直線距離y n、y G分別為當(dāng)前節(jié)點n和降落點G的橫縱坐標(biāo)。算法具體步驟如下：

（1）輸入起飛點、降落點以及障礙區(qū)域的節(jié)點信息，判斷從起飛點到降落點直線飛行是否穿過障礙物，若是則將起飛點信息存入OPEN LIST中，轉(zhuǎn)（2）；若否則直接結(jié)束。

（2）遍歷當(dāng)前OPEN LIST，找到f(n)最小值對應(yīng)的節(jié)點并展開，即找到從該節(jié)點到降落點穿過的第一個障礙物，將該障礙物的可用節(jié)點信息放入到OPEN LIST中，同時把OPEN LIST中已展開的節(jié)點放入到CLOSE LIST中。

（3）重復(fù)（2），當(dāng)OPEN LIST中的展開點與降落點之間沒有障礙物（即障礙物的節(jié)點信息為空）或OPEN LIST為空時結(jié)束循環(huán)。

3.3.2 航跡修復(fù)

通過上述過程得到航跡可能存在從起飛點到路徑中某個節(jié)點直線連接不穿過障礙區(qū)域的情況，因此需要對上一小節(jié)所得的航跡做檢查修復(fù)。如圖8所示，假設(shè)得到的航跡節(jié)點序列為X=[X1,X2,…,X n]，如果從節(jié)點X i到節(jié)點X k(1≤i＜k≤n)直線飛行不經(jīng)過障礙物，則節(jié)點X i與節(jié)點X k之間的所有節(jié)點都是冗余節(jié)點，將冗余節(jié)點從航跡節(jié)點序列中刪除。遍歷所有節(jié)點，把刪除冗余節(jié)點后的序列作為修復(fù)后航跡節(jié)點序列。

圖8 航跡修復(fù)示意圖Fig.8 Schematic diagram of track correct

對航跡檢查修復(fù)后可以規(guī)劃出一條由航跡節(jié)點依次連接而成的無人機折線飛行路徑，但在航跡節(jié)點處存在轉(zhuǎn)折角，由于四旋翼無人機具備空中懸停功能，不用考慮最大轉(zhuǎn)彎角和最小轉(zhuǎn)彎半徑約束。

綜上，送餐無人機避障航跡規(guī)劃的算法流程如圖9。

圖9 無人機航跡規(guī)劃算法流程Fig.9 Flow chart of drone track planning

4 實驗結(jié)果及分析

4.1 算例說明與參數(shù)設(shè)置

由于目前還沒有關(guān)于外賣配送的標(biāo)準(zhǔn)案例，本文以武漢市某美團外賣商家為研究對象，獲取該商家在12：00至12：30時間段內(nèi)接收的外賣訂單數(shù)據(jù)，生成訂單數(shù)量分別為25、30、35、40、45的五組算例作為實際案例進行計算。外賣一般送達(dá)時間為45 min，在30 min內(nèi)接收若干訂單后，餐品的預(yù)期送達(dá)時間還剩15～45 min，考慮到餐品出餐、包裝等過程，本文將配送時預(yù)期送達(dá)時間Ti的最小值設(shè)為10 min，最大值設(shè)為40 min，最遲送達(dá)時間Ti′=Ti+10。實驗參數(shù)設(shè)置如下：t s=2 min，s=40 km/h，Q=10，a=0.2，b=0.3，c1=0.5，c2=1，l=10 m。算法編程采用MATLAB R2018b，操作系統(tǒng)為Windows 10，電腦內(nèi)存為8 GB，CPU為Intel i7-7700M，主頻3.60 GHz。

4.2 實驗結(jié)果對比分析

為了驗證聚類時考慮時空距離對于減少配送成本和提高準(zhǔn)時送達(dá)率的有效性以及無人機騎手聯(lián)合外賣配送模式相較于僅騎手配送模式的優(yōu)越性，本文通過對上述五組算例R1（25）、R2（30）、R3（35）、R4（40）、R5（45）分別在不考慮時空距離和考慮時空距離的情況下進行求解，實驗結(jié)果如表1、表2所示。

表1 不考慮時空距離的實驗結(jié)果Table 1 Results without considering temporal-spatial distance

表2 考慮時空距離的實驗結(jié)果Table 2 Results considering temporal-spatial distance

可以看出，不論是僅騎手配送模式還是無人機騎手聯(lián)合配送模式，對同一算例而言，考慮時空距離后的送餐成本更少、準(zhǔn)時送達(dá)率更高；此外，不論是否考慮時空距離，對于同一算例而言，與僅騎手配送模式相比，無人機騎手聯(lián)合配送模式下的送餐成本更少，送達(dá)準(zhǔn)時率更高。實驗結(jié)果證實了考慮時空距離對減少送餐成本、提高準(zhǔn)時送達(dá)率的有效性以及無人機騎手聯(lián)合外賣配送模式相較于傳統(tǒng)僅騎手配送模式的優(yōu)越性。

選取算例R3（35）對求解過程做具體說明。R3（35）訂單數(shù)據(jù)如表3所示，禁飛區(qū)位置坐標(biāo)如表4所示，商家、顧客在地圖中的位置如圖10所示。

圖10 商家、顧客在地圖中的標(biāo)識Fig.10 Merchant and customers in map

表3 訂單信息Table 3 Orders details

表4 各禁飛區(qū)對角坐標(biāo)Table 4 Diagonal coordinates of no-fly zones

分別求解在不考慮時空距離情況下僅騎手配送模式和考慮時空距離情況下無人機騎手聯(lián)合配送模式的送餐成本和準(zhǔn)時送達(dá)率。首先分別使用不考慮時空距離和考慮時空距離的K-means算法對上述顧客點進行聚類，得到騎手初始路徑，結(jié)果如表5（括號內(nèi)表示聚類中心）、表6所示。使用變鄰域搜索算法對初始路徑進行優(yōu)化，得到兩種模式下騎手的送餐方案，在僅騎手配送模式下的目標(biāo)值和準(zhǔn)時送達(dá)率分別為74.59和87.10%，在聯(lián)合配送模式下的目標(biāo)值和準(zhǔn)時送達(dá)率分別為58.71和96.77%，送餐路徑如圖11所示，具體信息見表7（括號內(nèi)表示未能準(zhǔn)時送達(dá)的訂單）。

表7 優(yōu)化后的騎手路徑Table 7 Optimized rider path

圖11 兩種模式下的騎手路徑Fig.11 Rider path in two modes

表5 聚類結(jié)果Table 5 Customer clustering

表6 騎手初始路徑Table 6 Rider initial path

以商家位置為起點、以無人機騎手聯(lián)合配送模式下的騎手出發(fā)點作為終點，使用A*算法對無人機路徑進行規(guī)劃，航跡如圖12，具體信息如表8所示。

表8 航跡節(jié)點信息Table 8 Track nodes

圖12 無人機避障航跡Fig.12 Drone obstacle avoidance track

4.3 算法性能對比分析

為驗證改進后變鄰域搜索算法（AVNS）的有效性，在考慮時空距離的無人機騎手聯(lián)合外賣配送模式下，對上述R1、R3、R5三種不同規(guī)模的實驗案例，再分別使用變鄰域搜索算法（VNS）、遺傳算法（GA）和蟻群算法（ACO）進行求解，各運行50次，實驗結(jié)果如表9所示。對比四種算法的求解結(jié)果，發(fā)現(xiàn)在計算時間上，AVNS算法并非最短，但在任意一個算例下，AVNS算法均能收斂到較好的最優(yōu)解，并且GA、ACO和VNS求得的最差值、平均值、標(biāo)準(zhǔn)差和平均準(zhǔn)時率明顯差于AVNS算法，這意味著AVNS算法較其他三種算法有更好的穩(wěn)定性。上述實驗結(jié)果證實了改進后變鄰域搜索算法在求解外賣配送路徑優(yōu)化問題時的合理性及有效性。

表9 算法實驗結(jié)果對比Table 9 Comparison of algorithm experimental results

5 結(jié)束語

本文根據(jù)外賣配送領(lǐng)域出現(xiàn)的一種新興的配送模式，以最小配送成本為目標(biāo)構(gòu)建了無人機騎手聯(lián)合外賣配送模式的路徑優(yōu)化問題模型。針對模型設(shè)計了一種先聚類后優(yōu)化的兩階段啟發(fā)式算法，使用考慮了時空距離的K-means算法對顧客點聚類，分別使用改進的變鄰域搜索算法與A*算法對騎手路徑與無人機航跡進行規(guī)劃，通過多組算例實驗結(jié)果對比分析驗證了聚類時考慮時空距離對較少配送成本的有效性以及無人機騎手聯(lián)合外賣配送模式相較于僅騎手配送模式的優(yōu)越性。最后通過求解從武漢某美團外賣商家獲取的實際算例，驗證了本文提出的兩階段算法在真實外賣配送情景中的有效性。當(dāng)前研究還存在一些有待改進之處，如：考慮多個商家共同配送、考慮出餐時間的不確定性、考慮無人機在三維空間中的路徑規(guī)劃、考慮顧客滿意度等，在后續(xù)的研究中將重點考慮這些因素。