隨機旅行時間的外賣O2O配送車輛路徑問題

王帥　趙來軍　胡青蜜

摘 要：外賣O2O（Online to Offline）是一種典型的移動互聯網商業模式。入駐外賣O2O平臺的餐飲企業為增強顧客的配送滿意度，需要對其配送服務進行規劃設計。文章研究外賣O2O平臺上飲食類供應商外賣配送中的車輛路徑問題（VRP），通過對外賣配送特點的深入分析，采用模擬方法實現了隨機旅行時間分布的準確刻畫，以最大化顧客滿意度為目標，綜合考慮配送過程中的約束要求，建立了隨機旅行時間的帶顧客需求時間窗的VRP問題的數學模型。基于上海市徐匯區某入駐外賣O2O企業配送服務的算例，利用遺傳算法完成求解。結果顯示本文算法可以有效計算出響應顧客需求的最優車輛路徑，分析了顧客完全滿意度區間大小、顧客滿意度敏感性以及配送車輛數量等因素對配送方案總體滿意度水平的影響，提出了提高外賣O2O配送滿意度的建議。并針對外賣O2O商戶自負配送模式進行了研究，可為外賣O2O平臺上飲食類供應商改善配送和提升顧客滿意度提供決策支持。

關鍵詞：外賣配送；車輛路徑問題；顧客滿意度；隨機旅行時間；遺傳算法

中圖分類號：F252.14 文獻標識碼：A

Abstract： Takeout O2O（Online to Offline）is a typical mobile internet era business model. To promote customer satisfaction degree， takeout suppliers on the O2O platform need to implement proper service delivery planning. In this paper， we focus on the vehicle routing problem（VRP）during the takeout delivery service. We use the simulation method to model the distribution of stochastic travel time， and build mathematical model with considering all the constraints， to maximize customer satisfaction. In this paper， we take a takeout restaurant in Xuhui District in Shanghai which is on a O2O platform as the example， and use genetic algorithm to solve the VRP. The results show that the algorithm fits well. We test factors to assess the influence to the general customer satisfaction. This paper is based on a mainstream pattern of O2O takeout delivery， the self-organizing delivery. The conclusion can provide referential decision support to takeout suppliers and help them promoting customer satisfaction degree.

Key words： takeout delivery； vehicle routing problem； customer satisfaction； stochastic travel times； genetic algorithm

0 引 言

移動互聯網正在深刻改變人們的日常生活，外賣O2O（Online to Offline）則是移動互聯時代商業模式的典型。在外賣O2O模式下，外賣配送服務是實現Offline的重要環節，目前仍主要由入駐外賣O2O平臺的餐飲企業自行承擔。在提供服務的過程中，顧客往往約定外賣送達時間，商家需保障外賣的準時送達，一旦外賣未能準時送抵顧客處，顧客滿意度會受到影響，顧客會將不滿信息反饋到外賣平臺以供其他顧客參考，會損傷外賣提供商的品牌效應，對經營業績產生不良影響。因此，以最大化顧客滿意度為目標，合理高效地組織配送服務對進駐O2O平臺餐飲企業經營具有重要意義。

