基于改进遗传算法的冷链物流路径优化研究*

□ 解玉蝶

(江南大学 商学院，江苏 无锡 214122)

1 绪论

十三五规划指出“要大力发展城乡配送、冷链物流、第三方物流和绿色物流”，这代表着冷链绿色物流受到政府的高度关注和支持，有利于冷链物流行业的快速发展，但是我国冷链物流发展仍存在配送成本高、货损率高、环境污染严重等问题。因此，如何在冷链物流配送过程中合理调度车辆达到较高的企业效益和社会效益具有十分重要的意义。

车辆路径问题(VRP)是由Dantzig和Ramser于1959年首次提出[1]。随着冷链物流的不断发展，近年来，国内外众多学者对冷链物流VRP问题进行了广泛的研究。在考虑碳排放方面，方文婷等将节能减排转化为绿色成本，建立了以总成本最小为研究目标的冷链物流VRP模型，并将A*算法与蚁群算法相结合构造了一种混合蚁群算法进行求解[2]；陶帝豪、康凯、姚臻等考虑了冷链配送过程中的碳税成本，并设计了相应算法求解[3-5]；Liu G等在考虑碳税政策的情况下，构建了联合配送-绿色车辆路径问题(JD-GVRP)模型[6];Li L等研究了碳排放下的冷链综合库存路径优化问题[7]。在考虑顾客满意度方面，任腾等考虑了顾客满意度和道路拥堵状况，并设计了新的知识型蚁群算法[8]；Song M等研究了一个典型的冷链物流系统车辆路径问题(VRP)并提出一种改进人工鱼群(IAFS)算法[9]。在考虑不确定因素对冷链物流配送的影响方面，姚源果、吴欣等都考虑了实时路况对于冷链配送的影响[10-11]；缪小红、周新年等在保证货物不超载的情况下建立了配送模型[12]。在优化研究方法方面，Raut R.D.提出模糊多准则决策方法，并通过冷链第三方物流供应商(CTPLs)的评价和选择过程来改善食品损失[13]；Brito J.和Martinez F.J.等在建模和求解问题时，使用了一种软计算方法[14]；王维军等构建了带时间窗的冷链物流配送路径优化模型，用改进的智能水滴算法进行了求解[15]。

从以上分析可以发现，目前大多数关于冷链物流路径优化的研究范围已经很广泛，本文在现有研究的基础上，建立了以配送总成本最小为目标函数的冷链路径优化模型，并对传统遗传算法进行改进，对A企业冷链物流配送问题进行实证研究，证实了模型和算法的有效性和可行性，以期丰富冷链物流路径优化方面的研究。

2 模型构建与算法求解

2.1 问题描述与研究假设

在本文研究的冷链物流配送过程中，需要对六个方面的成本进行考虑，分别是车辆固定成本、运输成本、制冷成本、时间窗惩罚成本、货损成本以及碳排放成本。在顾客服务时间窗要求、车辆载重等约束条件下，构建以配送总成本最小为目标的冷链VRP模型，并求得最优配送方案。

本文假设条件如下：

①一个配送中心和多个客户点，位置、时间窗要求等信息都己知，且配送中心不会发生缺货现象；

②配送中心车辆充足且都是同一型号的汽油冷藏车；

③除极少数极端情况之外，配送车辆全程匀速行驶；

④所有配送车辆的实际载重不能超过其额定载重；

⑤所有车辆配送完成后不去其他地方，立即返回出发点；

⑥每个客户仅由一辆配送车辆为其提供服务；

⑦产品腐坏率一样，配送时间的增加以及环境温度的升高会导致变质致使成本增加；

⑧交通状况良好，不考虑交通拥堵情况，配送车辆平均速度己知；

⑨顾客的需求是静态的，一旦确定便不会发生改变。

2.2 符号及参数变量的设置

表1 变量设置及其含义

2.3 冷链物流配送路径优化目标函数构建

