基于改进遗传算法的生鲜农产品物流配送路径优化

陈鑫影，李依琳，肖司义

(大连交通大学 计算机与通信工程学院，辽宁 大连 116028)

车辆路径问题(Vehicle Routing Problem，简记VRP)是指在一定的约束条件下，以形成最小化配送成本为目标的配送路径方案.约束包括但不仅限于以下几点：客户需求量，客户要求时间，车辆容量等.需对配送车辆拜访客户的顺序进行合理的规划安排，最终得到实现上述目标最大化的车辆配送路径方案[1].在生鲜农产品的配送中，需要使用冷链物流进行配送，在传统的车辆路径问题的数学模型上加入冷链运输成本，就构成了生鲜农产品配送路径优化问题[2].由于利用传统方法解决车辆路径问题存在一些局限性，所以国内外学者多采用融合算法来解决该问题.Roberto等[3]在绿色车辆路径问题中，采用了遗传算法，以3-OPT局部搜索作为变异算子，并在碳排放模型中引入了道路坡度系数，以减少碳排放量.Altabeeb等[4]提出了一种新的混合萤火虫算法,将萤火虫算法与两种局部搜索和遗传算子相结合,解决受车辆容积限制的VRP问题.Saxena等[5]提出了一种遗传算法解决针对OpenMP编程模型的车辆路径问题.Lee等[6]针对电磁优化问题,设计了一种带有混合优化策略的改进新型遗传算法.Zhang等[7]提出了一种改进烟花算法，该方法基于生物地理学优化的迁移算子(BBO)得到爆炸算子，并开发了一种新的高斯变异算子，以解决高速列车调度问题.

上述研究虽取得了一定进展，但仍存在一些问题，如求解质量差、容易陷入局部最优等.遗传算法拥有极强的全局搜索能力，但容易陷入早熟收敛.烟花算法具有爆发性和多样性，可以跳出局部最优[8].因此本文融合遗传算法和烟花算法，设计一种改进型烟花遗传算法(Improved Fireworks-Genetic Algorithm,简称IFWGA),用以解决生鲜农产品配送的车辆路径问题.

1 生鲜农产品配送路径优化模型

本文主要研究生鲜农产品同城配送的车辆调度的物流路径优化问题，其问题可表述为：已知同城农产品的冷链物流配送车型，并且车辆数量足够，同时已知客户点的数量及需求量、客户期望送达时间和能接受的时间区间的条件下，建立该问题的数学模型.在完成客户需求量的情况下，尽量最小化成本，计算出一个物流配送方案[9].本文参考文献[10]，将碳排放成本和开/关门两种状态的货损率引入生鲜农产品配送路径的传统模型，提出了改进模型.该模型总成本包括以下5点:

(1)固定成本

固定成本包括租车和司机工人的工资等.若配送中心共有K辆车,则配送过程中的固定成本可用C1表示，见式(1).

(1)

式中：fk为来自第k辆车的固定成本;sk=1表示所生成的配送方案里有第k辆车的参加，sk=0代表第k辆车不参加.

(2)运输成本

运输成本是指车辆在物品配送的途中所产生的与距离相关的费用，如油耗、车辆保养等.由油耗量决定的运输成本C2，见式(2).

(2)

(3)惩罚成本

由于生鲜农产品新鲜易腐败的特性，其新鲜度会随着时间延长而逐渐下降，因此本文引入了惩罚函数这一概念.将客户可接受的迟到时间作为软时间窗，如果生鲜农产品超出了硬时间窗但未超出软时间窗，则用惩罚函数计算出惩罚成本并加入总成本之中.惩罚成本C3见式(3).

(3)

(4)货损成本

生鲜农产品具有易腐坏变质的特性.货损成本就是生鲜货品腐败变质、造成浪费时所形成的成本.在本文设计的模型中，货损成本共包括车门开启时的货损成本和车门关闭时的货损成本.