外賣配送服務是典型的旅行時間隨機的車輛路徑規劃問題（STVRP）。配送車輛路徑規劃問題（VRP）最早是由Dantzig和Ramser[1]提出來的，是指存在一定數量顧客的情況下，由配送中心組織車隊向顧客配送貨物，組織合理的行車路線方案，并能在規定的約束條件下，實現諸如路程最短、成本最小等目的。VRP問題的一個重要分類就是隨機性VRP，這是由于在現實生活中，往往會遇到一些不能精確預判結果、但能夠判斷結果出現規律的隨機事件，而STVRP就是隨機性VRP的一種。Laporte等人[2]對STVRP進行研究，提出了一種機會約束模型，并利用分枝割算法完成求解。Park和Song[3]改進了一種確定性VRP的求解算法，并構造了3種啟發式算法對STVRP進行求解。近年來，亞啟發式算法逐漸被應用到STVRP的求解中[4-6]，而其中具代表性的遺傳算法因其能有效解決TSP問題等組合優化問題，越來越被應用到為STVRP問題的求解[7-8]。STVRP的求解的難點之一在于對隨機性的處理，前人的研究工作中通常采用假設隨機旅行時間服從正態分布的方法，例如謝秉磊[9]利用正態分布假設通過遺傳算法求解了STVRP的機會約束模型。這類方法的優點是能夠有效簡化問題，在通用性問題中具備較強參考意義。但同時也存在不足：第一，這種假設使用同一統計分布（包括參數也相同）刻畫每段路程對應旅行時間所服從的統計分布，而現實中即使各段路程對應的旅行時間服從正態分布，其均值、方差等參數也往往存在差異，這樣表達與現實存在誤差；第二，適用條件受限，真實生活中的大量STVRP問題，其旅行時間服從分布特點與正態分布可能相差甚遠。因此，近年來STVRP的研究中更加注重對個性化現實問題的研究，魏明[10]對區域公交車調度的模型及算法進行了研究，戴韜等[11]則利用STVRP理論考慮了船舶航線規劃問題，而目前O2O領域的VRP問題研究仍然較少。學界對O2O模式的認識及其物流發展的理解在不斷深入。呂曉永[12]對O2O模式下電子商務物流配送現狀進行分析并提出了相應的對策。張穎春[13]對南京市外賣快餐配送的現狀進行了調查了解。趙璐[14]針對有道路限行情形下的集團蔬菜城市配送VRP問題進行了研究并利用遺傳算法進行了求解分析。翟恒星[15]針對生鮮O2O電商情形對同城冷鏈物流配送優化問題進行了研究。對本地O2O商業模式下物流配送的研究近年開始逐漸深入，楊博文[16]等人對O2O餐飲外賣目標市場發展趨勢進行了分析，但總體來看，目前外賣O2O情形下的STVRP問題學界的研究仍然較少。

本文所研究的外賣O2O環境下的VRP具有強烈的個性化特點。依據外賣配送特點，本文首先說明外賣O2O環境下的VRP問題是帶有需求時間窗的隨機旅行時間車輛路徑規劃問題（STVRP），提出了能夠精確刻畫隨機旅行時間分布的方法，建立了外賣配送VRP模型，進而利用遺傳算法完成求解，并進行了靈敏度分析，提出了提高O2O外賣配送滿意度的措施。

1 問題描述與分析

1.1 問題描述

本文研究的外賣O2O平臺上飲食類供應商的車輛路徑問題（VRP）以最大化顧客滿意度為目標，具體描述如下：（1）路網中存在單一配送中心，即O2O平臺上提供外賣供應的商戶；（2）車場多輛摩托車提供外賣配送服務；（3）配送車輛從車場出發，為分布在街區中不同地點的顧客服務，每個顧客僅能由一輛車服務且僅能服務一次，車輛完成全部配送任務后回到配送中心；（4）每個顧客有預設的需求時間窗，當車輛未能在預設的時間窗內抵達時，顧客滿意度會受到影響；（5）為了更好地組織配送，餐飲企業一般采用周期配送策略，即每個配送時段集中配送一次，要求車輛從車場出發后盡快返回以響應下一時段配送任務；（6）每輛車所服務顧客的總需求量要在該輛車載貨能力之內。由此可見，外賣O2O平臺上飲食類供應商的車輛路徑問題是帶有需求時間窗的隨機旅行時間路徑規劃問題（STVRP）。

1.2 隨機旅行時間服從分布刻畫

外賣配送車輛為摩托車，受城市道路路況影響小，在道路上的行駛速度可以認為是勻速行駛，其旅行時間隨機性的來源主要來自于途中遭遇紅燈產生的等待。事實上，配送車輛在遭遇紅燈時所經歷的等待時間服從均勻分布，假設配送車輛在兩點之間行車中經歷了n個紅燈，則配送車輛在兩點之間旅行時間所服從的分布即為n個均勻分布的疊加。

