于江霞，杜紅亞，羅太波

(西安電子科技大學(xué)經(jīng)濟(jì)與管理學(xué)院，西安710126)

0 引 言

即時(shí)配送是按照客戶隨時(shí)提出的配送需求，即刻在城市內(nèi)進(jìn)行取送服務(wù)的物流活動(dòng).《2019年第1季度中國(guó)即時(shí)配送市場(chǎng)研究報(bào)告》指出，65.4%的即時(shí)配送用戶會(huì)關(guān)注送達(dá)是否超時(shí)[1]，由此可見(jiàn)，配送的準(zhǔn)時(shí)性已成為影響客戶網(wǎng)購(gòu)決策的關(guān)鍵因素.如何提高配送準(zhǔn)時(shí)性是各企業(yè)共同面臨的難題，而對(duì)客戶進(jìn)行精細(xì)化管理成為解決該問(wèn)題的方法之一.因此，本文將客戶分類考慮到配送路徑優(yōu)化中，以期用最小的成本提高配送準(zhǔn)時(shí)性，為企業(yè)贏得更多潛在效益.

即時(shí)配送路徑優(yōu)化問(wèn)題是面對(duì)電子商務(wù)同城配送業(yè)務(wù)而提出的一類時(shí)效性和準(zhǔn)時(shí)性更強(qiáng)的帶時(shí)間窗車輛路徑問(wèn)題(VRPTW)，是對(duì)車輛路徑問(wèn)題(VRP)的擴(kuò)展.目前，VRPTW問(wèn)題可以分為如下幾類：軟時(shí)間窗[2]、硬時(shí)間窗[3]、模糊時(shí)間窗[4]、混合時(shí)間窗[5]的車輛路徑問(wèn)題.由于VRP帶有很多的不確定性因素，很多學(xué)者對(duì)隨機(jī)需求[6]、動(dòng)態(tài)需求[7]、需求可拆分[8]以及考慮交通路況[9]等的VRPTW 問(wèn)題進(jìn)行了研究并取得了很好的成果.近幾年，在即時(shí)配送領(lǐng)域，有關(guān)生鮮[10]、外賣[11]和“同日達(dá)”[12-13]的配送問(wèn)題受到很多學(xué)者的關(guān)注，但大多是圍繞客戶滿意度和服務(wù)客戶數(shù)的角度進(jìn)行研究.綜上，這些研究往往忽視了客戶價(jià)值因素，事實(shí)上，為不同價(jià)值客戶提供同樣的配送服務(wù)很有可能會(huì)造成優(yōu)質(zhì)客戶的流失.為了提高配送的準(zhǔn)時(shí)性并得到優(yōu)質(zhì)客戶的發(fā)展和維護(hù)，本文結(jié)合客戶的消費(fèi)特征構(gòu)建出基于客戶分類的即時(shí)配送路徑優(yōu)化模型，以總成本最小為目標(biāo)對(duì)即時(shí)配送車輛路徑問(wèn)題進(jìn)行研究.

1 客戶分類及懲罰函數(shù)設(shè)定

傳統(tǒng)的VRP模型認(rèn)為客戶價(jià)值是相同的，在設(shè)定懲罰函數(shù)時(shí)也是同等處理，這顯然違背了優(yōu)質(zhì)客戶想要得到更精準(zhǔn)配送服務(wù)的心理愿景，更是違背了商家想要維護(hù)和發(fā)展優(yōu)質(zhì)客戶的初衷.本文以RFM模型[14]即消費(fèi)近度R(最近一次購(gòu)買時(shí)間)、消費(fèi)頻次F和平均消費(fèi)額M為分類依據(jù)，對(duì)某即時(shí)配送平臺(tái)510位客戶的32 475條消費(fèi)數(shù)據(jù)進(jìn)行挖掘分析，對(duì)數(shù)據(jù)進(jìn)行歸一化處理后通過(guò)python3.6 平臺(tái)使用DBSCAN算法進(jìn)行聚類，得到四組數(shù)據(jù)，結(jié)果顯示噪聲比為0.39%，輪廓系數(shù)為0.706，聚類效果良好.由于客戶消費(fèi)近度R差別不大，本文主要根據(jù)消費(fèi)頻次F與消費(fèi)金額M來(lái)刻畫(huà)客戶特征，具體結(jié)果如圖1所示.

