英语原文共 6 页
带约束条件的选址-路径问题的粒子群算法研究
摘要：本文提出了一种粒子群算法来解决约束选址-路径问题（CLRP）。 提出了一种新的算法来解决CLRP。 在改进过程中，几种局部搜索算法可以优化解决方案。在一些实例上进行实际测试。 结果表明，我们的算法是简单有效的。
关键词：选址-路径问题，粒子群优化，启发式算法
1.引言
近年来，物流在我国经济中发挥着重要作用。许多研究人员一直致力于优化物流问题。选址-路径问题（LRP）是引起很多关注的问题之一。它可以被视为两个子问题的组合：设施位置问题（FLP）和车辆路径问题（VRP）。关于FLP和VRP的综述可以在Melo等人的文章中找到。Braekers（2009）等。和Eksioglu（2015）等。根据LRP的特性，它可以分别作为选址问题和路径问题来解决。然而，根据Watson-Gandy和Dohrn（1973）以及Salhi和Rand（1989）的研究，它通常会导致局部优化。由于这两个子问题相互依赖，因此同时考虑它们是解决这个问题的关键部分。在过去几年中已经研究了LRP的许多变体，并且可以在Prodhon和Prins（2014）的最新综述中找到整体描述。在我们的论文中，我们主要关注约束选址-路径问题（CLRP）。通过在仓库和车辆上增加容量约束，它是LRP的最基本的变体。
本文研究的CLRP可以在完整的无向图G =（N，E）上定义。 N是一组顶点，其包括m个可能的仓库的子集I和n个客户的子集J，而N =Icup;J。每个客户jisin;J有需求dj，通过车来运送货物。 每个仓库iisin;I具有最大容量Di. 当车辆沿着边缘（i，j）isin;E从节点i行进到节点j时，可获得行驶成本Cij。 使用同一辆车，并且每辆车的最大容量是Q.固定成本fi和F分别与使用新仓库i和使用新车辆相关。
必须遵守以下约束条件：
（1）每个客户只能由一辆车运送，并且只能被运送一次。
（2）每条路线总需求量不得超过每辆车的最大容量， 而且起始和结束必须在同一个仓库。
（3）每个仓库总需求量不得超过其最大容量。
目标是决定的仓库和决定的路线总成本最小化。
在本文中，我们提出了一种基于PSO（粒子群优化）的算法来解决这个问题。 PSO是一种基于仿生的智能算法，它可以很好地解决许多优化问题。 它已应用于许多领域（见Poli（2008））：遥感，生物医学，通信网络，聚类和分类，组合优化，设计等。
本文的剩余部分安排如下： 第2节简要回顾了文献。 第3节介绍PSO以及如何将其应用于我们的问题。第4节为实例计算。最后，第5节结论与展望。
2.文献综述
在过去的五十年中，这个领域已经发表过许多文章。 这些方法可以分为两类：函数方法和启发式方法。 由于CLRP是NP-hard问题，因此找到最优解的时间会随着实例的大小呈指数增长。 出于这个原因，已经提出了许多启发式方法，试图在合理的时间内给出近似解。
该领域的两项主要研究有：Nagy和Salhi（2007年）以及Prodhon和Prins（2014年）。 在Nagy和Salhi（2007）中，研究了2007年之前发表的文章，并通过选址-路径问题的四个关键方面进行了分类：层次结构，输入数据类型，计划周期，解决方法。 Prodhon和Prins（2014）可以被视为一种补充研究，并且提出了几个新的扩展方向，例如分析多级配送，多目标或者模糊数据。 这两种研究都集中在函数和启发式方法上，但我们的论文主要关注启发式方法。
普林斯（2006）等人提出了一种由两个阶段组成的算法：GRASP阶段和重新选择路径阶段。 在GRASP阶段，多样化模式被用作保证仓库选择多样性的一种方式，而集约化模式提供了基于从多元化建立的仓库的路线建设的加强搜索。 重新选择路径阶段被提议作为GRASP的后优化。 结果表明GRASP可以提高实例2/3的性能。 对于某些小型实例，它可以达到最佳解决方案。 该方法由Duhamel（2010）等人开发，可以被视为Prins（2006）等人的进一步改进。
普林斯（2006）等人提出了一种仿生的遗传算法。 对于每个后一代，以给定的概率执行局部搜索。 作者还使用新的距离测量方法来筛选后一代，以保持整体的多样性。
普林斯（2007）等人 详细阐述了一个包含两个阶段的元启发式方法。 第一阶段通过将指定的客户聚合为超级客户来处理设施位置。 第二阶段通过Granular Tabu搜索解决MDVRP（多站点车辆路径问题）。这两个阶段之间交换信息， 通过在每次迭代期间保存最有希望的边缘来避免过早合流。
除了普林斯等人的作品外，许多研究人员还开发了一些有趣的方法。 巴雷托（2007）等人提出了一种基于聚类分析的顺序启发式算法，并在不同的分组技术和接近度测度之间进行比较。 Marinakis和Marinaki（2008）描述了双层遗传算法。 文森特（2010）等人提出了一种模拟退火启发式算法来解决这个问题。 Ting和Chen（2013）通过使用蚁群优化来解决这个问题。 Escobar（2013）等人提出了一种两相混合启发式算法。 同一作者Escobar（2014）等通过使用粒度变量禁忌邻域搜索成功解决了同样的问题。 以牺牲效率为代价，Contardo（2014）等人获得高质量的解决方案。 为了在计算时间和解决方案质量之间取得平衡，Lopes（2016）等人提出了一种非常简单的遗传算法。
由于PSO是本文中一个突出的方法，因此我们也对在文献中使用PSO进行了回顾。 根据我们发现的文章，我们的主题只有四个。 其中，只有两篇文章解决了严格定义为CLRP的问题。
Marinakis和Marinaki（2008）混合PSO，多阶段邻域搜索 - 贪婪随机自适应搜索程序（MPNS-GRASP），扩展邻域搜索（ENS）和重新选择路径（PR）策略。 MPNS-GRASP用于生成初始粒子群，ENS用于提高求解质量。
Marinakis（2015）将PSO应用于具有随机性的LRP
要求和Bashiri和Fallahzade（2012）使用PSO解决随机供应链网络中的模型。
Liu和Kachitvichyanukul（2015）提出了一种将解决方案编码到每个粒子中的新方法。 在他们的文章中，他们通过使用名为GLNPSO的PSO变体来解决CLRP。 它是一种混合不同社会结构的粒子群优化算法。 对于对GLNPSO感兴趣的读者，请参阅Pongchairerks和Kachitvichyanukul（2005）以获取更多信息。 我们的方法受到这种编码方案的启发。 我们不是根据距离逐个将客户分配到每个仓库，而是首先分配位于仓库附近的客户。
在下文中，我们基于这种适应的编码方案详细描述了我们提出的整个算法。
3.选址-路径问题的粒子群算法研究
3.1粒子群优化算法（PSO）
PSO，由Eberhar（1995）和詹姆斯和拉塞尔（1995）等人提出，是一种基于人工智能并受鸟类行为启发的算法。 在解空间中，每个粒子（或个体）代表特定问题的一个解决方案。 后一代通过交换解决方案全部信息以及每个粒子所发现的最佳个体解决方案而得到优化。
定义如下： V =（vi1，...，vin）和X =（x1i，...，xni）分别表示粒子i的速度矢量和位置矢量，n是解空间的维数。 在每次迭代期间，每个粒子根据如下定义的更新规则调整其在解空间中的速度和位置：
t表示迭代的索引。 pbesti是粒子i发现的最佳解决方案。 相反，gbest是人口发现的最佳解决方案。 c1和c2表示加权系数，r1和r2是范围为[0,1]的随机数。
PSO可以使用许多变体。 为了平衡PSO的探索和开发能力，Shi和Eberhart（1998）引入了惯性权重w。 当它增加时，探索能力很强。 另一方面，随着它的减少，开发能力很强。 基于这一理论，Shi和Eberhart（1999）认为逐渐降低惯性权重值w会更好。 Clerc（1999）引入了压缩因子来简化更新规则中存在的系数。 门德斯（2004）等人提出了一个考虑每个粒子提供的所有信息的想法。
对于经典标准PSO，主要有三个版本：SPSO2006，SPSO2007，SPSO2011。 这三个版本的描述可以在Clerc（2012）中找到。 我们的方法基于SPSO2011，这是这种方法的最新发展。 使用惯性权重w的修改版本如下：
在SPSO2011中，在迭代t为每个粒子i定义超球面Hi（t）。 根据等式（5）计算该超球体的中心，并且半径等于Gi（t）-xi（t）。 xi（t）是一个随机点在超球面Hi（t）。 lbesti是粒子i的最佳邻域。 邻域的定义在Clerc（2007）中提出，我们选择第二种方法来实现随机拓扑（邻域）。 在该版本中，惯性权重w的值是固定的。
3.2 在CLRP中应用PSO的主要步骤
对于决策者来说，一个可行的CLRP解决方案应该很容易理解。 但是，当我们应用元启发式来解决相关问题时，我们还需要让算法了解如何处理解决方案。 这就是说，我们需要提出一种编码和解码策略：1）对可行解决方案进行编码，使元启发式处理变得容易。 2）从元启发式解码结果，使决策者易于理解。 我们将在3.3节讨论这个策略。
在PSO中，每个粒子代表一个解决方案，并且它们是在初始化过程中随机生成的。 这是使用PSO的优势之一，因为我们不需要刻意构建解决方案。 初始化后，我们解码这些粒子并评估它们的适应值。 然后pbesti和lbesti更新。 通过使用等式（3），（4）和（5），顺序地产生新的速度vi和位置xi。 在PSO中，新的位置xi可以被视为一种新的解决方案，这是PSO在解决方案空间中生成不同组合的方式。 当完成给定数量（FE）的粒子适应度评估时，停止算法。 主要程序如图1所示。
3.3 编码和解码
使用PSO解决CLRP的主要不同之处在于如何表示解决方案。 为了清楚地解释我们的方法，我们以实例coord20-5-1为例（请参阅“http://prodhonc.free.fr/”以获取更多详细信息）作为示例。 在这种情况下，有5个潜在的仓库和20个客户，其中涉及粒子维数为25。每个车辆和仓库的最大容量分别为70和140。 图2中提供了每个客户的需求。一种解决方案：
粒子如图3所示。第一部分是从1到5的储库部分，其值在[0,1]范围内。 通过按升序对储存库部分的值进行排序，生成储库的优先级列表，如图4所示。
第二部分是尺寸6到25的客户部分，其值的范围为[0,1]。 客户优先级列表（如图5所示）也可以通过执行与我们对仓库部分相同的操作来生成。
从图2中，客户的总需求量为315.由于每个仓库的容量为140，因此仓库优先级列表中的前三个仓库（2,5,3）可以满足这些需求。 然后他们将被选为所选的仓库。 为了清楚地解释我们的算法，我们根据坐标在地图上定位所有的仓库和客户来制作草图（见图6）。 对于每个库，绘制半径为r的圆。半径r等于距离的一半，该距离是两个选定的仓库之间的最短欧几里德距离。 斑点和十字架分别代表客户和仓库。 圈内的客户被分配到相关的仓库。 绘制圆圈的方式是第4节中的“聚类操作”。
在该分配之后，每个所选仓库的可用剩余容量在图7中描述，未分配的客户在图8中列出。
处理未分配的客户，我们使用流程图（图9）来描述此过程。在流程图中，P L（c）是根据客户c的距离按升序对客户进行排序的功能。我们的算法的主要思想是我们尝试形成一个“链”，其头部是未分配的客户，其尾部是指定的客户。我们尝试将“链条”中的客户分配到位于链条尾部的客户仓库。根据分配程序，我们从未分配的客户集U中随机选择客户2。由于最近的客户2尚未分配17，我们将其添加到列表A的尾部。同样，客户9也被添加到列表A中。以下要考虑的客户是20（最近的一个来自9），已经分配到仓库2。但是由于没有足够的剩余容量，因此正在考虑中的客户10不能使用此库。客户10的仓库客户9可用，因此我们将客户9分配给它。回到列表A中的客户，我们将它们分配给客户9的仓库。对于仓库2，分配的客户是[20 13 5 7 3 18 4 1 12]。仓库5 = [10,16,15,14,9,17,2]，仓库3 = [6,8,11,19]。
还应用聚类方法来选择路线。 通过按照图5中描述的优先级列表顺序对这些客户进行分类，它变为[4 5 1 20 7 13 3 12 18]。 选择客户4并将其插入新列表B。我们按升序排序（按距离4的顺序）分配给同一仓库的客户2。这些客户按此顺序插入列表B中，而未超过车辆容量。 在这种情况下，生成第一列表B1，其中列表B1 = [4 18 1 12]。 对于剩余的未分配客户，选择客户5并将其插入新列表B2中。 然后列出B2 = [5 13 3 20 7]。 然后从列表B1和B2中，使用名为最小附加成本的机制来优化路径。 仓库2的整个路径是[D2-4-1-12-18-D2; D2-3-7-5-13-20-D2]。
3.4 局部搜索
为了提高解决方案的质量，我们采取了Contardo（2014）等人的观点作为参考并选择该条中提出的几个程序：仓库互换，Giant tour split，2-OPT，2-OPT *。 我们还添加了另一个名为启发式扫描算法的局部搜索程序，由Gillett和Miller（1974）提出，用于最小化路径成本。 我们将启发式扫描算法和G
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