例如，配送車輛從A點前往B點，路程2 500m，車輛行駛速度為1 000m/min，期望遭遇2個紅燈形成等待，2個紅燈周期分別為1分鐘和2分鐘，則配送車輛在2個紅燈形成的等待時間分別服從均勻分布U0，1與U0，2。為了能夠方便計算，將2個均勻分布進行疊加處理。采用模擬的辦法：利用Python編程語言隨機生成1 000組服從U0，1與U0，2的數組，進行求和得到1 000個數以模擬等待時間；對1 000個數字利用統計軟件Minitab進行擬合得到結果如圖1所示，即等待時間服從統計分布為N1.052，0.6445。配送車輛勻速行駛的時間為2 500m÷1 000m/min=2.5min，由此得到配送車輛在A、B兩點間旅行時間服從分布為N1.052+2.5，0.6445，即N3.552，0.6445。

1.3 顧客滿意度刻畫

在外賣配送服務中，每個顧客有預設的需求時間點，記為t。而在t前后W時間范圍內，顧客滿意度不受影響，為100%，該時刻區間可以記為a，b，b-a的大小即為2W。當車輛未能在顧客預設的時間窗內抵達時，顧客滿意度會受到影響，滿意度隨抵達時間遠離a，b線性下降至0。因此，顧客滿意度隨配送車輛抵達時刻的對應關系可以刻畫為分段函數，如圖2所示，t是a，b的中值，顧客滿意度敏感性可用滿意度線性變化區間斜率的絕對值K表示。在現實配送情形中，可以出于簡化問題需求，將車輛可能遭遇的紅燈依據等待時長長短分為數種類型。

2 數學模型

3 算法設計

3.1 算法步驟

本文使用遺傳算法求解以上STVRP問題，具體算法步驟如下：

步驟1：生成初始種群；

步驟2：計算種群中各染色體適應度；

步驟3：針對種群中的各染色體進行遺傳操作；

步驟4：完成遺傳操作之后的染色體生成子代種群，判斷是否滿足算法終止條件，若已滿足則執行步驟5，否則返回執行步驟2；

步驟5：從種群中篩選出適應度值最大的染色體，對其進行解碼操作，輸出對應的路徑規劃方案。

3.2 編碼方法

本文采用整數編碼方法。例如某商家使用m輛配送車輛，存在n個顧客節點n≥m，則用整數1至n表示n個顧客節點，用0表示車場。編碼方法分3步完成：第一步，對1至n個顧客節點隨機排序生成一組排列；第二步，在n個數字之間的n-1個間隔中，隨機選擇m-1個間隔插入0；第三步，在排列的首尾兩端插入0。這樣可得到m個配送路徑方案，表示所有配送車輛必須從車場出發，配送完再返回車場。

3.3 初始種群生成

設定種群規模為50，初始種群生成通過多步循環完成，每一次循環包括兩步核心步驟：

Step1：依據4.2編碼方法隨機生成1組路徑規劃方案。

Step2：檢驗是否滿足約束條件，對通過Step1得到的路徑規劃方案進行約束條件的逐條檢驗。若未能夠通過全部檢驗，則該路徑規劃方案將被放棄，重復Step1；否則，該路徑規劃方案將成為1條初始染色體，若初始種群規模已達到50，則結束循環，否則，重復Step1。

3.4 適應度函數

遺傳算法通過不同染色體適應度函數值比較染色體之間的優劣，在選擇過程中淘汰適應度函數值劣者，保留適應度函數值較優者，以達到優勝劣汰目的。本文設計的適應度函數即為目標函數。

3.5 復制、交叉和變異

遺傳操作包括復制、交叉和變異。本文復制算子為選取最佳保留的輪盤賭復制法；交叉算子采用了MX1[17]；變異算子則采用隨機使用兩點交換。

3.6 終止條件

本文終止條件為最大迭代次數法與誤差范圍綜合考慮。本文規定最大迭代次數為5 000，當連續2次遺傳操作的目標值變化小于1%或抵達最大迭代次數時，算法終止。

4 數值實驗

4.1 參數設置

A餐廳是上海市徐匯區某O2O平臺上的餐飲企業，將于某日12：00～13：00時間段內對分布其周邊區域內的15個顧客需求點提供外賣配送服務，餐廳共有3輛摩托車配送車輛，每個車輛的裝載量為35（包裝盒數量）。

