基于遗传算法并考虑时间窗的冷链产品配送路径优化

侯 玲，张治国，徐英展

（1.四川大学锦城学院，四川 成都 611731；2.成都信息工程大学 物流学院，四川 成都 610103）

1 引言

随着经济发展和生活水平的逐渐提高，人们对生鲜产品的需求逐年增加，冷链配送得到高速发展。冷链物流需要在整个供应链环节对温度进行控制，以保证配送产品的质量，因此冷链配送有较强的时效性和质量要求。如何在降低物流成本的情况下优化配送车辆路径，实现快速准时配送，受到广泛关注。

Dantzig和Ramser[1]在1959年率先提出了车辆路径问题的数学模型，并对模型进行求解分析；Pedro Amorim[2]等研究了葡萄牙产品配送车辆路径优化问题，但没有涉及货物在运输中的损耗问题。我国对生鲜物流配送车辆路径的研究要滞后于国外，但仍然有很多学者取得了相应的成果：如李雅萍[3]研究了鲜活农产品的冷链物流车辆路径问题，将固定成本、运输成本和时间窗约束进行整合处理；潘璠，等[4]将物流及时性和客户配送与客户服务公平性考虑到生鲜产品配送车辆路径问题中，但是并没有引入时间窗等针对生鲜特殊属性的约束要求；葛显龙，等[5]提出带有时间窗的生鲜物流配送车辆路径问题，并设计自适应遗传算法求解了该模型。

通过以上分析总结可以看到，国内外学者们对VRP问题进行了许多探讨，由于生鲜产品的特有属性，其配送问题涉及到运输方案、模型目标等不同，因此在建模和求解算法上存在很大区别，已有文献多是沿用传统VRP问题的研究方法，没有充分考虑生鲜物流配送的损耗、客户的时间窗要求和需求动态性。

本文对冷链配送进行分析，充分考虑配送成本最小化和客户满意度最大化，在配送路径优化模型基础上为每个客户设置时间窗，在模型中加入时间窗约束，规定配送车辆必须在时间窗范围内到达客户位置并对其进行服务，若超过时间窗规定则会舍弃掉该规划方案；同时引用冷链产品腐蚀模型来评价配送产品的新鲜程度，在提高客户满意度的同时，优化后的路径使配送成本最小。在模型求解过程中，设计自适应遗传算法，通过MATLAB编程运算，得到全局最优解，并通过算例进行验证。

2 问题描述

本文所描述的冷链配送车辆路径优化问题是指一个配送中心有若干冷藏车，已知多个冷链配送需求点，且冷藏车能满足多个配送点的需求。冷藏车从配送中心出发，按照规划的配送顺序，将货品依次送至客户手中。其中，配送的货物为冷链生鲜产品，配送中心与各需求点以及各需求点之间的距离已知，配送中心的货物容量能满足所有需求点的货量需求，冷藏车的容量、运输费率、冷藏费率已知，生鲜产品的损耗系数已知，各冷藏车的载货量及费用相同，客户的需求量、要求运达时间窗已知。在上述条件已知的情况下，科学合理的对配送车辆进行路径优化，合理规划派送顺序，在产品配送满足所有客户时间窗要求的前提下，使配送总成本达到最小。

3 模型建立

3.1 建模思路

本文以配送总成本最小为前提，在总成本的计算中加入产品腐败成本和时间窗限制。不同客户有不同的时间窗要求，当一种配送方案的配送到达时间无法满足所有客户的时间窗要求时，将这种配送方案舍去。在客户满意度达到最大的情况下，得到最优的配送方案。

该冷链配送车辆路径优化模型主要考虑以下几点：

（1）冷链产品因其易腐特性，无法长时间保鲜，因产品腐败产生的费用是配送总成本的重要组成。本模型加入货损成本，更具现实意义。

（2）由于冷链产品易变质的特性，客户对配送时间都会有较严格的要求，而且货品配送至客户位置后，一般都会进行二次加工，不能在规定时间内将货物配送至客户手中就会大大降低客户满意度。本文路径优化模型加入客户时间窗要求，满足不同客户的时间要求，提升了客户满意度。

（3）模型以总成本最小化为目标函数，其中总成本包括车辆的派遣成本、运输成本、制冷成本以及冷链产品的变质损耗成本。在合理前提以及约束限制下，通过合理规划车辆配送顺序，使得在配送总成本最小的同时满足所有客户的时间窗要求。

（4）合理使用车辆资源。尽量以较少的冷藏车辆满足所有客户需求，减少车辆派遣费用，同时要求一辆冷藏车服务的客户不能过多，防止车辆超载和因服务时间过长而造成超时配送。

