改进蚁群算法优化车辆路径问题的研究①

邓会馨, 武俊丽

(佳木斯大学信息电子技术学院,黑龙江 佳木斯 154007)

0 引 言

近年来,随着公路和铁路交通运输的高速发展,配送运输行业也随之迅猛发展。汽车配送运输面临着城市交通路线复杂、配送用户多,危险品安全装卸等问题,例如成品油二次配送问题[1],因此保持车辆运输成本耗费的最小化是很重要的。配送问题可以简化为车辆路径优化问题,即在一定约束条件下通过调度可用车辆为配送节点提供高效的服务。因此,研究优化配送车辆路径问题,在降低配送成本和提升用户满意度等方面具有重要理论意义和现实意义。车辆路径问题自提出以来就得到了国内外研究者们的广泛关注,展开了大量深入研究。精确式算法是一类可获得具体问题的最优解的精确方案[2],但随着问题规模的扩大,求解时所需的计算时间呈指数型增长。因此,许多学者采用启发式算法以在一定时间范围内获得较高质量的近似解进行了广泛研究。一类以“构造”思想为代表的经典启发式算法[3-4]率先在车辆路径优化领域获得应用。该类算法的出现在一定程度上弥补了精确式算法在求解中大型规模的车辆路径问题时的局限性。此外,一类根据优化目标在连续迭代中不断更新个体结构的元启发式算法[5]逐渐成为近年来主流的解决方案。元启发式算法包含但不限于蚁群优化算法[6]、遗传算法[7]以及粒子群算法[8]。其中,蚁群优化算法借助其特有的正反馈、自组织、以及分布式机制等特点在路径优化领域得到了广泛应用。但收敛速度慢,全局寻优能力不足,容易陷入局部最优等不足仍然存在。文中,从避免早期盲目搜索、防止迭代后期搜索停滞以及提高算法收敛速度三方面对蚁群算法进行了综合改进,以全面提高求解精度和搜索效率。研究基于上述的改进蚁群算法(improved ant colony algorithm, IACA),针对带路径约束、时间窗约束和容量约束的车辆路径优化问题,提出优化以最小化配送车辆路径总成本为目标函数的算法。最后,基于Solomon基准数据集[9]展开对比试验进行该算法的高效性和实用性验证。

1 问题描述

带约束条件的车辆路径问题可以描述为:假设车辆集合K(K={1,…,m})和节点集合V(V={0}∪V0) 已知,其中,配送中心用0表示,配送节点用V0(V0={1,…,n})表示。要求通过调度可用车辆规划出一条能为一组已知分布情况和需求量的配送节点提供配送服务的路线。假设任意车辆都从配送中心出发,完成若干配送节点的配送任务后返回配送中心;每段配送路线中所有配送节点的需求量之和不超过单个车辆的最大载重量;单个车辆可以服务多个配送节点,但每个配送节点能且仅能被服务一次且不允许拆分交货;车辆对每个配送节点的配送服务必须在配送节点限制的时间窗范围内进行。车辆路径的优化目标是使构建的配送路线总行驶里程最短,运输时间最少和配送成本最小。

考虑带约束条件的车辆路径问题的数学模型公式(1)所示:

同时满足下列条件

(2)

(3)

(4)

(6)

(7)

(8)

(11)

2 改进的蚁群算法

为提高蚁群算法在带约束条件的车辆路径问题中的求解性能,从三方面对蚁群算法进行了改进:对参与条件转移概率的候选节点列表进行预处理减少路线构建过程计算的时间复杂度;提出插入式节约算法用于改进初始配送路线提高寻优精度;改进信息素更新策略加快算法收敛速度。

2.1 状态转移概率

根据蚁群系统算法[6],当车辆k位于位置i时对下一位将要访问的配送节点s的选择规则如下:

(12)

其中,τiu表示连接节点i到节点u的路径中的信息素强度;ηiu表示蚂蚁节点i转移至节点u的期望值,与连接两点的路径长度呈反比;α,β(α,β>0)代表信息素启发因子和期望启发因子的相对强弱;allowedk表示能接受在节点i服务完成后被车辆k访问的节点集合;q是[0,1]区间内呈均匀分布的随机数;q0是介于(0,1)之间的一个常数,它的大小决定了利用先验知识与探索新路径之间的相对重要性;S是根据公式(13)描述的转移概率产生的候选节点。

(13)

其中,pijk(t)表示t时刻车辆k在结束对节点i的服务后选择节点j作为下一个服务对象的概率,离蚂蚁当前位置较近或与当前节点i相连路径中信息素含量较高的节点被选择的概率较大。

传统蚁群算法对下一个节点选择在所有尚未被服务的节点中进行,该过程的时间复杂度达到O(n2),收敛速度较慢。为减少搜索空间加快算法收敛速度,提出在节点转移之前先利用公式(2)-(4)进行候选节点的筛选更新参与条件转移计算的节点取值范围。

筛选过程的主要步骤如下:

(1)输入包含所有未访问节点的集合V'0及现有路线R'。假设现有路线R'中最后访问的节点是r1。

(2)对未访问节点集合V'0进行遍历,假设当前未访问节点是r2,根据公式(2)-(4)判断能否将r2作为r1服务结束后下一个被访问的节点。

(3)将步骤(2)中满足不等式成立条件的节点存储于候选节点列表allowedk。