在本算例中，圖2中W的值為10min，K值為1，數據由某外賣O2O平臺入駐餐飲企業提供。顧客和配送中心的位置信息如圖3所示；表1顯示了各顧客點的需求信息（包裝盒數量）和預期抵達時間信息（圖2中t值），預期時間為17則表示顧客期望于12：17外賣送抵，表1顯示由于受到學生和白領午餐時間的影響，t值基本集中于12：00～12：30之間；表2羅列了可連通各點之間的距離，均來自于地圖的真實可行路徑距離，其它未在表格中顯示的兩點間距離表示該兩點之間不能夠直接相通，配送摩托車車輛在道路上平均速度250m/min，據此可以得到在不考慮紅燈引起的等待的情況下車輛在各點之間的旅行時間。出于簡化問題，將車輛可能遭遇的紅燈分為兩種類型：一種紅燈在一個周期內紅燈時長為1min，即車輛遇到此紅燈后等待時間服從U0，1，可稱為短紅燈；另一種紅燈在一個周期內紅燈時長為2min，即車輛遇到此紅燈后等待時間服從U0，2，可稱為長紅燈。配送車輛在每兩點之間行駛期望遭遇的紅燈數量和組合如表3所示，例如：2，1表示車輛在此弧上行駛期望遇到2個長紅燈和1個短紅燈。根據1.2有關外賣O2O旅行時間分布刻畫的分析方法可以得到配送車輛在各段弧上可能發生的旅行時間服從的統計分布，再與不考慮等待情況下勻速運動時間合并，可得到可連通各點之間車輛旅行時間分布如表4所示。

4.2 實驗結果

根據4.1中算例數據，設置遺傳算法所需參數：初始種群數量為100，交叉率0.3，變異率0.1，求解算例。

由實驗結果可知，路徑規劃方案構成3條回路：0-2-3-4-5-6-7-0，

0-12-11-10-9-8-0，0-13-1-14-15-0（見圖4），顧客平均滿意度為：84.7%，經檢驗，實驗結果滿足各項約束條件。

為了檢測算法的穩定性，在0，30之間隨機產生10組由15個數字構成數組，用以表示15個顧客點預期配送車輛抵達的時間，均在12：00，12：30時間范圍內，利用本文的算法進行求解，結果顯示顧客平均滿意度介于79%至92%的區間內，與平均值85.2%的差距在±8%以內。這表明本文算法穩定性良好，可以用以求解此類STVRP問題，協助O2O餐飲平臺入駐店家完成日常配送的車輛調度和路徑規劃。

4.3 靈敏度分析

本文主要著重考察以下3個因素對總體配送方案滿意度的影響：顧客完全滿意度區間大小、顧客滿意度敏感性以及配送車輛數量。

根據圖2描述，W的大小的2倍表示顧客滿意度達到100%的時間窗口寬度；K表示直線斜率絕對值，即顧客滿意度在線性變化區間隨時間線性變化的速度。因此，W可以用來刻畫顧客完全滿意度區間大小，K可以用來衡量顧客滿意度的敏感性，K值越大表明顧客敏感性越強。接下來考察對顧客完全滿意度區間大小和顧客滿意度的敏感性對總體配送方案滿意度的影響。

（1）考察顧客滿意度對總體配送方案滿意度的影響。令K絕對值為1，通過改變W大小，觀測總體顧客滿意度水平隨之變化的趨勢，表5和圖5顯示了實驗結果。結果顯示，總體配送服務質量隨顧客滿意度時間區間的擴大而增長，但增長變化率不斷減小，當W>10后，總體滿意度達到85%，滿意度提升速度變得極為緩慢。因此，對于商戶要通過商業活動如延時送達贈送代金券等活動盡可能誘導顧客的完全滿意度區間擴大，以本文算例為例，維持送達時間在客戶預期時間±10min以內對保證滿意度影響重大。當W從10增加到20的過程中，滿意度從85%上升至99%，但配送方案僅在0-2-3-4-5-6-7-0，0-12-11