第1組共80位客戶，其消費(fèi)頻次和金額都高于平均值，約占總消費(fèi)頻次和金額的50%左右，一旦失去此類客戶會(huì)對(duì)商家造成極大損失，故將其歸為核心客戶.因該類客戶對(duì)配送準(zhǔn)時(shí)性要求較高，為避免失去此類客戶必須在預(yù)計(jì)時(shí)間內(nèi)服務(wù)，所以懲罰成本為一個(gè)較大的數(shù)，其懲罰函數(shù)看似簡(jiǎn)單卻極為嚴(yán)格，具體為

式中：F1為核心客戶的懲罰函數(shù)；ti為客戶i的實(shí)際送達(dá)時(shí)間；Ti為客戶i的預(yù)計(jì)送達(dá)時(shí)間.

圖1 分類結(jié)果Fig.1 Classification results

第2組和第3組共280位客戶，或是消費(fèi)頻次或是消費(fèi)金額高于平均值，約占總消費(fèi)頻次和金額的40%～45%，是商家重點(diǎn)挖掘價(jià)值并發(fā)展為核心客戶的對(duì)象，本文將其歸為一類稱為潛力客戶.設(shè)定此類客戶在超時(shí)10 min內(nèi)的懲罰成本與超時(shí)時(shí)間呈線性增長(zhǎng)，當(dāng)超時(shí)10 min后為避免因超時(shí)過(guò)長(zhǎng)導(dǎo)致客戶產(chǎn)生負(fù)面情緒甚至流失，設(shè)定懲罰成本呈指數(shù)增長(zhǎng)，具體為

式中：F2為潛力客戶的懲罰函數(shù)；Cp為單位超時(shí)懲罰成本.

第4組共150位客戶，其消費(fèi)頻次與金額都低于平均值，約占總消費(fèi)頻次和金額的5%～10%，對(duì)企業(yè)的價(jià)值最低，將其稱為邊緣客戶.因其價(jià)值較低不宜投入過(guò)多成本來(lái)維護(hù)，本文設(shè)定此類客戶在超時(shí)10 min內(nèi)和10 min以外的懲罰成本均為固定值，具體為

式中：F3為邊緣客戶懲罰函數(shù)；P1為超時(shí)10 min內(nèi)的懲罰成本；P2為超時(shí)20 min內(nèi)的懲罰成本.

2 即時(shí)配送路徑優(yōu)化模型

2.1 問(wèn)題描述

本文研究的即時(shí)配送車輛路徑問(wèn)題如下：某即時(shí)配送平臺(tái)接到n位客戶的訂單，要求在客戶預(yù)計(jì)送達(dá)時(shí)間內(nèi)完成配送.其中，配送中心可支配的車輛數(shù)為m輛，配送車輛的最大容積為Q，若未能在客戶的預(yù)計(jì)時(shí)間內(nèi)送達(dá)則會(huì)產(chǎn)生相應(yīng)懲罰，不同類別的客戶所對(duì)應(yīng)的懲罰成本不同.因此，需要在滿足客戶需求的前提下，安排合適經(jīng)濟(jì)的配送方案.

針對(duì)該問(wèn)題，本文做出如下假設(shè)：

(1)車輛從配送中心出發(fā)，沿著一條路線將貨物送達(dá)指定客戶，最終回到原點(diǎn)；

(2)配送中心可使用車輛充足且型號(hào)和容量相同；

(3)每輛車可以服務(wù)多個(gè)客戶，但每個(gè)客戶僅能被一輛車服務(wù)一次；

(4)不考慮車流量及路況限制，車輛采用平均行駛速度.

2.2 模型構(gòu)建

本文所研究模型的變量和參數(shù)如下：

N——客戶點(diǎn)集合，N={i|i=0,1,2,…,n}，其中0為配送中心；

K——車輛集合，K={k|k=1,2,3,…,m} ；

Q——車輛的容積限制；

V——車輛行駛速度；

Ct——單位運(yùn)輸成本；

tij——車輛從客戶i到客戶j的行駛時(shí)間；

ts——客戶的服務(wù)時(shí)間；

qi——客戶i的需求量；

Ck——車輛k的固定成本；

xkl——若車輛k在l位置上服務(wù)了客戶，則xkl=1，否則為0；

——若車輛k在l位置上服務(wù)的客戶為i，則否則為0；

——車輛k從i駛向j則為1，否則為0；

hk——車輛k被啟用則為1，否則為0；

ai——若客戶i屬于核心客戶則為1，否則為0；

bi——若客戶i屬于潛力客戶則為1，否則為0；

ci——若客戶i屬于邊緣客戶則為1，否則為0.

根據(jù)以上描述，構(gòu)建基于客戶分類的即時(shí)配送路徑優(yōu)化模型，具體表示為

