基于訂單拆分的線上到線下連鎖門店配送優(yōu)化模型

辛禹辰，施勝男，楊華龍

(大連海事大學(xué)交通運(yùn)輸工程學(xué)院，遼寧大連116026)

0 引 言

為應(yīng)對(duì)電商的迅猛沖擊，零售企業(yè)實(shí)施O2O(Online To Offline)轉(zhuǎn)型策略，即將線下商務(wù)機(jī)會(huì)與互聯(lián)網(wǎng)結(jié)合，互聯(lián)網(wǎng)成為線下交易的前臺(tái)，利用連鎖門店(簡(jiǎn)稱門店)向客戶配送商品[1].客戶訂單存在差異性，每個(gè)客戶對(duì)不同商品有不同的需求量；各門店的庫(kù)存容量及其所擁有商品種類也存在差異，故會(huì)出現(xiàn)一家門店無(wú)法單獨(dú)滿足一個(gè)客戶訂單需求的情況.因此，研究基于拆單的O2O多家門店共同配送問(wèn)題具有重要的現(xiàn)實(shí)意義.

O2O門店配送涉及線上訂單分配和線下物流配送兩方面.線上訂單分配問(wèn)題，已有研究很少考慮商品區(qū)分，針對(duì)客戶只含一種商品訂單的分配問(wèn)題.Wang 等[2]針對(duì)電商與OTO 包裹集成配送優(yōu)化問(wèn)題，構(gòu)建了混合整數(shù)規(guī)劃模型，并設(shè)計(jì)適合大規(guī)模問(wèn)題的混合鄰域搜索策略.有關(guān)多種商品的訂單分配問(wèn)題研究較少，文獻(xiàn)[3]針對(duì)快餐企業(yè)O2O 訂單分配中一單多品情況，提出每份快餐訂單只能分配到一家門店的訂單分配模型，即在考慮訂單不拆分的情形下進(jìn)行訂單分配.針對(duì)O2O背景下，線下物流配送主要研究一家門店向客戶配送問(wèn)題.Zhang 等[4]研究了考慮揀選員學(xué)習(xí)效果的OTO 訂單揀選和配送優(yōu)化問(wèn)題，在一家社區(qū)超市對(duì)在線訂單進(jìn)行綜合揀選和配送；陳萍等[5]基于傳統(tǒng)的取送貨車輛路徑問(wèn)題，提出適合一家餐飲企業(yè)O2O 外賣配送的優(yōu)化模型，缺乏多家連鎖門店共同配送問(wèn)題的研究.

上述研究是針對(duì)O2O訂單分配和門店配送孤立的局部?jī)?yōu)化，容易出現(xiàn)商品不能及時(shí)送達(dá)、履約率低下等問(wèn)題.此外，一單多品O2O 訂單中，會(huì)出現(xiàn)訂單中的多種商品不能由一個(gè)門店滿足的情況，需要考慮將訂單拆分.現(xiàn)有關(guān)于一單多品O2O訂單拆分問(wèn)題的研究主要是配送中心發(fā)貨的情形.張凱源[6]等針對(duì)網(wǎng)上超市一單多品訂單拆分問(wèn)題，根據(jù)商品種類在配送中心對(duì)訂單進(jìn)行拆分；韓曙光等[7]研究電商一單多品訂單拆分及配送，在配送中心對(duì)訂單進(jìn)行拆分.訂單不拆分或只在配送中心進(jìn)行拆分的研究不適合OTO 背景下，線上訂單門店分配及發(fā)貨的實(shí)際需要.

因此，本文針對(duì)O2O 背景下零售企業(yè)門店一單多品訂單分配及配送問(wèn)題，考慮各門店庫(kù)存容量限制，以及可能存在回收客戶商品退回的實(shí)際情況，提出客戶訂單僅按商品類別拆分，從多家門店分別配送各類商品的策略，構(gòu)建基于訂單拆分的O2O 門店配送優(yōu)化模型，以期為零售企業(yè)順利實(shí)施O2O轉(zhuǎn)型策略提供科學(xué)參考.

1 基于拆單的O2O門店配送優(yōu)化模型

1.1 問(wèn)題描述及假設(shè)