D(t)=D0e-∂t是一个计算腐败率的函数.其中，某生鲜食品在t时间的新鲜程度由D(t)表示；该生鲜食品的原始新鲜程度由D0表示；∂表示腐败率；车辆的运输时间由t来表示.

车辆在关门状态下行驶时，∂可设置为一个常数，车辆在行驶过程中∂也会变大.基于函数D(t)，得到关门状态下的货损成本C41，见式(4).

(4)

在车辆到达客户点时需要开门卸货，开门状态下的货损成本C42,见式(5).

(5)

C4=C41+C42

(6)

(5)制冷成本

冷链物流车的制冷剂费用就是制冷成本.车辆在送货途中有开门、关门两种状态，在开门状态下冷气外泄会导致温度升高,因此本文的制冷成本分为开门、关门两种状态下的制冷成本.

用热负荷来表示关门状态的制冷剂消耗量.本文引入转化系数,用Qk1来表示k车运行时的热负荷，Qk2表示k车开门状态下传入的热量，C51表示关门状态下的制冷成本，C52表示开关门过程中的制冷成本，见式(7)～式(10).

Qk1=(1+β)RS(Tw-Tn)

(7)

(8)

Qk2=α(0.54Vk+3.22)(Tw-Tn)

(9)

(10)

式(7)～式(10)中：β∈[0.1，0.2]；P2表示单位距离行驶下的制冷成本；S表示车厢的表面积；Sw表示外部的车厢面积；Sn表示内部的车厢面积；R表示传热系数；Tw表示外部的温度；Tn表示内部的温度；tij表示客户i行驶到客户j的时间；α代表了开门的频率,其取值见表1.

表1 开门频度系数

因此，总制冷成本C5见式(11).

C5=C51+C52

(11)

(6)碳排放成本

本模型考虑了碳排放所带来的成本.车辆制冷和正常行驶排放的尾气都会造成碳排放的增加.车辆的燃油消耗量是由载重和距离决定的，载货量X的车辆在固定距离中的燃油消耗ρ(X)，见式(12).

(12)

式中：车辆的负载由X表示;ρ*是车辆满载状态的燃油消耗;ρ0是车辆在不装载货物时的燃油消耗;Q是额定载重.

E1表示由车辆载货行驶产生的燃油消耗量所产生的碳排放量，E2表示制冷产生的碳排放，基于E1和E2得出总碳排放成本C6，见式(13)～(15).

E1=e0ρ(X)d

(13)

E2=wXd

(14)

(15)

式中：车辆的负载由X表示，ρ(X)表示燃油消耗；e0是二氧化碳排放系数；车辆行驶的路程由d来表示；w是单位路程的由制冷剂导致的碳排放量.其他变量含义见式(2).

因此，总成本目标函数Z可由式(16)表示：

Z=Min(C1+C2+C3+C4+C5+C6)

(16)

2 车辆路径优化算法

2.1 算法设计思路

目前，生鲜农产品配送领域存在的主要问题包括求解结果差、运行时间长、陷入局部最优等.遗传算法[11]全局搜索能力强，但易陷入早熟收敛.烟花算法[12]具有机理简单和寻优能力强等优点.因此本文采用遗传算法为主框架，利用遗传算法全局搜索能力强的优点,结合烟花算法爆炸性的特点，在较优解附近产生更多解，在较差解附近产生较少解，以解决易陷入局部最优和早熟收敛的问题.

车辆路径问题要求算法前期具有较强的全局搜索能力，后期具有较强的局部搜索能力.结合高斯变异算子和柯西变异算子，“变异步长较大能提高算法的全局搜索能力.变异步长较小则能提高局部搜索能力”[13].

因此，本文将烟花算法的变异算子设计为两种步长，步长较大的变异算子(long step-size mutation operator，简称LSMO)和步长较短的变异算子(short step-size mutation operator，简称SSMO).为实现不同求解阶段两种变异算子的切换，引入动态切换概率，根据迭代次数不同，算法前期使用LSMO的概率较大，算法后期使用SSMO的概率较大.

