英语原文共 19 页

在时间窗约束下的车辆路径问题的多自适应粒子群优化算法

摘要：本文提出了一种新的粒子群优化（PSO）算法变体，用于解决带时间窗的车辆路径问题（VRPTW）。对于所提出的多自适应粒子群优化（MAPSO）算法，我们使用了三种不同的自适应策略。第一种自适应策略涉及使用贪婪随机自适应搜索过程（GRASP），该过程应用于生成初始解决方案时以及在算法迭代期间创建新解决方案时。第二种自适应策略涉及粒子从一种解决方案到另一种解决方案的运动中的适应性，其中使用了新的自适应策略，即自适应组合邻域拓扑。最后，粒子群优化算法的所有参数都具有适应性。该算法从参数的随机值开始，并且基于某些条件，在迭代期间调整所有参数。该算法在两个经典的基准实例集中进行了测试，其中包括56个具有100个节点的实例，另一个包含300个实例，其节点数在200到1000之间变化。该算法与其他版本的PSO进行了比较包括文献中表现最佳的算法。

关键词：粒子群优化带时间窗的车辆路径问题、组合邻域拓扑贪婪随机自适应搜索、程序适应性策略

1.简介

车辆路径问题（VRP）是组合优化、运筹学、尤其是供应链管理领域中最重要的问题之一。 不同学者根据现实生活中的问题，提出了许多VRP的变体，本文作者试图找到最合适的算法来解决他们的问题。 感兴趣的读者可以找到大量的涵盖了这些内容的论文[23,24,40,50]和书籍[16,46]。 VRP最重要的变体之一是使用时间窗口的变体。 这是一个非常重要的变体，因为在容量VRP中添加时间窗会导致更现实的问题。 而且，与容量车辆路径问题不同的VRP的其他变体往往会包含时间窗限制。

在带有时间窗的车辆路径问题（VRPTW）中，客户和可能的车辆与时间窗相关联。因此，必须在某个时间窗口内为客户提供服务，并且可允许车辆在某个时间窗口内运行。在本文中，正如大多数关于带时间窗的车辆路径问题[16,45,46]的出版物一样，该问题的目的在于为一组相同的容量车辆设计最低成本路线，这些车辆为地理位置分散的客户提供服务。在预先指定的时间窗口内，每个客户必须在指定的时间窗口内由车辆维修一次，并且车辆所服务的客户的总需求不得超过车辆的容量。如果车辆在客户的时间窗口的下限之前到达客户，则必须等待直到服务可用。该仓库也有一个时间窗口，所有车辆必须返回仓库，直到时间结束。在本文中，使用了分层目标函数，其中，最初，车辆的数量被最小化，然后，对于该数量的车辆，总行驶距离被最小化。

在本文中，提出了一种多自适​​应粒子群优化算法（MAPSO），其中使用了三种不同的自适应策略。粒子群优化算法已被证明是解决路由类型问题的一种非常有效的算法。我们的研究小组已经有效地应用粒子群优化的变种来解决容量车辆路径问题[28,30,33]，随机需求的车辆路径问题[31,32]，概率旅行商问题[ 29]和位置路由问题[27]。除了我们的小组之外，其他研究人员已经发表了一些基于PSO算法的非常有趣的VRP变体解决方案[1,9,17]。有关PSO在车辆路径问题中的应用的完整评论，请参阅[35]。所提出的算法与我们小组提出的其他算法的不同之处在于3.1节中描述的三种不同的自适应策略。为了确定这些适应策略是否有效，将所提出的算法与我们提出的其他版本的PSO进行比较，并且它们不使用适应性策略用于参数。比较在两组经典的基准实例中进行，这些实例用于测试解决VRPTW的各个算法。Solomon [45]提出的案例中包括56个实例，分为6组，节点数等于100，另一个由Gehring和Homberger [12]提出，包括300个不同大小的实例，分为5组节点数等于200,400,600,800和1000的实例，其中每个节点包含60个实例，每个不同的集合被划分为6个子集，每个子​​集10个实例。所提出的算法还与来自用于在相同的实例集中解决具有时间窗的车辆路径问题的文献中的一些最佳执行算法（其中二十个）进行比较。

引导我们扩展先前研究并提出具有这些自适应策略的PSO算法的动机是存在大量路由问题和大量解决这些问题的算法，并且所有算法都具有不同的参数（使用作者的有效方法是为他们的算法找到合适的参数）但是没有一组参数可以应用于每个路由问题。想要找出适用于所有问题的算法是几乎不可能的，但是我们提出了一种方法来为算法提供灵活性，以便在不受用户干扰的情况下为每个实例找到合适的参数集。因此，在过去提出了许多非常有效的算法来解决使用PSO的路由类型问题，并且没有用于找到最佳参数集的自适应程序，在本研究中我们希望扩展我们的研究。一种方式是提出一种新版本的PSO算法，用于解决路由类型问题，使用多种自适应策略来找到最有效的参数集，以便给出非常好的结果。我们以一种简单而有效的方式找到了一组参数，每组参数不同，但它们之间没有大的差异，我们更好地（在大多数组中），相等（在其他组中）或至少竞争中获得了计算结果（对于少数几组而言），与我们研究小组提出的其他PSO变体或者特别是用于解决带时间窗的车辆路径问题的文献中最有效的方法进行比较。

