基于改进的蚁群算法的目标物流车辆路径优化

曾 胜，王 兵，戴贤君

（1.皖江工学院电气信息工程学院，安徽马鞍山 243000；2.安徽工业大学电气与信息工程学院，安徽马鞍山 243000；3.中国计量大学生命科学学院，浙江杭州 310000）

0 引 言

冷链物流是指在整个物流过程中对温度敏感的产品（如食品、药品、化学品等）进行温度控制和监测的一种物流管理方式。冷链物流的发展受到全球经济、技术创新和消费者需求等多方面因素的影响。全球化趋势促使企业将供应链整合到全球范围内，这对冷链物流提出了更高的要求。协同作业、跨国合作和全球供应链的整合需要更高水平的冷链技术和管理。

冷链物流的发展已经近几十年了，但是冷链物流的路径设计一直困扰着物流公司，在路径行驶过程中总会遇到障碍物或者路况复杂的情况，针对此类情况车辆在行驶过程中应找到一条无障碍路线，缩短运输时间，降低运输成本，为物流公司节约成本。文献[1]提出了一种自适应调整启发函数解决机器人路径规划问题的改进蚁群算法；文献[2]改进了蚁群算法的状态转移方式和信息素更新方式，引入最大最小蚁群算法与2-opt 局部搜索算法；文献[3]在文中阐述所有蚂蚁遍历完所有待访问的收货点后搜索到的所有路径上的信息素进行更新而导致算法收敛和计算效率降低等缺陷，改进了算法中的状态转移概率公式，优化了信息素浓度设定和更新方式；文献[4]构建多核心的蚁群选择算法，并设计深度选择定义模型，利用临界预设法设计路径优化的选择方法。文献[5]针对传统蚁群优化（ACO）算法搜索路径时易陷入局部最优、路径过长、转弯角度过大等问题，提出一种基于转弯角度约束的改进ACO 算法。文献[6]提出一种改进的蚁群优化（IACO）算法，利用工作环境的全局信息建立目标吸引函数，提高蚁群选择最佳路径到达目标点的概率，缩短了算法的迭代时间；文献[7]提出一种改进蚁群算法，动态改进信息素更新策略和启发因子，并采用可行解先行策略；文献[8]基于多约束条件对传统蚁群算法状态转移启发函数和信息素进行了改进，较好地改善了算法的动态优化性能；文献[9]针对传统蚁群算法在解决室内疏散问题时存在收敛速度慢、容易陷入局部最优的缺陷问题，将火场的动态参数引入到蚁群算法中，对其路径选择策略、启发函数和信息素更新策略进行改进，为整个疏散群体求解更优的疏散路径；文献[10]研究物流路径优化问题，目的是有效降低物流配送距离，实现配送任务完成的高效率与低成本，通过对基本蚁群算法启发函数的优化提出改进蚁群算法。文献[11]采用局部最优和全局最优两种方式对传统蚁群算法的信息素更新方式加以扩大至最优解寻觅范围，并对启发因子的函数定义范围扩展至初始节点。文献[12]对客户选择策略采取分段计算的方法，以加快算法的收敛速度，并在构建一条完整的闭合路径时过滤距离路径较远的客户，提高搜索最优路径的能力。文献[13]设计随迭代时间改变的信息素浓度更新机制，改进蚁群算法实现放牧路径随牧场条件变化的及时优化，解决持续放牧的盲目性。

基于上面的研究成果，本文提出一种改进最优最差蚁群算法和启发因子算法进行路径优化的方法，此类方法可以缩短车辆行驶路径、节约时间，以最快的时间把生鲜产品运输到目的地。

1 目标物流车辆路径优化模型

本文以某H 公司为例，该公司的主要营业产品为运送冷链物流产品，产品主要由食品、生鲜产品等组成，其主要配送任务是把产品运输到各个网点，以达到客户的需求。为了下面建模方便，本文调查了该公司每月的运输量，图1 为2022 年一年的运输量。

