英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料

---

一种改进的蚁群算法及其在带时间窗车辆路径问题中的应用

摘要：蚁群算法（ACO）灵感来自蚂蚁物种的觅食行为，是用于解决硬组合优化问题的群体智能算法。 然而，该算法具有过早收敛和搜索速度低的缺点，极大地阻碍了其应用。 为了提高算法的性能，本文提出了一种混合蚁群算法（HACO）。通过调整信息素方法和引入灾难操作员，HACO可以防止搜索过程被困在局部最优解中。 然后，通过考虑候选列表并组合ACO与保存算法和lambda;-互换机制，HACO提高了收敛速度。 此外，本文给出了如何调整参数以实现算法性能良好的指南。 最后，HACO应用于带时间窗的车辆路径路径问题。 HACO解决组合优化问题的有效性通过将计算结果与以前在文献中提出的计算结果进行比较来验证。

关键词：蚁群算法 带时间窗车辆路径问题 组合优化问题

1 介绍

20世纪90年代由Colorni等人提出的蚁群优化（ACO）是一种元启发式算法，最初用于着名的旅行推销员问题。

ACO的基本想法是模仿真正的蚂蚁搜索食物的行为。 发现真正的蚂蚁能够通过称为信息素的芳香精华传达关于食物来源的信息。 当他们走动的时候，真正的蚂蚁根据发现的食物来源的质量来放置信息素。 观察信息素踪迹的其他蚂蚁被吸引追随。 因此，道路将得到加强，因此将吸引更多的蚂蚁。

根据上述行为机制，通过模拟人造蚂蚁搜索解空间，而不是真正的蚂蚁搜索环境来提出ACO。 比较与其他启发式，ACO具有积极反馈，分布式计算和建设性贪婪启发式的特点。

ACO已经被证明是一种解决组合优化问题的有效算法，但在实践中还有一些缺点：

●搜索通常被困在局部最优解中

●它需要大量的计算时间才能获得最优解

●调整参数难以实现性能

为了避免这些缺点，Stutzle和Hoos提出了一个MAX-MIN蚂蚁系统，邢和余提出了一种基于自适应调整信息素的改进蚁群算法。虽然这些提到的算法有效地阻止了搜索过程被困在局部最优解中，但是由于调整信息素需要大量的计算时间，所以搜索速度受到影响。 Bullnheimer等引入了一种改进的蚁群算法来解决车辆路径问题。他们的研究成功地提高了搜索速度，但是所提出的算法难以提高解决方案的质量。 Reimann等人提出了一种分岔算法，解决了车辆路径问题与基于蚂蚁系的扫描算法和禁忌的保存算法搜索算法。基本思想是根据一个初步的解决方案将问题分成几个不相交的子问题，然后通过ACO过程解决问题。该算法用于解决大规模问题时具有很大的优势，但是扩展其应用程序太复杂了。 Bell和McMullen提出了一个改进的ACO结合选择启发式和候选名单。该算法的搜索速度更快，但是当用于解决大规模问题时，解决方案的质量更差。 Han和Shi 提出了一种改进的ACO，用于图像分割中的模糊聚类。为了提高ACO的效率，在研究中采取了两项措施：一是利用原始图像信息设置初始聚类中心。另一个是提高启发式功能加快搜索过程。实验结果表明，改进的ACO优于原始ACO。然而，改进的ACO和其他启发式的解决方案质量没有比较，包括遗传算法，模拟退火算法，禁忌搜索算法等。Chen和Ting提出了一个改进的蚁群系统与SA和Balseiro等人提出了一种与插入启发式混合的多蚁群系统算法。虽然计算结果表明，所提到的算法与其他启发式算法具有竞争力，但是没有说明如何调整这些参数以达到良好的性能。值得注意的是，现有的改进ACO的研究已经做出了很大的努力，但是过早的收敛，搜索速度和参数设置还需要进一步研究。

在最近的工作中，我们提出了一种改进的ACO，防止搜索过程被困在局部最优解中，提高了收敛速度。 本文是我们以前的工作的扩展，并说明了这些参数通过进行详尽的测试来影响算法的整体性能。

