外賣配送路徑優化問題研究現狀與趨勢

唐夢影 楊中華

摘? 要：外賣配送路徑優化問題一直是外賣配送研究領域的難點和熱點。由于配送成本在總成本中占有較大的占比，所以至今以來國內外學者不斷提出外賣配送路徑優化相關的目標及算法的改進以提高配送效率。為了進一步梳理國內外研究現狀，文章針對外賣配送路徑優化問題的時間窗、取送要求、隨機性、開放型等特點特性，分別針對不同類型的外賣配送路徑優化問題，從優化目標和優化算法兩個方面進行了較為全面的綜述。最后，對外賣配送路徑優化領域一些新的研究方向進行了展望。

關鍵詞：外賣配送路徑優化；帶時間窗的車輛路徑問題；取送車輛路徑問題；隨機性車輛路徑問題；開放型車輛路徑問題

中圖分類號：F713.365.1??? 文獻標志碼：A??? DOI：10.13714/j.cnki.1002-3100.2024.13.010

Abstract： The optimization of takeaway distribution path has always been the difficulty and hotspot in the research field of takeaway distribution. Since the delivery cost occupies a large proportion in the total cost， domestic and foreign scholars have been constantly proposing the improvement of objectives and algorithms related to the optimization of takeaway distribution paths in order to improve the delivery efficiency. In order to further sort out the current research status at home and abroad， a comprehensive overview is conducted from two aspects： Optimization objectives and optimization algorithms for different types of takeaway distribution path optimization problem. The optimization problem of takeaway distribution path is categorized into different types based on its characteristics such as time window， pickup and delivery requirements， randomness， and openness， etc. Finally， some new research directions in this field are prospected.

Key words： optimization of takeaway distribution path; vehicle routing problem with time windows; vehicle routing problem with pickup and delivery; stochastic vehicle routing problem; open vehicle routing problem

0? 引? 言

近年來，外賣行業發展迅速，各大外賣平臺間的競爭日益增強，每單外賣的利潤率不斷下降，對配送成本的控制成為外賣平臺運營的重點問題。外賣配送路徑的優化成為外賣平臺控制成本、吸引客流量的關鍵。

外賣配送問題是指顧客在外賣平臺上下達訂單后，配送員在服務時間窗內根據訂單信息先前往對應的商家點進行取餐，然后將餐品送達到客戶手中的路徑規劃問題。與一般的配送問題存在的區別是，外賣配送具有帶時間窗、取送要求、隨機性、開放型等特點。國內外文獻針對外賣配送中的帶時間窗約束、取送要求、路網隨機性、配送路徑開放型等特點分別進行了研究，建立了考慮不同場景的外賣路徑優化模型，并提出了針對性的求解算法。本文期望針對不同場景的外賣路徑優化問題，從模型的優化目標和算法設計等兩個方面對國內外相關文獻進行歸納，厘清外賣配送路徑優化領域的研究現狀，為學者和行業從業人員提供有益的參考與借鑒。

1? 帶時間窗的車輛路徑問題

帶時間窗的車輛路徑問題（Vehicle Routing Problem with Time Windows， VRPTW）是在傳統車輛路徑問題上引入時間窗，將客戶期望被服務的時間標識出來，從而盡量在客戶能夠接受的時間內完成配送或取貨任務，以提高物流服務水平和服務質量。外賣配送路徑優化問題是一種典型的帶時間窗的車輛路徑問題，在外賣下單成功后，外賣平臺通常都對外賣送達客戶的時間有著嚴格的規定。

1.1? 優化目標

配送成本和時間滿意度通常是帶時間窗的車輛路徑問題最關注的兩個目標。在通常的研究中，學者基于時間窗約束構建時間懲罰成本并將其納入配送總成本。將定義為類似的，蔣麗等[1]基于商家和顧客的單側軟時間要求，建立了以距離成本和時間懲罰成本之和最小為目標的外賣配送優化模型；余海燕等[2]基于O2O生鮮外賣的硬時間窗要求，解決了配送距離最小為目標的外賣問題。

