考慮顧客時間緊迫度的生鮮電商配送路徑優(yōu)化問題

崔 巖， 張子祥， 時 新， 王曉亮， 王振鋒

(河南農(nóng)業(yè)大學(xué) 機電工程學(xué)院，河南 鄭州 450002)

考慮顧客時間緊迫度的生鮮電商配送路徑優(yōu)化問題

崔 巖， 張子祥， 時 新， 王曉亮， 王振鋒

(河南農(nóng)業(yè)大學(xué) 機電工程學(xué)院，河南 鄭州 450002)

針對不確定環(huán)境下生鮮電商路徑優(yōu)化問題，考慮客戶決策的有限理性特點，以累積前景理論為基礎(chǔ)，針對生鮮電商的特點，構(gòu)造以貨損成本、懲罰成本、運輸成本最小為目標(biāo)，以代理點需求、車輛裝載質(zhì)量和客戶要求服務(wù)時間窗為約束，建立了生鮮電商配送路徑優(yōu)化模型.采用改進(jìn)粒子群算法對模型進(jìn)行求解.計算結(jié)果表明：基于累積前景理論的模型能夠更有效的滿足客戶對時間窗的要求，會相應(yīng)的提高配送服務(wù)的滿意度并在一定程度上提高企業(yè)效益，為生鮮電商企業(yè)優(yōu)化配送路徑提供理論支撐.

累積前景理論； 車輛路徑問題； 生鮮電商； 時間窗； 改進(jìn)粒子群算法

0 引言

國內(nèi)生鮮電商的市場發(fā)展前景廣闊，但盈利情況卻僅有1%[1].影響生鮮電商盈利的因素主要有：我國冷鏈物流發(fā)展的滯后，生鮮電商配送成本過高.而帶時間窗的車輛路徑問題(VRPTW)分為軟時間窗和硬時間窗，是對VRP問題進(jìn)一步的改進(jìn).目前，對車輛路徑的研究大多采用啟發(fā)性算法，并取得了一定的成果.但是生鮮電商配送相較于傳統(tǒng)配送更看重于配送的及時性[2].生鮮電商的配送路徑優(yōu)化還處于起步階段.龔樹生，梁懷蘭[3]等對生鮮食品的冷鏈物流網(wǎng)絡(luò)進(jìn)行了研究.

然而常用的路徑優(yōu)化方案忽略了天氣、路況、人為等不確定因素的影響，導(dǎo)致配送方案結(jié)果存在一定偏差.配送路徑優(yōu)化很大程度上依賴于交通系統(tǒng)，而交通系統(tǒng)容易受供給和需求兩方面影響[4].不確定條件下人們的決策行為容易受到個人習(xí)慣偏好、對待風(fēng)險態(tài)度的影響.Kahneman等在有限理性假設(shè)的基礎(chǔ)上提出累積前景理論(cumulative prospect theory, CPT)[5].目前基于累積前景理論研究路徑優(yōu)化的文獻(xiàn)不多，任亮等[6]基于累積前景理論建立了考慮運輸時間的4PL路徑優(yōu)化模型.筆者主要針對顧客對時間窗的細(xì)化要求，建立了一個通過靈活調(diào)節(jié)懲罰系數(shù)來滿足不同顧客對時間窗的要求同時節(jié)省商家配送成本的模型.

1 問題描述

生鮮電商的配送問題可以描述為，顧客經(jīng)網(wǎng)站或手機APP下單后，商家安排配送.但不論是商家自行配送或者經(jīng)過第三方配送，都是先到相應(yīng)的代理點(或自營點、自提點)，然后再根據(jù)客戶地址進(jìn)行細(xì)化配送的，筆者基于此研究同城配送中心向各個代理點配送的路徑優(yōu)化問題.相較于經(jīng)典VRP問題[7]增添的約束條件如下：①針對生鮮食品的易腐特點增加了貨損成本；②針對電商配送的時間特性增加了懲罰成本；③運用累積前景理論確定單位懲罰系數(shù)；④每輛車載重量相同，行駛速度恒定，即配送時間僅與配送距離有關(guān).

1.1模型參數(shù)和變量

1.1.1 參數(shù)

