路徑優(yōu)化算法在外賣配送中的應(yīng)用

蔡 林，李英冰，鄒子昕

(武漢大學(xué)測繪學(xué)院，湖北 武漢 430079)

外賣O2O近年來得到極大發(fā)展，但其主要矛盾在于對(duì)速度掌控力較弱，如何合理安排配送路線是主要因素[1]。如何從配送員或整個(gè)外賣配送網(wǎng)絡(luò)的角度提高運(yùn)送的速度，一直是值得研究的問題，而提高速度可通過對(duì)配送路線進(jìn)行優(yōu)化，達(dá)到輔助外賣配送決策與提高配送效率的目的[2]。

配送路線優(yōu)化的出發(fā)點(diǎn)是要幫助配送員選出最優(yōu)或較優(yōu)路線方案，高效率地去往不同餐廳點(diǎn)和客戶所在地，從而節(jié)省配送時(shí)間，提高消費(fèi)者滿意度。許多學(xué)者在這方面展開了相關(guān)研究。文獻(xiàn)[3]通過分析餐飲O2O外賣客戶滿意度的特點(diǎn)，基于傳統(tǒng)的取送貨車輛路徑問題模型，提出一個(gè)適合餐飲O2O外賣配送的優(yōu)化模型，并提出了能夠有效求解該模型的啟發(fā)式算法，盡可能提高大量客戶的時(shí)間滿意度。文獻(xiàn)[4]通過利用聯(lián)合調(diào)度解決預(yù)訂模式和即時(shí)模式下的外賣生產(chǎn)配送問題，將多車多路徑配送和時(shí)間窗約束引入生產(chǎn)配送聯(lián)合調(diào)度模型中，主要為訂餐高峰期商家進(jìn)行訂單處理提供決策支持。文獻(xiàn)[5]設(shè)計(jì)一種考慮動(dòng)態(tài)需求的外賣配送路徑優(yōu)化模型及算法，基于同時(shí)送取貨VRP問題的求解策略,引入時(shí)間懲罰成本等,通過將商家與客戶進(jìn)行配對(duì)，并對(duì)其進(jìn)行聚類，對(duì)同一類設(shè)計(jì)遺傳算法，從而獲得啟發(fā)式路徑優(yōu)化方案。針對(duì)外賣配送的安全性，文獻(xiàn)[6]利用煙花算法解決在其情況下的路徑優(yōu)化問題。

目前現(xiàn)有大多數(shù)文獻(xiàn)均從多配送員多訂單的外賣配送網(wǎng)絡(luò)角度進(jìn)行研究，沒有考慮從一個(gè)配送員在平臺(tái)上已接收的自不同餐廳訂單的角度出發(fā)，速度一定的情況下，以時(shí)間最短為目標(biāo)確定最優(yōu)配送路線。因此本文從配送員角度出發(fā)，提出一種具有順序限制的最短路徑優(yōu)化算法，以達(dá)到對(duì)配送員到達(dá)餐廳點(diǎn)和客戶點(diǎn)的先后順序進(jìn)行協(xié)調(diào)安排的目的。

1 外賣配送路徑的問題描述

外賣配送問題實(shí)際上是一個(gè)特殊的TSP問題(旅行商問題)，TSP是路徑規(guī)劃及組合優(yōu)化領(lǐng)域的NP問題。問題的大致描述是：假設(shè)一個(gè)商人要拜訪n個(gè)城市，必須選擇所要走路線，路線限制條件是每個(gè)城市只能拜訪一次，且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是要求的路徑路程為所有路線方案中的最小值。目前已有大量文獻(xiàn)對(duì)TSP問題進(jìn)行研究[7]，側(cè)重的研究點(diǎn)主要為結(jié)合多種優(yōu)化機(jī)制設(shè)計(jì)啟發(fā)式混合算法和提升求解算法的效率與精度[8]。

