王帥　趙來(lái)軍　胡青蜜

摘 要：外賣(mài)O2O（Online to Offline）是一種典型的移動(dòng)互聯(lián)網(wǎng)商業(yè)模式。入駐外賣(mài)O2O平臺(tái)的餐飲企業(yè)為增強(qiáng)顧客的配送滿(mǎn)意度，需要對(duì)其配送服務(wù)進(jìn)行規(guī)劃設(shè)計(jì)。文章研究外賣(mài)O2O平臺(tái)上飲食類(lèi)供應(yīng)商外賣(mài)配送中的車(chē)輛路徑問(wèn)題（VRP），通過(guò)對(duì)外賣(mài)配送特點(diǎn)的深入分析，采用模擬方法實(shí)現(xiàn)了隨機(jī)旅行時(shí)間分布的準(zhǔn)確刻畫(huà)，以最大化顧客滿(mǎn)意度為目標(biāo)，綜合考慮配送過(guò)程中的約束要求，建立了隨機(jī)旅行時(shí)間的帶顧客需求時(shí)間窗的VRP問(wèn)題的數(shù)學(xué)模型?；谏虾Ｊ行靺R區(qū)某入駐外賣(mài)O2O企業(yè)配送服務(wù)的算例，利用遺傳算法完成求解。結(jié)果顯示本文算法可以有效計(jì)算出響應(yīng)顧客需求的最優(yōu)車(chē)輛路徑，分析了顧客完全滿(mǎn)意度區(qū)間大小、顧客滿(mǎn)意度敏感性以及配送車(chē)輛數(shù)量等因素對(duì)配送方案總體滿(mǎn)意度水平的影響，提出了提高外賣(mài)O2O配送滿(mǎn)意度的建議。并針對(duì)外賣(mài)O2O商戶(hù)自負(fù)配送模式進(jìn)行了研究，可為外賣(mài)O2O平臺(tái)上飲食類(lèi)供應(yīng)商改善配送和提升顧客滿(mǎn)意度提供決策支持。

關(guān)鍵詞：外賣(mài)配送；車(chē)輛路徑問(wèn)題；顧客滿(mǎn)意度；隨機(jī)旅行時(shí)間；遺傳算法

中圖分類(lèi)號(hào)：F252.14 文獻(xiàn)標(biāo)識(shí)碼：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 引 言

移動(dòng)互聯(lián)網(wǎng)正在深刻改變?nèi)藗兊娜粘Ｉ睿赓u(mài)O2O（Online to Offline）則是移動(dòng)互聯(lián)時(shí)代商業(yè)模式的典型。在外賣(mài)O2O模式下，外賣(mài)配送服務(wù)是實(shí)現(xiàn)Offline的重要環(huán)節(jié)，目前仍主要由入駐外賣(mài)O2O平臺(tái)的餐飲企業(yè)自行承擔(dān)。在提供服務(wù)的過(guò)程中，顧客往往約定外賣(mài)送達(dá)時(shí)間，商家需保障外賣(mài)的準(zhǔn)時(shí)送達(dá)，一旦外賣(mài)未能準(zhǔn)時(shí)送抵顧客處，顧客滿(mǎn)意度會(huì)受到影響，顧客會(huì)將不滿(mǎn)信息反饋到外賣(mài)平臺(tái)以供其他顧客參考，會(huì)損傷外賣(mài)提供商的品牌效應(yīng)，對(duì)經(jīng)營(yíng)業(yè)績(jī)產(chǎn)生不良影響。因此，以最大化顧客滿(mǎn)意度為目標(biāo)，合理高效地組織配送服務(wù)對(duì)進(jìn)駐O2O平臺(tái)餐飲企業(yè)經(jīng)營(yíng)具有重要意義。

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

本文所研究的外賣(mài)O2O環(huán)境下的VRP具有強(qiáng)烈的個(gè)性化特點(diǎn)。依據(jù)外賣(mài)配送特點(diǎn)，本文首先說(shuō)明外賣(mài)O2O環(huán)境下的VRP問(wèn)題是帶有需求時(shí)間窗的隨機(jī)旅行時(shí)間車(chē)輛路徑規(guī)劃問(wèn)題（STVRP），提出了能夠精確刻畫(huà)隨機(jī)旅行時(shí)間分布的方法，建立了外賣(mài)配送VRP模型，進(jìn)而利用遺傳算法完成求解，并進(jìn)行了靈敏度分析，提出了提高O2O外賣(mài)配送滿(mǎn)意度的措施。