cij為從點i到點j的運輸成本；l為配送中心的車輛數(shù)；bk為每輛車的載重量；wi為各代理點的需求量；cs為貨損成本；α為單位時間貨損系數(shù)；p為產(chǎn)品單價；Lvi為客戶允許服務(wù)開始時刻；Uvi為客戶允許服務(wù)延遲時刻；[eis,eie]為每個代理點i帶有的時間窗；tjl為車輛l從出發(fā)點到代理點j的時間;θei、θli為單位懲罰系數(shù)；s0l為車輛l出發(fā)時刻；sil為車輛l到達(dá)代理點i的時刻；tij為代理點i到j(luò)的運行時間；sei為對代理點i服務(wù)開始的時刻；sli為完成服務(wù)的時刻；ti為車輛完成代理點i配送任務(wù)所需要的服務(wù)時間；tmax為最大等待時間；te表示服務(wù)等待時間;Qi為懲罰成本，定義如下：

(1)

1.1.2 決策變量

將配送模型抽象為一個多重圖R(I,E).I(|I|=n)表示配送中心及各個代理點，其中配送中心編號為0，各代理點編號為1,2，…，n；E表示可選擇的配送線路的集合.配送任務(wù)及配送中心都以點i(i=0,1,2，…，n)來表示.定義變量如下：

(2)

電商物流運輸時間很難精準(zhǔn)定位，一般以離散時間進(jìn)行描述.因此，將總的配送時間tijl設(shè)為一個時間段上的離散型隨機變量，服從n個點上的均勻分布，且相互獨立.

G表示一條從起點到目的節(jié)點的通路，即優(yōu)化后的配送線路；t(G)為G的運輸時間；k表示G所包含的代理點個數(shù)(k∈n).

(3)

2 基于CPT的決策方案

由VRPSTW即軟時間窗車輛路徑問題可知，當(dāng)配送時間介于Lvi和ei，以及l(fā)i和Uvi之間，則需要給顧客一定的賠償，但對懲罰系數(shù)的要求則相對模糊，筆者引入CPT通過比較配送路線上運輸時間前景值來確定單位懲罰系數(shù)，從而對配送路線進(jìn)行微調(diào).而前景值可用價值函數(shù)和決策權(quán)重函數(shù)的乘積來表達(dá).單位懲罰系數(shù)表征如下：

θei=θli=kθ0,

(4)

式中:θ0為商家確定的固定懲罰系數(shù)；k為常數(shù)，表示客戶對時間窗要求的緊急程度.

2.1價值函數(shù)

價值函數(shù)的確定與參考點的選取密切相關(guān)，筆者假設(shè)客戶對配送時間的預(yù)期，參考點為t0.對于每個備選方案G，當(dāng)t(G)gt;t0時，任務(wù)晚于客戶預(yù)期的時間到達(dá)，表現(xiàn)為虧損；當(dāng)t(G)≤t0時，任務(wù)早于或吻和客戶預(yù)期的時間到達(dá)，表現(xiàn)為盈利或收支平衡.則價值函數(shù)可以表示為：

(5)

式中，0lt;α、β≤1分別表征價值函數(shù)的凹凸程度，α、β越大表示客戶對收益和損失越敏感，對運輸時間越在意；λ≥1，為損失相對收益的敏感性系數(shù)，λ越大表示客戶對損失的厭惡程度越高，即對時間的要求越苛刻.

2.2決策權(quán)重

大量研究證明：客戶在充滿不確定因素的情形下進(jìn)行決策時，往往得出偏離客觀概率p的主觀概率ω(p)的相應(yīng)結(jié)論.根據(jù)累積前景理論可知，主觀概率大的事件其客觀概率往往偏小，即主客觀概率事件在某種程度上存在很大偏差.

因此t(G)可以表示為以概率(p-m,…,pi,…,pn)取值(t-m,…,ti,…,tn)，并且取值從大到小排列，當(dāng)-m≤i≤0時，ti≥t0；當(dāng)0≤i≤n時，ti≤t0.

根據(jù)Tversky等[8]在1992年提出的主觀概率函數(shù)的形式，決策權(quán)重計算式如下：

(7)

(8)

式中：ω+(p)、ω-(p)分別為針對收益和損失時的權(quán)重函數(shù)；γ、δ為模型參數(shù)，Kahneman經(jīng)過試驗標(biāo)定γ=0.61，δ=0.69.

2.3累積前景值

在價值函數(shù)和決策權(quán)重的基礎(chǔ)上，根據(jù)CPT，路徑G的前景值可以表示為：

(9)

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

