英语原文共 15 页，支付完成后下载完整资料

通过人工蜂群算法解决软时间窗多目标车辆路径问题

关键词：算法分析、启发式人工蜂群算法、组合优化、实验结果、遗传与局部搜索、基于软时间窗的车辆路径规划。

摘要：

本文提出了一种使用混合启发式技术解决基于软时间窗的多目标车辆调度问题（VRPSTW）的新模型和解决方案。该算法是基于人工蜂群算法和基于领域的两步约束局部搜索上发展而来的。VRPSTW意味着计算一组具有固定容量的车辆从中央仓库到一组具有已知需求和预定时间窗口的从地理上分散的客户的路线。这里，时间窗口约束被放宽为“软约束”，即每当车辆在其时间窗口之外为客户服务时，其惩罚成本被添加到解决方案成本中。基于软时间窗的路径规划问题的解决方案具有有价值的实际应用。本文采用VRPSTW的直接解释作为多目标优化问题，即：在满足容量和时间窗口约束的情况下使总行驶距离，窗口违规次数和所需车辆数量最小化。我们的工作旨在在人工蜂群的觅食行为的启发下，平衡探索和利用，来避免局部最优并达到整体最佳。该算法被用于解决知名难题：所罗门的问题作为基准的实例。实验结果表明我们提出的方法非常有效，因为它提供了与文献中最著名解法具有竞争力的解决方案。最后，我们提供了所提出算法基于计算运行时间的分析。

第1章 绪论

由Dantzig和Ramser [1]首先引入的车辆路径问题（VRP）是一种组合优化问题，旨在通过一系列车辆为许多客户提供服务。每辆车都有一定的容量，每个客户都有一定的需求。具有时间窗的车辆路径问题（VRPTW）是VRP [44]的变体之一，其在计算机科学和运输工程文献中已被广泛研究。在此变体中，每个客户都必须在特定的时间窗口内提供服务。具有硬时间窗的车辆路径问题（VRPHTW）是VRPTW的一种已被充分研究的变体，其中客户的时间窗口绝不能违背[45]。VRPTW的另一种变体，具有软时间窗的车辆路径问题（VRPSTW），是VRPHTW问题条件的放宽，其中可以通过支付惩罚来违反时间窗口（正式定义参见3.1节）。

VRPTW及其变体是运输，配送和物流领域的重要问题。具体而言，VRPSTW似乎在应用上更具有实践上的吸引力，因为它们不需要硬时间窗口并且在实际中也不能准确地知道行进时间。正如[14]中所论述的那样，宽松的时间窗口可以降低总成本而不会影响客户满意度。可以将大量非紧急服务交付建模为具有时间窗口，其中具有软时间窗口将更好地服务于客户而不是由于硬时间窗口被破坏而丢弃可能的解决方案（例如，信件递送，报纸递送和包裹递送）。此外，VRPSTW是一种更通用的变体，因为它的解决方案可以通过适当应用惩罚来扩展以解决VRPTW的一些其他变体。此外，当硬时间窗口的问题不可行时，VRPSTW解决方案提供了可行的行动计划。其增强的实际可见性有助于针对其解决方案的更广泛和更深入的研究的同步发展。

在本文中，我们提出了一种算法，该算法受到基本人工蜂群（ABC）元启发式算法中蜜蜂行为的启发，并将其与邻域搜索空间中的多步骤开发相结合，以增强局部搜索。我们的工作的动力是由多方面驱动的。首先，ABC算法是一种新的基于群的元启发式方法，可用于解决硬组合优化问题，该方法在合理的时间限制内为文献中的许多问题提供了良好的解决方案（例如，叶约束最小生成树问题[18]，广义分配问题[19]，核心燃料管理优化问题[20]，旅行销售员问题[21]和数独难题[22]）。尤其对于对于像VRPSTW这样的问题，首先该问题不需要实时结果。其次，在文献中，大多数解决VRPSTW的尝试都利用了启发式方法，其中通常存在根据特定启发式排除被认为无趣的搜索空间的特定区域的可能性。一般而言，元启发式由于其随机性质，并不排除这种可能性。第三，元启发式是一种通用的算法框架，用于寻找优化问题的解决方案，在这种解决方案中，本地启发式方法被引导和调整以有效地探索解决方案空间。VRPSTW是离散优化问题（DOP），并且元启发式是用于生成DOP解决方案的流行算法方法。最后，不同的元启发式已经应用于其他VRP变体并提供了良好的结果[2-7]。所有这些因素都激励我们采用ABC启发的方法首次解决VRPSTW问题。

本文的主要贡献如下。在这里，我们提出了一种基于人工蜂群（ABC）元启发式算法来解决VRPTSW问题。我们将人工蜂群元启发式与邻域搜索空间中的多步探索以及随机全局探索混合。这种杂交导致快速收敛到局部或全局最优。通过这种新算法，我们努力将总行驶距离（成本）与罚款，违规次数和路线数量（车辆）最小化。此外，我们从理论上和实验上分析了算法的性能。特别是，我们使用公开可用的基准数据集进行了大量实验，以比较我们的算法与现有算法的性能。正如后面将要报道的，我们的方法为VRPSTW生成快速和高质量的解决方案。