图1 冷链物流每个月运输量

根据图1 可以看出，2022 年各月份对冷链物流产品需求量不一样，特别在夏季的时候对冷链物流的需求量大幅度增加，此时就会增加冷链物流公司的压力，为了解决面临的问题，要在时间、成本上节约，那此时就需要规划好路径。

1.1 问题描述

目标车辆运输过程中其目的在于降低运输成本，保证生鲜冷链物流产品在规定的时间内到达目的地。针对本文研究状况提出以下假设：

1）冷链物流运输车辆必须从始发地装满货物出发运送到目的地，再从目的地空车返回始发地。

2）对于车辆在运输过程中，保证其在每个运输点消耗的时间在一定的范围内。

3）车辆在满载过程中与空载过程中其行驶速度稳定，不考虑其拥堵情况。

4）对于运输所有车辆必须要保证满载货物不能超过其车辆运输的最大限度。

5）所有车辆型号保持一样且司机身体健康良好。

6）每辆车只服务本次指派的任务，不增加其他任务指标。

1.2 数学模型

传统的车辆运输没有考虑碳的排放运输成本，本文研究设计主要从两个方面降低运输成本：一是降低碳的排放成本；二是车辆运输成本。式（1）为总的运输成本。

1.2.1 碳排放因素成本

《碳排放权交易管理办法（试行）》已于2020 年12 月25 日由生态环境部部务会议审议通过，自2021年2月1 日起施行。此政策的出台致力于解决碳排放对环境产生的影响，本文冷链物流车的运输是通过燃油车进行运输，由于电动车行驶距离较近，不适合冷链物流的运输，所以采用燃油车进行运输，在使用燃油车的同时也应最大程度降低其运输成本，其中如下两个因素影响碳的排放成本：

1）冷链物流车的行驶速度影响碳的排放成本；

2）冷链物流车重量影响冷链物流车的排放标准。

G为冷链物流车重量，v为车辆行驶的速度，dij为仓库到客户之间的距离，xi为坐标点的横坐标，yi为坐标点的纵坐标，(xi1,yi1)为仓库坐标，(xi2,yi2)为客户点坐标，k为运输车辆数量，每千米固定燃油消耗为M，碳的每千米固定排放量为q，每千米碳排放成本为s，N= 1,2,…,n为物流点坐标点，α1为速度系数，α2为冷链物流车重量系数。

车辆行驶速度与重量不同，则排放成本不同，其成本计算公式如下：

速度成本：

重量成本：

碳排放总成本：

1.2.2 运输成本

1）固定成本

假设B0为冷链物流车与工作人员固定费用，xijk为决策变量，该固定费用主要包括运输过程中折损费用、司机的工资等费用。以下公式为冷链物流运输过程中固定费用：

2）制冷成本

为保证冷链产品足够新鲜，本文要控制制冷箱的温度，针对此类情况就会产生一个制冷成本，由于制冷成本与时间有关系，由此假设t1为仓库到卸货点时间，由于卸货过程中也会产生一个时间，设定为t2，假设每分钟行驶过程中的固定成本为Y1元，卸货过程中每分钟花的成本为Y2元，则制冷总成本如下：

3）运输成本

冷链物流车运输过程中也会产生相应的成本，比如车辆的油费，但是由于运输车辆重量影响油费的高低，那么设置每千米油耗率为β，β0为初始油耗率，公式如下：

4）损耗成本

ς1为货物在匀速行驶过程中新制冷系数，ς2为打开车厢物品制冷系数，t3为打开车厢时间。

5）总运输成本

总的运输成本主要由碳排放因素成本与运输成本构成。

约束条件：

2 算法模型

2.1 环境建模

本文针对蚁群算法采用栅格法进行路径规划，栅格法在Matlab 中仿真矩阵主要采用0、1 两个数据，0 代表无障碍物，1 代表有障碍物，栅格的设计主要以黑白为主，模型中栅格设计主要以正方形或者长方形为主，依次对网格区间设计各个区域。为表示网格的各个位置，使用了一种连续的标序，从左到右、从上到下依次排列，形成了一个完整的栅格图，图2 为环境模拟图。

