基于改进遗传算法的低碳冷链物流研究

刘子豪，刘祥伟

（安徽理工大学 经济管理学院，安徽 淮南 232000）

党的二十大报告再次强调要打造绿色低碳高质量物流体系，着重开展低碳物流、智慧物流、高效物流体系发展。低碳冷链物流路径优化研究在节约能源、减少排放、提高资源利用效率、降低物流成本、保障产品质量与安全以及推动低碳经济发展等方面具有重要意义，也符合可持续发展的需求，对于促进绿色物流发展具有积极作用。在生鲜食品运输过程中，货碳排放不可避免，如何科学地计算并对产品损耗进行控制是实现高质量生鲜食品运输的重点工作，邓红星等人构建考虑碳排放成本因素的模型，将碳排放成本计入模型之中［1］。

车辆路径（VRP）由Dantzig 等人在1959 年率先提出，是利用VRP数学模型建立解决该问题的启发式算法［2］。由于我国物流运输行业高速发展，VRP路径问题在国内已深入研究。第一，求解模型构建不断优化。首先对带有时间窗问题进行模型构建。魏子秋等人将软时间窗引入目标函数模型，利用客户期望时间窗模型，计算出超预期时间罚款成本［3］。李想等人提出多目标模糊需求最小成本求解模型［4］。李尤等人结合顾客满意度构建出模糊时间窗，并根据不同情景构建出相对应成本模型，然后在相关成本因素上进行多方面考虑［5］。李军涛等人针对碳排放因素采用投入产出法计算运输过程中所产生的碳排放量［6］，卢森等人提出生鲜行业的顾客满意度成本模型［7］。第二，算法模型不断改进。邵美晨采用NSGAⅡ算法对双目标路径优化问题进行求解［8］。张无瑞等人针对多中心车辆路径问题设计出两阶段自适应遗传算法，并结合TOPSIS模型［9］。郭文强等人在遗传算法基础上添加变领域搜索并结合A*算法［10］。周国华等人利用天牛须-遗传混合算法（BAS-AGA）对多层级选址问题进行求解［11］。

综上所述，针对车辆VRP路径优化问题，不仅进行了成本模型的考虑，更将算法进行了各种融合，问题不断复杂化，但是算法求解速度和精度都在提高。通过研究对象A，考虑碳排放和货运损耗，在遗传算法的基础上，综合已有的研究结果进行算法优化，从而实现降低排放成本和运费，以期提高企业经济效益，实现低碳绿色运输目标。

1 问题描述与模型构建

1.1 问题描述

带时间窗的车辆路径规划问题（Vehicle Routing Problem with Time Window，VRPTW）是在VRP基础上添加配送时间约束条件产生的一个新问题。在这类问题中，假定为单一配送中心，且顾客所需只由该配送中心提供服务，对指定车辆至目的地的最早或最晚到达时间进行确定，要求车辆必须以规定的服务时间到达，若提前或延后，均视为违背规定，并在路费方面给予处罚，且车辆负载具有最大限度，在完成工作后返回原配送中心。通过分析，将燃油费、固定费、损耗费、惩罚成本和碳排放等因素纳入成本目标函数计算，其中在计算货损成本时引入特定变质率与损耗率，将货损成本考虑为风险成本并计入目标函数之中，同时引入碳排放系数与碳排放价格，结合参考文献估算出碳排放成本，是复杂模型下的成本最优解问题，此问题旨在寻找满足所有约束条件的最优路径方案，求出最小配送成本。

1.2 参数设置

L0:表示配送中心；

M:｛1，2，3...m｝所有可用车辆的集合；

N:｛0，1，2...n}其中0表示配送中心，其他表示顾客配送点；

Q:表示运输车最大荷载量；

V0:表示运输车特定平均运输速度；

C:目标函数成本。

表1为模型相关参数值设定。

表1 基础参数设置

1.3 假设条件

（1）所有路径运输车均为相同型号，最大载重相同且无法装载超过载重限制的货物；

（2）每个客户必须被恰好一辆车服务，所有车辆最终必须返回起点中心；

（3）配送中心与客户的所有信息，包括需求量、位置与时间窗等均为已知条件；

（4）不考虑交通拥堵因素与其他未知因素，车辆假定为全程匀速行驶；

（5）所配送的产品是同一种类、同一规格的商品，没有差异性；

（6）每个配送点与配送中心之间的运输路径具有确定性，即路线确定、交通情况稳定、运输时间可控制；

（7）产品的每个客户（发货点或收货点）对于到达时间都有要求，即每个客户都有一个指定的访问时间范围，车辆必须在该时间窗口内到达客户处；损坏率为可控因素，即假定其在运输时间范围内损耗率相同；

（8）每辆运输车不考虑最大行驶距离，即假定不受可行驶距离约束；