2.2 算法流程

本算法将遗传算法与烟花算法相结合，并引入两种变异算子，生成的改进型烟花遗传算法流程如下:

2.2.1 染色体编码

编码采用自然数编码，0代表配送中心，n表示客户点数量，k为配送车辆数量.对于有n个顾客，k辆车的VRP问题来说，染色体长度为n+k+1.例如：有10个客户分别由4辆车进行服务,一条可能的染色体如下：

0，5，0，1，2，3，7，0，8，9，6，0，4，10，0

这条染色体表示的四辆车的行驶路线为：

第一辆车：0-5-0

第二辆车：0-1-2-3-7-0

第三辆车：0-8-9-6-0

第四辆车：0-4-10-0

2.2.2 选择

选择操作采用轮盘赌选择法,并在选择过程中引入精英保留策略.

2.2.3 交叉

采用PMX交叉(部分匹配交叉)，随机抽取两条父代染色体的位置相同的片段.交换该片段，由于交换后的染色体中会出现重复值，需要根据映射关系去掉重复值，找到该重复值在另一个片段的对应位置，替换掉该重复值，如果继续出现重复值，则一直循环此步骤，直到没有重复值.

2.2.4 变异

变异操作采用交叉变异,将两个随机选中的点进行交叉变异 ,这种变异方法适用于固定位置关系的问题[14].

2.2.5 烟花算法

对每代遗传算法的最优解和最差解执行烟花算法.具体步骤如下：

(1)计算爆炸数目

在烟花算法中,每个烟花的爆炸半径和爆炸产生的火花数目是根据其相对于烟花种群中其他烟花适应度值计算得到的[15],适应度优的个体爆炸数目更多.对于烟花xi,爆炸火花数目Si见式(17).

(17)

式中：f(xi)表示个体xi的适应度值；ymax是当前种群中适应度的最大值；常数M控制最大火花数量不会超过10,为了防止除0操作设置了一个非常小的常数ε.

为了平衡较优秀的火花和较差的火花周围产生的火花数目,做出了一些限制，Smax为最大火花数目，Smin为最小火花数目,见式(18)、式(19).

Smax=round(M·0.8)

(18)

Smin=round(M·0.1)

(19)

(2)计算爆炸半径

爆炸半径与个体适应度有关，适应度优的个体半径更小，爆炸半径Ai见式(20).

(20)

(3)产生爆炸火花

本文的爆炸算子的设计为三种方式，每个烟花随机采用其中的一种.第一种是单点交换，随机选择染色体中两个除配送中心以外的点，即非0点，交换两个点的位置；第二种是插入，随机选择一个点，插入到路径中其他位置；第三种是反转，将已经生成的路径的点反向排列生成新的路径.

(4)产生变异火花

本算法的变异算子设计与爆炸算子相同，不再赘述.根据路径优化问题的特点,为平衡局部搜索能力与全局搜索能力，本算法设计了两种不同步长的变异:第一种变异算子步长为1(SSMO)，分别对当前种群的最优解和最差解进行变异操作，其变异操作与产生爆炸火花的方式相同，上文已经做出了详细介绍；第二种变异步长为6(LSMO)，对当前最优解和最差解进行变异操作，如果在6步中，最优解更新，则重新计算6步，否则输出当前解.

算法生成一个随机数r∈[0,1]，当r小于当前变异概率p，则选择SSMO，否则选择LSMO.变异概率随着迭代次数增加变大，计算见式(21)：

(21)

式中:p为当前个体变异概率;max gen为最大迭代次数;gen为当前代数.

3 某生鲜连锁超市的案例分析

3.1 数据与参数设置