-10-9-8-0，0-13-1-14-15-0和0-8-9-10-11-12-0，0-7-6-5-4-3-2-0，0-15-14-1-13-0之中切換。這表明即使在商戶提供服務的過程中完全滿意區間擴大到一定程度，一個相對優化的方案已經出現，即使商戶繼續致力于改善顧客的完全滿意度區間但配送方案并不會發生顯著調整，滿意度也僅微幅上升，因此商家繼續商業活動投入就變得得不償失。

（2）考察顧客滿意度的敏感性對總體配送方案滿意度的影響。令W穩定為10，改變K的絕對值大小，觀測總體顧客滿意度水平隨之變化的趨勢，表6和圖6顯示了實驗結果。結果顯示，調整K值大小路徑方案僅發生有2種變化，2種方案對應圖6的表現是滿意度隨K變化的速率存在差異，這反應了顧客在滿意度敏感性不同情況下配送方案的差異。同時，滿意度隨K增大而下降，表明了顧客敏感性越高時商戶的配送服務越難以保證高滿意度。因此，對于商戶而言，通過市場行為去準確描述和改善顧客滿意度的敏感性對總體服務質量改善具有重要意義。

（3）考察配送車輛數量對總體配送方案滿意度的影響。分別改變配送車輛數量為2、3、4、5、6，得到總體滿意度變化如圖7所示。結果顯示，當使用2輛配送車輛時，平均滿意度水平最低，為72%；當使用4輛配送車輛時平均滿意度水平最高，為86%；3輛、5輛和6輛配送車輛對應平均滿意度水平分別為85%、83%和83%。配送車輛從2輛增加至4輛的過程中，總體滿意度水平不斷上升，但當使用5輛配送車輛時，可能導致配送車輛過早抵達顧客處，反而引起了顧客滿意度下降，而6輛車和5輛車產生的滿意度基本持平，這是由于兩種配送方案中每輛車負責的顧客數量已經很少，引起的滿意度差異也變得更為有限。配送車輛數量從3輛增加至4輛，平均滿意度僅增加了1%，考慮到使用4輛配送車輛引起更多的固定成本投入和人員工資成本支出，對于商戶而言使用3輛配送車輛是最優選擇。需要注意的是，當商家配備更多的配送車輛時，滿意度反而下降，這是由整點配送規則引起的，結果表明如果嚴格按照整點配送策略而非按需配送，則更多的配備車輛反而影響總體滿意度水平，由此可以發現外賣配送策略的復雜性：按需配送適合每輛車負責顧客數量極少的情形，而從配送管理規范化和規模化角度講，以整點配送為代表的周期配送策略更有意義，但需要認真計算配送成本尋找出最為合適的配送車輛數量。

5 結束語

隨著移動互聯時代的到來，外賣O2O配送正在蓬勃發展，引起了餐飲從業人員和O2O平臺的關注。本文研究了旅行時間隨機的外賣O2O配送VRP問題。考慮到外賣O2O配送特點，利用模擬方法準確的對旅行時間服從分布進行刻畫，并以顧客滿意度為優化目標，綜合考慮裝載量、按時返回、每一顧客點僅被服務一次等限制條件，建立了外賣O2O配送車輛路徑問題模型，并對上海市徐匯區某入駐外賣O2O平臺餐飲企業配送路徑方案進行算例分析。

敏感性分析表明：（1）實驗結果顯示伴隨顧客完全滿意度區間不斷寬松，滿意度提升速度不斷放緩，且當完全滿意度達到一定寬度時，滿意度提升速度變得極為緩慢，同時配送方案也逐漸穩定，這表明在一定商業活動投入后從商家的決策上將已經不發生變化，滿意度的進一步提升并不依賴于規劃的效率而來自于商業活動對顧客滿意度區間特點的影響。（2）實驗結果表明在顧客滿意度敏感性較強時，即使相同配送方案也將造成滿意度降低。因此，餐飲企業在提供配送服務時要努力通過商業活動和市場行為改善消費者的滿意度變化特點，一方面提高完全滿意度區間，另一方面改善消費者滿意度靈敏性；同時也要兼顧成本，在總體滿意度水平已經較高的情況下，由于配送方案同樣趨于穩定，繼續的商業投入變得不再經濟。（3）當對配送車輛數量進行改變時，隨車輛數量增加時，總體滿意度水平先升后降。當顧客總體滿意度達到一定程度時，配送車輛越多反而由于可能提前送達導致總體滿意度下降。因此，結合考慮到固定成本投入和人員工資成本支出，對商戶而言應該選擇一個最優的配送車輛數量。本研究為入駐外賣O2O平臺的餐飲企業日常運營中車輛配送路徑的選擇提供決策支持。

