趙強(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)化。
傳統(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ē)最大容量。
符號(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ā)最終回到商家,上述模型即為僅騎手配送模式下的騎手路徑模型。
針對(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.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.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ù)。
在無(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
由于目前還沒(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。
為了驗(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
為驗(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
本文根據(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)考慮這些因素。