1 問(wèn)題描述與分析

1.1 問(wèn)題描述

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

1.2 隨機(jī)旅行時(shí)間服從分布刻畫(huà)

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

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

1.3 顧客滿(mǎn)意度刻畫(huà)

在外賣(mài)配送服務(wù)中，每個(gè)顧客有預(yù)設(shè)的需求時(shí)間點(diǎn)，記為t。而在t前后W時(shí)間范圍內(nèi)，顧客滿(mǎn)意度不受影響，為100%，該時(shí)刻區(qū)間可以記為a，b，b-a的大小即為2W。當(dāng)車(chē)輛未能在顧客預(yù)設(shè)的時(shí)間窗內(nèi)抵達(dá)時(shí)，顧客滿(mǎn)意度會(huì)受到影響，滿(mǎn)意度隨抵達(dá)時(shí)間遠(yuǎn)離a，b線性下降至0。因此，顧客滿(mǎn)意度隨配送車(chē)輛抵達(dá)時(shí)刻的對(duì)應(yīng)關(guān)系可以刻畫(huà)為分段函數(shù)，如圖2所示，t是a，b的中值，顧客滿(mǎn)意度敏感性可用滿(mǎn)意度線性變化區(qū)間斜率的絕對(duì)值K表示。在現(xiàn)實(shí)配送情形中，可以出于簡(jiǎn)化問(wèn)題需求，將車(chē)輛可能遭遇的紅燈依據(jù)等待時(shí)長(zhǎng)長(zhǎng)短分為數(shù)種類(lèi)型。

2 數(shù)學(xué)模型

3 算法設(shè)計(jì)

3.1 算法步驟

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

步驟1：生成初始種群；

步驟2：計(jì)算種群中各染色體適應(yīng)度；

步驟3：針對(duì)種群中的各染色體進(jìn)行遺傳操作；

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

步驟5：從種群中篩選出適應(yīng)度值最大的染色體，對(duì)其進(jìn)行解碼操作，輸出對(duì)應(yīng)的路徑規(guī)劃方案。

3.2 編碼方法

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

3.3 初始種群生成

設(shè)定種群規(guī)模為50，初始種群生成通過(guò)多步循環(huán)完成，每一次循環(huán)包括兩步核心步驟：

Step1：依據(jù)4.2編碼方法隨機(jī)生成1組路徑規(guī)劃方案。

Step2：檢驗(yàn)是否滿(mǎn)足約束條件，對(duì)通過(guò)Step1得到的路徑規(guī)劃方案進(jìn)行約束條件的逐條檢驗(yàn)。若未能夠通過(guò)全部檢驗(yàn)，則該路徑規(guī)劃方案將被放棄，重復(fù)Step1；否則，該路徑規(guī)劃方案將成為1條初始染色體，若初始種群規(guī)模已達(dá)到50，則結(jié)束循環(huán)，否則，重復(fù)Step1。

3.4 適應(yīng)度函數(shù)

遺傳算法通過(guò)不同染色體適應(yīng)度函數(shù)值比較染色體之間的優(yōu)劣，在選擇過(guò)程中淘汰適應(yīng)度函數(shù)值劣者，保留適應(yīng)度函數(shù)值較優(yōu)者，以達(dá)到優(yōu)勝劣汰目的。本文設(shè)計(jì)的適應(yīng)度函數(shù)即為目標(biāo)函數(shù)。

3.5 復(fù)制、交叉和變異

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

3.6 終止條件

本文終止條件為最大迭代次數(shù)法與誤差范圍綜合考慮。本文規(guī)定最大迭代次數(shù)為5 000，當(dāng)連續(xù)2次遺傳操作的目標(biāo)值變化小于1%或抵達(dá)最大迭代次數(shù)時(shí)，算法終止。

4 數(shù)值實(shí)驗(yàn)