本文的其余部分安排如下。第2节回顾了有关VRPSTW的相关文献。第3节介绍了描述VRPSTW的符号以及ABC的基础知识，第4节描述了我们解决VRPSTW的方法。详细的实验结果和与文献中现有技术的比较分别在第5节和第6节中给出。最后，我们在第7节中总结了我们模型处理VRPTW其他变体的灵活性的简短讨论。

第2章文献综述

关于解决VRP，VRPTW和VRPSTW的文献已经有很多。这些解决方案包括精确方法，近似算法，启发式方法和元启发式方法。我们主要回顾启发式和元启发式方法，并简要回顾使用人工蜂群算法解决不同的其他问题。

三种简单的启发式算法[8]已经被提出过，即使用线性惩罚函数求解VRPSTW的最近邻，节省法和时空启发式算法，它们在所罗门基准数据集的子集表现了有效的性能。VRPSTW问题被启发式分解为赋值/聚类组件[9]，并使用随机生成的数据集以及所罗门的问题实例进行测试。最近邻域算法已被用于获得VRPSTW的良好解决方案[10]，其中最近邻域算法与问题生成器耦合，该问题生成器提供由于时间窗违规水平的操纵和允许这样的客户群而导致的大量实例。使用了一种目标规划方法[11]，该方法仅对中型（少于70个客户）交付问题有效，具有异构的车辆和多个目标。最近，格里奥兹[14]提出了一种新的迭代路径构造和改进算法来解决VRPHTW和VRPSTW问题。这种方法也在所罗门所有小型，中型和大型（25,50和100个客户）尺寸的问题实例上进行了测试。蒋和罗素[13]利用禁忌搜索方法，混合邻域结构和提前恢复，为所罗门的VRPSTW实例找到一些好的解决方案。其他的也有使用元启发式解决VRPSTW的其他尝试包括禁忌搜索[17]和具有统一罚函数的单一禁忌搜索[12]。

最近在不同的硬组合问题上应用ABC元启发式算法得到了很好的解决方案（例如，叶片约束最小生成树问题[18]，广义分配问题[19]，核心燃料管理优化问题[20]，旅行销售员问题[21]和数独问题 [22]）。增强的基于Pareto的人工蜂群（EPABC）算法[23]可用来解决多目标的作业车间软调度问题。在[24]中提出了离散人工蜂群（DABC）算法，迭代贪婪（IG）和迭代局部搜索（ILS）来解决流动调度问题，两位刘姓学者 [25]提出了一种混合离散人工蜂群（HDABC） 使用基于Nawaz Enscore Ham（NEH）启发式的随机自适应搜索程序（GRASP）来解决置换流车间调度问题的算法。混沌搜索ABC（CABC）算法用于[26]模拟PID（比例 - 积分衍生）控制参数调整和离散人工蜂群（DABC）算法在[27]中被提出，以解决批量流媒体流量车间调度问题。ABC算法用于解决多目标灵活作业车间调度问题[28]，随机资源约束项目调度问题（RCPSP）[29]以及发现交通信号的最优设置[15]。最近，ABC算法用于解决具有时间窗（VRPTW）的经典车辆路径问题，其中时间窗约束很难被保持[46]。在这项工作中，ABC算法以矢量评估方法实现，以开发VRPTW的多目标解决方案模型。

最后，杂交ABC算法与田口方法在[43]结构设计优化中的应用。最后，我们注意到其他基于群的元启发式技术也已用于文献中以解决各种科学和工程领域中的各种离散优化问题。虽然我们没有对这些问题进行详尽的审查，但最近的一些值得注意的工作包括粒子群优化算法及其在设计和制造领域的混合[40]，汽车工业的结构设计[41]以及车辆耐撞性设计[41]。

第3章问题定义和人工蜂群基础

本节介绍了理解本文所涉及主题所需的思路。首先，我们正式定义VRPSTW，然后简要介绍基本的人工蜂群元启发式。

3.1软时间窗车辆路径问题（VRPSTW）

软时间窗车辆路径问题可以被模型化为一个矢量图：。这里，是一系列有n 1个向量，其中代表客户，v0代表起始和结束仓库。同时，,,,是一组边，表示仓库与客户之间以及客户之间的连接。明显地，,其中是一系列的客户。我们使用T来表示车辆组。现在，我们定义以下变量：

• 表示每辆车辆，。
• 对于每一辆，都会分配一条路线，。
• 每一辆车都有一个固定的容量和相同的速度。所以，车队是同质的。
• 花费与路线的两端决定的路线有关，用表示。
• 时间点是对客户开始服务的时间。
• 对于每一个客户都有一个固定的需求.
• ，，是与客户相联系的时间窗，是与车站相联系的时间窗。

，，，，，，是非负整数。问题场景的概述如图3.1所示。

图1 一个典型地问题场景