式(4)為模型的目標(biāo)函數(shù)，使得固定成本、運(yùn)輸成本和超時(shí)懲罰成本之和最??；式(5)表示每輛車最多為n個(gè)客戶服務(wù)，一次只能服務(wù)一個(gè)客戶；式(6)表示每個(gè)客戶僅能被一輛車服務(wù)一次；式(7)保證和xkl的值一致；式(8)表示每輛車承載貨物總體積不能超過(guò)車輛可攜帶的最大容積Q；式(9)表示車輛是否被派出；式(10)表示車輛k到達(dá)客戶j處的時(shí)間tj與到達(dá)上一客戶i處的時(shí)間ti的關(guān)系；式(11)表示客戶i僅有一種類別屬性.

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

由于本文是對(duì)車輛數(shù)和車輛路徑的同時(shí)尋優(yōu)，常見(jiàn)的遺傳算法是以自然數(shù)編碼方式形成車輛路徑后再以插0規(guī)則形成子路徑，遺傳算子部分只能對(duì)代表車輛路徑的自然數(shù)進(jìn)行操作，容易陷入局部最優(yōu).本文提出了車輛數(shù)與車輛路徑對(duì)應(yīng)排列編碼的遺傳算法，通過(guò)對(duì)車輛數(shù)與車輛路徑的共同操作擴(kuò)大搜索面積并提高產(chǎn)生新有效基因的能力，從而克服早熟現(xiàn)象.算法流程圖如圖2所示，具體設(shè)計(jì)思想如下.

(1)編碼.本文編碼分為兩步：第一步，前n列隨機(jī)生成代表車輛數(shù)的0-1 實(shí)數(shù)，1代表車輛終止配送，0代表繼續(xù)配送；第二步，后n列隨機(jī)生成代表車輛路徑的1-n序數(shù)，2n列基因碼共同構(gòu)成一條染色體.例如有9個(gè)客戶點(diǎn)，染色體編碼為001010011241536978，此基因序列表示共4輛車，配送路徑分別為2-4-1，5-3，6-9-7，8.

圖2 算法流程圖Fig.2 Algorithm flowchart

(2)初始種群和適應(yīng)度函數(shù).首先由上述編碼方式隨機(jī)生成一組路徑方案，即一個(gè)V2n?N的二維矩陣(N為種群數(shù))，然后進(jìn)行約束條件的逐條檢驗(yàn)，若違反了某個(gè)約束條件，則給予一定懲罰使其適應(yīng)度降低從而將其淘汰.本文選取目標(biāo)函數(shù)的倒數(shù)為適應(yīng)度函數(shù)，即

(3)選擇.為提高遺傳算法性能，本文在輪盤(pán)賭的基礎(chǔ)上采用精英保留策略[15]，避免優(yōu)秀染色體被破壞，提高求解效率.

(4)交叉.對(duì)前n列0-1 數(shù)和后n列自然數(shù)共同進(jìn)行交叉操作.首先，使相鄰個(gè)體進(jìn)行兩兩配對(duì)，避免重復(fù)交叉.其次，在前n列0-1數(shù)中隨機(jī)選取交叉點(diǎn)i，取位置i的左邊部分進(jìn)行交換.在后n列自然數(shù)中隨機(jī)選中兩個(gè)基因點(diǎn)進(jìn)行交換交叉.通過(guò)對(duì)前n列與后n列的交叉操作產(chǎn)生新染色體，具體運(yùn)算原理如圖3所示.

(5)變異.對(duì)前n列0-1 數(shù)和后n列自然數(shù)共同進(jìn)行變異操作.在前n列中隨機(jī)選取變異點(diǎn)進(jìn)行0-1 互換變異.對(duì)于后n列，隨機(jī)選取兩個(gè)位置的基因進(jìn)行交換變異.通過(guò)上述對(duì)前n列和后n列的變異操作，得到新的子代染色體，具體運(yùn)算原理如圖4所示.

圖3 交叉操作示意圖Fig.3 Cross operation diagram

圖4 變異操作示意圖Fig.4 Mutation operation diagram

4 案例分析