TSP在實(shí)際生活中有許多應(yīng)用，如旅游路線規(guī)劃[9]、車間調(diào)度[10]、物流配送[11]等，雖然這些問題源于TSP，但又與標(biāo)準(zhǔn)的TSP有所區(qū)別。如在物流配送行業(yè)，特別是外賣配送行業(yè)中，對(duì)路線的選擇目標(biāo)是要求經(jīng)過每一個(gè)待配送點(diǎn)且總長度盡可能最短。與標(biāo)準(zhǔn)TSP問題不同的是這類問題通常有一個(gè)特定的起點(diǎn)，即配送運(yùn)輸工具當(dāng)前所在位置；同時(shí)最優(yōu)路線不要求是一個(gè)回路，即起始點(diǎn)與終點(diǎn)不一定要相同；除此之外，最重要的是各個(gè)中間節(jié)點(diǎn)往往有訪問順序的要求，即某些節(jié)點(diǎn)必須在訪問過另一些節(jié)點(diǎn)以后，才能夠被訪問。在外賣配送過程中，配送員同時(shí)接到多家餐廳的配送訂單，這些訂單對(duì)應(yīng)不同待配送客戶，此時(shí)配送員希望能夠找出一條最優(yōu)路徑，到達(dá)所有的餐廳點(diǎn)和用戶所在地，且某家餐廳必須要在其對(duì)應(yīng)的用戶所在地之前到達(dá)。本文將這類問題稱為具有順序限制的TSP問題。

假設(shè)a1為規(guī)定的起始點(diǎn)，某個(gè)可行解的路線表示為：S=a1b1a3a2b2b3，即相同下標(biāo)的字母，a必須出現(xiàn)在b之前。用da1b1表示a1點(diǎn)到b1點(diǎn)的距離，設(shè)各點(diǎn)的距離為歐氏距離，滿足三角不等式，且da1b1=db1a1。某個(gè)可行解的總長度用D表示，對(duì)于前述的S路線，其總長度為：D=da1b1+db1a3+…+db2b3。D為配送的總路線長度，但不同的配送路線使其長度不同，如何從眾多種路線中尋找一個(gè)最優(yōu)解即本文需解決的問題。

2 具有順序限制的TSP問題優(yōu)化解法

2.1 生成初始路線

當(dāng)一個(gè)配送員接收所有訂單后，有餐廳位置和客戶位置，需在此基礎(chǔ)上進(jìn)行初始路線的生成，初始路線的生成采用最鄰近算法。最鄰近算法采用一種廣度優(yōu)先的最短優(yōu)先思想[12]，只是在搜索過程中必須滿足順序限制，即餐廳點(diǎn)必在對(duì)應(yīng)的客戶點(diǎn)之前。

采用算法生成初始路線步驟如下：

(2) 建立路徑隊(duì)列S，將起始點(diǎn)a1插入S中。

(3) 從P中選擇距當(dāng)前點(diǎn)最近的一個(gè)點(diǎn)xi作為該路線的下一點(diǎn)，將此點(diǎn)從P中刪除，并放入S的末尾。

(4) 若xi∈A，則將?bi∈B加入P中；否則，轉(zhuǎn)入步驟(5)。

(5) 若P=?，則結(jié)束，S即為所求得路徑；否則，轉(zhuǎn)入步驟(3)。

經(jīng)過鄰近算法已生成一個(gè)可行解S，即配送員經(jīng)過所有餐廳且配送給客戶的初始路線，并以此解為基礎(chǔ)，進(jìn)行算法優(yōu)化。

2.2 LK算法優(yōu)化

LK算法為文獻(xiàn)[13]提出的一種局部搜索優(yōu)化算法,它是在k-opt局部搜索算法[14]的基礎(chǔ)上通過改變k來實(shí)現(xiàn)的，該算法能高效求解組合優(yōu)化問題的近似解，能使配送路線S更小化，LK算法可以與許多智能化算法在求解TSP問題組合時(shí)使用，如蟻群算法[15]。原始的LK算法是使用隨機(jī)產(chǎn)生的路徑作為算法的初始解，但文中應(yīng)用最鄰近算法生成初始解，即可行解S。

首先使用3-opt算法，算法流程如下：