4.1 參數(shù)設(shè)置

A餐廳是上海市徐匯區(qū)某O2O平臺(tái)上的餐飲企業(yè)，將于某日12：00～13：00時(shí)間段內(nèi)對(duì)分布其周邊區(qū)域內(nèi)的15個(gè)顧客需求點(diǎn)提供外賣(mài)配送服務(wù)，餐廳共有3輛摩托車(chē)配送車(chē)輛，每個(gè)車(chē)輛的裝載量為35（包裝盒數(shù)量）。

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

4.2 實(shí)驗(yàn)結(jié)果

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

由實(shí)驗(yàn)結(jié)果可知，路徑規(guī)劃方案構(gòu)成3條回路：0-2-3-4-5-6-7-0，

0-12-11-10-9-8-0，0-13-1-14-15-0（見(jiàn)圖4），顧客平均滿(mǎn)意度為：84.7%，經(jīng)檢驗(yàn)，實(shí)驗(yàn)結(jié)果滿(mǎn)足各項(xiàng)約束條件。

為了檢測(cè)算法的穩(wěn)定性，在0，30之間隨機(jī)產(chǎn)生10組由15個(gè)數(shù)字構(gòu)成數(shù)組，用以表示15個(gè)顧客點(diǎn)預(yù)期配送車(chē)輛抵達(dá)的時(shí)間，均在12：00，12：30時(shí)間范圍內(nèi)，利用本文的算法進(jìn)行求解，結(jié)果顯示顧客平均滿(mǎn)意度介于79%至92%的區(qū)間內(nèi)，與平均值85.2%的差距在±8%以?xún)?nèi)。這表明本文算法穩(wěn)定性良好，可以用以求解此類(lèi)STVRP問(wèn)題，協(xié)助O2O餐飲平臺(tái)入駐店家完成日常配送的車(chē)輛調(diào)度和路徑規(guī)劃。

4.3 靈敏度分析

本文主要著重考察以下3個(gè)因素對(duì)總體配送方案滿(mǎn)意度的影響：顧客完全滿(mǎn)意度區(qū)間大小、顧客滿(mǎn)意度敏感性以及配送車(chē)輛數(shù)量。

根據(jù)圖2描述，W的大小的2倍表示顧客滿(mǎn)意度達(dá)到100%的時(shí)間窗口寬度；K表示直線斜率絕對(duì)值，即顧客滿(mǎn)意度在線性變化區(qū)間隨時(shí)間線性變化的速度。因此，W可以用來(lái)刻畫(huà)顧客完全滿(mǎn)意度區(qū)間大小，K可以用來(lái)衡量顧客滿(mǎn)意度的敏感性，K值越大表明顧客敏感性越強(qiáng)。接下來(lái)考察對(duì)顧客完全滿(mǎn)意度區(qū)間大小和顧客滿(mǎn)意度的敏感性對(duì)總體配送方案滿(mǎn)意度的影響。

（1）考察顧客滿(mǎn)意度對(duì)總體配送方案滿(mǎn)意度的影響。令K絕對(duì)值為1，通過(guò)改變W大小，觀測(cè)總體顧客滿(mǎn)意度水平隨之變化的趨勢(shì)，表5和圖5顯示了實(shí)驗(yàn)結(jié)果。結(jié)果顯示，總體配送服務(wù)質(zhì)量隨顧客滿(mǎn)意度時(shí)間區(qū)間的擴(kuò)大而增長(zhǎng)，但增長(zhǎng)變化率不斷減小，當(dāng)W>10后，總體滿(mǎn)意度達(dá)到85%，滿(mǎn)意度提升速度變得極為緩慢。因此，對(duì)于商戶(hù)要通過(guò)商業(yè)活動(dòng)如延時(shí)送達(dá)贈(zèng)送代金券等活動(dòng)盡可能誘導(dǎo)顧客的完全滿(mǎn)意度區(qū)間擴(kuò)大，以本文算例為例，維持送達(dá)時(shí)間在客戶(hù)預(yù)期時(shí)間±10min以?xún)?nèi)對(duì)保證滿(mǎn)意度影響重大。當(dāng)W從10增加到20的過(guò)程中，滿(mǎn)意度從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之中切換。這表明即使在商戶(hù)提供服務(wù)的過(guò)程中完全滿(mǎn)意區(qū)間擴(kuò)大到一定程度，一個(gè)相對(duì)優(yōu)化的方案已經(jīng)出現(xiàn)，即使商戶(hù)繼續(xù)致力于改善顧客的完全滿(mǎn)意度區(qū)間但配送方案并不會(huì)發(fā)生顯著調(diào)整，滿(mǎn)意度也僅微幅上升，因此商家繼續(xù)商業(yè)活動(dòng)投入就變得得不償失。

