無(wú)人機(jī)騎手聯(lián)合外賣(mài)配送路徑優(yōu)化問(wèn)題研究

趙強(qiáng)柱，盧福強(qiáng)，王雷震，王素欣

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（3）無(wú)人機(jī)的飛行速度、電動(dòng)車(chē)的行駛速度恒定。

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

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

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

（7）送餐電動(dòng)車(chē)和無(wú)人機(jī)均有容量限制，且無(wú)人機(jī)最大容量等于電動(dòng)車(chē)最大容量。

2 模型構(gòu)建

符號(hào)定義如下：

K={k1,k2,…,k m}：騎手所駕駛的電動(dòng)車(chē)的集合；

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

G={g1,g2,…,g m}：無(wú)人機(jī)?？奎c(diǎn)集合，G?V；

t i：騎手騎行電動(dòng)車(chē)到達(dá)顧客i時(shí)的時(shí)間；

t s：對(duì)每個(gè)顧客的送餐服務(wù)時(shí)間；

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

s：騎手所駕駛電動(dòng)車(chē)的平均速度；

t ijk：表示騎手k從顧客點(diǎn)i到顧客點(diǎn)j之間所用時(shí)間；

qi：顧客i下單的外賣(mài)量；

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

Q：?jiǎn)蝹€(gè)送餐無(wú)人機(jī)的最大裝載量；

a：騎手所駕駛電動(dòng)車(chē)的單位距離運(yùn)輸成本；

b：無(wú)人機(jī)送餐時(shí)的單位距離運(yùn)輸成本；

xijk：決策變量，若騎手k從顧客點(diǎn)i到顧客點(diǎn)j時(shí)為1，否則為0。

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

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

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

最小化送餐成本的目標(biāo)函數(shù)如式（2），等式右邊三項(xiàng)分別為送餐時(shí)電動(dòng)車(chē)的運(yùn)輸成本、無(wú)人機(jī)運(yùn)輸成本和懲罰成本。

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

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

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

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

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

3.1.1 時(shí)空距離的定義

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

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

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

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

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

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

綜上，時(shí)間距離的計(jì)算公式如下所示：

3.1.2 顧客聚類(lèi)

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

（2）根據(jù)式（11）計(jì)算顧客點(diǎn)間的時(shí)空距離。

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

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

（5）種群進(jìn)化。通過(guò)對(duì)個(gè)體的選擇、交叉與變異來(lái)優(yōu)化種群。

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

將時(shí)空距離替度量換為空間距離度量即為不考慮時(shí)空距離的顧客聚類(lèi)。

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

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

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

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

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

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

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

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

3.2.1 變鄰域搜索算法

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

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

3.2.2 鄰域構(gòu)造

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

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

3.2.3 局部搜索

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

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

3.2.4 新解的接受策略

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

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

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

3.3.1 A＊算法

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

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

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

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

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

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

3.3.2 航跡修復(fù)

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果及分析

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

由于目前還沒(méi)有關(guān)于外賣(mài)配送的標(biāo)準(zhǔn)案例，本文以武漢市某美團(tuán)外賣(mài)商家為研究對(duì)象，獲取該商家在12：00至12：30時(shí)間段內(nèi)接收的外賣(mài)訂單數(shù)據(jù)，生成訂單數(shù)量分別為25、30、35、40、45的五組算例作為實(shí)際案例進(jìn)行計(jì)算。外賣(mài)一般送達(dá)時(shí)間為45 min，在30 min內(nèi)接收若干訂單后，餐品的預(yù)期送達(dá)時(shí)間還剩15～45 min，考慮到餐品出餐、包裝等過(guò)程，本文將配送時(shí)預(yù)期送達(dá)時(shí)間Ti的最小值設(shè)為10 min，最大值設(shè)為40 min，最遲送達(dá)時(shí)間Ti′=Ti+10。實(shí)驗(yàn)參數(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 實(shí)驗(yàn)結(jié)果對(duì)比分析

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

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

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

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

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

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

表3 訂單信息Table 3 Orders details

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

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

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

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

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

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

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

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

圖12 無(wú)人機(jī)避障航跡Fig.12 Drone obstacle avoidance track

4.3 算法性能對(duì)比分析

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

表9 算法實(shí)驗(yàn)結(jié)果對(duì)比Table 9 Comparison of algorithm experimental results

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

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