基于客戶分類的即時配送路徑優(yōu)化研究

于江霞，杜紅亞，羅太波

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

0 引 言

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

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

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

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

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

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

圖1 分類結果Fig.1 Classification results

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

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

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

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

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

2.1 問題描述

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

針對該問題，本文做出如下假設：

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

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

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

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

2.2 模型構建

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

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

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

Q——車輛的容積限制；

V——車輛行駛速度；

Ct——單位運輸成本；

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

ts——客戶的服務時間；

qi——客戶i的需求量；

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

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

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

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

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

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

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

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

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

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

3 遺傳算法設計

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

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

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

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

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

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

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

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

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

4 案例分析

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

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

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

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

表3 本文方案Table3 Scheme of this article

圖5 種群進化趨勢圖Fig.5 Trend of population evolution

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

將本文方案與企業(yè)當前沒有采取客戶分類的配送方案進行對比分析來驗證模型的合理有效性.其中，企業(yè)當前配送方案如表5所示，兩個方案的對比分析如表6所示.

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

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

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

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

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

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

5 結 論

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