與此同時，部分研究以最大化客戶時間滿意度為目標構建模型?；陬櫩推谕諘r間窗和到達客戶時間點之間的關系，陳萍等[3]利用線性函數量化顧客時間滿意度，提出了最大化客戶時間滿意度的單目標問題；在時間窗約束下，翟勁松等[4]構建了配送時間最短的單目標模型；周成昊等[5]將商圈看作配送中心，以快遞員數量和快遞員總行駛時間為最小化目標；在同時存在取餐節點時間窗和送餐節點時間窗的場景下，高椿林等[6]對員工滿意度的影響因素進行了量化分析，并將員工滿意度納入目標函數中，構建了以配送總成本、客戶滿意度、員工滿意度為目標的優化模型。

大多數外賣配送問題將優化目標定義為最大化客戶滿意度或者最小化配送成本的單目標優化問題，但是也有部分研究構建了多目標優化問題。徐肇元[7]提出了最大化客戶時間滿意度和最小化配送總成本的多目標問題。

1.2? 算法改進

在時間窗約束下，翟勁松等[4]用遺傳算法求解了配送時間最短的單目標模型；趙強柱等[8]設計了一種兩階段啟發式算法求解無人機騎手聯合外賣配送的路徑優化模型；其中第一階段是使用結合K-means的遺傳算法，綜合考慮顧客地理位置和時間窗要求計算時空距離，對顧客進行聚類，形成騎手初始路徑；第二階段是分別使用改進的變鄰域搜索算法和A*算法對騎手和無人機路徑進行優化；基于單側軟時間窗的需求，蔣麗等[1]通過設計新的狀態轉移規則和設置固定閾值來改進蟻群算法，求解需求可延遲的開放式眾包配送路徑優化問題；在硬時間窗約束下，鞠新誠[9]將配送員對道路的了解程度引入模型中，運用蟻群算法對外賣配送單目標問題進行優化；余海燕等[2]設計滾動時域延遲配送算法，解決了單目標的O2O生鮮外賣配送問題；對于同時存在取餐節點時間窗和送餐節點時間窗的情況，王海燕等[10]基于遺傳算法求解包含雙節點時間懲罰成本的單目標外賣問題；徐倩等[11]運用改進的自適應大鄰域搜索算法求解了多達4 000個節點的、以包含時間懲罰成本的物流配送平臺總成本最低為目標的外賣問題。

隨著外賣配送的發展，外賣配送的規模逐漸增大，顧客對配送時間的敏感性也逐漸增強。學者們將配送的時間要求引入到了目標函數之中，進行了客戶滿意度、時間懲罰成本的計算。徐肇元[7]將改進的SWEEP算法和改進的蟻群算法進行結合，運用結合形成的兩階段啟發式算法求解了基于客戶時間滿意度和配送總成本的多目標問題；高椿林等[6]提出基于非支配解集超體積的“HV貢獻值”的鄰域解評價策略，以及新的拆分和修復算子對自適應大鄰域搜索算法進行改進，求解以最小化配送總成本、最大化客戶滿意度和員工滿意度為目標的外賣訂單配送路徑優化模型。

2? 取送貨車輛路徑問題

在外賣配送過程中，配送員需要根據訂單要求先前往相應的商家點完成取貨任務，然后將外賣產品配送給對應的客戶點，整個過程有著嚴格的取送次序要求。針對外賣配送的取送特點，學者們也提出了不同的優化模型并以各種求解算法進行了研究。

2.1? 優化目標

針對配送車輛服務新需求需返回原點取貨的情形，陳嘉俊[12]構建了目標函數為最小化配送時間和總服務成本的優化模型；靳志宏等[13]根據不同站點的情況對取送貨任務進行分類安排，并構建了以最大化運輸效率為目標的優化模型；熊浩等[14]對取送交叉和外賣配送中多種不穩定因素的實時優化問題進行了深度分析，在優化目標中增加了騎手空駛成本和騎手等待成本兩個目標。