本文目标函数由固定成本、运输成本、制冷成本、时间窗惩罚成本、货损成本以及碳排放成本六部分组成，构建出考虑碳排放的冷链物流VRPTW模型为

(1)

s.t

(2)

(3)

EETi≤ti≤LLTi,i=1,2,…,n

(4)

(5)

xijk(1-xijk)=0,i,j=0,1,…,n;k=1,2,…,m

(6)

xik(1-xik)=0,i=0,1,…,n;k=1,2,…,m

(7)

yk(1-yk)=0,k=1,2,…,m

(8)

zik(1-zik)=0,i=0,1,…,n;k=1,2,…,m

(9)

式(1)表示目标函数，即固定成本、运输成本、制冷成本[16]、时间窗惩罚成本、货损成本以及碳排放成本[17]之和最小；式(2)表示每个客户仅由一辆冷藏车辆为其提供配送服务；式(3)表示车辆在执行配送任务时，装载的货物重量必须小于车辆额定载重;式(4)表示顾客收货时间窗要求；式(5)表示冷藏车辆均从配送中心出发，完成所有配送任务后均回到配送中心，形成一条闭合的配送路线；式(6)-(9)是变量取值约束，表示xijk、xik、yk、zik均为0-1变量。

2.4 改进遗传算法设计

本文选择遗传算法进行求解，遗传算法作为智能算法的一种，具有全局搜索能力强、应用范围广等优点，但是存在易早熟收敛、陷入局部最优解的不足，本文在传统遗传算法基础上引入了精英保留策略、逆转算子和移民策略。精英保留策略可以避免遗传操作过程中丢失潜在的最优解，逆转操作可以弥补其局部搜索不强的缺陷，移民操作可以在算法运行后期增加种群多样性，有效避免求解结果陷入局部最优。

本文改进遗传算法的求解步骤如下：

Step1：编码和解码。通过参数编码将解序列反映到遗传空间；再应用解码将处理过的遗传空间反映到解序列；

Step2：相关参数设置。确定了适应度函数，包括种群大小，交叉、变异概率以及算法终止最大迭代次数；

Step3：初始化种群。随机生成一合适数量的初始解；

Step4：计算个体适应度值。适应度高的遗传到下一代，本文设置总成本的倒数为适应度函数：

Step 5：选择。本文选择最常用的轮盘赌选择法来筛选染色体，同时，为避免交叉、变异过程中丢失和破坏上一代种群中的优秀个体，采用精英保留策略来储存算法求解过程中的优秀个体。本文保留父代个体中适应度取值排序处于前10%的个体，并用其替代后续子代中适应度取值排序处于后10%的个体，避免遗传操作过程中丢失潜在最优解。

Step 6：交叉。将群体内的各个个体随机搭配成对，对每一对个体以某种概率(称为交叉概率)遵循某一种规则交换它们之间的部分染色体，产生新的个体，本文采用OX交叉。

Step 7：变异。将变异算子作用在群体上，对选中的个体以某种概率改变某一个或某几个基因值。

Step8:逆转操作。变异操作后，对每个个体的两条染色体分别进行逆转操作，并根据逆转后适应度取值的大小决定是否保留逆转结果。

Step 8：移民操作。通过设定阈值判定当前的算法是否陷入了早熟收敛，如果是，则实施“移民策略”引入外部个体，以此来增加种群多样性，从而进一步增强种群搜索能力。为了解决遗传算法容易陷入局部最优解问题，本文采用“移民策略”将部分较为优秀的个体移植到目前保留的群体中，增加现有种群的多样性，从而提高算法搜索的高效性。首先需要判断算法当前是否出现了早熟收敛现象,当遗传算法表现为早熟收敛时,说明当前群体中个体的适应度非常相似，因此我们可以根据各群体的适应度方差来判断算法是否陷入了早熟收敛。为了便于计算,令

式中:fi为第i个个体的适应度;favg为群体的平均适应度;N为种群规模。当E小于某一阈值时,我们就认为当前的算法出现了早熟收敛现象,进而对其实施“移民操作”[18]。

