基于蚁群算法的乳制品配送路径优化研究

王瑾玮，王扬眉，薛瑞辰 （浙江万里学院 物流与电子商务学院，浙江 宁波 315100）

0 引 言

乳制品行业在中国国民经济和消费品市场中的地位举足轻重，该行业对于全民的健康而言有重大意义。新冠肺炎疫情突发给中国乳制品行业带来了巨大的挑战，消费群体的数量增长迅速、消费结构逐步提高、消费方式群体性改变，使得中国乳制品行业迎来了新的增长格局。在乳制品消费需求的变化下，乳制品企业要抓住消费新机遇，积极寻求发展，但由于乳制品的易腐特性，在运输中容易出现损耗，因此要提高冷链运输的效率，改善乳制品运输的质量。基于此，针对乳制品冷链物流的配送过程，构建由运输成本、制冷成本、货损成本和低碳环保成本构成的数学模型，利用蚁群算法建立路径优化模型可以降低配送成本，使运输距离最短，从而保证鲜奶的新鲜度，提高客户满意度。

1 文献综述

车辆路径问题（Vehicle Routing Problem,VRP），最早在1959年由Dantzig、Ramse(1959)[1]首次提出，它是指一个具有不同需求的顾客数目，配送中心将商品供应给顾客，并安排运输车辆，安排合适的运输路线，以满足顾客的需要，并在特定的条件下，以最短的路程、最小的成本、最少的时间来完成运输，车辆路径问题一经提出，便受到了许多专家学者的高度关注。

近年来，由于冷链物流的蓬勃发展，学者们对冷链物流路径优化的关注度越来越高，Russell Bent 等 (2004)[2]采用模拟退火算法，搜索车辆的路线数量，使用较大区域的搜索方法，建立低成本的路径优化路线；Ana Osvald、Lidija Zadnik Stirn (2007)[3]运用单边时间窗模型，解决了农业冷链路径优化问题；A.L.Kok、E.W.Hans、J.M.J.Schutten (2010)[4]考虑到城市交通和时间规则的影响，运用禁忌搜索算法建立模型；孔翔宇等(2010)[5]运用将局部信息素和全局信息素相结合改进蚁群算法，并将其应用于两个目标优化模型，以确定最佳路径；缪小红等(2011)[6]运用改进遗传算法，在货物没有过载的情况下，建立单配送中心路径优化模型；潘茜茜等(2016)[7]采用蚁群算法，考虑碳排放量建立路径优化模型；G.Poonthalir、R.Nadarajan.(2018)[8]将贪婪算法和粒子群算法相结合，考虑绿色成本建立目标优化模型；任腾等(2020)[9]等将信息素浓度的区间和蚁群算法相结合，以最小成本建立冷链车辆路径优化模型；王旭(2020)[10]运用遗传算法，建立使配送中心选址、路径优化问题的双层规划理论模型，上层模型可以确定选址中心，下层模型可以确定最优路径；王琴等(2022)[11]采用非支配排序遗传算法解决满载危险品运输车辆路径优化问题，将载货量变成动态参数，同时将需求量、人口密度、车辆速度等进行模糊变量。

冷链物流的发展非常迅速，学者们对此日益重视，但是上述的研究仍存在不足，算法能够解决VRP 问题中的部分问题，但是与实际车辆路径优化问题结合密切的研究并不多，目前冷链物流路径优化研究的目标大多数集中在农产品类，对于乳制品的研究较少，也缺乏与具体企业案例相结合的研究；而且冷链物流路径优化也主要集中在对模型算法求解的优化，并且优化目标单一，大多数学者的优化目标只是减少碳排放量或者降低成本，没有将经济发展和环保相结合。本文在构建优化目标函数时同时考虑最小成本和环低碳成本，并结合蚁群算法，扩展了低碳视角下冷链车辆路径优化的研究。在低碳视角下，建立模型来优化运输路径，降低物流配送的费用，缩短运输距离，提升顾客满意度，减少碳排放从而保护环境。

2 冷链物流成本模型

2.1 冷链物流路径规划问题建模研究

