生鲜农产品多车型冷链物流车辆路径优化

李军涛 刘明月 刘朋飞

(上海海洋大学 工程学院，上海 201306)

生鲜电商市场的崛起带动了冷链物流行业的发展，而车辆配送在整个物流系统中又是极为重要的一环。如何科学合理地规划配送路线，提高车辆利用率，是目前冷链物流企业亟需解决的问题[1]。

在已有相关研究中，针对冷链物流的路径优化问题大多数采用单车型配送[2-6]，而多车型主要是针对常温商品的配送[7-12]，且配送过程中车辆多假设匀速行驶，未考虑交通拥堵对实际配送的影响。对于冷链物流配送总成本构成方面，部分研究侧重于分析总成本之间的关系或将各项成本进行量化处理[13-14]。随着对低碳理念观点的深入，碳排放也被考虑其中[15-19]。目前，关于冷链物流配送总成本构成方面的研究较多，但是对配送总成本分析的不够全面。因此，本研究将在考虑拥堵指数的基础上，构建包含碳排放成本在内带有时间窗的多车型冷链物流车辆路径优化模型，拟采用自适应遗传模拟退火算法来进行求解，以期为冷链物流的车辆路径优化决策提供理论指导。

1 多车型冷链物流车辆路径优化模型构建

1.1 问题描述及假设

本研究对多车型冷链物流车辆路径优化问题描述如下：假设某冷链公司拥有1个配送中心和多种车型的车辆，配送节点(包括配送中心和配送点)集合为N{i|i=0,1,2,…,N}，车型集合为M{m|m=1,2,…,M}，车辆集合为K{k|k=1,2,…,K}。

为了对所研究的问题有更好的界定，假设条件如下：1)只有1个配送中心且能满足全部需求；2)配送中心存在多种型号的冷藏车，且车载容量不能超过该车型的最大载重量；3)车辆从配送中心出发，完成配送后并驶回；4)每个客户只能被1辆车服务，且只被服务1次；5)冷藏车服务时间均相同；6)制冷成本仅考虑运输过程中车辆维持低温所消耗的能量成本。

1.2 车辆行程时间分析

(1)

1.3 目标函数分析

1.3.1车辆配送总成本函数

1)冷藏车固定成本。

车辆的固定成本主要包括配送人员固定工资、车辆损耗成本以及车辆保养成本等。本研究假设配送中心车辆足够配送，且闲置车辆的成本不予考虑，则冷藏车固定成本F1为：

(2)

2)冷藏车运输成本。车辆的运输成本主要指燃油的消耗成本，与车辆行驶距离有关，行驶路程越长，燃油的消耗成本越高。在实际行驶过程中，车辆燃油消耗与速度之间存在非常复杂的非线性关系，且各路段对应的情况较复杂。因此本研究将油耗成本简化为单位距离运输成本与距离的乘积进行优化,则冷藏车运输成本F2为：

(3)

式中：p1为单位行使里程运输成本，元/km。

3)生鲜农产品货损成本。生鲜农产品货损成本主要指产品在配送过程由于配送时间长而导致部分产品损耗。本研究采用文献[20]中的生鲜度损耗系数的方法，则配送过程产生的货损成本F3为：

(4)

式中：p2为生鲜农产品单位价格，元/kg；T为生鲜农产品保质期，h；r为时间敏感调节因子；qi表示客户i的需求量，kg。

4)冷藏车制冷成本。制冷成本主要是指车辆在运输过程中为维持厢内低温所必须消耗的能量成本。由于制冷成本与车厢热传率、厢体受热面积以及内外温度差有关，则配送过程中产生的制冷成本F4为：

(5)

式中：p3为单位制冷剂的成本，元/kg；λ为漏热系数；R为冷藏车车厢热传率，W/(m2·K)；S为冷藏车车厢暴露于太阳辐射区域的面积，m2；ΔT为冷藏车内外的温差，℃。

5)时间窗惩罚成本。为保证生鲜农产品的质量，应对配送时间有更为严格的要求，时间惩罚成本函数C(ti)为：

配送过程中总时间窗惩罚成本F5为：

(6)

式中：ti为车辆到达客户i的时间点；[ei,li]为客户最期望服务的时间窗；[Ei,Li]为客户最大容忍的时间窗；a1为早到惩罚因数，元/h；a2为晚到惩罚因数，元/h。

6)碳排放成本。由于CO2排放量主要与燃油消耗量有关，而车辆行驶距离影响燃油消耗量，因此本研究选择投入产出法计算碳排放量。则配送过程中总碳排放成本F6为：

(7)