(4)输出候选节点列表allowedk,作为公式(12)-(13)中参数的取值范围。

2.2 插入式节约算法

其中,num(Rk)是计算路段Rk的节点数量的函数。

(1)Type I类型插入Type II类型的算法

(15)

(2)Type II类型插入Type II类型的算法

假设执行插入操作的对象是Type II类型的路段Rl和路段Rm,要求将路段Rl中所有配送节点插入路段Rm中,若在两路段合并过程中存在不满足公式(2)-(11)插入操作则代表插入失败。

(16)

2.3 信息素更新策略

在所有蚂蚁完成一次迭代搜索之后,需要更新所有路径上的信息素。为明显区分不同质量的路径以对后续蚁群的搜索方向提供指导,基于全局信息素更新策略提出按公式(17)进行信息素更新,即仅最优路线中的路径能成功遗留新释放的信息素。

τij(t+1)=(1-ρ)×τij(t)+Δτij

(17)

其中,τij(t)表示t时刻连接配送节点i与配送节点j的路径上的信息素含量;ρ表示局部信息素挥发因子,取值为区间为(0,1);Δτij表示蚂蚁在连接配送节点i与配送节点j的路径上释放的信息素,如式(18)所示:

其中,Q表示信息素常量;Zbest代表最优路线的总成本。

3 改进蚁群算法优化车辆路径问题的步骤

改进蚁群算法优化车辆路径问题的步骤如下所示:

步骤1种群初始化。设置最大迭代次数Iter,种群数量P,初始信息素浓度τ0,信息素挥发因子ρ,启发因子α,β,概率常数q0,信息素常量Q。初始化距离矩阵,信息素矩阵,设置全局最优解Sglobal的配送路线为空,对应的目标值函数为一个极大值。

步骤2构造蚂蚁的初始配送路线。首先,根据2.1节提出的预处理确定候选节点范围allowedk;其次,结合α,β,q0以及信息素矩阵,采用公式(12)确定当前路段的下一个访问节点s,直至完成所有配送节点的访问或不存在可用车辆,得到一条配送路线R。

步骤3优化蚂蚁的配送路线R。首先,采用公式(15)将剩余节点插入已有路线;其次,采用公式(16)对存在合并条件的路段进行优化;然后,按公式(1)计算新配送路线R′对应的目标函数值ZR′;最后,用配送列表S记录所有蚂蚁构造的配送路线和对应的目标函数值。

步骤4整合配送列表S中的配送方案。将配送列表S中目标函数值高于平均目标函数值的配送路线删除,并采用公式(16)对目标值低于或等于平均目标函数值的配送路线R′进行优化得到R″;然后,按公式(1)计算当前路线R″对应的目标函数值ZR″。

步骤5优化配送列表S中的配送方案。若ZR″

步骤6更新全局最优解Sglobal。若局部最优解Slocal的目标函数值小于全局最优解Sglobal的目标函数值,则用局部最优解Slocal更新全局最优解Sglobal。

步骤7全局信息素更新。结合ρ,Q以及全局最优解Sglobal,按公式(17)提出的信息素更新策略进行全局信息素更新。

步骤8循环执行步骤2～7,直至达到最大迭代次数Iter,输出全局最优解Sglobal。

4 算例测试与对比

采用Python 3.10编程语言测试,进行第3部分提出的改进蚁群算法(IACA)与改进的烟花算法(improved firework algorithm, IFA)算法[10]的对比实验。实验中IACA算法的各类参数设值如下:信息素挥发因子ρ=0.2;信息素启发因子α=4;期望启发因子β=2;种群规模P=100;初始信息素τ0=10;信息素常量Q=10;迭代次数Iter=80;概率常数q0=0.2。表1从最优路线花费的成本(Z)和使用的车辆数(N)两方面对实验结果进行了总结,其中,Gap数值通过Gap=(IFA-IACA)/IACA×100%计算所得。

表1 IACA与IFA的实验结果对比

由表1可知,IACA在C系列所有测试集中获得的最优路线的总成本均低于通过IFA获得的结果。其中,在C202测试集中获得了最大8.25%提升的最优解,在C101测试集中获得了最小1.98%的最优解,平均较IFA的最优解具有4.12%的提高。此外,IACA分别在50%的R系列测试集和60%的RC系列测试集中获得了较IFA更低成本的最优路线。其中,在R系列测试集中获得的最大提升出现在R202测试集中;在RC系列测试集中获得的最大提升出现在RC202测试集中。IACA能够在众多测试集中获得更优的结果,说明优化阶段提出的插入式节约算法具有提升种群多样性和寻优精度的效果;基于伪随机比例的状态转移规则和精英化的信息素更新策略对于引导蚁群搜索和加快算法收敛具有有效性。

5 结 语

针对优化带约束条件的车辆路径问题,提出了改进蚁群优化算法,对待访问节点列表采用预处理过程缩短蚁群路线构建过程中的计算时间,针对剩余节点和已有路线设计的插入策略对指导后续蚁群搜索方向、提升可行解质量方面具有积极作用。仅针对最优路线的全局信息素更新方案避免了信息素的无限积累有助于提高算法收敛速度。通过与IFA算法进行最优目标值对比,验证了针对蚁群算法提出的改进策略在提高求解精度和搜索效率方面具有有效性。未来将继续探索该问题衍生问题的解决方案。