1. 引言
随着我国经济和互联网的快速发展,生鲜电商的发展前景广阔。生鲜类产品因为健康绿色有机等特点深受消费者们喜爱,随着消费者对生鲜果蔬等绿色食品的需求不断增加,对冷链物流的需求也越来越大。由于生鲜产品具有易腐蚀性的特点,生鲜电商配送要求控温储存和运输,否则产品会产生损坏腐烂等情况。和传统物流相比,冷链物流会产生更多的碳排放,其中,冷链运输是最具有碳排放能力的一个环节。因此,如何制定合适的配送计划,在满足客户需求的同时实现节能减排,是目前生鲜电商企业需要着力解决的问题。
冷链车辆路径问题(Vehicle Routing Problem in Cold-chain Logistics Distribution, VRPCLD)是典型的车辆路径问题(Vehicle Routing Problem, VRP),也是NP-hard问题,国内外学者做了许多研究。Amorim等[1]根据生鲜产品容易腐败变质的特点,建立了最大新鲜度和最小成本的双目标模型。Chi等[2]用指数型衰减函数刻画生鲜产品质量的现象。李倩[3]等在考虑客户满意度的同时为了提升配送效率,以包括货损、惩罚成本在内的综合成本最低为目标,设计了精英策略的非支配排序遗传算法求解。李想[4]等综合考虑多种因素,以最小总成本、最低碳排放、最高产品新鲜度为目标,建立多目标生鲜配送模型。高浩然等[5]从时效和品质两方面衡量客户满意度,以总成本最小为目标构建易腐品冷链配送车辆路径优化模型。
随着绿色物流理念的提出,学者们也更重视物流中的碳排放。Ning等[6]通过碳税计量碳排放成本,以碳排放成本和综合成本最小为目标建立模型。周鲜成等[7]对绿色车辆路径问题进行了综述,介绍了关于碳排放的影响因素和主要测度方法、环境效益优化目标及目标函数的构成,分析了绿色车辆路径问题的求解算法和应用领域。宁涛等[8]在对碳税机制定量分析的基础上,综合分析物流配送中的产品配送量、配送时间以及装卸货时间等常规因素,提出了一种改进的基于自适应旋转角的量子蚁群算法。李熠胥等[9]针对同时取送货的绿色车辆路径问题,以最小化带碳排放费用的配送成本为优化目标,提出了一种数学规划方法与启发式算法相结合的三阶段拉格朗日启发式算法进行求解。
在实际配送时,生鲜电商企业需要综合考虑成本、客户、环境等多种因素,传统的单目标和双目标优化难以满足企业需求。基于已有的研究成果,本文首先考虑车辆载重对油耗的影响,分析计算得到行驶油耗成本以及产生的碳排放量;其次综合考虑企业效益、客户效益和环境效益,在车辆数、车辆容量等约束下,建立最小配送成本,最大客户满意度、最小碳排放的多目标生鲜冷链配送模型,并利用NSGA-II算法对模型进行求解;对于NSGA-II算法全局搜索能力较强但局部搜索能力较弱的特点,本文设计并融入了一种局部搜索算子,可以在保证NSGA-II算法全局搜索能力的同时,提高算法的局部搜索能力,让算法更好地进行求解。算法求解结果可以为生鲜电商企业配送提供参考。
2. 问题描述与模型建立
2.1. 问题描述
为了便于研究和分析,本文做出如下假设:
(1) 配送中心拥有一定数量的冷藏车,冷藏车为同一型号且具有容量限制;
(2) 冷藏车的速度恒定,从配送中心出发,完成客户的需求后回到配送中心;
(3) 单个顾客点的需求量不超过冷藏车的容量;
(4) 顾客点只允许一辆冷藏车服务;
(5) 冷藏车的实时载重会影响车辆行驶时的油耗和碳排放;
(6) 为了保证车厢处于低温状态,冷藏车需要使用燃油让车厢保持低温;
(7) 因为生鲜产品的特性,货物的新鲜度会逐渐下降,并产生货损;
(8) 当冷藏车在客户需求时间外送达时,会产生惩罚费用。
2.2. 符号定义
变量和符号含义如表1所示。
Table 1. The meaning of symbols, variables, and sets
表1. 符号、变量和集合的含义
符号 |
含义 |
|
所有节点集合 |
|
客户节点集合 |
|
配送车辆集合,共K辆冷藏车 |
|
从节点i到节点j的距离 |
|
车辆最大容量 |
|
车辆行驶时的载重 |
|
客户点需求量 |
|
配送总成本 |
|
客户满意度 |
|
客户点的满意度 |
|
客户点的服务时间 |
|
车辆行驶时间 |
|
车辆行驶速度 |
|
车辆到达节点的时间点 |
|
配送中心时间窗 |
|
客户期望时间窗(硬时间窗) |
|
客户可接受时间窗(软时间窗) |
|
车辆行驶油耗量(L) |
|
车辆制冷油耗量(L) |
|
0~1变量,当车辆k由i点向j点行驶时为1,否则为0 |
|
0~1变量,当客户i由车辆k服务时其值为1,否则为0 |
Table 2. Definition and value of refrigerated truck parameters
表2. 冷藏车参数定义和取值
参数 |
定义 |
取值 |
|
固定发车费用 |
200元/辆 |
|
车辆单位时间使用成本 |
60元/小时 |
|
车辆空载时,单位距离油耗量 |
0.2 L/km |
|
车辆满载时,单位距离油耗量 |
0.4 L/km |
|
燃油单价 |
6.5元/L |
|
行驶过程制冷机单位时间油耗量 |
3 L/小时 |
|
服务过程制冷机单位时间油耗量 |
6 L/小时 |
|
生鲜产品单价 |
5元/kg |
|
行驶过程新鲜度衰减率 |
0.005 |
|
服务过程新鲜度衰减率 |
0.01 |
|
单位时间早到时间窗惩罚成本 |
3元 |
|
单位时间迟到时间窗惩罚成本 |
5元 |
|
燃油排放系数 |
2.621 kg/L |
|
车辆最大容量 |
3500 kg |
|
单位产品价值 |
5元/kg |
2.3. 目标函数
本文将分析生鲜电商物流配送过程中产生的各项成本以及产生的碳排放,建立总配送成本最小、客户满意度最大、碳排放量最低的多目标路径优化模型。冷藏车参数的定义和取值如表2所示。
2.3.1. 成本函数
总配送成本
包括车辆固定成本
,行驶油耗成本
,制冷成本
,货损成本
,时间窗惩罚成本
。车辆固定成本
包括驾驶员工资等固定发车费用。
为固定发车费用,
为冷藏车单位时间使用成本,车辆使用成本
如(1)所示。行驶油耗成本
和车辆载重线性相关,在冷藏车空载时,单位距离的油耗量为
;在冷藏车满载时,行驶单位距离的油耗量为
,则冷藏车的行驶油耗量如(2)所示,行驶油耗成本如(3)所示,其中
为燃油单价,
为0~1变量。制冷成本的计算会分为车辆行驶过程和服务过程,
和
分别为冷藏车行驶过程和服务过程单位时间油耗量,则冷藏车从客户点i行驶到客户点j并为客户点j服务的过程中因制冷产生的油耗量如(4)所示,制冷成本如(5)所示,
为燃油单价,
为0~1变量。新鲜度函数为
,
为衰减率,t为时间,
为初始新鲜度,本文固定为1。冷藏车在配送时产生的总货损成本
如(6)所示,其中
和
分别行驶过程和服务过程的新鲜度衰减率,
为单位产品的价值。生鲜产品拥有易腐败的特点,客户会更加看重货物的送达时间,要求在指定的时间窗
内完成配送,提前或延后送达会产生对应时间窗惩罚成本,时间窗惩罚成本
如(7)所示。
(1)
(2)
(3)
(4)
(5)
(6)
(7)
2.3.2. 客户满意度
配送的时间会影响客户满意度。客户期望在硬时间窗
之间送达,在软时间窗
内送达会降低满意度。在不同时间段送达的满意度如(8)所示。
(8)
(9)
2.3.3. 碳排放量
配送过程产生的碳排放量主要由冷藏车发动机的燃油消耗产生,燃油消耗分为行驶油耗和制冷油耗。冷藏车的碳排放量
和燃油消耗量成正比,如(10)所示,其中
为燃油排放系数。
(10)
2.4. 数学模型
以总配送成本
最小,客户满意度
最大和碳排放量
最小为目标,构建多目标VRPTW模型,如(11)~(20)所示。
(11)
(12)
(13)
(14)
(15)
(16)
(17)
(18)
(19)
(20)
式(11)、式(12)、式(13)为三个优化目标;式(14)表示冷藏车的载重不超过最大容量;式(15)表示每个客户点只能被一辆冷藏车服务;式(16)表示冷藏车在完成配送后返回配送中心;式(17)表示每一个有需求的客户点都会被服务;式(18)表示每辆冷藏车在配送中心最早开放时间出发,在配送中心关闭前返回配送中心;式(19)表示冷藏车的配送过程连贯,没有等待时间;式(20)为决策变量的取值范围。
3. 局部搜索NSGA-II算法设计
本文构建的是囊括总成本、客户满意度、碳排放三个目标在内的多目标路径优化模型,对于多目标求解模型,通常采用加权的方式,将多目标问题转化为单目标问题,这种方法较为简单,但需要主观设置每个目标的权重,求解结果容易受到权重的影响。NSGA-II算法是在生成新一代种群时加入了快速非支配排序和拥挤距离排序,可以得到一个Pareto解集,决策者可以根据自身偏好与实际情况,灵活选择配送路径。NSGA-II算法由于交叉变异的原因拥有较强的全局搜索能力,交叉变异产生的解可以覆盖大部分解空间,但局部搜索能力较弱,因此本文在NSGA-II算法的基础上,加入了局部搜索算子,在交叉变异后,对每个染色体解的邻域进行搜索,再对种群进行非支配排序和拥挤度排序,保留较好的个体,通过迭代得到Pareto解集。
3.1. 染色体的编码和解码
本文采用自然数编码的方式对染色体编码,染色体长度为需求点数量,每条染色体代表一个解,每个客户点为染色体的基因。解码时根据冷藏车容量约束对染色体解码,从第一个客户点开始对所有客户点遍历,并将客户点的需求量加入冷藏车载重,若加入客户点i的需求量后超过冷藏车最大载重,则放弃该客户点,并为该客户点派一辆新的车,例如存在客户点1、2、3、4,当客户点4超过最大载重时,当前车辆配送路径为0 → 1 → 2 → 3 → 0,并将客户点4加入下一辆车的配送路径,其中0表示配送中心。
3.2. 算法流程
Step 1. 初始化种群。初始化各种参数与变量,设置最大迭代次数。对每条染色体的基因进行随机排列,在车辆载重的约束下生成初始种群。
Step 2. 遗传算子
选择算子。计算每条染色体的目标值与适应度,目标值Z为每个目标之和,适应度
,其值为目标值Z的倒数。本文根据每条染色体适应度的大小,采用轮盘赌的方法选择保留的染色体。
交叉算子。当生成的随机数小于交叉概率时,对两条相邻的染色体进行OX交叉,生成两条新染色体。
变异算子。本文采用两点交换变异。当生成的随机数小于变异概率时,对染色体进行两点交换。
Step3. 局部搜索。合并父代种群与子代种群,删除重复的个体,并对新生成的种群进行局部搜索操作。对于新生成种群的每一个个体,都进行局部搜索操作,以拓宽解的空间,增加种群的多样性。设置最大搜索次数Kmax,并计算当前个体的目标值,设当前局部搜索次数Ka为1,对当前个体随机采用交换、插入、逆序操作以求得其邻域,如图1所示,并计算邻域解的目标值,若邻域解优于当前个体,则将邻域解代替当前个体,重置邻域搜索的次数,令Ka = 0,若邻域解劣于当前个体,则邻域搜索次数加一。当邻域搜索次数大于最大搜索次数Kmax时,结束当前个体的邻域搜索操作。
Figure 1. Swap, reverse order, insert
图1. 交换、逆序、插入
Step4. 快速非支配排序和拥挤距离排序。计算族群中每一个个体的目标值,根据个体目标值的大小对种群中的个体进行快速非支配排序,然后计算每个个体之间的拥挤距离,通过个体的层级和拥挤距离对每个个体排序,保留排名靠前的个体生成新种群。算法的流程图如图2所示。
Figure 2. Algorithm flowchart
图2. 算法流程图
4. 算例分析
4.1. 实验设置
本文运用Solomon标准算例库的算例R204进行实验,其中配送中心坐标为(35, 35),客户点数量为100个,总需求量为1458个单位,假设一个单位的货物为10 kg,总的需求量为14,580 kg。算法采用matlab编程,程序运行的软件为Matlab R2016a。最大车辆使用数为5,种群大小NP为50,交叉概率
为1,变异概率
为0.3,最大局部搜索次数Kmax为200,最大迭代次数genmax为1000。
4.2. 运行结果分析
程序运行10次,得到pareto解集,如表3所示,最优总配送成本适应度曲线如图3所示。分析表3可得如下结论:(1) pareto解集的数量为50个,和种群大小相同,意味着求解多目标问题时,能得到较多的pareto解,配送路线能有更多的选择,配送中心可以根据偏好灵活选择。(2) 配送总成本和客户满意度呈现正相关,客户满意度随着配送总成本增加而增加,说明配送中心需要在配送总成本和客户满意度之间做出选择:若需要更高的客户满意度,让服务的客户更加满意,则需要增加配送总成本;若需要更低
Table 3. Pareto optimal solution set for multi-objective model
表3. 多目标模型的Pareto最优解集
前沿 |
|
|
|
|
|
|
|
|
|
1 |
6756.9 |
0.90 |
969.5 |
837.6 |
3005.1 |
1427.6 |
1061.4 |
976.7 |
286.3 |
50 |
10,783.1 |
0.99 |
1895.1 |
1886.6 |
4263.9 |
3314.1 |
1804.3 |
1385.8 |
15.0 |
均值 |
8371.2 |
0.96 |
1340.3 |
1232.7 |
3479.3 |
2193.0 |
1439.9 |
1130.8 |
128.2 |
Figure 3. Optimal total distribution cost fitness curve
图3. 最优总配送成本适应度曲线
的配送成本,让配送中心有更多利润空间,则会降低客户满意度。(3) 配送总成本和碳排放量呈现正相关,碳排放量增加,配送总成本增加,说明降低配送过程的碳排放量,和降低配送总成本的目标是一致的,配送中心在优化配送路径,降低配送总成本的同时也能减少碳排放的产生。(4) 前沿点1的配送总成本最低,碳排放量也最低,但客户满意度最低,和前沿点50相比,总成本降低4026.2元,碳排放量降低925.64 kg,客户满意度降低0.09,说明为了降低配送总成本和碳排放量,会增加客户不满。(5) 前沿点50客户满意度最高,为0.99,但其配送总成本、碳排放量都最高,说明为了提高客户满意度,会增加较多的配送总成本和碳排放量。
4.3. 与单目标模型比较
为了验证本文多目标模型的有效性,分别以最小成本、最短配送距离、最小碳排放为目标,建立单目标模型,将局部搜索算子融入遗传算法,得到混合遗传算法进行求解。算法参数和多目标模型相同,算例和多目标模型相同,结果如表4所示。
由表4得知,以总配送成本为优化目标时,与表3点1相比,配送总成本降低38.8元,碳排放量减少20.5 kg,如果要求总配送成本最低可以选择此方案,总成本最小的配送路线图如图4所示;以配送
Table 4. Three single-objective model solution results
表4. 三种单目标模型求解结果
|
|
|
|
|
|
|
|
|
|
总成本 |
6718.1 |
0.88 |
949.0 |
807.3 |
2968.7 |
1388.6 |
1070.8 |
964.8 |
325.4 |
距离 |
6928.2 |
0.88 |
953.9 |
755.0 |
290.0 |
1421.3 |
1323.1 |
944.4 |
333.0 |
碳排放 |
6764.9 |
0.87 |
948.5 |
795.1 |
2954.1 |
1392.1 |
1106.7 |
960.1 |
352.0 |
Figure 4. Minimum cost delivery diagram
图4. 最小成本配送图
距离最短作为优化目标时,和点1相比,总距离减少82.6 km,配送总成本增加171.3元,碳排放量减少15.6 kg,该方案虽然总距离和碳排放量减少了,但配送总成本增加了,不利于配送中心的整体效益,距离最短的配送路线图如图5所示;以碳排放量最小为优化目标时,和点1相比,配送总成本增加8.0元,碳排放量减少21.0 kg,该方案追求低碳时会更好。相对于点1,在客户满意度方面三种单目标模型都偏低,表明了本文的多目标模型可以兼顾总成本、客户满意度和碳排放量,平衡多个目标。
Figure 5. The shortest distance delivery diagram
图5. 最短距离配送图
4.4. 算法有效性
为了检验本文局部搜索NSGA-II算法的求解效果,将传统遗传算法和本文改进的算法进行比较。传统算法的参数和模型参数同4.1,采用R204算例进行实验。结果如表5所示,和NSGA-II算法相比,改进算法的最小值点(前沿点1)总配送成本降低2100.6元,客户满意度降低0.6,碳排放量降低480.2 kg;均值的总配送成本降低1665.1元,客户满意度降低0.3,碳排放量降低384.3 kg。改进算法在总配送成本和碳排放量的改进上有较好的效果,但客户满意度却不如NSGA-II算法,原因是NSGA-II算法在遗传
Table 5. Improved before and after comparisons
表5. 改进前后对比
|
|
|
|
|
|
|
|
|
|
|
改进算法 |
最小成本 |
6756.9 |
0.90 |
969.5 |
837.6 |
3005.1 |
1427.6 |
1061.4 |
976.7 |
286.3 |
均值 |
8371.2 |
0.96 |
1340.3 |
1232.7 |
3479.3 |
2193.0 |
1439.9 |
1130.8 |
128.2 |
传统算法 |
最小成本 |
8857.5 |
0.96 |
1449.7 |
1365.2 |
3638.2 |
2412.7 |
1486.3 |
1182.4 |
137.8 |
均值 |
10,036.3 |
0.99 |
1724.6 |
1669.6 |
4003.6 |
2975.9 |
1709.9 |
1301.2 |
45.8 |
算子的交叉、变异操作后,直接进行非支配排序和拥挤距离排序,部分单一目标较好但其他目标很差的解会被保留到下来,导致整体求解效果欠佳;改进算法在交叉变异之后,会进行局部搜索操作,整体目标值更好的解会参与非支配排序和拥挤距离排序,这些解会更容易保留下来。
5. 结论
生鲜电商配送需要综合考虑企业效益、客户效益和环境效益等多个方面,生鲜电商企业需要在多个目标之间取得平衡,制定合理的配送策略。对于生鲜电商物流车辆路径问题,本文考虑载重对冷藏车油耗和碳排放量的影响,以最小总配送成本、最大客户满意度和最低碳排放量为目标,建立多目标生鲜电商路径优化模型,设计了一种基于局部搜索和NSGA-II算法的混合算法。算例的结果表明:(1) 本文构建的模型能在配送总成本、客户满意度和碳排放量之间取得合理平衡;(2) 配送成本和客户满意度呈正相关,提高客户满意度会增加配送成本;配送成本和碳排放量呈正相关,降低碳排放量也能降低配送成本,生鲜电商企业的决策者需要根据实际需求,灵活选择配送方案。