式中：ce为单位碳排放的环境成本，元/kg；cd为柴油的二氧化碳排放系数；θ为单位距离燃油消耗量，L/km。

根据对以上6大成本的分析，车辆配送总成本函数Z1为：

(8)

1.3.2客户满意度函数

影响客户满意度的因素有多种，对于生鲜农产品的车辆路径优化问题，考虑到易腐蚀的特点，对于时间的要求较为严格。因此，本研究主要研究时间对满意度的影响，客户对时间的总体满意度函数Z2为：

(9)

时间满意度函数f(ti)为：

1.3.3目标函数统一量纲

本研究在将配送总成本和客户满意度视为同等重要的前提下，为统一目标函数，取客户不满意度为Z′2=1-Z2。采用模糊数学方法对配送总成本函数Z1和客户不满意度函数Z′2去标量化，并赋予相同权重，即两者权重系数均取0.5，则将双目标优化转化为单目标优化问题，建立包含配送总成本和客户满意度的总目标函数Z为：

(10)

式中：ω1为配送总成本的权重系数，由于配送总成本和客户满意度被视为同等重要，本研究取ω1=0.5；ω2为客户不满意度的权重系数，同上，本研究取ω2=0.5。

1.4 约束条件分析

多车型冷链物流路径优化模型的约束条件如下。

1)保证所有客户都能得到车辆配送的约束条件为：

(11)

2)客户i只能由1辆车负责配送的约束条件为：

(12)

3)客户j只能由1辆车负责配送的约束条件为：

(13)

4)保证冷藏车起始点均为配送中心的约束条件为：

(14)

5)单辆冷藏车负责配送的全部需求量不得超出该车型车载容量的约束条件为：

(15)

6)车辆在客户j处完成配送并驶出该配送点的约束条件为：

(16)

7)为保证客户满意度，冷藏车的到达时间必须在最大容忍时间窗[Ei,Li]内的约束条件为：

Ei≤ti≤Li

(17)

2 自适应遗传模拟退火算法求解模型

遗传算法虽然具有良好的全局搜索能力和鲁棒性强的特点，但易陷入过早收敛。模拟退火算法虽然较少受到初始条件约束，但易陷入局部最优。因此，本研究采用自适应遗传模拟退火算法，增强全局和局部的搜索能力。自适应交叉、变异计算及模拟退火更新规则如下：

1)自适应变异、交叉计算。自适应变异率Pmi和自适应交叉率Pci的计算公式为：

式中：Fmax为最大适应度；Fmin为最小适应度；Pm,max为最大变异概率；Pm,min为最小变异概率；Pc,max为最大交叉概率；Pc,min为最小交叉概率；e为一个很小的正实数，为防止分母为0。

2)模拟退火更新规则。取足够大的初始温度T0，取初始解S1。对当前解进行随机扰动产生新解S2,若此解质量更好，则接受新解；否则计算S2的接受概率：P=e(ΔE/kt)，随机产生一个[0,1]区间的随机数a，若a

3 算例分析

3.1 初始数据

为验证模型和算法的有效性及可行性，本研究以上海某生鲜农产品配送中心为例，采用大(A)、中(B)、小(C)规格的3种普通冷藏车车型向20个客户进行配送。假定车辆平均行驶速度v0为40 km/h，生鲜农产品单位价格p2为2元/kg，时间敏感调节因子r为0.5，生鲜农产品保质期T为36 h，服务时间t′为0.33 h，单位制冷剂的成本p3为13 元/kg，漏热系数λ为0.245，车厢热传率R为0.4 W/(m2·K)，车厢受太阳辐射的面积S为35 m2，车厢内外温差ΔT为30 ℃，早到惩罚因数a1为100 元/h，晚到惩罚因数a2为200 元/h，单位碳排放的环境成本ce为0.25 元/kg，柴油的二氧化碳排放系数cd为2.68。因考虑生鲜配送时间，仅研究4:00—13:00各路段的拥堵指数。算法参数设置如下：种群规模取200，迭代次数取500，最大变异概率Pm,max取0.05，最小变异概率Pm,min取0.01，最大交叉概率Pc,max取0.9，交叉概率Pc,min取0.8，降温速率q取0.95，初始温度T3取2 000，终止温度Tend取20。已知配送节点的位置坐标、需求量及时间窗(表1)，百度智慧交通网预测的拥堵指数(表2)，冷藏车运输过程中的参数值(表3)。使用Matlab软件进行编程，分别采用遗传算法和自适应遗传模拟退火算法求解多车型冷链物流车辆路径优化模型(式(10)～(17))。

表1 配送节点的位置坐标、需求量及时间窗Table 1 Location coordinate, demand and time window of distribution node