2.2? 算法改進

對于外賣配送中的取送流程，很多學者設計改進蟻群算法進行求解：蔣麗[1]針對“先取后送”的次序要求，在具有單側軟時間窗的開放式車輛模型中分別設置了單向路徑和雙向路徑，其中，單向路徑包含由起點指向商家的和由對應商家指向對應客戶的兩種路徑，雙向路徑指商家指向不對應客戶間的路徑；靳志宏等[13]針對離散型場站和聚集型場站分別采取一取一送和多次取餐一次送達的任務安排，并優化了蟻群算法中傳統的鄰域搜索算子，即用訂單顯示的成對的商家點與顧客點代替了單個點；鞠新誠[9]構建了考慮騎手對路網熟悉度的多取多送的路徑優化數學模型，并開發了三種特殊的鄰域搜索算子。

除了改進蟻群算法，學者們也設計了其他算法對外賣配送中的取送問題進行優化。陳嘉俊[12]基于配送車輛服務新需求需返回原點取貨的場景，同時考慮到商家會根據顧客位置決定是否進行服務的情況，研究了帶有取送貨的在線旅行商問題，針對需求點僅在正半軸和需求點在一般網絡上分別設計WAO算法和WAE算法；基于配送員在平臺上接收來自不同餐廳訂單的角度，蔡林等[15]提出了一種具有順序限制的路徑優化算法來實現配送員先取后送的次序要求，該算法首先基于最鄰近算法產生初始路徑，然后使用LK算法進行優化，最后使用末端-2-opt方法進行二次優化；陳露乾[16]設計了TS-Ropt在線算法來求解實時取送貨問題模型，其中，針對取送貨需滿足先取后送順序和取送節點成對匹配的要求，分別采用了交換點對算法和內部互換算法來實現路徑之間和路徑內部的鄰域搜素；對于取送交叉和中途接單問題，郭昊穎等[17]設計了考慮訂單有序性的初始種群生成方式，隨機比對交叉方式和基于訂單號的變異方式，對遺傳算法進行改進。

3? 隨機車輛路徑問題

由于外賣配送中訂單實時出現的動態性特點，近幾年越來越多的學者將研究重點關注到了外賣配送中的隨機車輛路徑問題，以減弱外賣配送中不確定因素對成本和客戶滿意度的影響。

3.1? 優化目標

對于外賣配送中行駛時間不確定的問題，趙向南等[18]假設配送員前往商家和顧客之間的行駛時間滿足伽馬分布，以運營成本和解的魯棒性作為優化目標建立優化模型。針對實際路網環境中速度動態改變的情況，楊愛芳[19]利用階躍函數對速度進行處理，研究了以配送成本和客戶滿意度作為雙目標的單配送中心的外賣配送優化問題。范厚明等[20]針對訂單需求的隨機和實時性，建立了以超時訂單比例、單均配送時間和單均行駛距離為優化目標的動態車輛路徑模型。杜丹丹[21]基于一個取餐點，考慮不同時刻商家出餐時間不同的情況，利用AnyLogic仿真軟件對商家出餐時間進行了模擬，并在目標函數中增加了車輛超載懲罰成本，構建了以最小化運輸成本、時間窗期望懲罰成本及車輛超載懲罰成本之和為目標的規劃模型。

外賣配送中的隨機因素有很多，一些學者也針對兩個及兩個以上的隨機因素同時進行了研究。李桃迎等[22]針對隨機訂單需求和隨機行駛時間同時進行研究，定義目標函數為外賣配送成本增量總和；其中，對于訂單需求隨機產生的情形，先采用高斯分布來模擬產生某個時刻的外賣訂單數，然后基于訂單需求數利用隨機數迭代產生每個訂單的商家、客戶經緯度等信息；而對于隨機行駛時間的處理是先假設每條邊相互獨立且平均速度相同，然后利用每條邊的距離除以平均速度對行駛時間進行模糊處理。熊浩等[14]研究了中途接單、臨時交通管制、商家出餐時間異常和顧客取餐時間異常四種擾動因素，在目標函數中增加了騎手空駛成本和騎手等待成本兩個目標。