图2 路径模型栅格图

2.2 传统的算法模型

传统的蚁群算法的研究设计如下：假设t时刻第k只蚂蚁从i位置点爬行到下个位置点j，设置初始释放的信息素为τij和启发信息βij，同时设置转移概率为Pk ij，α为信息素启发因子，β为期望启发式因子，dij表示从i位置点到j位置点的距离，ηij为期望启发式函数。则有：

蚂蚁在经过路径时会释放信息素，由于信息素随时间的推移产生挥发，传统蚁群在爬行过程中会产生迭代，此时会更新信息素，信息素更新公式如下：

式中：ρ是信息素挥发系数，一般设置为0 ＜ρ＜1；Δτij(t)表示是蚂蚁爬行从i城市到j城市t时刻的最佳释放信息素量；Q表示释放信息素的强度；Lbest表示蚂蚁爬行的最佳路径长度。

2.3 改进后的算法模型

改进后的蚁群算法主要对蚂蚁爬行过程中的释放因子进行改进，由于蚂蚁在爬行过程中其信息会发生很大的变化，对其信息素的收集会发生两种变化：一是所有蚂蚁爬行过程中蚂蚁群会选择另外一只优等蚂蚁而不是起初的优等蚂蚁，此时蚂蚁爬行过程中不同路径释放的信息素浓度会发生改变，由于在爬行过程中选择优等的蚂蚁，此时通过计算公式得出多个蚂蚁释放的信息素浓度；二是所有蚂蚁在爬行结束过程中选择其信息素浓度，但是由于优等蚂蚁不只是一个，有多条路径由多只蚂蚁释放的信息素浓度，此时寻找出的路径看不出哪条路径是最优路径，可能随机寻找出其中一条释放出信息素浓度比较多的一条路径，这种表面选择出来的路径并不代表是最优的路径，导致路径的选择发生改变。针对这两类情况，本文对蚁群算法的路径进行优化。

对于最优路径的寻找，规定了只有在最优路径上面的信息素浓度才会逐渐增加，非最优路径上的信息素都会慢慢挥发直至没有；其次，为了尽量避免出现搜索停滞的现象，把信息素限定在一个区间[τmin,τmax]中，任何大于或低于这个区间的信息素都会相应的用τmin、τmax进行替换。优化公式如下：

若τij(t) ≥τmax，则：

若τij(t) ＜τmin，则：

1）最优最差蚁群算法改进

最优最差蚁群算法的改进思想是通过更大限度地增强最优解，缩减更小的最差解，这样做的目的是使得蚂蚁在爬行路径中优化路线的信息素浓度与劣势路径信息素浓度彼此之间差距变大，促使蚂蚁都爬向优化路线那条路径，此时蚂蚁爬行基本上聚集在最优路线上，该方法也是改变传统的蚂蚁爬行路径，当信息素释放完，更新最差路径信息素浓度。

式中：ε为引入的算法参数；τ(i,j)为两地之间的信息素轨迹；Lbest为搜索路径中最优长度；Lworst为搜索路径中最差长度。

2）启发因子算法改进

由于蚂蚁在爬行过程中有热搜索过程，蚂蚁爬行过程中所谓绕开障碍物是指，由于在爬行过程中遇到路径区域温度高于其正常生存温度，此时蚂蚁就会绕开此路径，那此时蚂蚁的整个爬行路径会随之发生改变，对其启发因子就会产生影响。针对此类情况，本文对其传统的启发因子进行改进，引入一个自适应因子μ，dik为第k辆车到i点的距离，djk为第k辆车到j点的距离，启发因子的改进公式如下：

转移概率公式为：

2.4 改进后的算法步骤

改进后算法步骤如下：

