路徑優化算法在外賣配送中的應用

蔡 林，李英冰，鄒子昕

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

外賣O2O近年來得到極大發展，但其主要矛盾在于對速度掌控力較弱，如何合理安排配送路線是主要因素[1]。如何從配送員或整個外賣配送網絡的角度提高運送的速度，一直是值得研究的問題，而提高速度可通過對配送路線進行優化，達到輔助外賣配送決策與提高配送效率的目的[2]。

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

目前現有大多數文獻均從多配送員多訂單的外賣配送網絡角度進行研究，沒有考慮從一個配送員在平臺上已接收的自不同餐廳訂單的角度出發，速度一定的情況下，以時間最短為目標確定最優配送路線。因此本文從配送員角度出發，提出一種具有順序限制的最短路徑優化算法，以達到對配送員到達餐廳點和客戶點的先后順序進行協調安排的目的。

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

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

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

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

2 具有順序限制的TSP問題優化解法

2.1 生成初始路線

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

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

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

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

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

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

經過鄰近算法已生成一個可行解S，即配送員經過所有餐廳且配送給客戶的初始路線，并以此解為基礎，進行算法優化。

2.2 LK算法優化

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

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

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

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

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

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

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

(6) 若找完路徑上所有點，則結束，當前的SM即為尋找出的優化解。

2.3 使用末端-2-opt方法優化

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

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

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

3 試驗及分析

本文最后分別選取9個、16個、25個、52個點共4組試驗數據，分別包括餐廳點和客戶點，依次利用最鄰近算法、LK算法及末端-2-opt進行計算，結果見表1，通過比較各步驟所得路徑長度及運行時間，評價算法的優化效果。

表1 各算法計算結果

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

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

4 結 語

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