乳制品冷链路径问题以冷链配送路径问题为基础。在需要配送的城市区域中，由配送中心、需求点和冷藏车组成，它们在合理条件和有限条件下，从配送中心出发，使用固定的冷藏车类型，将货物配送到各个不同的需求点。基于此，构建数学模型以及选择算法，确定配送中心，使得使冷藏车辆从配送中心出发至各需求点的行驶过程中运输成本、制冷成本、损坏成本及碳排放等方面的总成本最小以及运输路线最短。

基本假设条件：

每个需求点之和小于车辆载重；

需求点的地理位置已知，每辆车的载重量大于需求点的需求量之和；

不考虑车辆在运输途中发生意外情况而导致配送异常的情况；

冷藏车仅在需求点停留，且车辆为匀速行驶；

车辆在行驶过程中车厢的内外温度一致，且车辆在行驶过程中车门密闭良好；

只存在一个配送中心，车辆的起点和终点均为配送中心；

每个需求点仅有一辆车送货，且不存在取货需求。

2.2 参数说明

本文关于模型的有关参数如表1所示。

表1 参数符号定义表

2.3 优化成本分析

2.3.1 固定成本

固定成本是车辆在运输货物的过程中产生的车辆的自然固定损耗。本文为求解方便，固定成本与车辆数量成正比关系，成本关系式如下:

2.3.2 运输成本

运输成本通路况的不同以及耗油量有关，本文选择一种车辆进行乳制品冷链运输，假设在乳制品运输过程中的速度为匀速，因此运输费用与冷藏车辆的运输距离成比例，这种比例表现为正比关系，成本关系式如下:

2.3.3 制冷成本

乳制品在运输时必须使用专用的冷藏车辆进行储存和运输，来保证乳制品有合适的储存环境，在实际的冷链运输过程中，在不同的运输条件下，不同的冷藏车辆所需的费用也不相同。基于文章的假设，我们选择同一种运输车辆，所以制冷成本可以分为两部分，即：行驶状态时的制冷成本和卸货状态时的制冷成本，制冷设备产生的制冷成本不同，本文将制冷成本分为行驶中和卸货时，成本关系式如下:表示车辆行驶过需求点i与需求点j的距离所花费掉的时间，ts表示车辆在需求点j卸货所花费掉的时间。

2.3.4 货损成本

由于乳制品具有易腐易变质的特性，所以在运输途中会受货物包装、货物碰撞、冷藏车温度与货物变质等方面的影响，卸货过程中受货物搬运损坏和温度损坏的影响,所以本文基于此对货损成本进行定义，假设条件是冷藏车的内部温度不变、由于乳制品碰撞而产生的货损成本忽略不计，本文的货损成本分为行驶状态中和卸载货物中，即货损成本就是将两部分产生的成本之和相加，关系式如下:

2.3.5 碳排放成本

碳排放成本是指在运输途中，由于使用冷藏汽车所造成的二氧化碳排放，二氧化碳的排放会使公司产生费用，是由公司所承担的环境费用。碳排放成本与碳税r、碳排放系数f及耗油量q相关。成本关系式如下：

2.4 优化模型的建立

总成本是由固定成本、运输成本、制冷成本、货损成本和碳排放成本相加而构成，因此模型如下:

3 蚁群算法模型求解

当影响因素复杂和约束条件多时，蚁群算法用时短、效率高。蚁群算法在车辆调度问题中应用广泛，文中使用蚁群算法求解乳制品冷链物流的路径优化问题。

以乳制品冷链运输成本最小为目标，构建一个最优的数学模型，采用蚁群算法对其进行优化，从而寻找出最佳配送路径，在多因素、多约束的情况下，蚁群算法是目前交通运输规划中常见的一种，是一种新的求解算法。

3.1 初始化种群

通过蚁群算法对群体进行初始化，获得了初始群体。具体操作步骤如下：

在所有的需求点中，每个蚂蚁都可以随意选取一个作为第一个访问点，在每个群体矩阵列表中，确定编号为1 的作为配送中心，在n个需求点，随机选择一个需求点作为该蚂蚁要访问的第一个需求点，将这个操作请求放到一个路径禁忌清单表中。

对任意的蚂蚁k按照算法中的状态变换规则对每一只蚂蚁进行实时修改，以确保每一只蚂蚁都能通过一个需求点，要求不断更新禁忌表，直到k只蚂蚁经过n个需求点。