3.2? 算法改進

外賣配送過程中，動態變化的路網情況導致了隨機的行駛速度。肖穎[23]基于同一路段不同時間段配送車輛行駛速度不同的情況，通過設置時間間隔，構建通過時段和路徑對實時車速進行匹配的速度分段函數，設計自適應遺傳模擬退火算法。針對隨機行駛時間的情況，趙向南、邢磊等[18]假設行駛時間滿足伽馬分布，設計了帶有精英策略的非支配排序遺傳算法；趙向南[24]通過蒙特卡羅模擬法對不確定旅行時間進行處理，將其納入外賣配送的混合整數規劃模型中，并針對單目標和多目標問題分別設計了禁忌搜索算法和帶有精英策略的非支配排序遺傳算法進行求解。

外賣配送中不同商家、同一商家不同時間段的餐品準備時間也存在差異。基于隨機的訂單準備時間，Min-Xia Zhang等[25]采用機器學習的方法利用顧客和商家的歷史習慣數據對訂單準備時間進行合理預估，設計了混合進化算法，該算法使用水波優化元啟發式算法解決訂單選擇的問題，運用禁忌搜索算法快速優化配送路徑；杜丹丹[21]基于一個取餐點，考慮不同時刻商家出餐時間不同的情況，利用AnyLogic仿真軟件對商家出餐時間進行了模擬，并設計改進的遺傳算法。

外賣配送中訂單需求的隨機和實時性特點也吸引了眾多學者的研究。Yanchao Liu[26]針對外賣配送中訂單需求和位置隨機的特點，提出使用無人機進行外賣配送的混合整數規劃模型，并設計了一種優化驅動的漸進式算法進行求解。陳露乾[16]基于禁忌搜索算法和貪婪算法，借鑒滾動時域策略和再優化策略的思想，設計了TS-Ropt動態在線算法。

外賣配送的實際場景其實是多個隨機因素組合出現的情況。近年來很多學者也對多個隨機因素同時出現的組合進行了建模與優化。孫寶鳳等[27]綜合考慮新需求出現、舊需求改變或取消、交通堵塞和配送車輛拋錨四種動態事件的影響，將滾動時域法、禁忌搜索算法和自適應大鄰域搜索算法相結合，完善動態算法框架。金玉環[28]同時考慮了取餐時間和行駛時間的隨機性，利用排隊論建立出餐排隊模型確定騎手取餐時間，通過模擬紅燈隨機等待時間確定行駛時間，設計NSGA-Ⅱ算法求解雙目標動態外賣配送路徑模型。對于中途接單、臨時交通管制、商家出餐時間異常和顧客取餐時間異常四種外賣配送中會出現的擾動情況，熊浩等[14]設計了改進的自適應大鄰域搜索算法。

4? 開放車輛路徑問題

外賣配送車輛路徑問題不同于一般的旅行商問題，單個配送員的配送路徑往往是不要求從配送中心出發，并且在完成最后一個客戶點的配送任務后返回配送中心的，屬于開放車輛路徑問題。但是，很多外賣配送路徑優化的研究中，研究者還是會將其作為旅行商問題處理，以減弱操作難度。為了對這一情況進行改進，近年來，很多的學者也將開放型車輛問題的處理方式運用到外賣配送的優化中。

4.1? 優化目標

針對配送員完成所有商家節點配送任務后無需返回起始點的情況，朱桐等[29]構建了最小化總配送成本的外賣配送路徑優化模型，其中總配送成本包括距離成本和懲罰成本；王中普[30]以最小化訂單服務延遲成本為目標函數，進行了動態開放鏈的無人機群外賣配送研究。

4.2? 算法改進