一家零售企業(yè)在較小區(qū)域(如城區(qū))內(nèi)擁有多家門店，一段時(shí)期內(nèi)線上平臺(tái)共接收N個(gè)客戶訂單.對(duì)于每一個(gè)訂單，企業(yè)可根據(jù)客戶地理位置、需求商品種類和數(shù)量，將訂單分配至門店，若該門店關(guān)于訂單中的某種(或某幾種)商品缺貨，則需要將訂單拆分，將缺貨商品組成的新訂單分配給其他門店.以此類推，直至該客戶訂單中商品完成配送為止.O2O背景下每位客戶(普通消費(fèi)者)訂單數(shù)量通常較少，故假設(shè)每家獲得配送任務(wù)的門店可將某種(或某幾種)商品作為一個(gè)包裹配送給客戶.在規(guī)定的時(shí)間窗內(nèi)，每輛車可以服務(wù)多個(gè)客戶，每個(gè)客戶能被多輛車服務(wù).若車輛早于或晚于客戶要求的時(shí)間窗到達(dá)，需要承擔(dān)相應(yīng)的懲罰成本.基于拆單的O2O 門店配送優(yōu)化問(wèn)題，是如何將線上平臺(tái)接收到的訂單分配至一個(gè)或多個(gè)門店，并設(shè)計(jì)各門店到客戶間物流總費(fèi)用最小的配送路徑.

為便于建模，給出以下假設(shè)：

(1)單家門店某種產(chǎn)品可以缺貨，全部門店不可缺貨；

(2)只允許按商品種類進(jìn)行訂單拆分，不對(duì)數(shù)量進(jìn)行拆分；

(3)門店把配送給同一個(gè)客戶的商品打包成一個(gè)包裹.

1.2 模型建立

符號(hào)說(shuō)明如下：

Δ={1 ,2,…,m,…,M} ——門店集合，其中，m表示門店序號(hào)，M表示門店總數(shù)；

Ω={M+1,M+2,…,M+N}——配送客戶集合，其中，N表示客戶總數(shù)；

Γm={1 ,2,…,k,…,Km} ——門店m配送車輛集合，Γm={1 ,2,…,Km} ，其中，k表示車輛序號(hào)，Km表示門店m擁有的車輛總數(shù)；

Φ={1 ,2,…,r,…,R} ——商品種類集合，其中，r表示商品種類序號(hào)，R表示商品種類總數(shù)；

U——車輛最大裝載量；

V——車輛行駛速度；

Wmr——門店m中商品r的庫(kù)存量；

F——車輛的固定成本；

G——車輛單位距離行駛成本；

Dir——客戶i對(duì)商品r的需求量；

Lij——門店(或客戶)i到門店(或客戶)j的距離，i,j∈Ω,i≠j；

δj——客戶j的時(shí)間偏離懲罰；

Ej——客戶j的最早服務(wù)時(shí)間；

Lj——客戶j的最遲服務(wù)時(shí)間；

——0-1變量，若由門店m出發(fā)的車輛k由客戶i到j(luò)，則取1，否則，取0，i≠j；

——0-1 變量，若由門店m出發(fā)的車輛k為客戶i配送商品r，則取1，否則，取0；

——車輛k由門店m出發(fā)到達(dá)客戶j的時(shí)間；

——門店m利用車輛k為客戶i配送商品r的數(shù)量.

構(gòu)建O2O門店配送優(yōu)化模型為

目標(biāo)函數(shù)：式(1)表示物流配送總費(fèi)用最小，第1 項(xiàng)為配送車輛的固定費(fèi)用，第2 項(xiàng)為配送車輛的運(yùn)輸費(fèi)用，第3 項(xiàng)為時(shí)間懲罰成本.約束條件：式(2)表示每個(gè)客戶每種商品的配送需求只能由一家門店和一臺(tái)配送車輛完成，式(3)表示每個(gè)客戶的每種商品配送需求均要得到滿足，式(4)表示門店配送的任一種商品總量均不超過(guò)該門店的庫(kù)存，即門店庫(kù)存量應(yīng)滿足其配送客戶的需求量，式(5)表示門店配送車輛數(shù)量約束，式(6)表示車輛從門店出發(fā)成功配送任務(wù)后返回門店，式(7)表示配送車輛不能從一家門店到另一家門店，式(8)表示從每家門店出發(fā)的每臺(tái)配送車輛至多為客戶配送一次，式(9)表示配送車輛從門店出發(fā)時(shí)裝載配送商品數(shù)量不能超過(guò)其裝載量限制，式(10)表示配送車輛到達(dá)客戶的時(shí)間，式(11)表示客戶配送時(shí)間偏離懲罰費(fèi)用取值.

2 求解算法設(shè)計(jì)