本文的其余部分安排如下。 第2节演示了改进的ACO，被称为混合蚁群优化（HACO）。 第3节给出了如何调整这些参数以达到良好性能的指导方针。第4节构建了时间窗（VRPTW）车辆路线问题的数学模型，并描述了解VRPTW的步骤。 第5节将计算结果与现有文献进行比较，并显示出良好的性能提出算法。 最后，第6节为今后的研究提供了结论和指导。

2.ACO算法的改进

为了防止搜索过程被困在本地优化解决方案中，HACO通过调整信息素方法和引入灾难运营商来呈现。 为了提高ACO的收敛速度，通过考虑候选列表并结合ACO与保存算法和lambda;-互换机制来呈现HACO。

2.1调整信息素的方法

考虑到信息素在蚂蚁殖民地之间信息交换的重要性，本节重点介绍调整信息素的三个方面，以避免HACO被困在局部最优解中。 细节如下：

1. 在ACO算法中，蚂蚁群落给出的信息素并不总是指示最佳方向，而从最优解离出的信息素有可能增强，这样可以防止其他蚂蚁找到更好的解决方案。 由于正反馈的影响，随机选择ACO中的参数不足以防止搜索被困在局部最优解中。

因此，本文将定性和随机选择与ACO结合起来，以提高全局优化能力。 当搜索被困在局部最优解中时，可以通过调整信息素并增加随机选择概率来进一步搜索解空间。

1. 在每个边缘，最大或最小的信息素路径可能导致搜索过早收敛。 因此，HACO提出tau;_min和tau;_max作为最小和最大信息素轨迹，并限制所有信息素路径tau;_ij以满足tau;_minle;tau;_ij le;tau;_max，这是基于MAX-MIN蚂蚁系统的基本思想。 同时，信息素轨迹故意初始化为tau;_max，这有助于在搜索开始时找到更好的解决方案。 另外，在信息素跟踪差异很大的情况下，计算tau;_ij和tau;_max之间的平均信息素路径的计算被吸收，这将在获得新的解决方案中发挥重要作用。
2. ACO算法难以解决大规模问题，因为轨道蒸发1-rho;的存在。 较大的1-rho;，全局优化能力将越好。 但如果是这样，算法的收敛速度就会变慢。 因此，为了克服困难，本文采用动态1-rho;值而不是常数值。

2.2 灾难运营人的介绍

虽然由于正反馈的特点，ACO具有快速的搜索速度，但是它倾向于被局限在最优解中。 由于遗传算法的突变操作可以提高人口的多样性，因此解决空间可以完全搜索。 因此，在ACO中采用与遗传算法突变相似的灾难运算符，以避免过早收敛。 通过在本地优化路径的某些部分大大减少信息素路径，该算法能够寻找更好的解决方案。 实验表明，引入灾难运营商可以有效提升全局优化能力。

此外，灾害路线以与遗传算法相似的方式由小的随机概率决定，因为信息素在先前路径中的分布将被太多的灾难发生所破坏。

2.3 候选人名单的策略

此外，在ACO算法中，当蚂蚁从节点i选择下一个节点j时，计算所有未干扰节点的转移概率将需要很长时间。通过分析具有多个节点的复杂地图，节点j应该靠近节点i [19]。因此，本文采用选择最近节点的策略来提高收敛速度。该策略的基本思想是根据与节点集中所有其他节点的距离将候选列表分配给每个节点。只有最近的节点被包括在当前节点的候选列表中，并且可以被选择为在路由中要被访问的下一个节点。候选人名单的大小已经通过将其大小限制为总客户数量的一小部分来确定。例如，在Bullnheimer等人的研究中，候选人名单的大小被设置为等于客户总数的四分之一，而不考虑客户数量[10]。如图1所示。有30个客户的候选人名单的大小限制为四舍五入的整数值七。

车厂

当前节点

候选节点

非候选节点

图1：候选人名单的例子

2.4 将ACO与保存算法和lambda;-互换机制相结合

ACO是与其他启发式组合为特征的强耦合算法。 因此，通过结合保存算法和lambda;-互换机制处理组合优化问题，可以大大提高收敛速度。

2.4.1 保存算法