(1) 從起始點(diǎn)開始，選擇一個(gè)與之相連的點(diǎn)x，選擇一條以x為頂點(diǎn)的，不屬于初始路線S的邊e1，設(shè)遠(yuǎn)端端點(diǎn)為xi。

(2) 選擇與xi相連的一個(gè)頂點(diǎn)xi+1，選擇以xi+1為端點(diǎn)的一條不屬于初始路線S的邊e2，設(shè)遠(yuǎn)端端點(diǎn)為xj。

(3) 選擇與xj相連的一個(gè)頂點(diǎn)xj+1，并連接該點(diǎn)與起始點(diǎn)之間的邊。

(4) 記d1=de1+de2+de3，d2=da1x+dxixi+1+dxjxj+1，若d1

(5) 若找完所有的點(diǎn)，且SM≠S，則用SM替換S作為當(dāng)前結(jié)果，返回步驟(1)；否則，若還未找遍所有點(diǎn)，則返回步驟(2)，從當(dāng)前點(diǎn)的下一點(diǎn)開始尋找。

(6) 若找完路徑上所有點(diǎn)，則結(jié)束，當(dāng)前的SM即為尋找出的優(yōu)化解。

2.3 使用末端-2-opt方法優(yōu)化

由于配送路線具有起始點(diǎn)且不要求最終路徑形成回路，則使用3-opt和2-opt算法所進(jìn)行的優(yōu)化不會(huì)涉及路徑上的最后一點(diǎn)，因此要對(duì)涉及末端點(diǎn)的可能優(yōu)化情況進(jìn)行單獨(dú)分析，在這里只考慮2-opt的優(yōu)化。算法步驟如下：

(2) 連接xixn，記為em1，連接xi+1xn，記為em2。

經(jīng)過最鄰近算法、LK算法、末端-2-opt算法后，得到配送員經(jīng)過餐廳地點(diǎn)和客戶點(diǎn)的一條優(yōu)良可行路線，且是具有順序限制的。

3 試驗(yàn)及分析

本文最后分別選取9個(gè)、16個(gè)、25個(gè)、52個(gè)點(diǎn)共4組試驗(yàn)數(shù)據(jù)，分別包括餐廳點(diǎn)和客戶點(diǎn)，依次利用最鄰近算法、LK算法及末端-2-opt進(jìn)行計(jì)算，結(jié)果見表1，通過比較各步驟所得路徑長度及運(yùn)行時(shí)間，評(píng)價(jià)算法的優(yōu)化效果。

表1 各算法計(jì)算結(jié)果

由表1知經(jīng)末端-2-opt算法優(yōu)化后所得長度最短,且LK算法在最鄰近算法上也有所提升，證明本文算法優(yōu)化是有效的。

以9個(gè)點(diǎn)的數(shù)據(jù)為例，各算法所畫出路徑如圖1所示。圖中圓形為餐廳點(diǎn)，三角形為客戶點(diǎn)，箭頭代表起始路線方向，數(shù)字相同的餐廳點(diǎn)與客戶點(diǎn)代表兩者存在對(duì)應(yīng)關(guān)系。從圖中可知3種算法均能有效算出一條可行解，從路徑長度方面比較，LK算法能夠優(yōu)化由最鄰近算法給出的初始路線，末端-2-opt算法能對(duì)LK算法得出的路線繼續(xù)優(yōu)化。由最鄰近算法生成初始路線，路線曲折且較長，經(jīng)過3次算法優(yōu)化后，路徑大幅度縮短，更適合配送路線方案的選擇。

4 結(jié) 語

本文從外賣配送員角度出發(fā)，提出了一種解決具有順序限制的TSP問題的優(yōu)化解法。優(yōu)化過程包括由最鄰近算法生成初始解，然后使用LK算法(3-opt、2-opt)優(yōu)化，最后使用末端-2-opt方法優(yōu)化。試驗(yàn)結(jié)果表明，該方法有效縮短了路徑的總長度，如能運(yùn)用在實(shí)際的配送行業(yè)中，將提高配送行業(yè)的工作效率，節(jié)約成本。