外賣配送最優(yōu)路徑模型設(shè)計

秦昕悅

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

1 問題的提出

1.1 問題背景

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

1.2 問題描述

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

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

2 問題分析

需要求完成全部訂單的最短配送時間，可轉(zhuǎn)化為最短路徑（TSP）問題，需要為送餐員設(shè)計最短配送路線，使得在完成既定任務(wù)的情況下，實現(xiàn)配送效率最高，配送時間最短。由于配送速度恒定，優(yōu)化目標(biāo)轉(zhuǎn)化為求距離的最小值?？紤]到摩托車承載能力的限制，將送餐員的配送路線分為如圖1、圖2 兩種情況。

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

3 模型假設(shè)

（1）假設(shè)送餐員僅能沿正方形網(wǎng)格線行駛，且道路可雙向行駛。

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

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

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

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

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

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

4 建模與求解

4.1 模型準(zhǔn)備

為了便于后續(xù)建模，首先需要對附件中的參數(shù)做出轉(zhuǎn)化，對坐標(biāo)的處理如下：

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

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

圖1

圖2

4.2 模型的建立與求解

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

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

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

4.2.1 基于模擬退火的路徑優(yōu)化算法[2]

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

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

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

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

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

（6）當(dāng)?shù)螖?shù)到達L 時，若新路線解k'在n 次沒有接受，則算法結(jié)束，得到最優(yōu)配送路線，否則T 減小(T＞0)，轉(zhuǎn)到步驟（2）；

4.2.2 模型的求解：

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

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

由此得到結(jié)論：若該送餐員從公司出發(fā)，完成全部任務(wù)，至少需要2023min。

5 模型的評價與改進

5.1 模型的評價

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

5.2 模型的改進

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

5.2.1 化單次決策最優(yōu)為全局最優(yōu)模型

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

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

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

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

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

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

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

表1：關(guān)于外派配送問題的主要決策變量及其對應(yīng)權(quán)重[4]

圖3：距離示意圖

圖4：局部最優(yōu)解與全局最優(yōu)解對比圖