保存算法是一种简单而有效的方法，是Clarke和Wright [20]提出的最广为人知的算法。 如图2（a）所示，该算法首先将每个客户分配到单独的路径。 然后，对于每对客户i和j，它评估通过在同一路线上组合两个客户可以获得的节省（如图2（b）所示），节省由公式 （1）

s_ij =2d_0i 2d_0j-d_0i-d_0j-d_ij=d_0i d_0j -d_ij

其中d_0i表示仓库0和节点i之间的距离。 d_0j表示仓库0和节点j之间的距离。 d_ij表示节点i和j之间的距离。 然后选择最佳组合，并重复该过程_。

车厂

车厂

图2：保存算法的基本思想

2.4.2 lambda;-互换机制

奥斯曼[1]提出的交换机制也是一种有效的方式。 在本文中，采用2-互换和or-交换机制来提高ACO的收敛速度。

双交换的基本思想是通过在最初的可行解中交换节点来实现的。 如图3所示，如果总成本降低，车辆的容量不被交换节点i 1和j 1，则该解决方案将被接受。

Or-互换的基本思想如图4所示。 通过将节点i插入到弧（j，j 1）中，如果总成本降低并且车辆的容量不被侵犯，则解决方案将被接受。

车厂

车厂

图3：两个交换的基本思想。

车厂

车厂

图4：or-交换的基本思想

1. 参数设置

HACO的一个关键特征是可以通过改变参数值来控制解决方案的质量。 为了说明这些参数如何影响我们算法的整体性能，最优解与关键参数（包括m，alpha;，beta;，Q等）之间的分析是在随机选择的C1-01问题上进行的，如下。

3.1 参数m

最优解与参数m之间的关系如图5所示。 当mgt;35，该算法的性能不能进一步提高。 因此，实验表明m可以在[0.3n，0.4n]的间隔内设置，其中n是客户数。

最优解

参数m

图5：最优解与参数m之间的关系

3.2 参数alpha;

最优解与参数alpha;之间的关系如图6所示。 较小的alpha;，收敛速度越慢。 另一方面，较大的alpha;，HACO越容易获得局部最优解。 因此，当alpha;在区间[2,3]中时，我们的算法的性能相对较好。

最优解

参数alpha;

图6：最优解与参数alpha;之间的关系。

3.3 参数beta;

最优解与参数beta;之间的关系如图7所示。 较小的beta;是，越来越难以获得最优解，因为蚂蚁随机搜索解空间。 另一方面，较大的beta;是收敛速度越弱。 因此，当beta;在区间4,6]中时，我们的算法的性能相对较好。

最优解

图7：最优解与参数beta;之间的关系。

3.4 参数Q

最优解与参数Q之间的关系如图8所示。 当Qgt;500，我们的算法的全局搜索能力变弱。 因此，实验表明Q应在[300,500]的间隔内设置。

最优解

图8：最优解与参数Q之间的关系

3.5 其他参数

对于其他参数，我们发现g在间隔[3,5]中是一个很好的设置。 此外，当候选列表大小等于n / 4时，我们的算法的性能相对较好，其中n是客户的数量。

1. HACO应用于VRPTW

为了验证HACO处理组合优化问题的有效性，应用于本节中的VRPTW。

4.1 VRPTW模型

4.1.1 问题定义

20世纪60年代初，车辆路径问题（VRP）已经成为组合优化领域的一个重要问题，并在过去40年中得到广泛的研究。 由于VRP已经被证明是一个强NP问题，所以在合理的时间内无法解决最优解（实际上，没有确切的算法可以一致地解决50-75位客户的问题）。

在本文中，HACO应用于VRPTW，它是VRP的延伸，具有客户最早和最新的服务时间。 目的是找到最低成本的路线，其中

●对于每个车辆路线，总需求不超过车辆的能力，

●所有车辆路线在车厂开始和结束

●每位客户只有一辆车完全访问一次

●所有客户都访问过，

●车辆到达每个客户的时间应在必要的时间内。

X_ijk=

0，否则

1，如果vi由车辆k服务

1，如果车辆k从客户vi到vj

Y_ik=

0，否则

4.1.2 VRPTW模型

数学模型如下构建：

(2)

取决于：

(3)

(4)

(5)

(6)

(7)

(8)

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[139409]，资料为PDF文档或Word文档，PDF文档可免费转换为Word