對于配送員完成最后一個配送任務后無需返回配送中心的情況，蔣麗等[1]添加了配送任務必須在顧客處結束，且配送完無需返回起始點的約束條件，并利用改進蟻群算法求解帶有軟時間窗的需求可延遲的開放式車輛路徑優化模型；蔡林等[15]首先基于最鄰近算法產生初始路徑，然后使用LK算法進行優化，最后使用末端-2-opt方法進行二次優化來設計具有順序限制的路徑優化算法；朱桐等[29]設計混合遺傳算法求解帶時間窗約束、配送順序限制、開放型的外賣配送問題；王中普[30]設計了變鄰域模擬退火算法用于動態開放鏈的無人機群外賣配送研究。

5? 結論與展望

本文結合外賣配送的特點從帶時間窗車輛路徑問題、取送貨車輛路徑問題、隨機車輛路徑問題、開放車輛路徑問題等四個方面對外賣配送路徑優化的研究現狀進行了總結和分析，發現：

（1）根據外賣配送的特點出發，從帶時間窗、取送貨、隨機、開放型等幾個角度探討后，發現外賣配送路徑優化領域中近幾年針對隨機車輛路徑問題研究的文獻較多，其中隨機車輛路徑問題主要考慮訂單需求隨機、配送行駛時間隨機、訂單準備時間隨機等三個方面。

（2）在外賣配送路徑優化的目標函數方面，隨著研究的深入，優化目標也從僅考慮外賣平臺的利益擴展到綜合考慮平臺運營成本、客戶滿意度、騎手目標等多個方面；優化目標的類型也從早期的最小化配送成本擴展到最小化配送成本、最大化客戶滿意度、最小化時間懲罰成本、最小化配送距離、最大化員工滿意度、最大化配送效率、解的魯棒性、超時訂單比例等多個方面。

（3）在外賣配送路徑優化的算法改進方面，隨著外賣節點規模的擴大，求解不同問題的元啟發式算法被設計和運用的越來越多，以擴大搜索規模提高解的運算速度；針對外賣配送的動態特點，算法中出現了多種算法混合、機器學習、滾動時域算法的運用等方面的改進。

外賣配送路徑優化屬于組合優化問題，隨著外賣需求的持續增加，基于不同場景的新目標和算法也不斷被提出，因此建議未來重點關注以下研究問題：

（1）將啟發式算法與機器學習進行結合，提高算法對動態場景的適用性。在實踐過程中，外賣運營平臺很難會針對不同的配送場景運用不同的算法進行求解，所以當算法能根據動態場景的特點自動進行調整時，就能更好地針對不同的環境進行配送路徑的指導。

（2）加強對動態場景下多目標權重設定的研究。不同場景下側重的目標往往會不同，以顧客時間窗為例，當配送時間超出時間窗時，有的顧客可能會接受賠償的方式，而有的顧客可能會直接選擇取消訂單，所以要針對不同的情況對同一目標賦予不同的權重。

（3）外賣配送過程中多種擾動因素的組合研究。外賣配送的過程中存在多個潛在的擾動因素，應對可能出現的擾動因素組合預測并進行場景的劃分，以盡可能小地減弱擾動因素對配送時間的影響。

參考文獻：

[1] 蔣麗，王靜，梁昌勇，等. 基于改進蟻群算法的眾包配送路徑研究[J]. 計算機工程與應用，2019，55（8）：244-249.

[2] 余海燕，唐婉倩，吳騰宇. 帶硬時間窗的O2O生鮮外賣即時配送路徑優化[J]. 系統管理學報，2021，30（3）：584-591.

[3] 陳萍，李航. 基于時間滿意度的O2O外賣配送路徑優化問題研究[J]. 中國管理科學，2016，24（S1）：170-176.

[4] 翟勁松，臺玉紅. 基于時間窗約束下的外賣配送路徑優化[J]. 物流科技，2018，41（3）：15-18.

[5] 周成昊，呂博軒，周翰宇，等. 以商圈為中心的O2O動態外賣配送路徑優化模型與算法[J]. 運籌學學報，2022，26（3）：17-30.

