基于蚁群算法的生鲜电商冷链低碳配送路径优化研究

李艳珍

(黎明职业大学，福建 泉州 362000）

一、研究背景及研究现状

（一）研究背景

近年来，电子支付的便捷、物流体系的完善、大数据的算法支持及移动购物的普及，有效地提高生鲜行业供给的质量，同时消费升级带动生鲜的需求旺盛。2021 年，中国生鲜电商完成3117.40亿元的市场交易份额，实现跨越式的扩张，占比同期上升18.2%。基于近几年消费者需求量增量比上升的情况，生鲜电商行业报告预计2023 年中国生鲜电商市场规模将达4198.30 亿元。[1]由于生鲜食品保质期短、易腐烂等特点，全程需要冷链配送，因此冷链物流将是一个巨大的市场。减少货损和保持新鲜是冷链物流的重要特征，在配送过程中对时间、环境等要求苛刻，加之人们对生鲜品质、配送服务的消费升级，使冷链物流配送备受关注。[2]在“30·60 双碳”目标下，交通运输与物流产业需要加速绿色、低碳转型之路。据统计，交通物流行业占全球二氧化碳排放量的21%，道路碳排放占整个运输部门碳排放量的70%。[3]王雁凤和黄有方[4]指出，预计到2050年物流运输行业的碳排放比2007 年将增加150%-250%。冷链物流是物流行业的高耗能、高碳排放业务。因此，在“双碳”目标下，如何加强冷链配送节能减排的路径设计和系统规划，在考虑经济成本的同时也要关注环境目标，成为冷链配送的研究重点。

（二）国内外研究现状

冷链物流的路径优化一直是物流领域的研究重点，最早的路径优化问题（Vehicle Routing Problems，VRP）研究自1959 年由Dantzig 和Rams⁃er[5]提出以来，引起了学术界的广泛关注。针对路径优化问题，学者们提出一系列优秀的精确算法，其中蚁群算法（Ant Colony Algorithm，ACA）被广泛应用。Zmazek.B[6]提出一种在汽车行驶和动力极限问题上增加了时间窗（CVRPTW）的优化算法，并且在一天之内进行多次往返，最后以实例说明该方法的正确性。Vijay Aggarwal[7]提出一种决定系统，用以确定合适的节点和价值来决定运输费用，并决定与结点数目相关的运输网络。Monitarian[8]利用数学方法，解决冷链配送次序问题，从而提高配送决策的科学性。国内学者对冷链物流路径优化研究也取得了重要成果。Mei-xian Song 等[9]提出一种改进的人工鱼群算法以考虑不同类型车辆的问题特征，该算法嵌入右移启发式算法，在不增加能耗的情况下提高用户满意度。樊世清等[10]以总成本最小为目标建立农产品冷链物流车辆配送路径优化模型，采用改进的蚁群算法进行求解得到最优方案。康凯等[11]采用局部搜索机制在算法中融入2-opt 局部优化方法，实现了对蚁群算法的改进。

随着节能减排成为全球关注的热点，越来越多的学者在研究冷链配送路径优化时也关注绿色目标的实现。王雁凤等[12]利用构建的港口群运输网络优化模型对25 种场景下的运输路径进行计算，得出最优的配置方案。周鲜成等[13]分析行驶时间和时变速度的关系，提出一种基于路段划分的行驶时间计算方法，采用MEET 模型测度碳排放，以车辆使用成本、驾驶员成本、油耗成本和碳排放成本构成的总成本作为目标函数构建时间依赖型GVRPTW 模型。Li-Yi Zhang 等[14]将低碳经济引入冷链物流，并与蚁群算法优化相结合。Yongbo Li 等[15]采用创新的方法更新信息素开发了改进后的蚁群算法，为多站点绿色低碳车辆路径问题提供更好的解决方案。范立南等[16]建立考虑碳排放的路径优化模型，并采用改进遗传算法对路径进行优化。

综上所述，对于冷链物流车辆配送路径问题，国内外学者已经进行了较为广泛的研究，但是在现存数学模型中，对惩罚成本、碳排成本等实际影响要素考虑不全的问题仍然存在，且蚁群算法初始信息素少、收敛速度慢的缺点仍未得到较有实用性的优化处理。以综合成本最小化作为优化目标，既考虑环境效益也考虑经济效益，将惩罚成本、碳排放成本引入模型参数中，再采用改进信息素更新方式和挥发量调整优化蚁群算法，结合优化后的模型和算法，以上问题将得到有效处理。本文以泉州市某生鲜电商宅配中心作为实例进行数据试验，解决其冷链末端物流成本高、响应速度慢和碳排量高的问题，有利于降低车辆配送成本、优化配送路径、提高冷链末端响应速度，以增加整体效益。

二、生鲜电商冷链低碳配送路径优化模型

（一）问题描述

本文探讨的生鲜电商冷链低碳配送路径优化问题具体可描述为：拥有m 台配送车辆的某生鲜电商冷链物流配送中心，为n个具备生鲜产品需求的客户提供冷链物流配送服务，n 个客户的需求量和地理位置固定且每个客户都有配送时间的限制，所有配送车辆统一从配送中心出发，完成配送服务后返回配送中心，在满足客户需求量、车辆载重量限制、配送时间条件下合理安排车辆，使目标函数最优化。在以综合总成本最小为目标的模型构建中，将运输成本、固定成本、货损成本、制冷成本、碳排成本、惩罚成本作为主要影响因素，寻找以客户需求、车辆载重、服务时间窗为约束的车辆配送最短路径，以优化冷链物流车辆配送路径。

（二）模型的假设条件与约束条件

1.假设条件

为了对该问题进行深入的研究，将问题转化成具体模型，需要做一定的假设：

假设1：配送中心的货物种类和货物数量可以满足客户的要求。

假设2：由单一配送点向多个客户提供配送服务。

假设3：配送过程中不考虑路况、天气等影响，每台车速度相同，配送完成后返回配送中心。

假设4：已知客户的产品需求量、地理坐标、时间窗要求和服务时间。

假设5：冷链运输的车辆都是相同型号的冷藏车，且在配送期间的运行速度一致。

假设6：各运输车辆的起始点均为配送中心，并完成配送后再返回。

假设7：随着剩余货物被服务客户点的需求量逐渐递减，车辆在配送过程中货物载重量随之变化。

假设8：配送车辆提前到达和推迟到达的惩罚系数已知并相同。

2.约束条件

建立模型时，还需满足以下的约束条件：

约束1：配送车辆的货物重量≤车辆最大的装载重量。

约束2：配送车辆均为包车运输，不与其他企业的货物放一起运输。

约束3：在顾客同意的时间窗口内完成冷链运输工作。

约束4：一辆冷藏运输车对应多个客户，货物装载时先配送的客户后装载。

约束5：每个客户需求点对配送时间有时间窗要求，且事先设定与时间窗相联系的惩罚时间系数。

（三）成本变量分析

根据问题描述和假设，在生鲜电商冷链车辆配送路径问题上，本文综合考虑冷链物流环节中各项成本，以总成本最小化为目标，总成本C由六个部分组成：固定成本C1、运输成本C2、货损成本C3、制冷成本C4、碳排成本C5、惩罚成本C6。

1.固定成本

固定成本C1：包括车辆的固定费用、月检费、司机工资等。固定成本仅与配送车辆的数量成正比。

式(1)中，m 表示配送点车辆数量，Fk表示车辆k所耗费的固定成本(k=1,2,3,...m)。

2.运输成本

运输成本C2：指配送过程中车辆在一定运输工作量内所分摊的油耗费用，一般与配送车辆的行驶里程成正比。

式(2)中，n 表示客户的数量，Cij表示车辆从客户i 到客户j 单位距离的油耗费用，dij表示客户i到客户j 之间的距离，Xij为0-1 变量，Xij=1 表示第k 辆车从客户点i驶向客户点j，相反，Xij=0 表示第k辆车未从客户点i驶向客户j。

3.货损成本

货损成本C3：指产品在随时间的变化而产生的损耗。

式(3)中，P1为产品单位价格，Qi为客户i 的产品需求量，a 为产品变质率，t0i为从配送点到客户点i的时间，yj为0-1变量，若车辆k为客户j服务，yj=1，否则，yj=0。

4.制冷成本

制冷成本C4：指为满足产品保温要求购买制冷剂而产生的费用，由于制冷剂也存在时效性，则不考虑行驶时间，制冷成本仅与运量有关。

式(4)中，qij为车辆从客户i 到客户j 之间的运量，P2为配送过程中单位重量的制冷成本。

5.碳排成本

碳排放成本C5：是指配送过程中车辆消耗燃料所产生的CO2排放成本，碳排放量=燃料消耗量×CO2排放系数。[14]燃油消耗量既与运输距离有关，也和车辆载重量有关。

式(5)中，E 为车辆单位距离的油耗，e 为CO2排放系数，Pc为单位碳税价格。

6.惩罚成本

惩罚成本指车辆未能满足客户的服务时间窗要求而产生的赔付成本。处罚费与顾客接受服务的时间窗口有关，并对顾客的满意程度产生一定的影响。在生鲜产品的运送中，应注意其配送的时间性，以确保商品在顾客手中的安全。[17]为此，提出了一种基于混合时窗的限制条件，该方法可以使配送车辆在最优配送时间前或在最优配送时间后抵达，但必须付出相应的处罚费用。但在超出顾客可以接受的时间窗口以外，配送车辆不得无限地抵达，否则将会导致交易失败。惩罚函数用表示：

式（6）中：∞表示极大值；μ表示超过单位时间产生的成本；惩罚成本用C6表示：

（四）模型构建

综上所述，构建的生鲜电商冷链物流配送路径优化模型如下：

1.算法设计

蚁群算法是一种仿生智能算法，主要用于路径优化模型的求解。[18]该算法具有正反馈机制、并行搜索性、自组织性和较强的鲁棒性、易于与其他算法结合等优点。相较于其他算法，它在搜索效率和时间复杂度方面具有明显优势，故被采纳用于模型求解。

（1）蚁群算法基本设置

在完成蚁群算法的数学建模之前，做出以下假设：第一，蚂蚁不会在路上一遍又一遍地访问同一个客户；第二，蚂蚁可以知晓客户之间的距离，在其他条件相同的情况会倾向于前往最近的客户。第三，蚂蚁在行进过程中会释放信息素，且倾向于选择信息素浓度较高的方向行进。

（2）参数初始化

设蚂蚁数量m，客户数量n，客户i 和客户j 之间的距离为dij（i,j=1,2,...,n）；

t 时刻客户i 和客户j 之间的路径上信息素浓度为τij（t）；初始时各路径的信息素浓度相同，设为常数τij（0）=τ0；客户坐标设为（x，y），其中客户i到j的距离公式为：

（3）算法设计

职业教育人才的培养，有其特殊的一面，更强调实践性和创造性。因此，在具体的质量评价中，亟需企业的参与，形成以职业能力评价为导向，企业等用人单位、院校教师、校外指导教师等多主体共同参与的质量评价体系。

当前蚂蚁在客户i，只考虑信息素浓度对蚂蚁选择路径的影响：

①参数说明

allowedk：第k（k=1，2，...，m）只蚂蚁暂未访问的客户集合，即接下来可以选择的客户；t 时刻第k 只蚂蚁从客户i 转移到客户j 的概率，值越大，前往客户j的概率就越大；s：暂未访问的客户集合（allowedk）中的某一个客户；对于j∉allowedk，意味着客户j 已经被访问过了，则被选择的概率为0；初始第k 只蚂蚁随机在某一客户，则集合allowedk中有（n-1）个元素；接下来蚂蚁根据（n-1）个非0 的的值，前往下一个客户。此时有（n-2）个元素，继续计算下一个目标客户，直至集合为空，代表蚂蚁遍历了所有客户。

②公式分析

由公式（14）可知，这是基于只考虑信息素浓度的情况，所以在最初几次迭代的时候，每条路径的信息素浓度都很低。在t=0 时，信息素浓度是透明的，每条路径的信息素浓度都相等，导致蚂蚁选择路径的随机性非常大。为了解决这个问题，在公式（14）的基础上引入新的变量，公式如下：

公式（15）相比较于公式（14），距离d 也是概率计算时需要考虑的因素。从客户i 到客户j 的路径距离越小，1/dij的值越大。假如在信息素浓度τ 一样的时候，若1/dij的值越大，则概率P 越大，蚂蚁选择较短路线的概率更大。

2.算法优化

从式(13)(14)(15)中可以看出，每只蚂蚁在行走过程中都会释放一定量的信息素，而信息素的浓度会随着时间而变化，而蚂蚁更大概率选择信息素浓度更高的路径。但蚁群算法有收敛速度慢、易陷入局部最优的缺陷，而α 和β 分别决定信息素浓度和转移期望对蚂蚁选择可能性的贡献程度。基于此，本文通过改进初始信息素分布及信息素更新方式优化算法设计。

（1）改进初始信息素分布

在初始条件下，各路径上的信息素含量是相同的，此时蚁群处于盲目搜索阶段，这时寻优效果差，搜索效率低。为此本文提出了一种改进的初始信息素分布方式，改进后的初始信息素分布为：

式(16)(17)中，C为常数，du,sg为转移栅格到起点和终点连线的距离，即转移栅格离起点和终点连线的距离越远，该路线上的初始信息素浓度越低，反之就越高。因此，为避免初期蚂蚁盲目搜索，通过设置分布不均匀的初始信息素以提高搜索效率。

（2）改进信息素更新方式

随着迭代次数的增加，几条较优路径上的信息素差异越来越不明显，导致蚁群收敛速度逐渐变得缓慢。本文结合精英蚁群算法，设计新的蚁群的信息素更新规则。在所有蚂蚁个体完成一次迭代后，所有路径上的信息素都会更新，为避免出现局部最优，加快后期最优路径上信息素的积累，采取如式(18)的全局信息素更新方式：

三、实例分析

（一）算例描述

以福建省泉州市某生鲜电商宅配中心为例，从配送点(P0)向5 公里区域范围内的10 个客户点(P1,P2,P3,...,P10)配送多种生鲜产品，配送点（P0）的坐标为(110.408，21.201)，本文选取门店为起点建立平面直角坐标进行实验。各客户点详细需求信息如表1所示，门店与客户点、各客户点之间的距离如表2所示。

表1各客户点详细需求信息表

（二）实验参数设置

本文的模型参数设定如下：

(1)配送车辆的最大载重量QM为25kg；（2）配送过程中匀速行驶速度为40km/h；（3）单位运输成本为2 元/km；（4）车辆的固定成本F 为500 元/辆；（5）生鲜产品的平均单价P1为10 元/kg；（6）变质率a 为1%；（7）单位时间内的能耗E 为1.2元/h；（8）惩罚系数u 为20 元/h；(9)客户需求量、客户可接受的时间窗(表1)和门店与客户、客户与客户之间的距离(表2)均已知。

蚁群算法初始参数设置如下：蚂蚁数量为2，最大迭代次数Ncmax 为100，当Nc＜30 时，α=1，β=1，π=1，Q=100；当30＜Nc＜60 时，α=3，β=5，π=0.75，Q=50；当60＜Nc＜100 时α=5，β=1，π=0.5，Q=1。

（三）算法流程

为了使得改进算法更加稳定和快速地求解模型并得到最优解，本文综合蚁群算法基本原理和改进方式，归纳出以下步骤：

步骤1：进行蚁群算法参数初始化。初始化的关键参数包括：信息素重要程度因子α、启发函数重要程度因子β、信息素挥发因子π、信息素释放总量Q，根据式(16)，设置当前迭代次数为Tij(0)=C+f(j)，最大迭代次数为Nc=100；

步骤2：初始化蚂蚁群体。将m 只蚂蚁随机搁置在n个城市上；

步骤3：初始化蚂蚁位置。构建禁忌表，并将Tabuk 清空，将蚂蚁个体访问的第一个城市放进禁忌表中，如禁忌表已满，则转至步骤4；

步骤4：状态选择转移。在蚂蚁未访问过的城市，基于满足客户需求量和服务时间窗的约束进行各个因子值的选取，根据式(1)计算各条路径的选择概率Pij(t)，利用轮盘赌法选择转移点，并将下一步待访问的城市置于Tabuk 表，直至蚂蚁访问完所有的城市；

步骤5：判断是否所有蚂蚁得到最优解，是则继续进行下一步，否则回到步骤3；

步骤6：计算所有蚂蚁的适度值，得到最优蚂蚁个体及其相关目标数据，记录最短路径和总长度；

步骤7：当所有蚂蚁完成一次循环后，路径上的信息素需要根据式(18)进行更新，清空Tabuk 且转至步骤4继续迭代；

步骤8：当算法达提前设定的最大迭代次数，迭代结束，随即得出最终的最小综合成本及对应的最短配送路径。

（四）结果分析

在操作系统为win11 的环境下，使用Matlab R2021b 编码求解，Intel(R)Core(TM)i5-8250U CPU 1.6GHz(8GBRAM)进行求解，分别采用传统蚁群算法和优化后的蚁群算法对生鲜电商冷链物流配送路径优化模型进行求解10次，综合成本的求解结果，如表3所示。

表3 蚁群算法优化前后求解结果

从表3中可以看出，优化前的蚁群算法求解得到的综合成本最终解和平均值分别为32.80 和33.11，优化后的蚁群算法求解得到的综合成本最终解和平均值分别为28.75和30.23。相比之下，优化后的蚁群算法求解结果分别比优化前的蚁群算法求解结果小4.05和2.88。这表明优化后的蚁群算法的求解优化效果和收敛效率均优于优化前的蚁群算法。

由图1可得出优化前求解的配送路线，最短路径长度为16.24 km。配送点的2 辆车为10 个客户服务，车辆1 依次为客户点P1、P7、P3、P2、P6提供配送服务，车辆2 依次为客户点P9、P10、P8、P4、P5 提供配送服务，配送完成后车辆均返回配送点，可得出表4。

图1 优化前的配送路线最短路径图

表4 蚁群算法优化前求解的配送路线

由图2可得出优化后求解的配送路线，最短路径长度为14.45km。配送中心的2 辆车为10 个客户服务，车辆1 依次为客户点P2、P3、P8 服务，车辆2 依次为客户点P1、P7、P4、P10、P9、P6、P5服务，配送完成后车辆都返回配送点，可得出表5。

图2 优化后的配送路线最短路径图

表5 蚁群算法优化后求解的配送路线

通过图1 和图2 的对比可以看出，优化前的配送路线减少了许多不必要的路径交叉，最短路径长度减少1.79km，提高约11%的速率，从而缩短配送时间的行驶里程，使得综合成本更小化。结果表明，优化后的蚁群算法的初始信息素释放速度和收敛效率均优于优化前的蚁群算法。

四、结论

针对低碳背景下冷链物流配送的热点问题，通过综合考虑生鲜冷链末端物流配送过程中的车辆固定成本、运输成本、碳排成本等，以客户需求量、车辆载重量和客户要求服务时间窗为约束，构建以综合总成本最小为目标的生鲜冷链物流车辆配送路径优化模型。为了避免传统蚁群算法的局限性，通过改进初始信息素分布和信息素更新方式，提出优化的蚁群算法并用来求解建立的车辆配送问题模型。实例仿真试验结果表明，相对于传统蚁群算法，优化后的蚁群算法求解车辆配送问题模型的效率更高，且能获得效益更大的最优解，其主要体现于初期蚂蚁搜索目的性增强，提高了搜索效率，后期收敛速度增快，有利于信息素积累，使得最短路径总长度变小，从而降低综合总成本。

综上，本研究获得生鲜电商冷链低碳配送路径优化的成果，对冷链物流的低碳配送具有一定指导意义和应用价值，为生鲜电商冷链的低碳配送决策提供参考。