在不確定情況下，考慮不同客戶對時間窗的嚴(yán)格要求程度的生鮮電商配送優(yōu)化模型如下：

(10)

在系統(tǒng)優(yōu)化設(shè)計問題式(10)中，目標(biāo)函數(shù)表示總成本最??；約束條件C1，使車輛l 裝載的貨物總量不大于車輛的限定容量；約束條件C2保證每個代理點只由一輛車配送且所有代理點都得到配送；約束條件C3、C4、C5保證可形成回路；約束條件C6、C7分別是服務(wù)結(jié)束時間和最大等待時間的量化說明；約束條件C8表示一條線路上兩鄰接任務(wù)存在的條件；約束條件C9為時間窗約束；約束條件C10為規(guī)定是0或1規(guī)劃問題.其中懲罰函數(shù)的懲罰因子由式(4)和(9)確定.

經(jīng)多方研究證明，VRPSTW問題屬于NP難題.筆者所構(gòu)建的模型是在VRSTW問題的基礎(chǔ)上進(jìn)行改進(jìn)的，也歸結(jié)于NP問題.對于這類問題人們嘗試運用各種啟發(fā)式算法來求解，并取得了很多成果.

由于PSO算法容易出現(xiàn)早熟收斂或停滯現(xiàn)象，易陷入局部極值[9].對PSO算法最具代表性的幾種變形有：線性遞減PSO算法(LDPSO)[10]、帶壓縮因子的PSO算法(CPSO)[11].筆者結(jié)合相關(guān)文獻(xiàn)，對基本粒子群算法在學(xué)習(xí)因子和慣性權(quán)重兩方面進(jìn)行改進(jìn)，提高算法收斂速度.

4 粒子群優(yōu)化算法與設(shè)計

4.1PSO算法

PSO算法是Kennedy和Eberhart通過對鳥群飛行行為的研究于1995年首次提出的[12]，具有個體數(shù)目少、計算簡單等優(yōu)點.筆者將PSO應(yīng)用于生鮮電商車輛配送路徑的優(yōu)化求解中，取得了預(yù)期的效果.PSO算法按式(11)、(12)來更新位置和速度，直到迭代結(jié)束.

vij(t+1)=ωvij(t)+c1r1[pij-Xij(t)]+

c2r2[pij-Xij(t)];

(11)

Xij(t+1)=Xij(t)+vij(t+1),j=1,2,…,d，

(12)

式中:c1、c2為學(xué)習(xí)因子，取值在0～4之間，通常c1=c2=2；r1、r2為(0,1)之間均勻分布的隨機數(shù)；ω為慣性權(quán)重，SHI等[13]經(jīng)過大量實驗證明，如果加速度系數(shù)保持常數(shù)不變，ω隨算法迭代的進(jìn)行而線性減小，將顯著改善算法的收斂性能.

4.2改進(jìn)PSO

兩個學(xué)習(xí)因子在優(yōu)化過程中隨時間進(jìn)行在[cmin,cmax]進(jìn)行變化，稱為同步變化的學(xué)習(xí)因子，這使得粒子在優(yōu)化前期能加強全局搜索能力；在優(yōu)化后期有利于收斂到全局最優(yōu)解.第t次迭代時學(xué)習(xí)因子的取值公式為

(13)

為克服ω的線性遞減所帶來的不足，將PSO算法中ω設(shè)定為服從某種隨機分布的隨機數(shù).首先，在進(jìn)化初期隨機ω可能產(chǎn)生相對有效的值，加快算法的收斂速度；其次，若算法在初期找不到最優(yōu)點時，ω的隨機生成可以克服ω線性遞減使得算法最終收斂不到此最優(yōu)點的局限.

ω的計算公式為

(14)

式中：N(0,1)表示標(biāo)準(zhǔn)正態(tài)分布的隨機數(shù);rand(0,1)表示從0到1之間的隨機數(shù).

4.3改進(jìn)算法的實現(xiàn)步驟

同步學(xué)習(xí)因子隨機權(quán)重粒子群算法的偽代碼如下所示.

①Input: 種群最大迭代次數(shù)M，粒子數(shù)目N、D、cmax、cmin、μmax、μmin，以及隨機權(quán)重方差

②Initialize: 初始化種群E0，設(shè)置種群代數(shù)g=0

③根據(jù)式(10)中的目標(biāo)函數(shù)計算初始種群E0個體適應(yīng)度函數(shù)fitness(x(i,:))