[6] 高椿林，張維存，許建. 考慮員工滿意度的多目標外賣訂單配送路徑優化研究[J]. 河北工業大學學報，2023，52（1）：86-96.

[7] 徐肇元. 基于兩階段啟發式算法的多目標外賣配送優化分析[J]. 測試技術學報，2019，33（4）：340-345.

[8] 趙強柱，盧福強，王雷震，等. 無人機騎手聯合外賣配送路徑優化問題研究[J]. 計算機工程與應用，2022，58（11）：269-278.

[9] 鞠新誠. 考慮騎手對路網熟悉度的O2O外賣配送路徑優化[D]. 大連：大連海事大學，2020.

[10] 王海燕，戴雪. 基于雙節點時間窗的外賣配送路徑優化研究[J]. 福州大學學報（哲學社會科學版），2021，35（6）：42-46.

[11] 徐倩，熊俊，楊珍花，等. 基于自適應大鄰域搜索算法的外賣配送車輛路徑優化[J]. 工業工程與管理，2021，26（3）：115-122.

[12] 陳嘉俊. O2O模式下配送車輛實時路徑選擇研究[D]. 重慶：重慶郵電大學，2019.

[13] 靳志宏，鞠新誠，郭加佳，等. O2O模式下外賣騎手的配送路徑優化[J]. 大連海事大學學報，2019（4）：55-64.

[14] 熊浩，郭昊穎，鄢慧麗，等. 考慮取送交叉和多種擾動因素的外賣配送路徑優化研究[J]. 湖南大學學報（自然科學版），2022，49（10）：92-102.

[15] 蔡林，李英冰，鄒子昕. 路徑優化算法在外賣配送中的應用[J]. 測繪通報，2019（11）：22-25.

[16] 陳露乾. 基于實時訂單的O2O外賣實時取送貨路徑優化[D]. 北京：北京交通大學，2021.

[17] 郭昊穎，熊浩，任汭楊，等. 允許取送交叉和中途接單的外賣配送路徑優化[J]. 系統工程，2022，40（5）：70-81.

[18] 趙向南，邢磊，靳志宏. 考慮不確定行駛時間的雙目標外賣配送路徑優化[J]. 大連海事大學學報，2019，45（4）：65-72.

[19] 楊愛芳. 外賣配送路徑優化研究[D]. 西安：西安電子科技大學，2020.

[20] 范厚明，咸富山，王懷奇. 動態需求下考慮訂單聚類的外賣配送路徑優化[J]. 系統仿真學報，2023，35（2）：396-407.

[21] 杜丹丹. 考慮商家出餐時間的外賣即時配送優化研究[J]. 物流工程與管理，2023，45（5）：138-142.

[22] 李桃迎，呂曉寧，李峰，等. 考慮動態需求的外賣配送路徑優化模型及算法[J]. 控制與決策，2019，34（2）：406-413.

[23] 肖穎. 時變路網下M公司外賣眾包配送派單及路徑優化研究[D]. 重慶：重慶大學，2021.

[24] 趙向南. 考慮不確定因素的外賣配送路徑優化研究[D]. 大連：大連海事大學，2020.

[25]? ZHANG M X， WU J Y， WU X， et al. Hybrid evolutionary optimization for takeaway order selection and delivery path planning utilizing habit data[J]. Complex & Intelligent Systems， 2021（8）：4425-4440.

[26]? LIU Y. An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using drones[J]. Computers & Operations Research， 2019，111：1-20.

[27] 孫寶鳳，楊悅，史俊妍，等. 考慮真實場景動態事件的動態取送貨問題[J]. 浙江大學學報（工學版），2020，54（8）：1604

-1612，1644.

[28] 金玉環. 考慮隨機時間的外賣配送路徑優化研究[D]. 西安：長安大學，2021.

[29] 朱桐，江歡. 基于遺傳算法的外賣配送路徑優化研究[J]. 輕工科技，2020（12）：51-53，93.

[30] 王中普. 基于動態開放鏈的無人機群外賣配送路徑優化研究[D]. 沈陽：沈陽建筑大學，2022.