被允许的最大超出惩罚时间长度。因此，对于一个客户，他的宽松时间窗为。提前到达的惩罚为，滞后到达的惩罚为，如果各自车辆到达时间提前或者滞后，惩罚将会被加到服务花费。这里和都是系数，。VRPSTW的“窗口中断”发生在客户未在非宽松时间窗口内被提供服务时。特别地，如果客户在或中被提供服务，那么我们就会有“窗口中断”，并且会在成本中加上适当的惩罚。我们的目标是计算一组路线，以总成本最小化和满足以下约束的窗户约束条件：（i）每个客户只提供一次服务；（ii）每条路线的起始于v0，i，。e：，终止于仓库；（iii）遵守客户的（放松）时间窗口以及车辆的容量限制；（iv）所有车辆必须在车辆段的时间窗口内启动并返回仓库。

3.2 人工蜂群算法基础

人工蜂群算法是由[30]提出的基于种群的元启发式算法，它模拟蜜蜂的智能觅食行为，以解决多维和多模态优化问题。在基本的人工蜂群算法中，每种食物来源代表了所考虑问题的可能解决方案，食物来源的花蜜量（合适度）代表了解决方案的质量。有三种类型的蜜蜂：工作者，旁观者和侦查者 该算法假设每种食物来源只有一只在工作的蜜蜂，即：食物来源的数量与使用的蜜蜂数量相同。被遗弃的食物来源的蜜蜂变成了一个侦察兵，一旦它找到一个新的食物来源，它就会再次被雇用。ABC算法是一种迭代算法。算法的每个循环包括三个步骤：

（1）工作者和旁观者蜜蜂选择食物来源。

（2）计算食物来源的健康度。

（3）确定侦察蜂并将其引导到可能的食物来源。

（4）记录最佳解决方案

最初所有的蜜蜂都是侦察兵。在与随机产生的食物来源（解决方案）相关联后，它们成为受雇的蜜蜂。在每次迭代期间，每个被雇用的蜜蜂根据花蜜量（合适度）确定其当前食物源附近的最佳食物来源，并且如果其花蜜量更好则移动到该解决方案。然后，所采用的蜜蜂将这种花蜜信息（解决方案的质量）共享给旁观者，并且他们执行基于概率的食物来源选择，因此食物来源（解决方案）的倾向随着其花蜜量（总质量）增加而增加。选择食物来源i的概率pi是：

其中()是食物来源代表地解决方案的合适度，是食物来源的总数。

如果解决方案耗尽并且在预定次数的迭代中没有改善，那么它被其相关的工作者蜜蜂放弃并且它变成了侦察者。然后，它随机探索新的食物来源，变成工作者并利用邻域搜索空间以获得更好的解决方案。重复整个过程直到满足终止条件。在这里，旁观者和工作者在搜索空间中进行开发过程。侦察员控制着探索过程。因此，总有一种方法可以将开发（通常是本地）和探索（通常是全球）方法混合在一起，以搜索更高质量的解决方案。

第4章 用于VRPSTW的ABC启发算法（Bee_VRPSTW）

在本节中，我们介绍Bee_VRPSTW算法，该算法受到[30]提出的蜜蜂智能觅食行为的启发，后来由[31]改进了数值优化问题。为了解决像VRPSTW这样的离散优化问题，我们将使用和旁观者蜜蜂进行的开发扩展到邻居候选者选择分为两个步骤。我们进行了随机交换，随后进行随机排列，以便在由当前信息引导的约束局部搜索空间内生成更高质量的邻域解。第5节和第6节显示，根据经典ABC算法，所提出的开发方法与蜜蜂进行的探索的整合导致快速收敛以及改进的解决方案。

表1：实验计划的参数

4.1 解决方案展示

我们问题的每个解决方案都可以看作是（车辆的）路径的集合，其中每个路线由整数值的矢量表示。回想一下，对于每辆车将有一条路线。如果车辆为客户服务按照的路线，那么代表路线的矢量为。

4.1.1 生成初始解决方案（食物来源）

按照以下步骤初始化单个解决方案：

• 对于每个车辆，随机客户从可用客户池中移除并分配给而不违反容量约束。
• 首先，为每辆车分配位客户，然后终止该车辆的分配过程。

如果仍有一些未分配的客户，则会将其分配给车辆而不违反其容量限制。

• 如果在所有步骤之后仍有未分配的客户，则丢弃该解决方案并从头开始初始化过程。

为了确保多样性，确保每个初始解决方案都是独一无二的

4.1.2 确定邻里解决方案（食物来源）

在被分配到随机初始解决方案（食物来源）之后，每个被雇用的蜜蜂探索当前分配的解决方案的邻域区域以获得良好的邻域解决方案。期望利用当前解决方案的信息来指导该本地搜索。因此，对当前的解决方案执行以下两个步骤，以产生高质量和多样化的邻域解决方案。这里，第一步通过同时插入和删除来影响两条路径，而第二步随机重新排列路径中的客户：

1、从所有的解中随机选取两条不同的路

资料编号：[3124]