在最初的蚁群算法中，一般都是以轮盘赌作为基础，其原理就是随机一条行驶路径上的信息素浓度变浓时，蚁群就会感知到信息素浓度的增加，蚁群从而会朝着信息素浓度增加的方向移动，算法就会逐渐转为贪婪算法，使算法过早成熟，算法的最优解也会陷入局部最优。为解决这一问题，本文把轮盘赌和确定性选择法则结合起来，对算法进行改进，判定性的选取准则关系式如下：

其中，初始化参数q0表示在[0,1]内的数目；q表示在[0,1]内的数目；启发τij(t) 函数指在时刻t需求点i至j距离内信息素浓度的大小；信息启发因子α的大小能反映出蚂蚁在选择路线时所占的比重；ηij(t) 表示从客户需求点i至j之间的启发程度，且，期望启发因子β表明在选择行进路线时可见度的相对重要性。

如果q＞q0，算法则会进行轮盘赌选择，关系式如下：

其中，S表示还需要访问的需求点。当蚂蚁在需求点i时，恰好初始化参数值处于[0,q]的范围内，用确定的选择法则来寻找下一个待访问点，或者使用轮盘选择规则来寻找下一个目标。

3.2 更新信息素

当k只蚂蚁走访完所有的需求点n个后，任意两需求点之间的联系路径上的信息素浓度将会及时更新，关系式如下：

其中，τij(t+1) 表示在第 (t+1) 代的结果下，需求点i至j连接线路上的信息素浓度大小，信息素挥发系数ρ表示在[0,1]内的数目，表示k只蚂蚁在经过（i，j）路径时释放的信息素浓度，表示k只蚂蚁共同在（i，j）路程中所释放的信息素浓度的总和。

蚁周模型的具体规则如式：

其中，LK表示k只蚂蚁行走的路程，Q表示k只蚂蚁走过所有需求点之后所释放的信息素总量。

蚁量模型的具体规则如式：

其中，dij表示路径（i，j）长度。

蚁密模型的具体规则如式：

3.3 输出最优解

在找到最好的路径优化方案并在迭代次数达到最大的情况下，将所得的最优解对应路径表的编号转化为成各需求点的编号，即为该次算法求解出的最短路径和最小成本。

3.4 蚁群算法流程图

蚁群算法流程图如图1所示。

4 仿真实验

4.1 研究实例背景介绍

N 企业成立于1963年，公司集科研，种植，养殖，加工，营销，物流配送于一体，是涵盖医疗、跨境贸易、文化艺术、酒店旅游等诸多产业在内的国家重点龙头企业。旗下有涌优、宁波牌、亚格力、涌佳、雍佑、好牧、简糖、格伦维尤、雅尊等品牌。集团一直以“好牛奶是养出来的”为战略理念，为了养好牛，花大手笔在海外收购了10 平方公里澳洲牧场引进种牛，又在国内杭州湾建立了6 000 亩的生态牧场，让消费者切身体验到在江南同样能养出好牛、挤出好奶；集团致力于做新鲜好牛奶，从牧草种植、奶牛养殖源头环节，再到生产加工、冷链运输新鲜配送，全链条追溯，层层把控牛奶品质。主要经营液态奶、奶牛养殖、自营及代理各种商品的进出口等。

N 企业的产品服务，目前乳制品产品有新鲜屋、新鲜瓶、新鲜包、新鲜杯等七大系列50 余种产品，包括大众化的宁波牌与高端的涌优品牌产品，例如:华东地区首款有机鲜牛奶、高品质涌优鲜牛奶、常喝肠年轻嚼着喝的麦Q 风味发酵乳、5 种益生菌发酵的裸酸奶、不添加食品添加剂的零尚酸牛奶、融入城市印记的印象宁波系列牛奶等产品深入人心，均受到消费者的好评。

N 企业的商业模式：送奶到家、直销点、奶站、商超卖场、电话送奶、团购、在线订奶等销售渠道，共同构建起了特有的“新鲜通路”，让人们在家里、在办公室、在学校、在食堂，甚至在逛街购物时都能喝到新鲜的宁波牛奶。送奶到家服务是其旗下的特色渠道，在全国首先创立早晚两次送奶模式，覆盖了浙江省近10 个城市。