表2 百度地图智慧交通网预测的拥堵指数Table 2 Congestion index predicted by Baidu map intelligent traffic network

表3 冷藏车运输过程中的参数值Table 3 Parameter values of refrigerated truck during transportation

3.2 运行结果分析

3.2.1单车型与多车型结果对比分析

为验证多车型配送的有效性，本研究采用3种车型单独配送与多车型混合配送对比分析，假设单车型配送时，每种车型最多有15辆车可供配送，其余参数保持不变，计算结果见表4。可以看出，采用多车型相比配送总成本最低的C型车配送，满意度提高1.28%，总目标函数降低31.40%，虽然C型车固定费用和运输费用都较低，但由于装载能力弱，导致配送延误降低客户满意度。同样，相比满意度最高的单车型A型车配送，虽然多车型配送在满意度上有所下降，但配送总成本降低20.01%，总目标函数降低38.80%。因此，在将配送总成本和客户满意度视为同等重要的前提下，多车型配送相比单车型更具优越性。

表4 单车型和多车型配送对算例中各目标函数值的影响Table 4 Effects of distribution of single model and multi-model on the value of each objective function in the example

The same as Fig. 1, Table 5 and Table 6.

3.2.2算法对比分析

本研究分别采用遗传算法和自适应遗传模拟退火算法来对多车型冷链物流路径优化模型进行求解，相比传统遗传算法，自适应遗传模拟退火算法收敛更快，能得到更小的总目标函数值，有效避免了遗传算法的“早熟”现象，提高了算法性能(图1)。与传统遗传算法相比，采用自适应遗传模拟退火算法求解，不仅使配送总成本降低3.52%，而且使满意度提高29.54%(表5)。因此，采用自适应遗传模拟退火算法更具有效性。

表5 遗传算法和自适应遗传模拟退火算法对算例的运算结果Table 5 Path optimization results of the two algorithms for multi-vehicle distribution

图1 遗传算法和自适应遗传模拟退火算法的迭代过程示意图Fig.1 Iterative process diagram of genetic algorithm and adaptive genetical simulated annealing algorithm

3.3 参数敏感性分析

为了考察生鲜农产品的价格、保质期以及时间敏感调节因子参数对各目标函数值的影响，以多车型冷链物流路径优化算例中参数的初始值为基准，令各参数从基准值逐渐增加(减少)5%、10%、15%、20%，当某个参数变化时，其他参数值保持不变，得到生鲜农产品的价格、保质期、时间敏感调节因子对算例中各目标函数值的影响，计算结果见表6。可见：当生鲜农产品价格p2参数变化时，对满意度影响较小，对配送总成本影响较大，但是价格与配送总

表6 价格、保质期、时间敏感调节因子对算例中各目标函数值的影响Table 6 Effects of price, shelf life and time sensitive regulatory factor on each objective function value

成本并不成正相关。由于定价升高，配送车辆发生相应变化，车辆固定成本会大幅度增大或减小，从而导致配送总成本发生改变。因此，适当的定价可使最优值最小，满意度最高，碳排放量和货损成本也相对较低。随着生鲜农产品的保质期T的增长，虽然降低了货损成本，但也会引起配送总成本的增加，主要包括制冷成本以及时间窗惩罚成本。因此，过长的保质期不一定有利于公司的配送。时间敏感调节因子r表示农产品对时间的敏感度，r值越小，农产品对时间越敏感，其生鲜度耗损系数越大，货损成本越高，但是配送总成本并不随r值减小而增大。在多车型冷链物流路径优化算例中，当r增加10%左右时，其配送总成本最低，满意度最高，最优值最小。因此，配送总成本并不是随着生鲜农产品对时间敏感度的增加而增加。

4 结束语

本研究针对冷链物流车辆路径优化问题，在考虑交通拥堵的情况下，为响应节能环保政策，以包含碳排放在内的配送总成本最小化和客户满意度最大化为总目标，构建带有时间窗的多车型路径优化模型,运用百度智慧交通网预测的拥堵指数进行算例分析。结果表明：1)采用多车型配送相比单车型不仅提高了车辆的有效利用率，而且使配送总成本和客户满意度达到相对最优水平，有利于企业的长久发展；2)自适应遗传模拟退火算法在寻优能力和寻优效率上较传统遗传算法均有明显的改善，其配送总成本和满意度也都优于传统遗传算法；3)根据生鲜农产品的价格、保质期、时间敏感调节因子参数对各目标函数值的影响分析可得，适当的定价对企业配送有利，过长的保质期会增加配送总成本，生鲜农产品对时间的敏感度与配送总成本不成正相关。