（9）所有的顾客需求均为静态，不考虑实时变动因素。

1.4 路径优化目标函数模型构建

1.4.1 固定成本

固定成本并不考虑运输时间及车辆使用年限产生的动态成本变化，只涵盖运输过程中相关工作人员薪酬、车辆折旧费以及车辆维护费等费用。

式中，fm为第m辆车的固定使用费用；Gm为0，1 决策变量，若Gm=1，表示第m辆冷藏车被使用，否则Gm=0.

1.4.2 运输成本

车辆运输成本主要包括车辆燃油费用，在不考虑路况与气温等不可控因素的情况下，车辆燃油费用与运输车行驶距离成正比。运输成本为

式中，f2表示运输车在单位距离行驶过程中所产生的运输成本；dij表示配送中心i与顾客服务点j之间的距离，为0，1决策变量，当冷藏车m从配送中心i配送到超市门店j时，，否则，数值为0.

1.4.3 货损成本

根据生鲜农产品变质的客观规律构造函数I（t）=IOe-ε来定量描述生鲜农产品的变质程度，其中I（t）表示在时间t时刻生鲜农产品的变质程度，I0表示初始状态下货品品质水平，ε表示变质速率，变质率数值与货物所处自然环境的温度及湿度等相关，且与运输花费时间呈指数型增长关系［12］。运输车辆到达门店j时，打开车门前在行驶过程中产生的货损成本为

在整个产品流通过程中装卸服务在自然环境下进行，车内温度会与所设定的理想温度产生差异，意味着其变质率与在运输过程中处于特定温度条件下的变质率有所差异，故应根据所设定的服务时间内计算其损耗成本，公式如下:

式中，p为生鲜农产品的平均单位价格；ai为顾客i对于生鲜产品的需求量；为运输车从顾客i到顾客j之间运输所花费的时间；ε1为生鲜农产品在特定温度下的变质率为0、1 变量，当车辆为生鲜超市门店i服务时，则=1，否则=0；ε2为在顾客进行装卸等服务期间产品特定变质率；ti为在客户i的冷藏车服务时间。

1.4.4 碳排放成本

碳排放成本包括制冷导致的碳排放和在生鲜运输过程中的耗用能源，包括汽油、柴油等所造成的二氧化碳排放的费用两部分组成的成本。其中燃油消耗量与交通工具的运输距离和载重成正比，为将碳排放转化为成本，引入碳排放数值关系函数［13］，如下列函数所示

式中，e0表示运输车辆在空载情况下单位配送距离所产生的油耗量；e1为满载情况下的油耗量；Q为冷藏车的额定载重量，m=1，2，3；x为车辆载重量。

在生鲜农产品配送过程中燃油所产生的碳排放成本为

式中，Pc为单位碳税价格；ρ为碳排放系数；λ为配送单位重量货物行驶单位距离制冷产生的排放；Qij为从超市i到超市j运送的货物量。碳成本公式如下

1.4.5 惩罚成本

时间惩罚成本［ETi，LTi］为超市门店i期望被服务的时间窗；［EETi，LLTi］为超市门店i可以接受服务的时间窗。事实上，逾越时间窗规定并不会产生惩罚性费用，但会对顾客满意度产生影响。因此必须考虑时间窗，将时间窗约束转化成本对路径选择进行约束［14］。然而，本研究的研究对象是易腐败的生鲜品，迟早都会出现产品损耗，因而必须将惩罚性费用引入成本模型中，以促进客户的满意度和提升产品的质量。图2说明惩罚性费用与时间的关系。

惩罚时间与时间窗之间函数关系如下:

约束条件（11）表明为客户提供服务的运输车数量不超过配送中心拥有的运输车总和；

约束条件（12）表示所有运输车对配送点逐一提供服务后返回配送中心；

约束条件（13）表示每条运输路线上的运输车所运输货物重量不超过最大荷载量；

约束条件（14）表示每个顾客必须由一辆运输车提供配送服务，且每个配送中心有且只能有一次配送机会，不考虑动态需求；

约束条件（15）与（16）表示0、1决策值约束；

约束条件（17）表示配送时间要在所设定的约定时间窗内。

2 改进遗传算法设计与算法步骤

2.1 改进遗传算法设计

传统遗传算法在处理单目标问题方面表现出较强的适应性，但对于NP-Hard 多目标路径优化问题而言，其选择操作通常基于适应度函数对个体进行评估，选择概率与适应度相关。而在多目标路径优化问题中，个体之间的相似性往往会导致种群陷入局部最优解。为了解决这一问题，在传统遗传算法的基础上，改进后的遗传算法引入了贪婪算法、精英保留策略以及移民操作。通过利用贪婪算法构建初始化种群，可以快速生成一组较好的个体，增加了初始种群的多样性。同时，通过精英保留策略在每一代中保留适应度最好的个体，防止种群陷入局部最优解。此外，引入移民操作可以在不同子种群之间进行个体交流，增加种群的多样性，并避免陷入局部最优解。