（2）考察顧客滿(mǎn)意度的敏感性對(duì)總體配送方案滿(mǎn)意度的影響。令W穩(wěn)定為10，改變K的絕對(duì)值大小，觀測(cè)總體顧客滿(mǎn)意度水平隨之變化的趨勢(shì)，表6和圖6顯示了實(shí)驗(yàn)結(jié)果。結(jié)果顯示，調(diào)整K值大小路徑方案僅發(fā)生有2種變化，2種方案對(duì)應(yīng)圖6的表現(xiàn)是滿(mǎn)意度隨K變化的速率存在差異，這反應(yīng)了顧客在滿(mǎn)意度敏感性不同情況下配送方案的差異。同時(shí)，滿(mǎn)意度隨K增大而下降，表明了顧客敏感性越高時(shí)商戶(hù)的配送服務(wù)越難以保證高滿(mǎn)意度。因此，對(duì)于商戶(hù)而言，通過(guò)市場(chǎng)行為去準(zhǔn)確描述和改善顧客滿(mǎn)意度的敏感性對(duì)總體服務(wù)質(zhì)量改善具有重要意義。

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

5 結(jié)束語(yǔ)

隨著移動(dòng)互聯(lián)時(shí)代的到來(lái)，外賣(mài)O2O配送正在蓬勃發(fā)展，引起了餐飲從業(yè)人員和O2O平臺(tái)的關(guān)注。本文研究了旅行時(shí)間隨機(jī)的外賣(mài)O2O配送VRP問(wèn)題?？紤]到外賣(mài)O2O配送特點(diǎn)，利用模擬方法準(zhǔn)確的對(duì)旅行時(shí)間服從分布進(jìn)行刻畫(huà)，并以顧客滿(mǎn)意度為優(yōu)化目標(biāo)，綜合考慮裝載量、按時(shí)返回、每一顧客點(diǎn)僅被服務(wù)一次等限制條件，建立了外賣(mài)O2O配送車(chē)輛路徑問(wèn)題模型，并對(duì)上海市徐匯區(qū)某入駐外賣(mài)O2O平臺(tái)餐飲企業(yè)配送路徑方案進(jìn)行算例分析。

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

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

參考文獻(xiàn)：

[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] 李建，張永，達(dá)慶利. 第三方物流多車(chē)型硬時(shí)間窗路線問(wèn)題研究[J]. 系統(tǒng)工程學(xué)報(bào)，2008，23（1）：74-80.

[7] 李向陽(yáng). 遺傳算法求解VRP問(wèn)題[J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2004，25（2）：271-273.

[8] 張麗萍，柴躍廷. 車(chē)輛路徑問(wèn)題的改進(jìn)遺傳算法[J]. 系統(tǒng)工程理論與實(shí)踐，2002，22（8）：79-84.

[9] 謝秉磊，李軍，郭耀煌. 有時(shí)間窗的非滿(mǎn)載車(chē)輛調(diào)度問(wèn)題的遺傳算法[J]. 系統(tǒng)工程學(xué)報(bào)，2000，15（3）：290-294.

[10] 魏明，靳文舟，孫博. 隨機(jī)旅行時(shí)間的區(qū)域公交車(chē)調(diào)度模型及算法[J]. 公路交通科技，2011，28（10）：124-129.

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

-238.

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

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

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

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

[16] 楊博文，王靜，段輝. O2O餐飲外賣(mài)目標(biāo)市場(chǎng)發(fā)展趨勢(shì)分析[J]. 科教導(dǎo)刊（電子版），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.