（5）减少单个客户的被服务次数。指一个客户仅由一辆冷藏车进行配送，避免客户的货品需求被分割，减少客户操作次数的同时降低配送环节总成本。

3.2 模型的一般假设

在冷链配送环节中存在很多不可避免的复杂因素，如道路状况、车辆状况、天气等复杂因素，这些因素无法避免并会导致计算结果存在一些细微误差，但不影响优化合理性。因此，本文进行以下合理假设：

（1）假设配送道路均为畅通，冷藏车在配送中视为匀速运动；

（2）冷藏车的载重量可以满足若干个需求点的需求量；

（3）冷藏车载重量等参数均相同且状况良好；

（4）客户的需求量、位置、时间要求等参数已知；

（5）配送中心的容量可以满足所有需求；

（6）所运载货品为单一类型的货品；

（7）在配送过程中，冷藏车车厢内外的温度保持恒定不变。

3.3 模型的约束条件

本文配送路径优化模型必须在满足一定约束条件下进行，在约束条件的限制下求得总成本最低方案。根据冷链配送的实际情况，针对模型的基本条件，提出约束条件如下：

（1）冷藏车配送路径起点和终点均为冷藏库；

（2）规划方案要满足所有需求点的需求量；

（3）冷藏车的装载量必须小于冷藏车的额定装载量；

（4）一辆冷藏车可以负责多个配送点的配送任务；

（5）每个配送点只能由一辆冷藏车一次性完成配送；

（6）车辆必须在需求点的时间窗内送达。

3.4 模型的参数设置

O表示冷链配送中心；

M={i=1,2,...,M0}表示配送需求点即客户的集合；

N={n=1,2,…,N0}表示冷藏车的集合；

P表示冷藏车的最大容量；

Fn表示第n台冷藏车的派遣成本，Cp为总派遣成本；

c0为冷藏车每公里运输成本，C0为冷藏车总运输成本；

α为制冷剂单价,β为单位时间制冷剂消耗量，Cf表示配送过程总制冷成本；

price为配送货品单价，η为冷链配送中货品的

U=O⋃M表示所有节点的集合，包括冷链配送中心和需求点；

Qi表示第i个客户的冷藏品配送量；损耗系数；

dij表示从需求点i到需求点j的路程长度；

tij表示从需求点i到需求点j的运输时长，其中i,j∈U；

ti1表示客户的时间窗上限，ti2表示客户的时间窗下限，其中i∈U；

V为冷藏车行驶的平均速度；

Ctotal表示冷链物流配送总成本。

决策变量：

Xijn表示第n(n ∈N )辆冷藏车是否从需求点i到需求点j(i ,j∈M )间进行派送，值为1时表示是，值为0时表示否；

Yin表示第i(i∈M)个需求点是否由第n辆冷藏车进行派送，值为1时表示是，值为0时表示否；

3.5 冷链产品物流配送成本分析

（1）车辆派遣费用。车辆派遣费用主要包括车辆保养、维护以及人力资本费用等，包含哪些费用及如何计算费用视具体情况而定，为方便计算，不进行展开细化，车辆派遣成本可以表示为：

（2）运输成本。运输成本指在配送环节中，因车辆行驶而产生的费用，一般指油耗费用。总运输成本C0可表示为：

（3）制冷成本。冷链配送环节中，冷藏车通过一些措施来控制车内温度，使货品一直保存在低温环境中。在配送过程中，一直会有制冷费用的产生，制冷费用与运输时间有关，本文用β表示制冷剂单位时间的消耗量，冷链配送运输过程中制冷成本费用可表示为：

（4）冷链产品损耗成本。由于冷链产品的易腐败特性，在低温配送过程中，虽然处于相对低温的状态，但仍然存在腐蚀变质过程。本文在冷链产品配送环节成本中增加了因冷链产品腐败而带来的腐败损耗成本。

因本文讨论的冷链产品配送一般为市内配送，配送时间相对较短，并且冷藏车车厢内部处于相对低温环境，冷链产品的腐败速率大大减小，运用简单的常速连续型质变曲线来描述冷链产品配送过程中的品质变化情况，如图1所示。

图1 常速质变连续型质变曲线

运输过程中货品的损耗系数为η，冷链产品单价为price，则运输过程中冷链产品的损耗成本Cs可以表示为：

因冷链产品品类众多，大多数包装良好，如红酒、牛奶等生鲜产品，在配送环节中基本不会发生腐败情况，所以损耗成本计算要根据实际情况而定。

3.6 模型建立

模型中各表达式含义如下：

