周李晶

（華北電力大學(xué) 經(jīng)濟與管理學(xué)院，北京 102206）

1 引言

電商的迅速發(fā)展使實體店受到前所未有的壓力，各零售商紛紛轉(zhuǎn)型，線上和線下共同協(xié)力滿足客戶要求，線上接收客戶訂單，完成資金流和信息流的流通，線下致力于服務(wù)質(zhì)量，保證顧客的忠誠度。隨著市場競爭的加劇，電商企業(yè)需根據(jù)市場需求制定戰(zhàn)略以加大市場份額，O2O模式的優(yōu)勢愈發(fā)明顯。

O2O 模式指的是線下的商務(wù)時機和互聯(lián)網(wǎng)聯(lián)合，使互聯(lián)網(wǎng)變成線下業(yè)務(wù)的平臺。最典型的O2O模式應(yīng)用案例是餐飲行業(yè)，外賣的飛速發(fā)展使消費者的多樣化需求更能得到滿足，快節(jié)奏生活中點外賣成為工作人群的首選。O2O供應(yīng)鏈?zhǔn)菢?gòu)建以交易平臺為中心的物流網(wǎng)絡(luò)，顧客在平臺上下單，訂單信息通過匯總移交給食品零售商進行生產(chǎn)制作，然后平臺發(fā)放配送訂單，由配送員根據(jù)實際情況選擇接收配送訂單，完成配送任務(wù)。配送是最接近消費者的一環(huán)，是O2O供應(yīng)鏈的關(guān)鍵環(huán)節(jié)之一，配送效率的提升可以促進供應(yīng)鏈整體效率的提升，供應(yīng)鏈效率的提升也進一步提高了物流配送效率，兩者相輔相成[1]。

中國餐飲外賣市場正在發(fā)生一些深刻變化，推動這些變化的既來自于外部環(huán)境，也來自于內(nèi)部原因。從配送入手優(yōu)化配送路線，可以節(jié)約成本并提高效率，從而提升顧客滿意度，保證顧客忠誠度，使供應(yīng)鏈整體效益得以增加。以供應(yīng)鏈視角去解決配送這個瓶頸問題，可以從多個主體出發(fā)考慮路徑優(yōu)化問題，在保證供應(yīng)鏈整體效益基礎(chǔ)上盡可能滿足多方需求。

O2O 模式的興起給學(xué)者們提供了新的研究思路。孔棟，左美云和孫凱[2]在早期總結(jié)出3個分類維度并構(gòu)建了O2O 模式分類體系。趙道致和楊潔[3]提出決策模式的選擇策略，根據(jù)決策主體構(gòu)建三個模型并分別分析其利潤。趙志偉和喬晗[4]通過大數(shù)據(jù)分析了加盟外賣平臺后利潤變化的影響因素。尤寶慶[5]將供應(yīng)鏈管理融入O2O配送模式中，分析兩者關(guān)聯(lián)，為電子商務(wù)和物流業(yè)的發(fā)展提供新的視角。顧淑紅和花均南[6]基于茶葉行業(yè)特點分析消費者特征以增加柔性化。趙泉午[7]等人構(gòu)建了配送中心到需求點近似配送距離的選址及分配優(yōu)化模型。陳萍和李航[8]以顧客滿意度最大化為目標(biāo)，其中滿意度以到達(dá)時間的函數(shù)進行描述，對配送路徑進行優(yōu)化。

餐飲O2O 配送是多方參與的活動，牽扯到多方利益，但大多數(shù)學(xué)者僅僅考慮單目標(biāo)的優(yōu)化。缺乏從供應(yīng)鏈視角去考慮路徑優(yōu)化問題，因此本文在考慮O2O配送特點的基礎(chǔ)上，結(jié)合道路交通狀況，考慮配送車輛的最大里程數(shù)基礎(chǔ)上，搭建配送總時間最短作為上層目標(biāo)，固定成本、配送成本和時間懲罰成本之和最小為下層目標(biāo)的雙層規(guī)劃模型，考慮車輛總數(shù)和顧客時間窗，采用NSGA-Ⅱ算法求得可行的訂單分配和配送路徑。

2 問題描述

在餐飲外賣環(huán)境基礎(chǔ)上進行研究，首先要分析外賣配送的特點。通常情況下，外賣訂單的接單高峰期是每天中午和晚上用餐時間，大量配送員被調(diào)用起來完成分配或者主動接收訂單，接到訂單后立即趕往餐廳實體店等待食品的完成，然后再立即送至客戶手中，其間有時間限制。時間越短，顧客滿意度就越高。時間是外賣配送重點關(guān)注的因素之一，同時平臺也關(guān)注配送成本的問題。餐飲實體店希望平臺能夠高質(zhì)量地完成線上訂單以及線下配送工作，從而提高顧客的忠誠度，平臺則希望在滿足餐飲實體店的前提下縮減物流成本來獲得更多利潤。

