容量约束选址-路径问题的简单启发式算法

欧洲计算优化杂志11（2023）100063一种概念简单的容量约束选址-路径问题Maximilian Lözier，Enrico Bartolini，MichaelSchneider德国亚琛工业大学德国邮政讲座ARTIcLE IN fO ABSTRA cT保留字：位置路由位置路由简单启发式仓库配置优化定位-路径问题（LRP）联合优化站点的定位和车辆的路径。研究最多的LRP变体，容量限制LRP（CLRP），已经通过大量的元启发式方法来解决。这些方法通常将问题分解为定位阶段和路径选择阶段，定位阶段用于确定有希望的停车场配置，路径选择阶段用于解决车辆路径选择问题以评估先前确定的停车场配置的质量不幸的是，CLRP文献并没有阐明哪些算法功能对解决方案质量和运行时间的影响最大的重要问题本文的目的是提出一个概念上简单（但合理有效）的启发式CLRP，并提供了一些见解设计成功的元算法这个问题。我们的算法是一个混合组合（i）GRASP阶段，使用可变的邻域下降的局部改进的位置阶段，(ii)路由阶段的可变邻域搜索我们分析算法组件对解决方案质量和运行时间的影响。此外，我们发现，用于评估所调查的仓库配置质量的次优路由解决方案倾向于导致仓库配置有太多开放仓库。我们提出了一个仓库配置优化阶段，以弥补这一缺点，我们表明，* 通讯作者。电子邮件地址：E-mail：E-mail@dpo.rwth-aachen.de（M.Löchier），bartolini@dpo.rwth-aachen.de（E.Bartolini），schneider@dpo.rwth-aachen.de（M.Schneider）。https://doi.org/10.1016/j.ejco.2023.1000632192-4406/© 2023作者。由Elsevier Ltd代表欧洲运筹学协会（EURO）出版。这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表欧洲计算优化杂志期刊主页：www.elsevier.com/locate/ejco2M. Lözier等人/EURO Journal on Computational Optimization 11（2023）100063该算法组件显著有助于我们方法的解决方案质量，使其能够与文献中的最先进方法相比提供版权所有2023作者。由Elsevier Ltd代表欧洲运筹学协会（EURO）出版。这是CCBY-NC-ND许可证（http：creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍在选址-路径问题（LRP）中，车辆的路径决策与站点的选址决策是联合进行的。相互独立地做出这些类型的决策可能会导致次优结果（见[28]）。LRP已经研究了几十年，研究界一直非常活跃，特别是在过去几年。这可以通过对最近在很短时间内发表的LRP文献的大量调查来证明（见[16，9，27，8，1，29，18]）。对于早期的LRP调查，我们建议读者参阅Min等人。[19][21][22][23][24][25][26][27获能型LRP（CLRP）是研究最多的LRP变体。给定一组潜在容量受限的车辆段位置和一组具有已知需求的客户，CLRP的目标是以最小化总成本（包括车辆段和车辆的固定成本以及可变路线成本）的方式确定要开放的车辆段以及从开放的车辆段CLRP假设每个车辆段的容量限制车辆数量不受限制，且车辆段容量限制分配给每个车辆段的路线上的总需求。详细的混合整数规划公式见附录A.CLRP是NP难的，因为它包含了仓库选址问题和有能力限制的车辆路径问题（VRP）。由于其计算的复杂性和实际意义，大量的研究社区已经致力于开发高质量的启发式方法。许多建议的算法将问题分解为一个位置分配阶段，在该阶段中，要开放的设施和客户对设施的分配被确定，以及一个路由阶段，在该阶段中，VRP被解决为每个开放的设施。在路由选择阶段通常也允许分配决策（导致多站点VRP，MDVRP），在许多情况下，在反馈回路中迭代地求解这两个阶段。用于CLRP的最有效的启发式方法使用各种范例：大邻域搜索[14]、模拟退火（SA，参见[33]）、蚁群优化[31]、模因算法[17]、可变邻域搜索（VNS，参见[23，13，12]）、贪婪随机自适应搜索程序（GRASP，参见[10，6]）和集成整数线性规划技术的数学方法[26，23，11，6]。对于个人作品的摘要，我们建议读者参考洛佩斯等人的调查[16]，Prodhon和Prins [27]，Schneider和Drexl [29]。M. Lözier等人/EURO Journal on Computational Optimization 11（2023）1000633在文献中已经注意到，解决方案的质量强烈地依赖于开放的设施（参见，例如，[25]）。因此，许多成功的物流公司采用多样化和集约化技术，深入研究潜在的仓库配置空间在这种情况下，GRASP是一种经常使用的方法（参见，例如，[25、10、22、6]）。除此之外，CLRP文献并没有阐明为什么某个启发式算法比其他具有可比复杂程度的方法表现得更好，或者提出的启发式算法的哪些组件对解决方案质量和运行时间具有最大的在本文中，我们开发了一个元启发式混合相结合的GRASP的位置阶段与VNS的路由阶段，称为GRASP/VNS，以解决CLRP。GRASP阶段使用可变邻域下降（VND）来改进由随机构造启发式算法给出的路由解决方案，而不是贪婪的局部搜索相同的VND组件也用作VNS内的本地搜索本文件的目的是：• 提出了一个概念上简单的启发式CLRP，实现了合理的性能的基准集从文献。近年来，研究界一直提倡开发更简单的因此，GRASP/VNS的设计保持简单，并且几个已知的算法组件以新的和成功的方式组合这种设计还能够灵活适应其他LRP变体，如第2.4节所述。• 提供一些见解，哪些组件使（GRASP为基础的）元启发式有效的CLRP。我们更详细地解释了几个实施决策，并研究了我们的GRASP/VNS解决方案的质量和运行时的主要组成部分的效果在我们的方法的开发和测试中，我们发现，确定高质量的路由解决方案不仅对最终解决方案的质量很重要，而且对准确评估仓库配置的质量在GRASP阶段，用于评估所调查的仓库配置质量的次优路径选择方案为解决此问题，我们采用仓库配置优化阶段，对可行配置进行快速评估，减少开放仓库的数量。在数值研究中，我们表明，这种算法组件和VNS组件的彻底最终路由显着有助于我们的方法的质量在Tuzun和Burke [32]、Barreto [4]和Prins等人的常用CLRP基准[24]，与现有技术相比，我们的方法提供了合理的本文件其余部分的结构如下。我们在第2节中详细描述了我们的解决方法。我们的数值研究调查的GRASP/VNS的不同组成部分的效果的解决方案的质量和运行时间，并比较我们的方法4M. Lözier等人/EURO Journal on Computational Optimization 11（2023）100063←←∈←←←←←← ∅{大型类人猿生存方案阶段（见第2.1节）}最好的对于n次抓取迭代，sRECWA（）sVND（s）更新集合Sbest存储三个最佳解端{路线改善阶段（见第2.2节）}Sbest←shortVNSRun（Sbest）{使用短VNS运行的路线改进s←bestOf（Sbest）{仓库配置调整阶段（见第2.3节）}Ω生成ηdcr可行仓库配置，其中一个仓库小于s对于ωΩ dosinitialSolution（ω）{将所有客户分配到ω中最近的仓库，并通过专用路线为他们提供服务}sVND（s）% s shortVNSRun（% s）如果s改进了s，则ss如果结束，则结束{最终化阶段（见第2.3节最后一段）}s←longVNSRun（s）{使用长VNS运行改善}Fig. 1. GRASP/VNS算法概述。在第3节中描述了对现有技术的评价，随后在第4节中给出了简短的结论。2. 用于CLRP的我们实现了一个混合的解决方案方法相结合的GRASP的位置阶段与VNS的路由阶段。图1给出了我们的GRASP/VNS的伪代码概述，下面将对其进行描述GRASP/VNS 使 用 Prins 等 人 [25] 提 出 的 随 机 扩 展 Clarke 和 Wright 节 约 算 法（RECWA）来确定初始仓库配置和车辆路线，随后通过贪婪局部搜索进行改进我们注意到基本GRASP程序的以下问题：基于本地搜索返回的通常质量相当低的路由解决方案来评估仓库配置这可能会导致在比较仓库配置的潜力时做出错误的决策，并且在彻底的路由阶段之后，由其他配置主导的配置可能会如果在路线选择阶段固定了仓库配置，则这一点尤其成问题，因此必须在GRASP阶段找到最佳配置。为了解决这个问题，我们的算法使用以下两个措施：（i）我们用VND代替贪婪的局部搜索，VND能够处理相对于车辆和/或仓库容量不可行的解决方案，并旨在尽快修复这些解决方案（见第2.1节），以及（ii）我们不仅保留GRASP阶段的一个解决方案，而且存储在GRASP阶段发现的三个最佳解决方案注意，存储的解的数量是算法的参数我们的初步实验表明，M. Lözier等人/EURO Journal on Computational Optimization 11（2023）1000635·在质量和运行时间之间提供了一个合理的权衡这三种解决方案的路由通过路由改进阶段进行改进，该阶段执行少量的VNS迭代（参见第2.2节）以求解底层MDVRP。我们进一步改进了最佳解决方案，发现这一点如下：我们观察到的GRASP阶段的趋势，打开太多的仓库，因为客户不能适应到次优路线的路线解决方案在GRASP阶段。我们设计了一个仓库配置优化阶段，在减少开放仓库数量的情况下，对仓库配置的盈利能力进行快速评估（见第2.3节）。在此步骤中，新生成的仓库配置也通过短VNS运行进行了改进，以便与当前最佳解决方案进行公平比较在最终化阶段，我们的算法使用长VNS运行来进一步改进到那时为止找到的最佳解决方案的路由（参见第2.3节）。2.1. GRASP阶段GRASP阶段的核心要素是Prins等人的RECWA。[25]。与Prins等人[25]类似，RECWA在分散和强化阶段之间交替重复进行。RECWA首先将客户分配到最近的具有足够容量的仓库，在从仓库出发的专用路线上为每位客户提供服务，并在没有指定客户的情况下关闭设施随后，两条路线的所有可行合并对不违反车辆或仓库容量限制的合并进行评估。RECWA评估将合并路线分配给可用站点的所有可能性。我们将具有最佳节省的合并移动存储在大小为l的受限候选列表中，并以均匀概率从该列表中随机选择要执行的移动在RECWA的每次迭代中，大小l在区间[1，lmax]内随机变化，其中lmax是用户定义的参数。重复这一程序，直到无法找到导致成本降低的可行合并为止随后，我们通过VND使用表1中的运算符定义的邻域以给定的顺序改进所得解的路由。算子的顺序是根据它们对解的结构影响来选择的，在我们的计算实验中，我们表明，与每次VND重新启动时选择随机顺序相比，建议的顺序是有利的（见3.3节）。在VND的每次迭代中，执行第一个改进移动。不可行解s被赋予目标值Fg（s）=F（s）+M Vc（s），其中F（s）表示标准目标值，Vc（s）表示车辆和车辆段的容量违规量，M是一个非常大的惩罚因子。以这种方式，VND将总是偏好减少解决方案中的容量违规量的移动，而不是改善路由距离的移动，从而将搜索引导到可行的解决方案。由于认识到解决方案的质量在很大程度上取决于其设计，罐配置，我们进行n次抓取迭代的GRASP程序，如Prins等人提出的那样，在n次划分分散和n次intensification迭代[25]第10段。这两个阶段都是基于限制可用于6M. Lözier等人/EURO Journal on Computational Optimization 11（2023）100063表1VND的邻域运算符。订单 操作员描述1Split-1在任何开放的停车场打开包含单个客户的新路线。2重新定位-1从路由中提取单个客户，并将其插入同一路由的另一位置或任何其他路由。3Exchange-1交换来自相同或不同路由的两个客户。4Split-2包含两个连续客户的新路线在任何开放的车辆段打开5搬迁-2与Relocate-1相同，但两个连续的客户被重新定位，保留原来的秩序。6Exchange-2与Exchange-1相同，但交换了两个连续的客户，保留其原始顺序。7Split-b在任何开放的站点打开包含客户i及其所有前任的新路由8Split-f在任何开放的站点打开包含客户i及其所有后继者的新路由9Relocate-b客户i及其所有前任在任何位置移动到相同或不同的10Relocate-f客户i及其所有后继客户移动到相同或不同的路由在任何位置。112-选择权：两条从同一个停车场出发的路线重新连接，第一条路线的第一部分与第二条路线的第二部分连接，反之亦然。12交换-b客户i及其所有前任与客户j及其所有前任交换。客户i和j在不同的站点处于不同的路线上。13交换-f客户i及其所有后继者与客户j及其所有后继者交换。客户i和j在不同的站点处于不同的路线上。初始客户分配到可用仓库I的子集I'。在多样化阶段的第一次迭代中，所有仓库都可用，并可能开放。在接下来的迭代中，最初只有两个仓库可用于定义I'：第一个仓库被迭代选择，使得I的每个仓库至少被打开一次，第二个仓库从剩余的仓库中随机抽取。通过这种方式，系统地探索解决方案空间，并且每个仓库至少使用一次。所有客户都被顺序地分配到I '中他们最近的仓库。如果由于容量冲突而无法分配客户，则打开离客户最近的仓库随后，如上所述执行合并不仅I'中的站点而且所有站点都被认为是合并路线的起始和结束位置。在强化阶段，只有在I'中的在前一个分散阶段的最佳解中开放的仓库可以被使用。这里，不仅客户的分配被限制到该子集，而且在RECWA期间的合并操作也被限制到该子集2.2. 使用可变邻域搜索的路径改进阶段一般来说，GRASP生成的车辆路线质量一般。我们应用一个短的VNS运行，以进一步改善路由解决当前CLRP解决方案的底层MDVRPVNS最初由Mladenović和Hansen提出[20]，在越来越大的邻域中搜索，以摆脱局部最优。给定用于所谓的摇动步骤的一组预选邻域和用于局部搜索的一般不同的邻域：从当前解S开始，M. Lözier等人/EURO Journal on Computational Optimization 11（2023）1000637SSS图二.有四条路线的循环交换运营商。表2VNS中使用的邻域概述电话：+86-10 - 8555555传真：+86-10 - 855555551112131415161718涉及的44555555最大1 2 3 4 5 6 1 2 3 456123456使用第一个振动邻域生成新的解，并从那里执行局部搜索。在我们的实现中，如上所述的VND被用作本地搜索组件。如果这样获得的解"“具有比当前解低的质量，则选择下一个振动邻域来重复该过程。如果找到了更好的解决方案，或者已经探索了所有可用的震动邻域，则使用第一个震动邻域重新开始搜索我们通过循环交换算子定义了震动邻域，该算子以循环的方式在路线之间移动客户序列[15]。图2描绘了具有四个路由i=1、 2、 3、 4的示例，其中在路由之间交换从Vi到Wi如表2所示，我们区分了由该操作器生成的18个邻域。注意，图2中的示例对应于表2中的邻域7-12中的任何一个在循环交换中涉及的路线以以下方式确定首先，从所有路由的集合中随机抽取基本路由。路线的质心由路线上所有客户的平均笛卡尔坐标和路线起源的站点的平均笛卡尔坐标给出。第二，所有路由按照其质心与基本路由的质心之间的距离的递增顺序进行排序，并且从列表的开头开始获取要参与循环交换移动的路由的数量。要交换的客户的数量从1到给定的最大序列长度的区间中随机抽取每一条路线都有一次抽签请注意，所得到的解决方案在容量约束方面可能不可行此解决方案通过应用局部8M. Lözier等人/EURO Journal on Computational Optimization 11（2023）100063搜索，即，第2.1节中描述的VND。路由改进阶段中的短VNS运行在n次短迭代之后终止而没有改进。2.3. 仓库配置完善和最终确定阶段根据我们的计算经验，在大多数情况下，由GRASP确定的仓库配置如上所述，GRASP倾向于开设太多的站点，因为客户不能适应GRASP阶段期间确定的路由解决方案的次优路由为了弥补这一缺陷，我们使用了一个仓库配置调整阶段，该阶段系统地评估了仓库配置，减少了仓库数量从GRASP和路线改进阶段发现的最佳车辆段配置开始，我们确定了恰好少一个车辆段的ηdcr可行配置，仅限于开放车辆段的总容量足以满足总客户需求的车辆段。更准确地说，我们对少一个仓库的随机配置进行抽样，直到找到ηdcr可行配置，或者评估了所有可能的配置我们从产生的列表中随机选择一个仓库配置，并将所有客户分配到其最近的仓库，每个客户最初都通过专用路线提供服务由此产生的解决方案可能在仓库容量方面不可行首先，通过第2.1节中描述的VND的一次运行来改进（或在解决方案不可行的情况下进行修复）。接下来，利用短VNS运行进一步改进路由，该短VNS运行在n次短迭代之后停止而没有改进。这允许将所得到的解决方案与当前最佳解决方案进行公平比较。如果得到的解决方案改进了当前的最佳解决方案，则它成为新的最佳解决方案，否则它将被丢弃。重复上述过程，直到我们检查了ηdcr贮库配置。请注意，可能存在小于ηdcr的可行仓库配置，其中一个仓库小于GRASP确定的最佳解决方案在这种情况下，我们将开放仓库的数量增加1，并随机生成更多的配置，直到我们调查了ηdcr仓库配置。我们决定不调查开放式仓库数量甚至少于最佳仓库配置减1的仓库配置，因为仓库数量如此之少的配置不太可能产生良好的目标由于路由成本高在最终化阶段，我们尝试通过执行长VNS运行来进一步改进在仓库配置优化阶段发现的最佳解决方案的路由，该运行在最终迭代后终止而没有改进。2.4. GRASP/VNS的灵活性，以适应其他问题的变化GRASP/VNS使用算法组件，该算法组件允许该方法直接适应其他LRP变体，这些变体的特征在于附加的路由约束，例如时间窗口、同时拾取和交付或优先级M. Lözier等人/EURO Journal on Computational Optimization 11（2023）1000639限制，如线路和回程。由于组件的以下特性，这是可能的• GRASP：RECWA基于节省试探法的原理，由于导致不可行路由的合并被丢弃，所以该节省试探法可以容易地适于处理合并阶段中的附加路由约束。在GRASP的分散和密集阶段，限制候选名单的使用和站点的可用性不受额外路线限制的影响GRASP还包含一个VND组件，其灵活性概述如下。• VND：额外的路由约束需要通过额外的惩罚项来扩展广义目标函数，以处理关于新约束不可行的解决方案。新罚则的计算必须对所有邻域操作者都适用。请注意，选择已证明对给定路由约束有效的特定邻域运算符是很容易的。• VNS：抖动邻域不需要任何修改，因为关于新约束的潜在不可行解可以由如上所述的VND处理。3. 计算研究本节介绍了我们的数值实验，以（i）研究我们算法的核心组件对运行时间和解决方案质量的影响（第3.3节和第3.4节），以及(ii)将GRASP/VNS与最新技术水平进行比较（第3.5节）。第3.1节介绍了所使用的基准集，第3.2节描述了算法的参数设置。3.1. 基准实例Barreto [4]提出的基准集（以下称为Barreto集）由19个实例（最多318个客户和15个站点）组成，其中大部分是从经典的VRP实例改编而来的。文献中的比较方法仅使用集合中的13个实例的子集，因此，我们在计算研究中仅考虑这13个实例以进行有意义的比较。尽管如此，我们在附录B的表10中报告了其余6例的结果。关于Barreto 集，车辆容量通常是有限的，在我们的计算研究中使用的13个实例中，有4个也限制了停车场容量。Tuzun和Burke [32]提出了一组36个具有容量限制的车辆和没有仓库容量的实例，称为Tuzun-Burke集。实例从100个客户和10个仓库到200个客户和20个仓库。具有不同密度的客户群的实例和具有均匀分布的客户的实例包含在集合中Prins等人[24]的基准称为Prodhon集，由30个实例组成，范围从20个客户10M. Lözier等人/EURO Journal on Computational Optimization 11（2023）100063表3GRASP/VNS的参数整定。值Δa是到BKS的平均间隙。lmax1234567Δa0.750.800.680.740.770.720.68不46.0646.5745.3946.4446.2046.3548.39ndiv/n int1/72/63/54/45/36/27/1Δa0.920.840.670.780.770.710.77不43.2242.6243.4245.9547.8650.1551.04从5个站点到最多200个客户和10个站点的实例。所有实例都受到车辆和车辆段容量的限制，该集合包括具有两个或三个客户集群的实例以及具有均匀分布的客户的实例3.2. 参数设置和计算环境大多数算法参数是迭代限制，定义了不同算法组件的终止标准。这些参数控制解决方案质量和运行时间之间的权衡，我们将它们设置为以下值，以便在算法开发期间提供理想的权衡：ngrass=160，nshort=10，ηdcr=15，nfinal=600。对于其余参数，我们进行了简单的参数调整，旨在确定合适的参数设置，同时避免将设置过度拟合到所考虑的问题实例。为此，我们使用了一组43个实例，其中仅包括来自三个基准集的实例，最多有100个客户和10个仓库。我们从GRASP/VNS开发过程中发现的以下基本设置开始：受限候选列表的大小lmax=4，发散迭代次数ndiv=4，以及强化迭代次数nint=4。在第一步中，我们在范围1，...，7.对于每个值，我们对所有实例执行五次运行，并在表3中报告Arnold和Sörensen [3]的最佳已知解（BKS）的平均百分比差距Δa和平均运行时间t。我们检测到Δ a = 0的最低间隙。68以及l max = 3时的最短平均运行时间，我们选择l max作为最终值。接下来，我们测试值ndiv/nint= 1/7，2/6，...，7/1，并找到Δ a = 0的最小间隙。67，ndiv/nint=3/ 5，平均运行时间为43.42秒，非常接近整体最小值，42.62秒因此，我们选择最终参数值ndiv= 3和nint=5。实验清楚地表明，我们的算法对于合理范围内的参数值的修改是相当稳定的我们在表4中总结了所有参数的最终设置。GRASP/VNS是用C++实现的，我们在Intel Xeon E5- 2430 v2 CPU的单核上运行所有实验，CPU的主频为2.5 GHz，64 GB RAM，运行CentOS7.内存消耗始终保持在256 MB以下。M. Lözier等人/EURO Journal on Computational Optimization 11（2023）10006311表4GRASP/VNS的最终参数设置把握停止标准lmaxn抓取ndivnintηdcrn shortn final3 1603515 10 600表5VND邻域算子有效性的实验结果。删除操作员DiΔaΔtpFptSplit-10.1537.590.991.00搬迁-10.24-1.981.000.49Exchange-10.011.420.931.00Split-2-0.03-0.970.030.66搬迁-20.23-2.591.000.99Exchange-20.011.080.121.00Split-b-0.02-0.570.270.57分裂-f-0.06-0.370.100.31Relocate-b0.050.840.940.98Relocate-f0.001.790.641.002-选项 *0.080.051.000.13Exchange-b-0.010.190.900.17交流-f-0.050.770.040.973.3. 邻域算子在本节中，我们研究了VND中邻域操作符的选择及其执行顺序对GRASP/VNS性能的影响。第一个实验研究是否可以在不影响性能的情况下减少邻域算子的集合。我们调查所有的算法变体，通过从表1中删除一个邻域运算符的时间出现对于每个变体，我们在所有基准测试实例上运行五次。在表5中，我们报告了与基本设置相比，与BKS的平均百分比差距的绝对变化（DiΔa）和平均运行时间的百分比变化（Δt）。使用双侧Wilcoxon符号秩检验研究结果的统计学显著性列pF报告了假设的p值，即由两个算法变量获得的客观值来自不同的分布。列pt报告运行时的类似p值结果表明，从VND中移除的操作符不会提高解的质量，统计显著性超过90%。特别是，Split-f的改善幅度最大，显著性水平仅为10%。因此，我们保留表1中的所有运算符来定义VND邻域集值得注意的是，删除Split-1将算法的运行时间增加了35%以上。这可以解释为Split-1能够通过打开额外的路由来快速修复不可行的解决方案，并被放置在评估顺序的第一个位置。因此，如果允许不可行的解，则似乎可以解释为，求值顺序中的第一个位置12M. Lözier等人/EURO Journal on Computational Optimization 11（2023）100063表6Tuzun-Burke、Prodhon和Barreto基准集上八种不同算法配置的比较我们将汇总结果报告为Arnold和Sörensen [3]中报告的每种配置与BKS的平均百分比差距（Δa），以及以秒为单位的平均运行时间（t）。所有实例图尊伯克普罗东·巴雷托Δa不ΔatΔa不Δa不G3.12114.533.71180.743.1675.901.3720.29GF1.74200.911.82305.972.11143.730.6541.89GRI2.39117.392.75184.542.5578.561.0421.04GRI F1.72204.75312.35美元2.09147.440.6739.03GDCR2.52154.473.68240.301.73105.871.1628.92GDCRF1.21241.07361.06美元0.82178.940.5252.16GRI DCR1.91149.99231.411.40104.460.9229.56GRIDCRF1.20233.62348.820.85174.360.5551.35第二个实验调查的顺序，其中运营商的评价GRASP/VNS的性能的影响。我们使用邻近算子的完整集合，但是在每次运行中随机地在VND中改变它们的顺序。我们对所有问题实例进行了五次运行与具有表1的固定邻域顺序的变体相比，到BKS的平均间隙减少了0.12%，并且平均运行时间增加了53.46%。对于解决方案质量和运行时间的差异，双侧Wilcoxon符号秩检验确定的显著性水平至少为0.99。我们认为与解决方案质量的改善相比，运行时间的增加很大，因此我们决定将邻域运算符的顺序固定在VND内。3.4. 算法组件我们的GRASP/VNS包括四个部分：GRASP阶段（G）、路线改善阶段（RI）、车辆段配置完善阶段（DCR）和最终确定阶段（F）。在本节中，我们将更详细地评估每个组件如何对我们算法的解决方案质量和运行时间做出贡献，以便能够深入了解CLRP成功的元计算设计为此，我们研究了我们算法的八种不同配置，它们被唯一地识别为四个分量G，RI，DCR和F的组合。表6显示了在所有实例和单个实例集上运行五次相应配置的累积结果。单个运行的解决方案是配置找到的最佳解决方案，直到其最后一个组件完成。我们报告Arnold和Sörensen [3]中最佳已知解（BKS）的平均百分比间隙Δa和平均运行时间t。完整的GRASP/VNS的结果，即，在每个实例的基础上，可以在表8 附录B.我们提出以下意见：M. Lözier等人/EURO Journal on Computational Optimization 11（2023）10006313• 包含所有组件的最终配置，即，G RI DCR F在解决方案质量方面优于所有其他配置，这表明每个组件都有助于最终质量。• 最终化阶段是GRASP/VNS的一个重要组成部分，因为它能够显着提高解决方案的质量，每当它被添加到一个配置。一般来说，这些大的改进证明了F的额外运行时间，例如，相当于完整算法配置G RI DCR F的运行时间的大约33%。如果更多地强调运行时间，G RI DCR在更短的时间内提供相对不错的质量。然而，在实践中，很可能通过保持F并减少其VNS迭代的次数可以获得• 对不包括F的配置进行比较似乎具有误导性，因为只有使用第2节中所述的高质量路由解决方案才能充分发挥已识别的仓库配置的潜力。例如，虽然G DCR的表现明显不如G RI，但包括F表明配置GDCRF提供比G明显更好的溶液质量RIF的成本 运行时间适度增加15%。• 在仓库成本是主要成本因素的情况下，DCR的贡献要比在路线成本是主要成本因素的情况下将G RI DCR F的性能与G RI F的性能进行比较，我们可以看到仅在Prodhon集上获得解质量的显著改进，而在Barreto集和Tuzun-Burke集上只能找到很小的改进。在后两组的情况下，与路线成本相比，仓库开放成本很小，因此，关闭仓库不太可能改善总体成本。因此，为了节省运行时间，如果处理具有这种特殊成本结构的实例，然而，在现实世界中，位置的开放成本通常超过路由成本，因此，包括DCR是有益的。3.5. 与最先进技术的在 本 节 中 ， 我 们 将 GRASP/VNS 的 解 决 方 案 质 量 和 运 行 时 间 与 Tuzun-Burke ，Prodhon和Barreto基准上文献中最有效的CLRP启发式方法进行比较。在表7中，对于每种方法，报告了每个单独实例集和所有三个实例集的BKS平均间隙（取自Arnold和Sörensen [3]）和平均运行时间。提供了以下比较方法的结果（下面解释了相应作者报告结果和运行时• DLPP [10]给出了在5次运行中获得的最佳溶液和最佳运行时间• YLLT [33]、ELT [11]、ELBT [12]和AS-PF1 [3]提供了单次运行的结果• 对于HCC的两种变体[14]和SL-TBSA速度 [30]，该表报告了5次运行的最佳结果和每次运行的平均运行时间表7GRASP/VNS与最先进方法的比较。对于每种方法，我们将每种方法找到的最佳解的平均差距报告给BKS如Arnold和Sörensen [3]中所报告的（Δb），以及Tuzun-Burke、Prodhon和Barreto基准测试集上的运行时间（t）（以秒为单位）。对于HCC-此外，我们报告的基准测试环境用于每种方法和一个共同的时间测量的基础上，在测试中使用的处理器的及格分数基准DLPPYLLT公司简介HCC-5000KELTCCGΔb不Δb不ΔbΔa不ΔbΔa不Δb不ΔbΔa不图尊伯克1.406071.598260.530.991660.390.6016211.243920.270.662590普罗东1.172580.514220.500.78900.400.518440.621760.180.381163巴雷托0.041880.251610.120.21350.020.053540.741050.150.66279平均1.094050.965640.450.781160.340.4711170.932630.220.551685处理器类型酷睿2四核酷睿2四核Opteron 275Opteron 275酷睿2双核至强E5462处理器速度2.83千兆赫2.66 GHz2.20 GHz2.20 GHz2.00 GHz3.00 GHzPassmark评分122211596856857921219校正的时间344 ×545455 ×5532 ×51451428 ×10基准测试TC ELBT LFS-Hybrid GA LFS-Hybrid GA+SL-TBSA速度AS-PF1GRASP/VNSΔb不Δb不ΔbΔa不ΔbΔa不ΔbΔa不Δb不ΔbΔa不图尊伯克1.332020.862010.961.55860.811.193640.310.57660.34160.860.881.72351.19普罗东0.451910.43910.430.71730.370.581990.100.20320.14104.600.330.85174.36巴雷托0.07490.63530.040.26190.000.06930.000.08100.0486.230.110.5551.35平均0.801740.661350.611.02700.510.772570.180.35440.21127.220.541.20233.62处理器类型XP 2500+酷睿2双核i7-4790i7-4790至强E5-2670i7-4790至强E5- 2430 v2处理器速度1.83千兆赫2.00 GHz3.60千兆赫3.60千兆赫2.60 GHz3.60千兆赫2.50 GHzPassmark评分54479222262226165222261439校正的时间66 ×1074108 ×5397 ×551 ×5197234 ×514M. Lözier等人/EURO Journal on Computational Optimization 11（2023）100063M. Lözier等人/EURO Journal on Computational Optimization 11（2023）10006315• 对于CCG [6]，TC [31]，LFS的两个变体[17]和GRASP/VNS，该表显示了10次运行中的最佳结果和每次运行的平均运行时间此外，该表还报告了所使用的处理器以及各个处理器的单个内核的Passmark分数（参见www.cpubenchmark.net）。虽然由于不同的操作系统和编程语言，不可能对运行时进行完全精确的比较，但我们使用此信息将所有运行时转换为基于我们用于测试算法的CPU的常见时间度量此外，方法的运行时间乘以报告的解决方案质量所基于的运行次数。GRASP/VNS的性能与现有技术相比是相当合理的。考虑到三个基准集中的每一个的平均解质量和运行时间，只有最近提出的方法TBSA速度和AS能够主导GRASP/VNS，即，所有其它比较方法在三个基准集中的至少一个上或者更慢或者实现更差的解质量。另一方面，GRASP/VNS实现了几乎相同的解决方案的质量，最近提出的LFS-混合GA+，而需要更少的运行时间。就平均解质量Δa而言，HCC-考虑到Δb和Δa之间的差异，GRASP/VNS似乎比比较方法略差，但偏差仍在合理范围内。鉴于GRASP/VNS的概念简单，效率和鲁棒性似乎是相当合理的。特别是，我们要强调我们的算法的简单性相比，两个主导算法SL-TBSA的速度和AS。GRASP/VNS的仓库配置搜索基于对可用仓库的直接抽样，并将客户分配到其最近的仓库，以及新引入的仓库配置优化阶段。通过一个随机储蓄启发式和改进的VNS内使用本地搜索的路由。相比之下，SL-TBSA速度具有在由交换和反转运算符定义的仓库配置邻域上操作的复杂位置阶段。该搜索使用下界技术、将现有路线规划解决方案转换为新的车辆段配置以及评级功能判断尚未由路由组件评估的站点配置的潜力。路由阶段是一个具有连续稀疏化的粒度禁忌搜索，一个更复