訂單分配和配送相結(jié)合的O2O門店配送優(yōu)化模型，實(shí)質(zhì)上是對(duì)帶時(shí)間窗的多車場(chǎng)車輛路徑問(wèn)題的擴(kuò)展，是NP難題.借鑒文獻(xiàn)[8]，設(shè)計(jì)先拆單分配，后配送路徑優(yōu)化的兩階段啟發(fā)式算法.首先，基于所有門店和客戶間的距離，進(jìn)行訂單就近拆單分配，大幅降低計(jì)算復(fù)雜性；然后，設(shè)計(jì)改進(jìn)的禁忌搜索算法對(duì)配送路徑進(jìn)行優(yōu)化.

2.1 線上訂單就近拆單分配

訂單就近拆單分配算法是按商品種類(而非按數(shù)量)進(jìn)行客戶訂單拆分，通過(guò)判斷某門店是否擁有某客戶需求的某種商品，判斷訂單是否需要拆分.在此基礎(chǔ)上，計(jì)算各客戶與各門店間的距離，按就近原則進(jìn)行訂單分配.具體步驟如下：

Step 1計(jì)算各客戶點(diǎn)與各門店之間的距離.

Step 2對(duì)客戶需求的每一種商品分別進(jìn)行分配.將客戶到各門店間的距離按升序排列，判斷距離客戶最近的門店是否能滿足客戶的某種商品需求.如果是，則該客戶的該種商品由最近的門店進(jìn)行配送服務(wù)；如果否，則轉(zhuǎn)Step 3.

Step 3除去已判斷過(guò)的門店，繼續(xù)判斷剩余門店中距離其最近的門店是否能滿足該客戶的某種商品需求.如果是，則將該客戶的該種商品由該門店進(jìn)行配送服務(wù)；如果否，則繼續(xù)Step 3.

Step 4輸出各客戶的訂單分配結(jié)果.

2.2 改進(jìn)的禁忌搜索算法

結(jié)合問(wèn)題模型特點(diǎn)，在鄰域結(jié)構(gòu)產(chǎn)生方面對(duì)禁忌搜索算法加以改進(jìn)，設(shè)計(jì)搜素速度更快的改進(jìn)禁忌搜索算法.具體步驟如下：

Step 1解的表示及初始解的生成.對(duì)節(jié)點(diǎn)進(jìn)行編號(hào)，0表示門店，如某條線路為0-4-8-10-0，表示客戶點(diǎn)4、8、10 由此線路配送.每條線路均從0 開始，經(jīng)過(guò)數(shù)個(gè)客戶點(diǎn)，最終以0結(jié)束.說(shuō)明車輛從門店出發(fā)，最終返回門店.采用隨機(jī)方式生成初始解.

Step 2鄰域結(jié)構(gòu).采用交換算子、插入算子及2-opt 交換算子3 種算子構(gòu)成的混合鄰域變換.交換算子是將解的排列中任意兩個(gè)客戶點(diǎn)的位置進(jìn)行交換，插入算子是將排列中一個(gè)客戶點(diǎn)插入到第一位置或某個(gè)客戶點(diǎn)之后，2-opt 交換算子是把兩個(gè)客戶點(diǎn)之間的所有客戶點(diǎn)路徑順序翻轉(zhuǎn)[9].在算法搜索過(guò)程中可以隨機(jī)地從3 種算子中選擇一種，以改變固定的搜索順序.

Step 3禁忌表.將每次迭代得到的最優(yōu)解作為禁忌對(duì)象放入禁忌表中，取禁忌長(zhǎng)度為一個(gè)常數(shù).

Step 4候選集合的確定.從當(dāng)前解的鄰域中隨機(jī)選擇若干個(gè)鄰居作為候選集合.

Step 5終止準(zhǔn)則的確定.采用迭代指定步數(shù)的終止準(zhǔn)則.

3 算例分析

假設(shè)某O2O零售企業(yè)有6家門店，網(wǎng)上接到54位客戶的訂單(坐標(biāo)點(diǎn)均選自標(biāo)準(zhǔn)算例庫(kù)R111 的前60個(gè)坐標(biāo)點(diǎn)，其中，每隔9個(gè)選一個(gè)為門店，剩余的為客戶點(diǎn))，該企業(yè)共有100種商品.隨機(jī)生成各門店商品庫(kù)存.門店庫(kù)存變化難以度量且門店庫(kù)存對(duì)訂單分配影響較大，對(duì)6家門店各種商品的總庫(kù)存進(jìn)行假設(shè)；門店除為線上客戶訂單服務(wù)外，還要為到店選購(gòu)商品的客戶服務(wù)；此外，門店還需保留一部分庫(kù)存以備不時(shí)之需.因此，門店庫(kù)存由這3部分組成，線下客戶難以預(yù)測(cè)及保留庫(kù)存不定，假設(shè)6 家門店各種商品的總庫(kù)存均為線上所有客戶訂單各種商品總需求的3 倍.首先，隨機(jī)產(chǎn)生每位客戶訂單商品的需求信息，商品種類數(shù)服從區(qū)間為[1,10] 的均勻分布，每種商品購(gòu)買數(shù)服從區(qū)間為[1,3] 的均勻分布.然后，運(yùn)用均勻分布在區(qū)間為[1,100] ，隨機(jī)生成各門店庫(kù)存商品種類，匯總每種商品r的所有客戶需求數(shù)量并乘以3(倍)作為該商品的總庫(kù)存量Wr；根據(jù)各門店隨機(jī)生成庫(kù)存商品種類情況，在含有商品的門店中，運(yùn)用偽隨機(jī)數(shù)發(fā)生器，依此總庫(kù)存量Wr生成各門店含有商品r的庫(kù)存數(shù)量.車輛固定成本為50元/車次，可變成本為0.7元/km，載重限制為20件包裹，平均行駛速度為60 km/h，早到懲罰系數(shù)為1，晚到懲罰系數(shù)為3.5.