因此本文研究的內(nèi)容可以描述為：配送員在開始接單時刻前到達(dá)起始點，起始點是地區(qū)中心大型商業(yè)聚集區(qū)，從起始點開始接單后到多個商家和消費者間進行取餐和送餐，對于同一個訂單要保證先取餐后才能送至客戶。合理分配訂單和配送路徑，使配送員經(jīng)過合理的路線完成配送任務(wù)，再次回到起始點進行下一次接單。在滿足消費者需求、車輛總數(shù)和最大里程數(shù)等限制下，商家以總時間最短、平臺以配送成本最低作為目標(biāo)為消費者進行服務(wù)。

結(jié)合外賣配送特點可作如下假設(shè)：

（1）每個時刻有等待接單的配送員數(shù)量限制；

（2）外賣配送通常采用電動車進行配送，有最大行駛里程限制；

（3）將滿足每個消費點的需求，并且只能由一輛車訪問一次；

（4）配送途中不接單，有商家消費者先后次序的要求；

（5）消費點處有時間限制，到達(dá)時間超過規(guī)定時間要有懲罰；

（6）高峰期送餐會受到路況信息的影響，這種影響已知；

（7）調(diào)動配送員從起始點出發(fā)，在交付任務(wù)完成后返回起始點。

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

3.1 符號說明

R={m|m=1,2,...,M} 表示餐廳集合;

C={n|n=1,2,...,N} 表示消費者集合;U=R ?C 表示所有節(jié)點集合;

訂單o=(mo,no),mo ∈R,no ∈C；

I表示訂單的集合；

V={k|k=1,2,...,K}表示車輛的集合；

L表示每輛車充滿電后運行的總里程；dij表示從i到j(luò)的距離，i ∈ U,j ∈U ；

p表示單位運輸成本；

v表示正常行駛的速度；

αij表示i到j(luò)路徑的交通路況系數(shù)；

E表示車輛起始點；

Te表示從起始點出發(fā)的時間，Te=0；

TAi表示車輛到達(dá)i的時間點；

TLi表示車輛離開i的時間點；

[a,b]表示消費者的時間窗；

PT表示餐廳備餐時間；

WT表示為顧客服務(wù)時間；

Ti表示到達(dá)時間，i ∈U；

β表示單位時間懲罰成本；

FC表示固定成本；

PC表示時間懲罰成本。

決策變量：

xijk：車輛k從節(jié)點i駛向j則取1，否則為0；

yok：把訂單o分配給車輛k則取1，否則為0。

對符號dij進一步說明，考慮到現(xiàn)實生活中道路設(shè)施布置，總是存在任意點i到j(luò)的可行路徑存在，且距離長度使用曼哈頓距離進行測算。

3.2 模型建立

上述餐飲配送路徑優(yōu)化問題可以通過以下雙層規(guī)劃模型進行描述：

上層模型：

上述模型中，目標(biāo)函數(shù)（1）表示的是以餐飲商家為出發(fā)點考慮最小化配送時間，由準(zhǔn)備時間、運輸時間、服務(wù)時間三部分組成；約束（2）保證每個顧客只訪問一次；約束（3）和（4）表示從起始點出發(fā)的車訂單完成后回到起始點；式（5）是連續(xù)性約束；式（6）表示車輛總數(shù)限制；約束（7）表示每輛車總里程限制；約束（8）是每個訂單只能分配給一輛車；式（9）是決策變量約束。

下層模型：

上層模型的約束同樣也是下層模型的約束。此外，下層模型中，目標(biāo)函數(shù)（10）表示從平臺出發(fā)的最小化總成本，并且分為三個部分：派車固定成本、運輸成本和時間懲罰成本；式（11）表明從起始點出發(fā)時間為0；約束（12）表示訪問順序的約束，先到餐飲點再到消費者；式（13）表示從離開i點到達(dá)j的時間點計算；式（14）和式（15）分別是離開餐飲點和消費點的時間點計算；約束（16）是時間窗限制。

其中時間懲罰成本函數(shù)如下所示：

懲罰函數(shù)中懲罰成本與超出消費者時間窗的時間存在線性關(guān)系，這是符合實際情況的。

4 算法設(shè)計

本文建立的上述模型是典型的整數(shù)雙層規(guī)劃模型，屬于NP-hard問題，沒有精確的算法，遺傳算法是常用來求解雙層模型的算法。雙層規(guī)劃模型是一個需要綜合考慮上下層求解的問題，并且上下層具有不同的優(yōu)先級。上層是從餐飲商家出發(fā)考慮建設(shè)更快的響應(yīng)系統(tǒng)，僅對上層模型進行分析，在數(shù)量不大的情況下接收到的訂單都可以進行相對合理的分配。但下層決策者不光要完成時間上的要求，還需要在訂單和路徑安排上進行優(yōu)化，使總成本達(dá)到最低。對這個問題，需采取時間懲罰函數(shù)連結(jié)兩層模型，使得兩者彼此牽制，才能得到雙方都比較滿意的結(jié)果。