④Fori=1 toNdo

⑤Forj=1 toDdo

⑥初始化各微粒的位置x(i,j)和速度v(i,j)

⑦End for

⑧End for

⑨Fori=1 toNdo

⑩p(i)=fitness(x(i,:))，y(i,:)=x(i,:)

5 案例分析

由于生鮮電商的發(fā)展處于起步階段，關(guān)于生鮮電商配送路徑優(yōu)化的研究及案例較少，因而采用文獻(xiàn)[14]的案例，在Matlab 2012a運行環(huán)境下，對模型進(jìn)行驗證.該問題有10個配送網(wǎng)點,已知車速30 km/h，每輛車的載重量為10 t，平均運輸成本為1元/(t·km).群體規(guī)模為50，學(xué)習(xí)因子最大值取2.1，最小值取0.8；隨機慣性權(quán)重平均值的最大值取0.8，最小值取0.5，方差取0.2.tmax=40 min，θ0=20,Qmax=1 000，α=β=0.88，λ=2.25；迭代次數(shù)200次，針對本問題，分別用本文算法、改進(jìn)的遺傳算法和傳統(tǒng)算法進(jìn)行對比，其最優(yōu)解的對比結(jié)果如表1～3所示.

表1 3種算法30次獨立運行結(jié)果比較

表2 3種算法成本比較結(jié)果Tab.2 The cost comparison of three kinds of algorithm

表3 3種算法計算結(jié)果比較Tab.3 The calculation results of three kinds of algorithm

從表2和表3可以看出，筆者所采用的模型和算法在收斂速度上強于傳統(tǒng)算法的24次，稍弱于對比算法的17次，具有如下優(yōu)勢：

(1)充分考慮了顧客對時間窗的需求，盡管3種模型違反時間窗的個數(shù)都是5個，但傳統(tǒng)算法在5-1的配送過程中遲到了20 min；對比算法盡管避免了類似問題，但是在8-7的配送過程中，早到了36 min，這部分懲罰成本過大；修改后平均懲罰時間和最大違反時間都有很大程度的縮減，明顯縮短了顧客的等待時間.

(2)結(jié)合時間因素在電商配送中所占的比重，在考慮懲罰成本和平均違反時間窗的情況下，本模型相比傳統(tǒng)算法和對比算法，在運輸成本和貨損成本沒有太明顯增加的情況下，總成本節(jié)省了1 143元和717元，說明本模型更符合生鮮電商配送的要求.

(3)根據(jù)累積前景理論來突出客戶對時間窗的要求，靈活調(diào)節(jié)懲罰系數(shù)，對配送路線進(jìn)行精細(xì)化處理，提升客戶滿意度.應(yīng)用累積前景理論來檢驗最優(yōu)路線，根據(jù)前景值的大小來判別實際送達(dá)時間與客戶期望時間之間的差距，來確定單位懲罰系數(shù)是否需要調(diào)整，使配送時間更貼近客戶需求，從而達(dá)到提升客戶滿意度的目的.

6 結(jié)論

為提高生鮮電商的配送效率，節(jié)省生鮮電商整體成本，考慮出行的不確定性因素和人們決策的有限理性特點，結(jié)合生鮮電商配送的時效性，引入前景值理論，提出了帶軟時間窗的生鮮電商路徑優(yōu)化模型.并對粒子群算法進(jìn)行改進(jìn)后求解該模型.根據(jù)CPT理論，電商企業(yè)可以根據(jù)顧客對時間窗的要求，靈活調(diào)節(jié)懲罰因子，從而對配送線路進(jìn)行微調(diào)，提升顧客對配送服務(wù)的滿意度.結(jié)合具體案例進(jìn)行驗證，通過對3種算法進(jìn)行對比分析，證明了模型的有效性，求得最優(yōu)路線，降低了整體成本，說明該模型在優(yōu)化生鮮電商配送路徑上的可行性.

[1] Chinese electronic commerce research center. 2015 annual China e-commerce market data monitoring report [EB/OL]. [2017-02-16] http://www.100ec.cn/zt/2015sndbg.

[2] 潘璠，吳一帆，董明.生鮮食品配送車輛路徑優(yōu)化[J].貴州農(nóng)業(yè)科學(xué)，2013,41(4):223-227.