使用本文方法和文獻(xiàn)[3](訂單不拆分)方法運(yùn)行算例，訂單分配結(jié)果分別如圖1 和圖2 所示，其中，編號(hào)D1～D6為門店，編號(hào)1～54為客戶.

圖1 本文方法訂單分配Fig.1 Order allocation by this paper

圖2 訂單不可拆分下訂單分配Fig.2 Order distribution without order split

對(duì)比圖1 和圖2 可以看出，在相同情況下，本文方法能完成所有訂單的配送；訂單不可拆分時(shí)，造成26 位客戶的訂單不能及時(shí)配送，約占總客戶數(shù)的48.15%.

門店庫(kù)存數(shù)量對(duì)客戶訂單履約率產(chǎn)生很大影響.令各門店商品總庫(kù)存量為客戶訂單總需求量(例如本文隨機(jī)生成量為596)的1～7 倍，進(jìn)行敏感性分析，在訂單可拆分的情況下，門店能夠完成全部客戶訂單的配送任務(wù)，配送總費(fèi)用的敏感性分析如圖3所示.

圖3 配送總費(fèi)用敏感性分析結(jié)果Fig.3 Sensitivity analysis results of total distribution cost

由圖3 可以看出，隨各門店商品總庫(kù)存量的增加，配送總費(fèi)用不斷下降，但門店庫(kù)存量從客戶訂單需求量的1 倍增加到7 倍時(shí)，配送總費(fèi)用從1 973.56 元下降至1 092.68 元(下降了44.63%)，配送費(fèi)用并未隨之成倍下降.這是因?yàn)殚T店商品庫(kù)存量增加，可以減少客戶訂單拆單，配送距離減少，配送費(fèi)用下降，但庫(kù)存與配送成本間存在效應(yīng)背反規(guī)律.因此，零售企業(yè)需要權(quán)衡門店線下和線上需求與庫(kù)存關(guān)系，結(jié)合門店庫(kù)存容量，保持合理的商品庫(kù)存規(guī)模.

訂單不可拆分時(shí)，未履約訂單數(shù)及其比率敏感性分析如圖4所示.

圖4 未履約訂單敏感性分析結(jié)果Fig.4 Sensitivity analysis results of unfulfilled order

由圖4 可以看出，隨門店總庫(kù)存量升高，未能服務(wù)的客戶數(shù)及其比率隨之降低，但仍有部分客戶未能得到服務(wù).如門店商品總庫(kù)存量為客戶訂單總需求量7倍時(shí)，仍然有10位客戶(約占18.52%)的訂單未能得到及時(shí)配送.而按本文方法，只要各門店商品總庫(kù)存量大于等于客戶訂單總需求量，客戶訂單及時(shí)配送履約率便可達(dá)到100%.因此，對(duì)客戶訂單進(jìn)行拆分處理是非常必要的，能夠有效地提高客戶訂單及時(shí)配送履約率.

4 結(jié) 論

本文針對(duì)O2O背景下訂單分配與配送問(wèn)題進(jìn)行聯(lián)合優(yōu)化.與不拆單方法相比，按照商品種類(不按數(shù)量)進(jìn)行拆單，客戶訂單中某一種類的商品只能由一家門店配送，不僅便于管理客戶退貨，還能提高客戶訂單的及時(shí)配送履約率.研究表明，在O2O 背景下，對(duì)客戶訂單按商品種類進(jìn)行拆分處理必要且有效；電商零售企業(yè)需要保持各門店合理的商品庫(kù)存規(guī)模，以滿足客戶線下和線上O2O訂單的需求.