目标函数（5）为冷链配送的总成本，包括车辆派遣成本、运输成本、制冷成本与货品损耗成本，模型以总成本最小化为决策目标；式（6）限制冷藏车不能超载；式（7）表示出发冷藏车总数不得大于最大车辆数N0；式（8）表示配送起点和终点均为配送中心；式（9）表示一个需求点只能由一辆冷藏车完成配送；式（10）为流量守恒限制，即到达需求点的车辆必须离开需求点；式（11）为各需求点间行驶时间的计算公式；式（12）表示冷藏车需要在规定时间内到达客户位置；式（13）、式（14）为决策变量。

4 基于遗传算法的模型求解

由于问题的复杂性，本文采用遗传算法求解，具体算法流程如图2所示。

4.1 染色体编码

进行染色体编码时，需要将所有车辆的线路选择情况转化为遗传算法的染色体集合，每条染色体代表着不同的车辆路径选择方案，通过对每条染色体的适应度评价和遗传操作，筛选出较优的线路方案。

本文采用实数编码的方法，以需求点的个数即客户数量M0作为基因长度，第M个基因位即代表第M个需求点。用车辆数量N0作为基因位的基因值，即1到N0的随机整数，代表每个需求点被分配到的配送车辆。如染色体4242113表示第5、6个需求点由车辆1配送，第2、4个需求点由车辆2进行配送，第7个需求点由车辆3进行配送，第1、3个需求点由车辆4进行配送。

这种编码方式只体现了冷藏车需要对哪几个配送需求点进行配送，而没有将具体的配送顺序体现出来，所以在后续的适应度计算中，会将不同车辆的需求点按时间窗排序，以时间窗排序的结果进行适应度计算。

图2 遗传算法流程图

4.2 种群初始化

种群初始化是遗传操作的开始，初始种群由一定规模的不同个体组成，通过适应度的计算、选择、交叉、变异等操作生成子代群体，之后不断进行迭代计算，直到达到模型算法的终止条件。所以，初始种群的个体数量影响着后续遗传操作过程，由于模型程序的特殊性，当初始种群过小时，可能出现种群中无可适应环境的个体的情况，无法进行后续的遗传操作；当初始种群过大时，则会导致运算时间过长，降低计算效率。

本文讨论的冷链产品配送，一般为市内短途配送，所涉及需求点较少，不需要很大的初始种群规模，因此，初始群体中的染色体数定为100个，运用MATLAB程序生成100行、M0列的矩阵，使用实数编码生成初始种群。

4.3 适应度函数处理

适应度用来表示每条染色体的生存概率，用适应度函数求出每一代种群中所有染色体的生存概率，从而根据每条染色体的生存概率进行比较和筛选。由于本文的目标函数为配送总成本最小，因此，在目标函数的处理上以总成本的倒数作为适应度函数，即f=1/Ctotal。如果染色体所对应的配送方案违反了模型的约束条件，则将该方案的配送成本Ctotal设为inf，即无限大，使得该染色体的适应度f=0。

4.4 遗传操作

（1）选择算子。选择操作的目的是选择较好的个体进入下一代，淘汰掉适应度差的个体。选择操作以适应度的大小为依据判断个体是否能进入下一代，即种群基因的优胜劣汰。本文选择轮盘赌策略和最大保留策略相结合的方法来选择算子。轮盘赌策略是通过个体适应度占群体总适应度的比例计算出来，通过个体适应度的占比来选择个体，但是当种群数量过大时，往往不能选择合适的算子，即相当于随机选择个体，所以结合最大保留策略，即将群体中适应度最高的个体保存到下一代，并且保留的个体不进行交叉变异操作，以确保目前较好的染色体会保留到子代，提高算法的有效性，促进算法收敛。

（2）交叉操作。交叉操作是生成新染色的主要途径，通过将两条染色体的部分基因互换来生成新的染色体，参加交叉的染色体由交叉概率来确定，本文采取单点交叉的方法随机选择一个位置作为交叉点进行配对交叉，如图3所示。

图3 交叉操作示意图

（3）变异操作。为了扩大遗传算法的搜索空间，对部分染色体进行变异操作，通过改变某个染色体的部分基因来生成新的染色体，进行变异操作的个体通过变异概率进行选择。本文采用产生随机数的方法进行变异，即随机选择一个基因位进行变异，如图4所示。

4.5 终止条件

当整个基因流程操作循环次数达到迭代次数上限时，即可得到最优染色体，从而得出最优的行车线路方案。

图4 变异操作示意图

5 算例分析

5.1 算例数据