本文采用西安市某即時(shí)配送公司提供的數(shù)據(jù)，該公司是一家專業(yè)的即時(shí)配送服務(wù)公司，為客戶提供餐飲外賣、商超便利等配送服務(wù).對(duì)該平臺(tái)進(jìn)行數(shù)據(jù)采集，以某時(shí)刻的業(yè)務(wù)場(chǎng)景為例，為36個(gè)客戶點(diǎn)提供服務(wù)，通過(guò)規(guī)劃出合理的配送方案以滿足客戶需求并保證總成本最低.模型參數(shù)如表1所示，其中，固定成本的設(shè)定綜合考慮了購(gòu)買車輛的費(fèi)用、配送員的平均薪資、車輛的維修費(fèi)和折舊費(fèi)以及車輛的使用壽命和出車次數(shù)而設(shè)定，因配送車輛大多為電動(dòng)車，運(yùn)輸成本根據(jù)電池續(xù)航能力和充電費(fèi)用而設(shè)定，懲罰成本是調(diào)研和參考企業(yè)目前的懲罰成本并結(jié)合本文的相關(guān)分析而設(shè)定的.以上述聚類結(jié)果為基礎(chǔ)，采用貝葉斯算法訓(xùn)練數(shù)據(jù)得到分類模型以判定36個(gè)客戶的所屬類別，客戶需求信息及類別判定結(jié)果如表2所示.

表1 相關(guān)參數(shù)取值Table1 Related parameter values

以上述客戶類別判定結(jié)果為基礎(chǔ)，通過(guò)MATLAB R2016a平臺(tái)求解配送方案，設(shè)置交叉概率pc和pc1分別為0.9和0.92，變異概率pm和pm1分別為0.08和0.05，終止迭代次數(shù)G為600.得到基于客戶分類的配送方案如表3所示，其算法的種群進(jìn)化趨勢(shì)如圖5所示.

表2 客戶需求信息及所屬類別Table2 Customer demand information and category

表3 本文方案Table3 Scheme of this article

圖5 種群進(jìn)化趨勢(shì)圖Fig.5 Trend of population evolution

從圖5可以看出，該算法具有收斂性，種群最終向優(yōu)秀發(fā)展.為了驗(yàn)證算法的有效性，將傳統(tǒng)遺傳算法與本文算法隨機(jī)試驗(yàn)6次得到的方案進(jìn)行對(duì)比，結(jié)果顯示本文算法尋優(yōu)能力更強(qiáng)，具體如表4所示.A為傳統(tǒng)遺傳算法，B為本文算法.

將本文方案與企業(yè)當(dāng)前沒(méi)有采取客戶分類的配送方案進(jìn)行對(duì)比分析來(lái)驗(yàn)證模型的合理有效性.其中，企業(yè)當(dāng)前配送方案如表5所示，兩個(gè)方案的對(duì)比分析如表6所示.

由表6可以看出，本文方案中一類和二類客戶的配送延時(shí)較企業(yè)配送方案有明顯降低，提前到達(dá)率達(dá)到了99.48%，一類客戶和二類客戶的配送時(shí)效性也分別提高了56.05%和19.23%.另外，總的配送用時(shí)和超時(shí)時(shí)間也有相應(yīng)改善，分別減少了15.73%、85.95%.雖然從短期看企業(yè)需要付出一定成本，但是通過(guò)客戶分類企業(yè)可以使其資源得到合理分配，通過(guò)準(zhǔn)時(shí)性的提高來(lái)建立良好口碑從 而吸引和發(fā)展優(yōu)質(zhì)客戶，贏得更多長(zhǎng)期潛在效益.

表5 企業(yè)配送方案Table5 Distribution scheme of enterprise

表6 兩種方案對(duì)比分析Table6 Comparative analysis of two schemes

為了驗(yàn)證模型的適用性，本文增設(shè)了兩個(gè)案例進(jìn)行分析.其中，采用本文客戶分類得到的方案為a、c，企業(yè)不進(jìn)行客戶分類的方案為b、d，具體如表7所示.

表7 其他案例的對(duì)比分析Table7 Comparative analysis of other cases

綜上所述，本文方法雖然支付了一定的額外成本，但從長(zhǎng)期的戰(zhàn)略角度看，有利于發(fā)展維持優(yōu)質(zhì)客戶并吸引新客戶，擴(kuò)大企業(yè)影響力并促進(jìn)企業(yè)的可持續(xù)發(fā)展.

5 結(jié) 論

為提高配送準(zhǔn)時(shí)性并得到優(yōu)質(zhì)客戶的發(fā)展和維護(hù)，從戰(zhàn)略角度為企業(yè)尋求更多潛在效益，本文對(duì)客戶消費(fèi)數(shù)據(jù)進(jìn)行挖掘分析，將客戶分為三類，根據(jù)每類客戶的特點(diǎn)設(shè)置了超時(shí)懲罰函數(shù)，構(gòu)建了基于客戶分類的即時(shí)配送路徑優(yōu)化模型，同時(shí)設(shè)計(jì)了合適的遺傳算法求解算法.實(shí)驗(yàn)結(jié)果驗(yàn)證了模型的合理性和算法的有效性.