[3] 龔樹生，梁懷蘭.生鮮食品的冷鏈物流網(wǎng)絡(luò)研究[J].中國流通經(jīng)濟，2006(2):7-9.

[4] 王紅玲，鄭綱，何劍峰. 基于改進(jìn)粒子群算法的生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化研究[J].貴州農(nóng)業(yè)科學(xué)，2010,38(31):17961-17962.

[5] SIMON H A. A behavioral model of rational choice [J].Quarterly journal of economics, 1955, 69(1)99-112.

[6] TVERSKY A, KAHNEMAN D. Advances in prospect theory: Cumulative representation of uncertainty [J]. Journal of risk and uncertainty, 1922, 5(4): 297-323.

[7] 任亮，黃敏，王興偉. 考慮客戶拖期厭惡行為的4PL路徑優(yōu)化問題[J]. 計算機集成制造系統(tǒng)，2016,22(4): 1148-1154.

[8] 張維澤，林建波，吳洪森，等.基于改進(jìn)蟻群算法的物流配送路徑優(yōu)化[J].浙江大學(xué)學(xué)報(工學(xué)版)，2008,42(4):575-577.

[9] LING S H, IU H, LEUNG F H F, et al. Improved hybrid particle swam optimized wavelet neural network for modeling the development of fluid dispensing for electronic packaging[J]. IEEE transactions on industrial electronics, 2008, 55(9):3447-3460.

[10] SHI Y, EBEGERT R. Empirical study of particle swarm optimized[C]//Int Conf on Evolutionary Computation. Washington: IEEE, 1999: 1945-1950.

[11] CLERC M, KENNEDY J. The particle swarm explosion, stability, and convergence in a multidimensional complex space [J]. IEEE Transaction on evolutionary computation, 2002, 6(1):58-73.

[12] SUN J, FANG W, Wu X J, et al. Quantum-behaved particle swarm optimization; Analysis of individual particle behavior and parameter selection [J].Evolutionary computation, 2012, 20(3):349—393.

[13] Y Shi, R C EBERHART. A modified swarm optimizer[C]//IEEE International Conference of Evolutionary Computation. Anchorage, Alaska: IEEE Press, 1998.

[14] 莊景明，彭昕昀. 基于改進(jìn)遺傳算法的新鮮農(nóng)產(chǎn)品配送路線優(yōu)化研究[J].江西師范大學(xué)學(xué)報(自然科學(xué)版),2012,36(4):400-402.

FreshAgriculturalProductE-commerceDistributionRoutingProblemConsideringTimeDemandofCustomer

CUI Yan, ZHANG Zixiang, SHI Xin, WANG Xiaoliang, WANG Zhenfeng

(School of Electro-mechanical Engineering, Henan Agricultural University, Zhengzhou 450002, China)

This paper aims to explore fresh agricultural product E-commerce routing problem under uncertain environment. Considering the characteristic of the bounded rational of customer decision, fresh agricultural product E-commerce routing optimization model was established based on Cumulative Prospect Theory (CPT). According to the characteristics of fresh agricultural E-commerce supplier for fresh features. The model took the minimum cargo damage costs, transportation costs and the penalty costs as objective, the agents point demand, goods loading and times window of logistic services about customer requirements as constraints. An improved Particle Swarm Optimization algorithm was used to solve there parts of model respectively. reference examples. Simulation and test results showed that, the model based on CPT met customer requirements on time window more accurately and improved customer satisfaction. This study could provide theoretical support to the fresh E-commerce suppliers to optimize the distribution path.

CPT; vehicle routing problem; fresh E-commerce; time windows; an improved particle swarm optimization

2017-04-15；

2017-08-20

國家自然科學(xué)基金資助項目(71001111)；河南省科技廳科技攻關(guān)國際合作項目(30600802)；2016年度河南農(nóng)業(yè)大學(xué)科技創(chuàng)新基金資助項目(KJCX2016A04)

崔巖(1965— )，女，河南南陽人，河南農(nóng)業(yè)大學(xué)副教授，主要從事農(nóng)產(chǎn)品物流、交通運輸?shù)确矫嫜芯?

王振鋒(1982— )，男，河南淅川人，河南農(nóng)業(yè)大學(xué)副教授、博士，主要從事農(nóng)產(chǎn)品物流研究，E-mail:285291380@qq.com.

1671-6833(2017)06-0059-05

TP29

A

10.13705/j.issn.1671-6833.2017.06.008