本文的其余部分安排如下：在第2节中，给出了关于自适应策略和VRPTW的简短文献综述，在第3节中给出了所提算法的分析表达，而在第4节中给出了计算通过与文献中的其他算法的分析比较，提出并分析了算法的结果。最后，在第5节中给出了结论和对于未来的展望。

2.文献综述

这个方向的研究学者们已经提出了许多用于计算PSO算法参数的自适应策略，其中大多数被表示为自适应粒子群优化算法[APSO] [49]。 有些论文致力于寻找增加或减少惯性因子的自适应方式，通过迭代找到加速系数或两者。 而且，模糊系统已被用于惯性权重的适应性。 有许多出版物使用自适应策略来改变使用不同类型的适应性的人口规模。 有关PSO适应性的分析性评论，请参阅论文[34]中的评论部分。有许多已经提出了许多算法用于解决具有时间窗的车辆路径问题与本文使用相同的公式 [2-8,12,13,17,19-22,25,26,36- 39,41,42,44,47,48]。

3. 多自适应粒子群优化算法

3.1MAPSO的三种新型自适应策略分析

在本节中，详细分析了所提出的多自适应粒子群优化算法（MAPSO）。 并且，在详细分析所提出的算法之前，我们分析了所提出的算法中包含的三种自适应策略。

最初，在算法的初始化阶段以及在算法迭代期间创建新解决方案时，基于贪婪随机自适应搜索过程（GRASP）[11]的自适应策略被用于初始解决方案的开发以及迭代期间的解决方案。 利用该策略，我们开发了许多新的解决方案，其中每个解决方案彼此不同并且确保粒子多样化以便从不同的方面对解决方案进行分析。

所使用的第二种自适应策略涉及粒子从一种解到另一种解的运动。这是算法的一个非常重要的部分，与过去一样，粒子群优化算法在路由问题以及组合优化问题中的主要难点，是连续值中解的转换，以及信息的丢失。我们的团队在[30]中提出了避免这种转变的一种方法，并将其表示为组合邻域拓扑，其中使用路径重新连接程序将粒子从一种解移动到另一种解。在PSO中添加路径重新链接程序并且显着改善了PSO算法在这类问题中的准确性，并在一些问题，如在具有随机需求的车辆路径问题[31]中，表现明显优于经典的元启发式和进化算法算法。路径重新链接[15]的使用给出了需要逐步过程从一个解转移到另一个解的算法。然而，对于VRPTW的解决方案，由于存在时间窗口，使用该过程可能导致许多不可行解。这不是一个未解决的问题，因为通过使用合适的策略再次获得路线的可行性，然而，这可能导致计算时间的增加，并且在一些解决方案中，可能导致路线数量的增加。因此，在本文中，提出了新版本的组合邻域拓扑（CNT），即自适应组合邻域拓扑（ACNT），其中CNT的条件得以维持，而不是使用路径重新链接策略，自适应存储器提出了程序。在这个过程中，主要思想是从一个解到另一个解的移动，以便使用整个流程来实现。因此，创建了两种自适应存储器，其中在第一种中使用一个数字来记录具有特定节点集（不考虑节点序列）的优化次数参与全局最佳粒子的次数。这个数字会增加（或根据某些条件而减少）优化成为新解的可能性。在第二自适应存储器中，对于每个粒子的个体最佳解决方案遵循相同的过程。添加一个记录在整体或个体最佳解决方案中呈现路线的连续迭代的数字受到禁忌搜索[14]的中期和长期记忆的启发。

最后，在第三自适应策略中，所有参数（加速系数，迭代，局部搜索迭代，速度的上限和下限以及每个群中的位置和粒子数）在过程期间被调整，因此，算法独立工作，不受用户的任何干扰。 所有参数都是随机初始化的，之后，在迭代过程中，参数采用三种不同的条件进行调整，第一种用于除粒子数量以外的所有参数，第二种用于增加粒子数量和 第三个用于减少粒子数量。

3.2紧缩粒子群算法