Step1：初始化信息素。在问题空间中的每个可能的解都有一个与之相关的信息素值τij。初始时，信息素值通常被设置为与τij相等的小值。

Step2：初始化蚁群。在问题空间中随机放置蚂蚁数量为k，每只蚂蚁从问题的一个解空间点开始。

Step3：蚂蚁路径选择。每只蚂蚁按照一定的规则选择移动路径，通常蚂蚁选择路径的概率与路径上的信息素浓度和路径距离dij有关，信息素浓度高的路径和之前蚂蚁走过的路径有更大的概率被选择。

Step4：改进算法蚂蚁移动。蚂蚁按照选择的路径移动到下一个解空间点。在移动过程中可以考虑引入一些随机性，加入最优最差、启发因子算法的多样性。

Step5：更新信息素。当所有蚂蚁完成移动后，根据其走过的路径更新路径上的信息素。通常路径上的信息素会蒸发，则引入[τmin,τmax]信息素浓度，此外由于热区域的影响，引入新的启发因子η*ij，然后根据蚂蚁的移动路径和问题的优化目标增加新的信息素。

Step6：重复迭代最大迭代次数Ncmax。重复上述步骤多次，直到满足停止条件Ncmax＜N。停止准则可以是达到一定的迭代次数、找到满意的解或其他预定条件。

Step7：输出结果。最后从所有蚂蚁的移动路径中选择一条最优解作为算法的输出。

3 目标物流车路径优化实证

3.1 路径模拟仿真

设置初始释放的信息素为τij和启发信息βij，同时设置转移概率为Pkij，α为信息素启发因子，β为期望启发式因子，ρ是信息素挥发系数，Q表示释放信息素的强度，ε为引入的算法参数，μ为自适应因子，Ncmax为最大迭代次数。各参数设置如表1 所示。

表1 参数设置

图3 为传统蚁群算法的路径优化仿真图。图4 为改进后蚁群算法的路径优化仿真图。

图3 传统的蚁群算法仿真

图4 改进后的蚁群算法仿真

根据图3 与图4 仿真对比可以看出，经过改进后的蚁群算法路径更近且收敛性更好，更符合冷链物流公司的设计方案。

3.2 成本计算

本文以H 冷链物流公司为例，对其参数与路径坐标进行设置。G为冷链物流车标准重量6 t，v为车辆行驶的速度60 km/h，dij为仓库到客户之间的距离，k为运输车辆数量，每千米固定燃油消耗为M=0.08 L，碳的每千米固定排放量为q=0.3 mg，每千米碳排放成本为s=0.5 元，设置物流车数量为k=15，α1为速度系数0.2，α2为冷链物流车重量系数0.3。t1为仓库到卸货点时间3 h，卸货过程中也会产生一个时间t2为1 h，假设每分钟行驶过程中的固定成本为Y1=10 元，卸货过程中每分钟花的成本为Y2=2 元，每千米油耗率为β=0.06 L，初始油耗率β0=0.03 L，ς1为货物在匀速行驶过程中新制冷系数0.3，ς2为打开车厢物品制冷系数0.5，t3为打开车厢时间2 min。车辆行驶坐标如表2 所示。

表2 车辆行驶坐标

表2 为车辆可供选择的路线，通过蚁群算法和优化后蚁群算法选择出路径最短的路线，再计算相应的成本。从表中可以看出3号路线路径最短，那么所花的成本最低。

根据表2 选择dij为3 号路线的距离。表3 为成本计算表。通过表3 成本计算可以看出：利用蚁群算法的模型可以降低运输成本；优化后的成本比传统蚁群算法的成本要低。

表3 成本计算表元

4 结 语

本文通过研究表明，H 冷链物流公司运输量较大，通过蚁群算法模型设计明显提升了运输效率，大大增加了公司的运输量，但本文同时也对传统蚁群算法进行改进，优化车辆路径，使得H 冷链物流公司达到了最低成本，有效地节约了配送成本，改善了物流配送的效率。

注：本文通讯作者为曾胜。