摘 要： 针对不确定环境下生鲜电商路径优化问题，考虑客户决策的有限理性特点，以累积前景理论为基础，针对生鲜电商的特点，构造以货损成本、惩罚成本、运输成本最小为目标，以代理点需求、车辆装载质量和客户要求服务时间窗为约束，建立了生鲜电商配送路径优化模型.采用改进粒子群算法对模型进行求解.计算结果表明：基于累积前景理论的模型能够更有效的满足客户对时间窗的要求，会相应的提高配送服务的满意度并在一定程度上提高企业效益，为生鲜电商企业优化配送路径提供理论支撑.
关键词： 累积前景理论； 车辆路径问题； 生鲜电商； 时间窗； 改进粒子群算法
国内生鲜电商的市场发展前景广阔，但盈利情况却仅有1%[1].影响生鲜电商盈利的因素主要有：我国冷链物流发展的滞后，生鲜电商配送成本过高.而带时间窗的车辆路径问题(VRPTW)分为软时间窗和硬时间窗，是对VRP问题进一步的改进.目前，对车辆路径的研究大多采用启发性算法，并取得了一定的成果.但是生鲜电商配送相较于传统配送更看重于配送的及时性[2].生鲜电商的配送路径优化还处于起步阶段.龚树生，梁怀兰[3]等对生鲜食品的冷链物流网络进行了研究.
然而常用的路径优化方案忽略了天气、路况、人为等不确定因素的影响，导致配送方案结果存在一定偏差.配送路径优化很大程度上依赖于交通系统，而交通系统容易受供给和需求两方面影响[4].不确定条件下人们的决策行为容易受到个人习惯偏好、对待风险态度的影响.Kahneman等在有限理性假设的基础上提出累积前景理论(cumulative prospect theory, CPT)[5].目前基于累积前景理论研究路径优化的文献不多，任亮等[6]基于累积前景理论建立了考虑运输时间的4PL路径优化模型.笔者主要针对顾客对时间窗的细化要求，建立了一个通过灵活调节惩罚系数来满足不同顾客对时间窗的要求同时节省商家配送成本的模型.
生鲜电商的配送问题可以描述为，顾客经网站或手机APP下单后，商家安排配送.但不论是商家自行配送或者经过第三方配送，都是先到相应的代理点(或自营点、自提点)，然后再根据客户地址进行细化配送的，笔者基于此研究同城配送中心向各个代理点配送的路径优化问题.相较于经典VRP问题[7]增添的约束条件如下：①针对生鲜食品的易腐特点增加了货损成本；②针对电商配送的时间特性增加了惩罚成本；③运用累积前景理论确定单位惩罚系数；④每辆车载重量相同，行驶速度恒定，即配送时间仅与配送距离有关.
1.1 模型参数和变量
1.1.1 参数
cij为从点i到点j的运输成本；l为配送中心的车辆数；bk为每辆车的载重量；wi为各代理点的需求量；cs为货损成本；α为单位时间货损系数；p为产品单价；Lvi为客户允许服务开始时刻；Uvi为客户允许服务延迟时刻；[eis,eie]为每个代理点i带有的时间窗；tjl为车辆l从出发点到代理点j的时间;θei、θli为单位惩罚系数；s0l为车辆l 出发时刻；sil为车辆l到达代理点i的时刻；tij为代理点i到j的运行时间；sei为对代理点i服务开始的时刻；sli为完成服务的时刻；ti为车辆完成代理点i配送任务所需要的服务时间；tmax为最大等待时间；te表示服务等待时间;Qi为惩罚成本，定义如下：
(1)
1.1.2 决策变量
将配送模型抽象为一个多重图R(I,E).I(|I|=n)表示配送中心及各个代理点，其中配送中心编号为0，各代理点编号为1,2，…，n；E表示可选择的配送线路的集合.配送任务及配送中心都以点i(i=0,1,2，…，n)来表示.定义变量如下：
(2)
电商物流运输时间很难精准定位，一般以离散时间进行描述.因此，将总的配送时间tijl设为一个时间段上的离散型随机变量，服从n个点上的均匀分布，且相互独立.
G表示一条从起点到目的节点的通路，即优化后的配送线路；t(G)为G的运输时间；k表示G所包含的代理点个数(k∈n).
(3)
由VRPSTW即软时间窗车辆路径问题可知，当配送时间介于Lvi和ei，以及li和Uvi之间，则需要给顾客一定的赔偿，但对惩罚系数的要求则相对模糊，笔者引入CPT通过比较配送路线上运输时间前景值来确定单位惩罚系数，从而对配送路线进行微调.而前景值可用价值函数和决策权重函数的乘积来表达.单位惩罚系数表征如下：
θei=θli=kθ0,
(4)
式中:θ0为商家确定的固定惩罚系数；k为常数，表示客户对时间窗要求的紧急程度.
2.1 价值函数
价值函数的确定与参考点的选取密切相关，笔者假设客户对配送时间的预期，参考点为t0.对于每个备选方案G，当t(G)gt;t0时，任务晚于客户预期的时间到达，表现为亏损；当t(G)≤t0时，任务早于或吻和客户预期的时间到达，表现为盈利或收支平衡.则价值函数可以表示为：
(5)
式中，0lt;α、β≤1分别表征价值函数的凹凸程度，α、β越大表示客户对收益和损失越敏感，对运输时间越在意；λ≥1，为损失相对收益的敏感性系数，λ越大表示客户对损失的厌恶程度越高，即对时间的要求越苛刻.
2.2 决策权重
大量研究证明：客户在充满不确定因素的情形下进行决策时，往往得出偏离客观概率p的主观概率ω(p)的相应结论.根据累积前景理论可知，主观概率大的事件其客观概率往往偏小，即主客观概率事件在某种程度上存在很大偏差.
因此t(G)可以表示为以概率(p-m,…,pi,…,pn)取值(t-m,…,ti,…,tn)，并且取值从大到小排列，当-m≤i≤0时，ti≥t0；当0≤i≤n时，ti≤t0.
根据Tversky等[8]在1992年提出的主观概率函数的形式，决策权重计算式如下：
ω+(p)=
;
(7)
ω-(p)=
;
(8)
式中：ω+ (p)、ω- (p)分别为针对收益和损失时的权重函数；γ、δ为模型参数，Kahneman经过试验标定γ=0.61，δ=0.69.
2.3 累积前景值
在价值函数和决策权重的基础上，根据CPT，路径G的前景值可以表示为：
V(G)=
(G)V(ti)+
(G)V(ti).
(9)
在不确定情况下，考虑不同客户对时间窗的严格要求程度的生鲜电商配送优化模型如下：
(10)
在系统优化设计问题式(10)中，目标函数表示总成本最小；约束条件C1，使车辆l 装载的货物总量不大于车辆的限定容量；约束条件C2保证每个代理点只由一辆车配送且所有代理点都得到配送；约束条件C3、C4、C5保证可形成回路；约束条件C6、C7分别是服务结束时间和最大等待时间的量化说明；约束条件C8表示一条线路上两邻接任务存在的条件；约束条件C9为时间窗约束；约束条件C10为规定是0或1规划问题.其中惩罚函数的惩罚因子由式(4)和(9)确定.
经多方研究证明，VRPSTW问题属于NP难题.笔者所构建的模型是在VRSTW问题的基础上进行改进的，也归结于NP问题.对于这类问题人们尝试运用各种启发式算法来求解，并取得了很多成果.
由于PSO算法容易出现早熟收敛或停滞现象，易陷入局部极值[9].对PSO算法最具代表性的几种变形有：线性递减PSO算法(LDPSO)[10]、带压缩因子的PSO算法(CPSO)[11].笔者结合相关文献，对基本粒子群算法在学习因子和惯性权重两方面进行改进，提高算法收敛速度.
4.1 PSO算法
PSO算法是Kennedy和Eberhart通过对鸟群飞行行为的研究于1995年首次提出的[12]，具有个体数目少、计算简单等优点.笔者将PSO应用于生鲜电商车辆配送路径的优化求解中，取得了预期的效果.PSO算法按式(11)、(12)来更新位置和速度，直到迭代结束.
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为学习因子，取值在0～4之间，通常c1=c2=2；r1、r2为(0,1)之间均匀分布的随机数；ω为惯性权重，SHI等[13]经过大量实验证明，如果加速度系数保持常数不变，ω随算法迭代的进行而线性减小，将显著改善算法的收敛性能.
4.2 改进PSO
两个学习因子在优化过程中随时间进行在[cmin,cmax]进行变化，称为同步变化的学习因子，这使得粒子在优化前期能加强全局搜索能力；在优化后期有利于收敛到全局最优解.第t次迭代时学习因子的取值公式为
c1=c2=cmax-
×t.
(13)
为克服ω的线性递减所带来的不足，将PSO算法中ω设定为服从某种随机分布的随机数.首先，在进化初期随机ω可能产生相对有效的值，加快算法的收敛速度；其次，若算法在初期找不到最优点时，ω的随机生成可以克服ω线性递减使得算法最终收敛不到此最优点的局限.
ω的计算公式为
(14)
式中：N(0,1)表示标准正态分布的随机数;rand(0,1)表示从0到1之间的随机数.
4.3 改进算法的实现步骤
同步学习因子随机权重粒子群算法的伪代码如下所示.
①Input: 种群最大迭代次数M，粒子数目N、D、cmax、cmin、μmax、μmin，以及随机权重方差
②Initialize: 初始化种群E0，设置种群代数g=0
③根据式(10)中的目标函数计算初始种群E0个体适应度函数fitness(x(i,:))
④For i=1 to N do
⑤For j=1 to D do
⑥初始化各微粒的位置x(i,j)和速度v(i,j)
⑦End for
⑧End for
⑨For i=1 to N do
⑩p(i)=fitness(x(i,:))，y(i,:)=x(i,:)
End for
pg=x(N,:)
pg为全局最优；
For i=1 to (N-1) do
If fitness(x(i,:))lt;fitness(pg)，pg=x(i,:)
End if
End for
For t=1 toM do
根据更新学习因子，更新权重
For i=1 to N do
根据式(11)式(12)更新粒子的速度和位移
If fitness(x(i,:))lt;p(i), p(i)=fitness(x(i,:))， y(i,:)=x(i,:)
End if
If p(i)lt;fitness(pg)
pg=y(i,:)
End if
End for
End for
Return: 系统最小的xm和fv
由于生鲜电商的发展处于起步阶段，关于生鲜电商配送路径优化的研究及案例较少，因而采用文献[14]的案例，在Matlab 2012a运行环境下，对模型进行验证.该问题有10个配送网点,已知车速30 km/h，每辆车的载重量为10 t，平均运输成本为1元/(t·km).群体规模为50，学习因子最大值取2.1，最小值取0.8；随机惯性权重平均值的最大值取0.8，最小值取0.5，方差取0.2.tmax=40 min，θ0=20,Qmax=1 000，α=β=0.88，λ=2.25；迭代次数200次，针对本问题，分别用本文算法、改进的遗传算法和传统算法进行对比，其最优解的对比结果如表1～3所示.
表1 3种算法30次独立运行结果比较
Tab.1 The comparison of 30 independent runs ofthree of algorithms
30次运行结果传统算法对比算法改进算法最优值452641003383最差值453641203484平均值452841123385方差1.61.41.5
表2 3种算法成本比较结果
Tab.2 The cost comparison of three kinds of algorithm
算法运输成本/元货损成本/元惩罚成本/元违反时间窗平均惩罚时间/min改进算法44117821160511.6对比算法43018001880512.6传统算法53219532041519.6
表3 3种算法计算结果比较
Tab.3 The calculation results of three kinds of algorithm
项目传统算法对比算法改进群算法最优解452641003383最优解迭代次数241720最优路线0-2-3-9-5-1-0;0-4-8-7-6-10-00-2-1-3-9-5-0;0-4-8-7-6-10-00-2-1-7-9-6-0;0-4-8-4-5-10-0
从表2和表3可以看出，笔者所采用的模型和算法在收敛速度上强于传统算法的24次，稍弱于对比算法的17次，具有如下优势：
(1)充分考虑了顾客对时间窗的需求，尽管3种模型违反时间窗的个数都是5个，但传统算法在5-1的配送过程中迟到了20 min；对比算法尽管避免了类似问题，但是在8-7的配送过程中，早到了36 min，这部分惩罚成本过大；修改后平均惩罚时间和最大违反时间都有很大程度的缩减，明显缩短了顾客的等待时间.
(2)结合时间因素在电商配送中所占的比重，在考虑惩罚成本和平均违反时间窗的情况下，本模型相比传统算法和对比算法，在运输成本和货损成本没有太明显增加的情况下，总成本节省了1 143元和717元，说明本模型更符合生鲜电商配送的要求.
(3)根据累积前景理论来突出客户对时间窗的要求，灵活调节惩罚系数，对配送路线进行精细化处理，提升客户满意度.应用累积前景理论来检验最优路线，根据前景值的大小来判别实际送达时间与客户期望时间之间的差距，来确定单位惩罚系数是否需要调整，使配送时间更贴近客户需求，从而达到提升客户满意度的目的.
为提高生鲜电商的配送效率，节省生鲜电商整体成本，考虑出行的不确定性因素和人们决策的有限理性特点，结合生鲜电商配送的时效性，引入前景值理论，提出了带软时间窗的生鲜电商路径优化模型.并对粒子群算法进行改进后求解该模型.根据CPT理论，电商企业可以根据顾客对时间窗的要求，灵活调节惩罚因子，从而对配送线路进行微调，提升顾客对配送服务的满意度.结合具体案例进行验证，通过对3种算法进行对比分析，证明了模型的有效性，求得最优路线，降低了整体成本，说明该模型在优化生鲜电商配送路径上的可行性.
参考文献：
[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] 潘璠，吴一帆，董明.生鲜食品配送车辆路径优化[J].贵州农业科学，2013,41(4):223-227.
[3] 龚树生，梁怀兰.生鲜食品的冷链物流网络研究[J].中国流通经济，2006(2):7-9.
[4] 王红玲，郑纲，何剑峰. 基于改进粒子群算法的生鲜农产品配送路径优化研究[J].贵州农业科学，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路径优化问题[J]. 计算机集成制造系统，2016,22(4): 1148-1154.
[8] 张维泽，林建波，吴洪森，等.基于改进蚁群算法的物流配送路径优化[J].浙江大学学报(工学版)，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].江西师范大学学报(自然科学版),2012,36(4):400-402.
Abstract: 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.
Key words: CPT; vehicle routing problem; fresh E-commerce; time windows; an improved particle swarm optimization
收稿日期:2017-04-15；
修订日期：2017-08-20
基金项目：国家自然科学基金资助项目(71001111)；河南省科技厅科技攻关国际合作项目(30600802)；2016年度河南农业大学科技创新基金资助项目(KJCX2016A04)
文章编号:1671-6833(2017)06-0059-05
中图分类号： TP29
文献标志码：A
doi:10.13705/j.issn.1671-6833.2017.06.008