以某牛奶公司部分配送订单为例，该公司对市内12个配送点进行配送，配送出发点和终点为0，配送需求点为12家超市，配送中心与12个配送点的间距见表1。

表1 配送中心及配送点间距表（单位：km）

每天运载奶制品的冷藏车从配送中心出发的时间为上午8:00，出发后，依次到达各个配送需求点位置进行配送。每个客户的时间窗和需求量各不相同，为方便程序计算，将客户要求到货时间转换为发车时间的差值的时间窗，当天客户的时间窗和需求量见表2。

公司的冷藏车采用耗油制冷，通过计算即可得出单位时间内的制冷成本αβ=7元/h。冷藏车每公里的运输成本c0=0.75元/km。以客户数目换算人力资源使用费用为车辆派遣成本，车辆派遣成本为Cp=60元。冷藏车在市区中的行驶速度V=40km/h，因运输产品为包装较好的牛奶，所以在计算成本的过程中不计算货品的损耗成本，所以η=0。

每辆冷藏车能装载100件牛奶，客户的需求量订单也以件数为单位，故以牛奶的件数为冷藏车装载量和客户需求量单位，车辆载重P=100。

表2 配送点的需求量与时间窗

5.2 参数设定

需求点数量M0=12；配送站点闲置冷藏车数N0=5；冷藏车的额定载重量P=100；冷藏车每公里的运输成本c0=0.75；冷藏车单位时间的制冷成本αβ=7；货品的损耗系数η=0；冷藏车行驶的平均速度V=40；遗传算法交叉概率jc=0.9；遗传算法变异概率by=0.1；遗传算法每代个体数gan=100；遗传算法迭代次数gn=100。

5.3MATLAB求解

本文运用MATLAB2013a进行编程求解冷链产品配送路径优化问题，设定好参数后在MATLAB2013a中导入程序代码，即可得出最佳路线方案。

冷藏车1：配送中心→配送点1→配送点3→配送点7→配送点9→配送中心；

冷藏车2：配送中心→配送点8→配送点11→配送中心；

冷藏车3：未发车；

冷藏车4：配送中心→配送点12→配送点4→配送点5→配送点2→配送点6→配送点10→配送中心；

冷藏车5：未发车。

具体各配送点到达时间见表3。

冷藏车返回配送站点的时间也做了记录，记录情况如下：

冷藏车1：发车时间8:00，返回配送站点时间10:04，耗时124min；

表3 配送点到达时间

冷藏车2：发车时间8:00，返回配送站点时间9:08，耗时68min；

冷藏车3：未发车；

冷藏车4：发车时间8:00，返回配送站点时间10:19，耗时139min；

冷藏车5：未发车。

5.4 优化结果分析

本文运用数学模型和遗传算法，通过MATLAB编程进行求解运算，并以某牛奶公司的部分配送数据为例，规划了一套新的冷链配送车辆路径规划方案，可以从以下两个方面检验方案的可行性：

（1）配送路径的合理性。被选中的3辆冷藏车从配送中心出发，按照各自的配送顺序依次对客户完成配送服务，完成所有配送服务后返回配送中心。

（2）配送的时间窗约束。本文的配送模型加入了时间窗的约束条件，目的是让所有冷藏车都能在客户规定的时间内到达客户位置，若算例的优化结果发生了提前配送或者超时配送的情况，则说明模型算法不合理。由表3可知，冷藏车到达客户位置对客户进行服务的时间均在客户的时间窗要求内，3条配送线路均没有出现提前配送或者超时配送的情况，满足了所有客户的时间窗要求，对客户满意度有很大的提升。

综上所述，通过本文的模型与算法得出的配送车辆路径规划方案科学合理，路径无交叉、重复的现象，同时，得出的车辆路径规划方案满足了所有客户的时间窗，有效提升了客户满意度。

6 结语

本文综合考虑了冷链物流的易腐败特点、客户的时间窗要求等，以总成本最低为数学模型的决策目标，提出产品冷链物流配送路径优化的数学模型，然后合理使用并改进遗传算法，使用MATLAB数学软件进行编程求解，合理规划冷链配送车辆的行驶路径。最后以某牛奶公司的配送情况为算例，优化配送路线，使配送车辆都能在规定时间窗内对客户进行服务，提升了客户满意度，真实反映最小化配送总成本的同时达到全局优化。

本文设计的数学模型与算法编程仍有一定的局限性。如当订单过多、约束条件过多时，可能出现无法进行遗传操作的情况，所以当出现订单过多的情况时，要结合实际情况，对遗传算法的部分参数进行修改，如种群数量、迭代次数以及交叉变异的概率，从而使模型算法更加高效地运行。