2.1.1 贪婪算法初始化种群

本质是在局部搜寻最优解，达到局部最优目标。具体操作如下:在种群随机选取一个客户Ii，将其添入个体之中，然后在未加入个体的群体中进行搜索，找出距离目前客户最近的客户Ij并加入个体之中，如此循环操作直至所有顾客均加入个体。由于运输车具有运载重量限制，故其算法也应设置约束条件，公式如下

对各条基因上相应的生鲜需求量进行累计，当累计至第n个客户时，顾客总需求量小于车辆最大荷载数，累计至n+1 顾客时，结果则相反，那么此时就在第n个顾客后插入终止编码符号0，表示一条染色体编码完成，如3-5-1-6-9-4-0，如此反复直至所有个体均被编入，形成可以满足种群数量规模的数目。

2.1.2 精英策略

具体操作为:首先依据适应度函数值从大到小进行排序，后将排在前10%的优秀个体进行保留，对续子代染色体进行适应度评估，接着将所保留的优秀个体替代子代后10%劣质基因。替代完成后进行轮盘赌法，为确保所保留的优秀基因能够全部保留，在轮盘中单独设置概率为1的区域。而其他个体通过个体适应度占群体总适应度的比例来赋予比例，通过轮盘形式随机选取，采用下列公式进行概率赋值。

2.1.3 PMX部分匹配交叉

基因交叉是指将两个父体的部分基因进行替换，在保留父代部分相较优秀的基因前提下产生新的子代，其中常用方法为PMX（Partially Mapped Crossover，简称PMX）交叉。其原理是从两个父代染色体中选择两个交叉点，将这两个交叉点之间的基因段交换位置，并保持其中的元素映射关系不变，进行交叉后执行冲突检测，消除交叉后所形成的重复个体。具体操作如下。

步骤1:从一组父代染色体中随机选取位置相对应的两个基因作为起止位置。

步骤2:交换所选取两组基因位置。

步骤3:做冲突检测。根据两组所交换的基因建立映射关系，如图5 所示，以3-6-2 这一映射关系为例，在子代A 中编号为2 的基因重复存在，此时根据映射关系，将原父代基因2 转变为基因3，以此重复操作，直到没有重复冲突基因为止。操作如图5所示。

2.1.4 逆转算子

采用逆转算子策略，将子代基因进行基因突变操作，具体操作为:随机选取片段基因上的两个基因位置点，将片段内基因进行逆转。

2.1.5 移民策略

移民策略是在交叉变异操作后，由于交叉变异具有随机性，可能会将优秀个体或优秀子代进行破坏，而移民策略是在保留潜在最优解的前提下人为将优秀个体保留至群体之中，可增强种群多样性与后代基因的质量，从而提升算法搜索能力与准确性。需要进行该操作应根据已设定的阈值进行判定，判断是否有早熟收敛迹象，公式如下:

其中，fi表示第i个体的适应度值，favg表示整个群体的平均适应度，当结果E低于所设定的值时便进行移民操作，增强算法收敛性。

2.1.6 动态交叉变异概率

动态改变交叉变异概率的原理为当种群适应度趋于一致或有陷入局部最优可能时增加其概率，而当种群适应度过于分散则可适当降低交叉变异概率，公式如下:

其中，f'表示所挑取两个要交叉的个体中适应度值较大的，f要变异的个体的适应度值。Pc1，Pc2分别表示最大与最小交叉概率，Pm1，Pm2分别表示最大和最小变异概率，Pc1，Pc2，Pm1，Pm2均为0 至1 之间的常数。设置Pc1=0.8，Pc2=0.6，Pm1=0.1，Pm2=0.001.

2.2 算法步骤

经过上列算法改进后再编入算法步骤之中，引入贪婪算法、动态交叉变异概率以及精英策略与移民操作，步骤示意如图8所示。

3 实例验证

3.1 门店距离与需求信息

以合肥市周谷堆蔬菜交易中心A 为研究对象，依据相关资料在合肥市不同行政区选取20 个顾客，其中配送中心以“0”表示，“1～20”代表20个不同的顾客。依据百度地图进行标点得到服务点分布图，再使用相关地图测距工具，建立以横纵坐标为（25，15）的距离图，坐标数据来源于百度地图，位置如图9所设计。参考当地瓜果蔬菜交易数据对服务点的需求量、配送时间与时间窗要求进行估计。

表2 运输车辆数据

为直观观测地理位置分布，通过Excel软件，将位置坐标转换为单位为km的散点分布图，如图10所示。

