周李晶

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

1 引言

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

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

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

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

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

2 問(wèn)題描述

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

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

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

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

（2）外賣配送通常采用電動(dòng)車進(jìn)行配送，有最大行駛里程限制；

（3）將滿足每個(gè)消費(fèi)點(diǎn)的需求，并且只能由一輛車訪問(wèn)一次；

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

（5）消費(fèi)點(diǎn)處有時(shí)間限制，到達(dá)時(shí)間超過(guò)規(guī)定時(shí)間要有懲罰；

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

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

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

3.1 符號(hào)說(shuō)明

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

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

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

I表示訂單的集合；

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

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

p表示單位運(yùn)輸成本；

v表示正常行駛的速度；

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

E表示車輛起始點(diǎn)；

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

TAi表示車輛到達(dá)i的時(shí)間點(diǎn)；

TLi表示車輛離開(kāi)i的時(shí)間點(diǎn)；

[a,b]表示消費(fèi)者的時(shí)間窗；

PT表示餐廳備餐時(shí)間；

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

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

β表示單位時(shí)間懲罰成本；

FC表示固定成本；

PC表示時(shí)間懲罰成本。

決策變量：

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

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

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

3.2 模型建立

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

上層模型：

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

下層模型：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 餐飲商鋪?zhàn)鴺?biāo)

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

表3 訂單信息

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

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

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

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

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

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

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

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

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