本文基于目前全國范圍內外賣O2O配送服務的主流形式，即商戶自負配送模式進行研究。事實上，在以北上廣深為代表的一線城市，目前O2O外賣平臺的配送服務正在呈現出新特點，即由外賣O2O平臺組建配送團隊對商戶和顧客提供配送服務。餓了么、美團外賣和百度外賣在內的多家外賣O2O平臺巨頭企業均在進行自建物流體系的嘗試，使得外賣配送服務呈現出了新的特點。因此，對于新形勢下外賣O2O平臺配送的VRP問題，作者后續將進行進一步研究。

參考文獻：

[1] Dantzig G B， Ramser J H. The truck dispatching problem[J]. Management science， 1959，6（1）：80-91.

[2] Laporte G， Louveaux F， Mercure H. The vehicle routing problem with stochastic travel times[J]. Transportation science， 1992，26（3）：161-170.

[3] Park Y B， Song S H. Vehicle scheduling problems with time-varying speed[J]. Computers & Industrial Engineering， 1997，33（3）：853-856.

[4] Chatterjee S， Carrera C， Lynch L A. Genetic algorithms and traveling salesman problems[J]. European journal of operational research， 1996，93（3）：490-510.

[5] Belfiore P， Tsugunobu H， Yoshizaki Y. Scatter search for vehicle routing problem with time windows and split deliveries[J]. Vehicle Routing Problem， 2008（5）：1-14.

[6] 李建，張永，達慶利. 第三方物流多車型硬時間窗路線問題研究[J]. 系統工程學報，2008，23（1）：74-80.

[7] 李向陽. 遺傳算法求解VRP問題[J]. 計算機工程與設計，2004，25（2）：271-273.

[8] 張麗萍，柴躍廷. 車輛路徑問題的改進遺傳算法[J]. 系統工程理論與實踐，2002，22（8）：79-84.

[9] 謝秉磊，李軍，郭耀煌. 有時間窗的非滿載車輛調度問題的遺傳算法[J]. 系統工程學報，2000，15（3）：290-294.

[10] 魏明，靳文舟，孫博. 隨機旅行時間的區域公交車調度模型及算法[J]. 公路交通科技，2011，28（10）：124-129.

[11] 戴韜，楊稀麟. 考慮時間窗與隨機航行時間的船舶航線規劃[J]. Computer Engineering and Applications， 2012，48（25）：234

-238.

[12] 呂曉永. O2O模式下電子商務物流配送現狀分析及對策研究[J]. 價值工程，2016，35（7）：98-99.

[13] 張穎春，劉愛軍. 南京市外賣快餐配送的現狀分析與對策思考[J]. 江蘇商論，2015（3）：26-29.

[14] 趙璐，趙磊，朱道立. 有道路限行的集團蔬菜城市配送車輛路徑問題[J]. 上海管理科學，2013，35（5）：38-45.

[15] 翟恒星. 生鮮O2O電商同城冷鏈物流配送優化研究[D]. 大連：大連海事大學（碩士學位論文），2015.

[16] 楊博文，王靜，段輝. O2O餐飲外賣目標市場發展趨勢分析[J]. 科教導刊（電子版），2015（22）：146-147.

[17] Blanton Jr J L， Wainwright R L. Multiple vehicle routing with time and capacity constraints using genetic algorithms[C] // Proceedings of the 5th International Conference on Genetic Algorithms. Morgan Kaufmann Publishers Inc.， 1993：452-459.