本文采用某生鲜连锁超市的案例测试IFWGA算法在生鲜农产品物流配送路径优化问题中的可行性.该超市坐标数据来自百度地图，共收集了50家分店坐标，选择最中心的一个点作为配送中心.客户需求量和时间约束均为虚拟数据，使用excel的rand函数随机生成.根据市场调查，生鲜食品均在上午进行配送，因此时间在6∶00—12∶00中随机生成.由于车容量是6，因此每个客户的需求量不宜过大，在0～2之间随机生成.考虑到货物以吨为单位，服务时间在0～40 min内随机生成.

相关参数设置：种群大小为100，迭代数为1 000，交叉概率为0.8，变异概率为0.2，代沟概率为0.9，爆炸数目为10，最大爆炸半径为10.

在内存为4GB、CPU为10代i5、500GB固态硬盘的电脑上，采用MATLAB 2020进行仿真实验.实验分别从运行时间、求解质量、收敛速度方面测试了GA、FWA-EI、IFWGA和FWGA算法.其中FWGA算法是IFWGA删除LSMO和SSMO两种变异算子的算法.利用FWGA算法进行对比实验，旨在测定两种变异算子对结果的影响.

3.2 实验结果

3.2.1 求解质量对比

为验证IFWGA算法的求解质量，分别截取了GA、FWA-EI、FWGA、IFWGA算法的结果路径图，并记录了十次求解结果，见图1和表2.

试验结果表明：IFWGA得到的最优解比较稳定，4次达到最优解，对GA、FWA-EI和FWGA的结果都有明显的优化，仅有一次FWGA的运行结果略优于IFWGA.结合表2可计算得出，在总成本方面，IFWGA比GA优化了39.8%，比FWA-EI优化了16.9%，比FWGA优化了16.2%.

(a) 遗传算法(GA)

表2 总成本对比

3.2.2 收敛速度对比

为对比GA、FWA-EI、FWGA和IFWGA的收敛速度，截取了4种算法的迭代曲线图，并总结了4种算法达到最优解的代数，见图2.

图2 迭代曲线图

可以看出，IFWGA的收敛速度明显高于FWGA、GA和FWA-EI，GA在800代之后陷入局部最优，FWA-EI在900代陷入局部最优，FWGA在580代之后陷入局部最优，IFWGA在250代就达到最优.

3.2.3 运行时间对比

为了验证GA、FWA-EI、FWGA和IFWGA的运行时长，分别对4种算法运行了10次，运行时间对比见表3.其中，GA平均运行时间为54.38 s，FWA-EI的平均运行时间为76.23 s，FWGA的平均运行时间为65.72 s，IFWGA的平均运行时间为63.44 s.FWGA较FWA-EI运行时间快了10.51 s，优化了13.8%；IFWGA较GA慢了9.06 s；IFWGA较FWA-EI 运行时间快了12.79 s，优化了16.8%；IFWGA较FWGA快了2.28 s，优化了3.5%.IFWGA运行时间较FWA-EI有明显优化.虽然IFWGA在运行时间上比GA稍长一些，但在可接受范围内.IFWGA在运行时间上比FWGA快了一些，而且求解质量更高.证明IFWGA的改进和两种变异算子的设置是有效的.

表3 运行时间对比 s

4 结论

目前生鲜农产品配送存在求解结果差、运行时间长、早熟收敛等问题.为解决这些问题，首先，本文将碳排放成本和开/关门两种状态的货损率引入生鲜农产品配送路径的传统模型，提出了其改进模型.然后，将烟花算法与遗传算法相结合，每代种群中的最优解和最差解执行烟花算法，产生爆炸火花和变异火花，以增加种群的多样性.同时，为提高算法效率，兼顾全局搜索能力和局部搜索能力,设置了两种步长的动态变异算子SSMO和LSMO,由此得到IFWGA算法.

最后，选取某生鲜连锁超市的案例，从运行时间、求解质量、收敛速度方面，对GA、FWA-EI、FWGA和IFWGA 4种算法进行了对比测试.发现本文提出的IFWGA算法的收敛速度较快，变异算子设置较为合理，求解质量较高.