Step9：回到步骤4重新循环，直至满足终止条件，跳出算法。

3 实证分析

本文以无锡市A企业冷链物流配送问题为例，对其在无锡地区的配送活动进行分析研究。A企业是无锡一家专业从事生鲜农产品批发配送业务的企业，虽然近年来以专业化的操作和科学化的管理在无锡发展壮大，但是在当前的冷链配送过程中仍然存在配送路径规划不科学、成本高等问题。本文用设计的改进遗传算法对于A企业进行实证求解，为今后配送路径规划提供参考。

3.1 配送数据及参数设置

A企业顾客信息表如表2所示，表中序号0为配送中心，1-20为A企业顾客门店。

表2 A企业冷链配送信息表

表3 模型相关参数取值

表4 遗传算法相关参数取值

3.2 求解结果分析

论文采用Matlab R2019a对算例进行仿真求解，用传统遗传算法与改进遗传算法分别对程序运行 10 次，结果对比如表5所示。

表5 传统遗传算法与改进遗传算法求解冷链路径优化结果对比

由表5可得，Matlab运行10次，传统遗传算法求解A企业冷链物流配送路径优化需要7辆车，平均总成本为6994.71元，平均运行时间为17.85s。改进后的遗传算法求解绿色视角下A企业冷链物流配送路径优化需要5辆车，平均总成本为5910.69元，平均运行时间为28.25s。这说明改进遗传算法虽然求解时间增长，但是求得的配送方案所用车辆数更少，总成本更小，这说明改进遗传算法的求解结果比传统遗传算法更优。

取传统遗传算法与改进遗传算法求解10次中结果最优的一次迭代函数如图1、图2所示。

图1 传统遗传算法求解迭代图

图2 改进遗传算法求解迭代图

两种算法求解路径优化问题迭代图显示，传统遗传算法于80代左右便开始收敛，而改进遗传算法大约在134代左右开始收敛。与传统遗传算法相比，改进后的遗传算法虽然求解时间加长，但是改善了传统遗传算法容易早熟收敛的缺陷，使得求解总成本比传统遗传算法更小，最优解更优，这充分说明了本文设计的改进遗传算法的有效性。

传统遗传算法与改进遗传算法求解10次中结果最优的一次配送方案路线如图3、图4所示。

图4 改进遗传算法求解最优配送方案路线图

传统算法和改进遗传算法求解最优的一次配送方案行驶总里程以及总成本详细信息如表6所示。

表6 传统遗传算法和改进遗传算法求解最优配送方案详细信息

通过表6可得，传统遗传算法求解最优配送方案配送总里程为240.426km,配送总成本为6886.1元，需要7辆车进行配送，7条配送路线分别为：0→7→4→11→0；0→20→17→0；0→16→14→15→0；0→13→1→12→0；0→2→5→3→6→0；0→19→8→10→0；0→9→18→0。改进遗传算法求解最优配送方案配送总里程为219.84 km,配送总成本为5812.6元，需要5辆车进行配送，5条配送路线分别为：0→19→5→7→4→0；0→11→13→16→15→0；0→8→2→6→3→0；0→18→9→17→20→0；0→10→1→14→12→0,配送总距离和总成本分别降低了9.4%和18.5%。由此可得,改进的遗传算法对A企业配送周边生鲜需求点的冷链物流配送路径求解比传统遗传算法求解配送路径总距离更短、总配送成本更低。

4 结论

本文将冷链物流车辆路径优化问题作为研究方向，目标是如何安排车辆调度进行配送以达到配送总成本最小。为了改善传统遗传算法容易陷入局部最优解和早熟收敛的缺陷，引入精英保留策略和移民策略进行改进，通过改进遗传算法对A企业冷链物流配送案例进行求解，验证了本文设计的改进遗传算法能够改善传统遗传算法的不足，并且使得求解结果更优，为解决相关冷链物流配送路径优化问题提供了参考。