結(jié)合實際意義和模型的特點，本文采用NSGA-Ⅱ算法進行求解。NSGA-Ⅱ算法是Deb 等學(xué)者在2000年對NSGA算法的改進，由此能通過計算得到一系列多樣性好、分布均勻的最優(yōu)解集。NSGA-Ⅱ是目前最流行的多目標(biāo)遺傳算法之一，它降低了非劣排序遺傳算法的復(fù)雜性，具有運行速度快，解集的收斂性好的優(yōu)點。NSGA-Ⅱ算法的流程具體如下：

（1）隨機產(chǎn)生初始化種群。

（2）使用帕累托優(yōu)勝級別排序法對種群內(nèi)全部個體進行分級排序。

（3）根據(jù)種群個體特點選擇精英個體進入下一代種群。

（4）使用模擬二進制交叉等方法產(chǎn)生子代種群。

（5）將父代中精英個體和子代種群合并構(gòu)成下一代種群。

（6）如果達(dá)到迭代次數(shù)條件則停止并輸出結(jié)果;否則繼續(xù)循環(huán)。

5 算例結(jié)果與分析

為驗證所建模型的合理性和算法的有效性，本文以北京市昌平區(qū)回龍觀鎮(zhèn)地區(qū)的外賣配送為例，將商業(yè)聚集地點作為餐飲商家，將回龍觀各小區(qū)作為消費者，通過查閱資料獲取合理的相關(guān)數(shù)據(jù)，構(gòu)建測試算例并進行仿真實驗。

根據(jù)地圖實際情況建立坐標(biāo)軸，商家和消費者地點坐標(biāo)見表1 和表2。假設(shè)某時刻T，外賣平臺接收到30 個訂單，訂單具體情況見表3。假設(shè)在T 時刻，在初始點有20輛車等待分配，由于使用電動車進行配送，最大里程數(shù)為15km，單位運輸成本4元/km，速度15km/時，備餐時間和等待時間都是5min，單位懲罰成本0.5元/min，固定派車成本5元/輛，交通阻塞系數(shù)為隨機生成0.5-1范圍內(nèi)的數(shù)來降低行駛速度，時間窗采用實際平臺上常見的標(biāo)注時間30min。設(shè)計算法采用Matlab2014a實現(xiàn)。

表1 餐飲商鋪坐標(biāo)

表2 消費者坐標(biāo)

表3 訂單信息

最終路徑規(guī)劃圖如圖1所示，商業(yè)聚集區(qū)比較聚集，居民區(qū)往往距離熱鬧繁華的商業(yè)街有一定距離，而且小區(qū)分散較廣，遠(yuǎn)不如商業(yè)區(qū)的密集程度。這也是導(dǎo)致配送員在分配時只能拿到1 至2 個訂單的原因。從圖中也可以發(fā)現(xiàn)，距離下單餐館比較近的地區(qū)往往多單一起配送，而位于較遠(yuǎn)處的消費者配送時目的較為明確，方向比較固定。

圖1 最終配送路徑規(guī)劃圖

表4 最終求解的訂單分配與路徑規(guī)劃

實驗結(jié)果表明，在滿足時間約束條件下，所花費的成本為667.93 元，其中固定派車成本20 元，從表4可以看到20 輛車都進行派遣來滿足上層時間的要求，懲罰成本為31.74 元，并不是很高，除個別訂單外，大部分滿足在30min 以內(nèi)。每個人接收1 至2 個訂單，比較符合現(xiàn)實情況。

采用NSGA-Ⅱ算法的收斂圖如圖2 所示。該算法的收斂速度快，迭代50 次即趨于平穩(wěn)，算法效率高，說明該算法是有效可行的。

6 研究結(jié)論與展望

圖2 下層模型求解的收斂曲線

本文從供應(yīng)鏈的角度，從餐飲商家和外賣平臺兩個參與主體出發(fā)，解決了餐飲O2O 模式中各主體不同優(yōu)化目標(biāo)的問題，建立了上層模型時間最短,下層模型配送成本最低的雙層規(guī)劃模型,并采用NSGA-Ⅱ算法來進行求解,算例求解的結(jié)果證實了模型和算法的合理性和有效性。除此之外,實驗結(jié)果表明,為了滿足商家時間上的要求，盡可能把所有配送車輛派遣出去，而且懲罰成本比派遣的固定費用更影響決策。因此，本文提出以下建議：各主體應(yīng)該具備基本的供應(yīng)鏈思維，不應(yīng)盲目追求自己的目標(biāo)，而是把供應(yīng)鏈作為一個整體來尋求利益最大化；外賣平臺應(yīng)該提升自己的管理能力，要充分考慮顧客和餐飲商家的感受，建立起公平完善的管理機制，合理地進行決策；物流專員也應(yīng)該提高服務(wù)水平，以保持較高的客戶滿意度。

在未來的研究中，還可以重點關(guān)注自營物流與第三方物流的合作，并考慮加入訂單不確定因素，更接近現(xiàn)實生活。