混合蚁群算法的改进及其在车辆路径调度中的应用研究

发布时间：2020-05-25 22:36

【摘要】：蚁群算法是一种模拟蚂蚁觅食行为的群体智能算法。蚁群算法具有自组织性和正反馈性,使其具有高度的适应性,因此被广泛的用于路径规划问题、图着色问题、集成电路设计、数据聚类分析等领域。但蚁群算法也具有收敛慢、易于陷入局部最优的缺点。因此,研究蚁群算法的改进具有重要的理论意义。随着经济全球化和信息化的发展,物流业迅速成为具有巨大潜力和发展空间的新兴服务产业,物流业也是我国十大产业振兴计划中的第十个产业。车辆路径问题是物流配送问题的理论模型,因此,研究车辆路径问题具有重要的实用价值。本文主要工作如下:1.讨论了蚁群算法的基本原理和发展过程,详细描述了蚂蚁系统、精英蚂蚁、蚂蚁排序和最大最小蚁群算法。讨论了蚁群算法的参数设置对算法性能的影响,以及蚁群算法的特点。2.针对带时间窗的车辆路径问题模型,本文提出了一种蚁群优化算法。该方法改进了状态转移概率,增加了时间窗的影响因子,并将信息素挥发率做递增调整。同时,提出了一种快速构造初始解的方法。通过与已知最优解的对比证明了该算法的有效性。3.讨论了蚁群算法在带时间窗同时送取货车辆路径问题中的应用,提出了一种混合蚁群优化算法。该算法增加了候选集策略,提前排除不满足条件的客户。并在蚁群优化算法的基础上继续改进了状态转移概率,增加了需求量的影响因子。该算法将蚁群算法与蛙跳算法相融合,先将蚁群排序后分组,再进化每个组内用三角概率分布选择出来的蚂蚁,进化步骤采用局部搜索算法,最后重新排序和分组,如此循环一定次数。实验表明将这两种群体智能算法相融合,减少了计算量,同时提高了解的质量。4.讨论了动态车辆路径问题,提出了并行蚁群优化算法。该算法将解决动态问题的过程分成了两个阶段,第一阶段通过混合蚁群优化算法来规划初始路径。第二阶段把工作日分成等长的时间片段,每个时间片段检查是否有新客户,有则重新规划路径。每次完成规划,信息素得到保留,继续参与下一次的规划,所以时间片段之间形成了正反馈,最终方案不断得到改善。同时利用了蚁群算法的并行性,引入了并行计算,每只蚂蚁并行的构建路径。实验表明,该并行蚁群优化算法不但提高了解决方案的质量,同时也减少了运算时间。
【图文】：

过程图,蚂蚁,过程图,信息素

发式全局优化算法。2.1 蚁群算法的基本原理根据文献[35]所描述，蚁群算法的理论来源是：在自然界中，，在蚂蚁觅食的过程中，蚂蚁会在所经过的路径上留下一种分泌物，蚂蚁相互之间能够感知到这种分泌物，这就形成了蚂蚁之间相互交流的信息。因此学者们将这种分泌物称为“信息素”。更短的路径上的信息素积累的更快，蚂蚁更倾向于选择信息素更浓的路径，这就形成了一个正反馈的现象。但是，信息素会随着时间挥发。一段时间过后，最短的路径积累的信息素远远多过挥发的信息素，而在更长的路径上，大部分的信息素都被挥发了，因为两种路径信息素累积量显著的差距，最终所有蚂蚁都会选择最短的路径。蚂蚁的觅食过程如图 2.1 所示：A巢食A巢食

对比图,初始解,对比图,算法

图 3.1 使用初始解算法对比图，加强了初始解路径上的信息素之后，算法一开始就，提高了初始解集的质量，而且算法的收敛速度也大时就得到了最优解。而不加强初始解路径上的信息素很差，且陷入了局部最优解。概率算法很少考虑时间窗，但是对于带时间窗的问题，时此，本算法考虑进了时间窗因子，提出了一种新的状窗的紧迫性因子和时间窗最早开始时间因子。时间窗紧的客户。时间窗最早开始时间确保了开始时间晚的因素都可以帮助改进蚁群算法找到最有效的路径，并
【学位授予单位】：重庆邮电大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：U491;TP18

【参考文献】