N 企业目前在整个乳制品冷链物流的配送过程中,司机在乳制品配送时根据以往的配送工作经验来进行货物配送，配送路线缺乏科学性的计算，存在严重不合理的情况，配送过程中存在资源浪费和时间浪费，配送情况的不合理性体现在配送路径缺乏科学性和忽视了节能减排的要求，以N 企业为案例，建立合理的数学模型，优化乳制品冷链运输的配送路径，提高配送效率和降低碳排放量，提高顾客满意度。

4.2 研究实例描述

本文通过使用兰图绘制图系统得到了N 企业在宁波市城区内各自营的经纬度位置，对各门店进行整理编号，从配送中心开始依次编号，配送中心的为1 号，10 个需求点编号依次为2，3，……，11。配送中心1 以及其余10 个需求点的具体地理位置信息如表2所示。

表2 需求点坐标信息

N 企业各自营点的经纬度、各需求点的需求量以及每个需求点的服务时间如表3所示。

表3 需求点位置及需求量

4.3 仿真实验结果分析

为验证算法的有效性，选取N 企业的乳制品配送路径进行仿真实验，为保证乳制品的新鲜程度和乳制品的食品安全程度，所以配送中心需要每天对各需求点进行一次配送任务。车辆在运输过程中保持匀速行驶，对车辆的配置以及运输过程中产生的各种成本参数进行如下定义如下表4所示。

表4 车辆配置及成本参数

本文进行仿真模拟操作使用惠普PAVILION 计算机,运行环境为windows10 家庭版，处理器为Intel(R)Core(TM)i5-8250U CPU@1.60GHz。基于此环境进行仿真模拟，利用MATLAB(2021a)软件进行仿真计算。

设置各个参数: 蚂蚁数量m=15，迭代次数NC=100，信息素重要程度因子α=1.0，启发函数重要程度因子β=5.0，常系数Q=1.0，信息素挥发因子ρ=0.1，经过10 次仿真实验,全部的计算结果如表5所示。

表5 计算结果及路径

续 表

由上表可知最优计算结果为第9 次仿真实验，最优路径的运输需要3 辆车，最优路径为83km，最少运输成本为2 160 元，MATLAB(2021a)仿真的最优路径如图2所示。

通过MATLAB(2021a)软件仿真得出的最优路径图可知：配送车辆为3 辆，从配送中心出发，具体每辆车的最优路径，每辆车经过需求点而行驶的距离以及每辆车的运输量如表6所示。

表6 车辆最优路径、运输距离及运输量

通过迭代次数图可以得出，当迭代次数为20 时候，最优路径趋于平稳不再变化，迭代次数如图3所示。

4.4 算法测试对比

本文选择的蚁群算法是一种用来寻找优路径的算法,同时增加了遗传算法和禁忌搜索算法的对照实验，可以看出通过蚁群算法计算得到的路径是最优的，成本也是最优的，蚁群算法在解决路径优化问题有明显的优势，通过对比计算结果如表7所示。

表7 算法对比结果

5 结 论

随着低碳环保和可持续发展的趋势，乳制品冷链物流的发展迅速，但也面临着一个新的挑战：企业在降低环境污染的前提下，如何优化产品的配送路线。本文通过实地调研，通过兰图绘地图制图系统确定了N 企业在宁波市区的主要自营点的地理位置，并且分析了N 企业的乳制品配送服务中存在的配送现状，通过对蚁群算法的学习，将N 企业的配送路线与蚁群算法相结合，从低碳角度出发，建立了以运输、制冷、货损和绿色低碳成本为目标的最优路线。

该方法可以有效解决大型冷链流的配送路径问题，并可降低运输费用、降低碳排放费用、提高企业的经济效益，同时还可以降低配送过程中的燃油和污染物排放量。该方法运用了基于实例的求解方法，建立了一种基于蚁群算法的单一配送中心配送乳制品的优化方法，从而提高了算法的适用性。为了检验该方法与其他方法相比的优越性，利用MATLAB 软件进行了模拟，结果表明：采用蚁群算法可以得出最佳的配送路线，从而节省运输费用、缩短运输距离、改善服务品质、确保产品的新鲜程度、提升顾客满意度，以期能为所在行业的决策者在降低环境污染的同时，提供相关的政策建议。