外賣配送最優路徑模型設計

秦昕悅

（南京信息工程大學雷丁學院 江蘇省南京市 210000）

1 問題的提出

1.1 問題背景

隨著互聯網的發展以及人們生活節奏的加快，越來越多的人選擇用手機APP 上的外賣平臺購買外賣。由于外賣配送的特殊性，訂單能否準時送達直接關系到顧客的滿意程度。如何合理高效地安排配送路線及配送人員，對于提高商家的競爭力有重要意義。

1.2 問題描述

假設某外賣公司所在城市的路網由邊長為500m 的正方形網格構成，道路可雙向行駛。派送員所在的公司位于城市正中心，且在開始新的一天的工作前必須先去公司簽到。派送員騎行速度為20公里/小時，且最多同時派送兩份外賣。此外約定，客戶不對10公里外的商戶下單，所有外賣訂單的備餐時間均為15min。

根據以上信息，建立模型解決以下問題：某送餐員從公司出發，為其規劃設計配送路線，配送人員要完成全部的123 個配送任務，需要的最短時間？

2 問題分析

需要求完成全部訂單的最短配送時間，可轉化為最短路徑（TSP）問題，需要為送餐員設計最短配送路線，使得在完成既定任務的情況下，實現配送效率最高，配送時間最短。由于配送速度恒定，優化目標轉化為求距離的最小值。考慮到摩托車承載能力的限制，將送餐員的配送路線分為如圖1、圖2 兩種情況。

本題為旅行商路徑規劃問題(TSP)，這里引入并改進了模擬退火算法以解決此類復雜的NP 完全問題。該算法有較強的局部搜索能力，程序運行時間短，且能保證最終結果逐步收斂于全局最優解，比較兩種配送路線下的最優解，取最小值為本題的最終解。

3 模型假設

（1）假設送餐員僅能沿正方形網格線行駛，且道路可雙向行駛。

（2）假設外賣訂單的備餐時間均為15 分鐘。

（3）假設送餐員配送速度為20km/h。

（4）假設問題二中所有訂單在同一時刻下單。

（5）假設忽略配送過程中的一些突發因素，如：用戶失聯、臨時交通管制、運輸工具損壞、天氣異常等等。

（6）假設一個客戶的訂單只能由一輛車進行配送。

（7）假設不考慮配送員的個體差異性。

4 建模與求解

4.1 模型準備

為了便于后續建模，首先需要對附件中的參數做出轉化，對坐標的處理如下：

記A(x1,y1)，B(x2,y2)為任意兩點，d 為兩點間的距離。由于配送員僅能沿網格線行駛（圖3），則d= |x1-x2|+|y1-y2|。

將123 組商家和客戶的坐標參數導入MATLAB，運用上述距離函數其進行轉化，得到一個246*246 大小的矩陣，其中記錄了商家-商家，商家-用戶，用戶-用戶，用戶-商家的距離。

圖1

圖2

4.2 模型的建立與求解

根據以上分析，問題可轉化為求最短路徑的TSP 問題，該類問題用傳統方法通常較難處理，本文引入模擬退火算法。該算法原理簡單且易于實現，有較強的適應性，它在搜索過程中引入隨機因素，使結果有一定的概率跳出局部最優解（圖4 的B 點），收斂全局最優解（圖4 的C 點）。圖3 為距離示意圖。

需要注意的是，模擬退火算法有一系列嚴格條件，如：需要較高的初始溫度，結束時溫度需足夠低，降溫速度不能過快等。在算法的迭代過程中，為了避免陷入局部最優，需要增強擾動規則的隨機性，對路徑優化過程中所有可能的配送路線組合進行統計，很大程度上增加了算法的運算量。這一系列因素造成了該算法的求解時間較長[1]。

根據上述對算法的局限性分析，我們引入了波爾茲曼常數q(q=1.3806488×10-23)更新移動規則，從而縮短計算時間，提高運行速度。

4.2.1 基于模擬退火的路徑優化算法[2]

（1）取溫度T0，使T0足夠大，令T = T0，記送餐員有k 條初始配送路線，溫度T 的迭代次數為L；

（2）對k 條初始配送路線執行步驟（3）～（6）；

（3）通過改變配送次序以擾動初始配送路線，記產生的新解為k'；

（4）記新解k'與初始配送路線k 的路線長度之差為增量Δt'，即Δt'=Z(k')-Z(k)；

（5）若Δt'＜ 0,則更新k'作為路線的當前解，否則以作為新解的接受概率，q 為波爾茲曼常數；

（6）當迭代次數到達L 時，若新路線解k'在n 次沒有接受，則算法結束，得到最優配送路線，否則T 減小(T＞0)，轉到步驟（2）；

4.2.2 模型的求解：

利用matlab軟件編程（程序略），對該路徑最優化問題進行求解。

針對圖1 的配送方式（即商-客-商-客），得到配送員行駛的最短路線為1909 個網格，由于1 網格=0.5km，v=20km/h，所以配送員完成全部配送任務需要2863min ；而對于圖2 的配送方式，得到配送員行駛最短路徑為最短路線為1349 個網格臨界時間2023min。

由此得到結論：若該送餐員從公司出發，完成全部任務，至少需要2023min。

5 模型的評價與改進

5.1 模型的評價

本次建模中，對模型做出了較為理想的假設，缺乏自適應性與應用價值。在實際外賣配送過程中，往往存在一些不定因素，如：商家出餐效率異常、用戶失聯、運輸工具損壞、臨時交通管制等等。這些因素均會對騎手配送效率，用戶體驗，商家（外賣平臺）的利益產生影響，因此在實際多變量決策過程中，需給予其一定權重（表1）。

5.2 模型的改進

結合以上分析，對本模型做出如下改進。

5.2.1 化單次決策最優為全局最優模型

本次建模僅針對單批次給定的123 筆訂單作出優化決策，在實際外賣配送過程中，商家和外賣平臺追求的往往不是單次決策的最優，而是追求一段時間內所有訂單的指派結果的全局最優，即單均配送時長短、平均超時率低等等。

記et，ed為在某一時間段內單均送達時刻與配送員單均行駛距離，di為期望送達時刻，（1 ≤i ≤n），(i，c)為訂單i 的送貨任務，ρ 為超時率，m 為配送員數量，seqj為對配送員j 所分配的任務執行順序，(1 ≤j ≤m），則目標函數如下：

5.2.2 基于馬爾可夫決策過程的修正模型[5]

由于未來訂單信息的未知性，建模的難度大大增加。若仍沿用此前的模型，可能會導致所得結果并非最優。因此，在t 時刻進行決策的時候，既需要考慮已確定的訂單，還需要考慮未來的尚未確定的訂單。

由此，外賣配送問題為信息不完備的動態規劃問題。這里我們引入馬爾可夫決策過程（MRP）。對于一個隨機過程，其未來狀態的條件概率分布僅依賴于當前狀態，而與它過去和未來的狀態都是不相關的。記π 為給定配送策略，配送過程中的狀態集合為S，si為送餐員第i 次配送的狀態，si∈S，則MRP 的數學表達式如下：

若A 為動作集合，ai表示第i 步動作(i=1,2,…，t)，則狀態si下采取配送動作ai的最優動作價值函數為：

如果配送策略π 優于π'，即在π 下，單均配送時長更短、平均超時率較低，則vπ(s)≥vπ'(s)（π ≥π'），通過最大化q*(si,a)，可以幫助配送員找到最優策略v*(a|s)，

表1：關于外派配送問題的主要決策變量及其對應權重[4]

圖3：距離示意圖

圖4：局部最優解與全局最優解對比圖