图1 多路径规划示意图

图2 时间惩罚成本与时间关系图

图3 父代基因片段选取示意图

图4 子代基因交换示意图

图5 冲突检测示意图

图6 最终子代基因示意图

图7 子代基因突变操作示意图

图8 改进遗传算法的求解步骤

图9 顾客地理位置

图10 客户分布散点图

配送中心所用车辆为解放冷藏车，通过车辆生产商获取运输车参数信息，如表2 所示。从表2 可知，该型号最大运输荷载为10t，且生鲜运输多为上午4:00—9:00 之间，不需考虑市区内堵车的影响，依据行政区内运输车限速政策，可假定总体车队平均行驶速度为60 km/h，每辆运输车的固定使用成本为300 元/辆，每辆运输车的单位行驶距离成本为2 元/km，其他基础参数设置与上文保持一致。

表3中，编号0表示配送中心，1～20表示顾客编号，通过地图工具以（25，15）为配送中心向四周辐射并测算出顾客所在坐标轴距离以及根据市场综合判断出期望时间窗与可接受时间窗，需求量依据相关统计资料进行特定估算。

表3 A企业冷链配送需求信息表

3.2 模型求解与结果分析

3.2.1 传统遗传算法与改进遗传算法对比

通过MATLAB2021 对VRP路径最优问题进行实例仿真，电脑处理设备参数为12thGenIntel（R）Core（TM）i5-12500H 2.50 GHz，内存16GB.设定初始种群NP（0）为100，算法迭代次数MAXGEN为2000，交叉变异概率采用动态自适应概率，代沟GGPA=0.9.

分两个模块进行数据求解与对比分析，下列为传统遗传算法与改进遗传算法之间性能的对比。

在对两种基因算法路径优化迭代图（图11）进行比较后，得到如下结论:传统遗传算法在经历200次迭代后便开始收敛，600次迭代后陷入局部最优，而改进后的遗传算法在大约850次迭代后开始趋于收敛，求解时间虽然加长，但所求总成本数值更小，最优解更优。

图11 传统遗传算法与改进遗传算法求解迭代对比图

通过表4 可知传统遗传算法成本最优解为4284.63 元，需6 辆车配送，配送路线为［0，9，7，16，1，0］，［0，18，17，13，8，0］，［0，10，3，4，0］，［0，14，15，19，0］，［0，6，5，12，0］，［0，2，20，11，0］.改进后遗传算法最优成本为4088.79 元，需6 辆车配送，配送路线为［0，6，4，10，0］，［0，19，17，13，1，0］，［0，16，17，14，12，0］，［0，20，9，8，3，11，0］，［0，18，5，0］，［0，2，15，0］.改进后的总成本下降近4.5%，其中运输成本下降近7.9%.图12与图13分别为传统遗传算法与改进遗传算法路径图。

表4 遗传算法与传统遗传算法最优配送方案详细信息 单位:元

图12 传统遗传算法路径图

图13 改进遗传算法路径图

3.2.2 碳排放成本对改进后遗传算法求解影响

为在改进遗传算法基础上考虑碳排放成本是否会影响路径抉择与最优解数值，将目标函数中不包含碳排放成本的算法与包含碳排放成本的算法进行对比，不包含碳排放成本的算法模型中的碳排放成本是根据求解结果进行独立计算。图14与图15分别为不包含碳排放成本路径与包含碳排放成本路径。

图14 不包含碳排放成本路径

图15 包含碳排放成本路径

表5 结果为在最大迭代次数内的最优解。经过仿真运行，通过两组数据的比较，可以得到如下结论:在考虑到碳排放的前提下，总成本不仅没有增加，反而减少了2.3%，碳排放的成本下降了2.1%，运输费用降低了8%.这是由于碳排放成本与时间成正比，要降低碳排放成本，需要尽量缩短运输路程，以降低成本，从而对货物运输费用和损耗费用产生影响。该算法能增强收敛性和搜索能力，同时还指出路径优化中碳排放成本具有重要意义。

表5 包含碳排放成本与不包含碳排放成本最优配送详细信息 单位:元

4 小结

目前生鲜农产品冷链运输存在求解结果差异较大且运行时间长、易陷入局部最优解等问题。文章首先将碳排放成本引入生鲜配送成本模型之中，对传统求解模型进行改进，然后采用贪婪算法构建出初始种群，为增加种群多样性与最优解搜索能力在动态概率交叉、变异后引入移民策略。最后对A 企业进行实例验证，运用MATLAB2021 对传统遗传算法与改进后的遗传算法进行数据对比，验证文章设计后的遗传算法可以改善传统遗传算法的不足，该研究对于改进遗传算法缺陷以及绿色冷链提供一定的参考。