在PSO算法中，最初随机创建一组粒子，其中每个粒子都有可能的解，它在解空间中具有位置并且以给定的速度移动。在VRPTW中，通过巡回的路径表示（即，通过节点的特定序列）记录粒子。并且当一个经典的PSO算法应用于路由问题时，它需要从连续值到离散值的一系列变换，反之亦然，以便计算每个粒子的速度方程（见下面的方程式（ 1））。每个粒子的位置由向量x i =（x i 1，x i 2，hellip;，x id），i = 1,2，hellip;N（N是种群大小，d是向量维度的数量），并且在预定义的适应度函数上评估其性能。速度v ij表示将粒子从一个位置移动到另一个位置所做的变化。在PSO算法中，粒子可以遵循其自己的路径，或者它可以移动到迭代期间的最佳位置（pbest ij），或者它可以移动到最佳粒子的位置（gbest j）。在收缩PSO [10]中，用于速度和位置的方程式如下：

并且其中：

t是迭代计数器,c1和c2是加速系数，rand1和rand2是两个处于（0，1）之间的随机变量。

3.3自适应组合邻域拓扑

在本文提出了一种新式的组合邻域拓扑（CNT），即自适应组合邻域拓扑（ACNT），在ACNT中，使用两种存储器，一种用于全局最佳粒子（一般的全局最佳解决方案，因为最佳粒子可能在迭代期间改变并且被表示为全局最优解（GBM））而另一种用于每个粒子分开（它表示为个人最优解（PBM））。具有相同节点集但具有不同节点序列的两条路由被记录为存储器中的一个解决方案，并且保持的序列是具有不违反约束的更好成本的路径。在每次迭代中，GBM和PBM中的路由有两种可能。一种可能是，已经属于GBM（或PBM）的路径出现在全局最佳粒子（或个人最佳粒子）上，因此，显示路径的时间（迭代）的数量（ GBMval l和PBMval l其中l是GBM和PBM中不同路由的数量，分别是GBM（或在PBM中）增加1。另一种可能性是出现在全球最佳粒子（或个人最佳粒子）上的新路线，因此，它必须在GBM（或PBM）中添加GBM中路线的计数器（或者在PBM中，l，增加1和GBMval l（或PBMval l取决于具体情况）取初始值等于1。

通常，粒子可以遵循其自己的路径，或者朝向其先前的最佳解决方案，或者朝向全局最佳解决方案（针对群中的最佳粒子）。 这是通过路径重新连接策略在CNT中实现的。 在ACNT中，选择来自两种自适应存储器GBM或PBM的多个路由。 如果粒子朝向全局最佳解决方案，则从GBM中选择路线;如果粒子朝向个人最佳解决方案，则从PBM中选择路线。 此过程的下一步是粒子如何决定遵循整个群体的先前最佳或全局最佳。 在算法的这个阶段，我们保持与CNT相同的程序，并进行适当的调整[30,31]。 首先，我们计算出每个粒子的速度方程的平均值：

此外， L 1和L 2的值由以下等式计算：

其中t是当前迭代，iter max是最大迭代次数，u bound和l bound是每个粒子的速度的上限和下限。 参数w 1和w 2控制值L 1和L 2的范围。 如果在某些迭代中粒子的速度违反了这些边界，那么，速度将在边界内用新值初始化。 参数w 1和w 2应该具有大的值，因为期望L 1的值在算法的开始时尽可能大并且在迭代期间减小。 此外，L 2的值应该大于L 1的值，因此，w 2的值应该大于w 1的值。

平均v值有以下三种情况：

1.平均值v lt;L 1：两个存储器中没有任何选择，这意味着粒子遵循其自己的路径。

2. L1le;平均值vle;L2：粒子选择来自PBM的路线。

3. L 2 lt;平均值v：粒子选择来自GBM的路线。

在算法的开始，L 1和L 2具有较大的值。 这些值在迭代期间减小，这是因为在这种情况下，增加了从两个存储器中选择路径的可能，另一方面，减少了使用本地搜索通过其自身搜索解空间的可能。

因此，根据先前对L 1和L 2的选择，从存储器中选择多条路线，并从粒子中选择多条路线。从存储器中选择的路线的百分比取决于速度的平均值（平均值v）。如果在粒子选择朝向其个人最佳解决方案的情况下，该值接近L 1，那么，大多数路线是从PBM存储器中选择的，如果它接近L 2，那么，大多数从当前解决方案中选择路线（因为它认为L1le;平均值v lt;L 2）。另一方面，在粒子选择朝向其全局最佳解决方案的情况下，如果该值接近L 2，那么，大多数路线是从GBM存储器中选择的，并且如果它远离L 2，大多数路线都是从当前的解决方案中选择的。选择路由的方式是两个节点不能属于两个不同的路由。与此过程一样，有可能在某些路径中不分配某些节点，基于3.4节中描述的过程使用贪婪程序，以便从这些节点生成新路由。

3.4 初始解决方案的描述

通常在PSO算法中，初始解是随机产生的。但是，这可能会导致非常糟糕

资料编号：[4378]