车辆路径问题的人工蜂群算法优化及应用研究

工程科学与技术，国际期刊22（2019）727完整文章一种求解有能力车辆路径和网络优化的Fuat Simsira，Dursun Ekmekcib，a土耳其卡拉布克大学工业工程系b土耳其卡拉布克大学计算机工程系阿提奇莱因福奥文章历史记录：收到2018年2018年12月25日修订2019年1月3日接受2019年1月23日在线提供保留字：车辆路径问题优化人工蜂群算法A B S T R A C T车辆路径问题（VRP）是长期以来通过尝试不同技术并在优化方面引起关注而在大多数VRP类型中，路线成本与距离相关，距离较短的解决方案被认为是更成功的解决方案。虽然最短距离目标在成本和时间方面为企业提供了显着优势，但这使得它对进一步研究具有吸引力。当从不同的角度研究具有不同方向和区域的车辆路径问题时，可以说最接近实际应用的方法是同时送货和取货的车辆路径问题（VRPSDP）。在这项研究中，一个解决方案的建议，提出了VRPSDP使用人工蜂群（ABC）算法和应用程序进行了测试，通常用于VRPSDP在文献中的基准问题数据集。当结果与文献中的最低成本的路线解决方案相比，据观察，尽管参数很少，所提出的方法可以产生低成本的解决方案非常接近的最成功的解决方案在文献中。©2019 Karabuk University. Elsevier B.V.的出版服务。这是CCBY-NC-ND许可证（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍运 输 和 通 讯 技 术 的 发 展 因 此 ， 当 今 市 场 竞 争 根 据 Toth 和Vigo[40]，特别是在运输领域，使用计算机辅助方法可以实现5%-20%的节省在这种情况下，VRP的解决方案可以为降低成本提供显著的优势[6]，VRP被定义为确定车辆的最佳路线的问题，这些车辆将从一个或多个仓库出发，用于地理上分散的客户的交付和拾取服务。VRP中的基本方法是通过规定从单个仓库满足具有已知需求量的所有客户的需求，并且仅使用一辆运输车辆访问每个客户来提供所有配送需求[4]。Dantzig和Ramser在1959年针对配送汽油的卡车车队的路线成本最小化的研究可以被认为是对VRP的系统的第一次研究[9]。从*通讯作者。电子邮件地址：fuatsimsir@karabuk.edu.tr（F. Simsir），dekmekci@karabuk.edu.tr（D. Ekmekci）。由Karabuk大学负责进行同行审查从1959年起，在生产和服务部门的大部分物流运输和配送部门，从汽车到食品，从纺织品到货物，都提出了不同的VRP解决方案[28，19]。当对VRP的研究进行检查时，可能会遇到不同类型的问题，其中节点上的交付和拾取在不同的时间彼此独立地执行[12]。在VRP类型中，VRPSDP类型在与现实生活物流活动的相似性方面尤其突出。VRPSDP最显著的特点是，所有要交付给客户的货物都从仓库发出，所有要从客户那里收到的货物都发送到同一个仓库[1]。各种启发式和元启发式方法以及VRPSDP解决方案的精确方法。在这项研究的范围内，它的目的是开发一个算法，具有可接受的范围内的解决方案的时间，找到低成本的路线，为车辆的能力有限，同时进行交付和皮卡活动，在各种类型的多客户端网络模型。该路线的成本较低，也将带来优势，如更高的效率，更低的燃料消耗和更短的交付时间，同时减少车辆的数量，以及使用。在上述目标的框架中，ABC算法已被优选为方法。ABC算法可以用于其他类型的问题，其中元启发式方法可以使用，它被观察到产生成功的结果https://doi.org/10.1016/j.jestch.2019.01.0022215-0986/©2019 Karabuk University.出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表工程科学与技术国际期刊杂志主页：www.elsevier.com/locate/jestch728F. Simsir，D.Ekmekci/工程科学与技术，国际期刊22（2019）727ð Þ联系我们XXXX在许多应用中，特别是NP难的组合优化问题。ABC算法是一种基于种群的高效算法，除了在局部搜索方面的成功表现外，它还可以扫描大范围的解，同时通过使用ABC算法，我们的目标是能够成功地扫描搜索空间，具有不同程度的波动，由于在VRPSDP问题的节点间距离和负载需求的变化。1.1. VRPSDP的数学公式VRPSDP可以是定义如：在的关闭图模型GV;E;V0; 1;. ;n是节点的集合。 节点0代表仓库中心，其他代表要访问的客户。E<$fi;j：i;j2Vg是边的集合，每条边的成本为c成本（距离）。所有车辆请进入仓库-房子都是齐次Q，对车辆的数量没有限制。车辆同时从仓库出发，并在路线终点返回仓库。每辆车的通行能力不应超过沿线的车辆。每一个客户i2V只访问一辆车，只有一次。交付给每个客户的di从每个客户处拾取P1。VRPSDP的数学公式可以定义如下：这样的问题被认为是NP难问题[42]。Applegata等人[2]对Bellman-Held-Karp算法进行了详细分析，该算法包含NP-hard问题解决方案的动态解。他们用Bellman-Held-Karp算法检验了问题的复杂性和求解时间。随着城市数量的增加，n22n的当我们达到n = 29时，内存需求超过12 GBy- tes，并且测试在没有计算最佳巡回的情况下终止。由于车辆容量随着问题中节点数量的增加而变得不足，因此开发了一种两步解决方案，其中节点被分组，然后路由[31]。1.2. VRPSDP的简要文献综述Min[31]提出了具有同时分布/聚合的多节点VRP解决方案的第一种方法。在Min的研究中开发的解决方案包括三个阶段：为客户节点创建集群，为创建的每个集群分配适当的运输工具，以及路由每个运输车辆所属的集群。Dethloff[11]开发了一种基于加法的启发式方法，n n最小cij xij1联系我们nxij¼1 8i¼1;：;nj¼0n比Min. Bianchessi和Righini[5]使用的结果更成功Dethloff公式Nagi和Salhi[32]在文献中提出了另一种为VRP开发的交付和拾取方法。该算法是有用的VRPSDP以及一般的解决方案，为一些混合情况下，只有交付执行的一些客户，只有拿起是每。x0jj¼0n≤m≤300n为一些客户设计的Cetin等人[6]认为这种新模型比Min的方法更成功Tang和Galvão[39]提出了两种启发式局部搜索解决方案，巡回分区和扫描算法。 许多解决方案Xxij<$Xxji8i<$1;：;n已经为巡回分区方法提出。其中一j¼0nj¼0n是由Cristofides，Mingozzi和Toth[15，8，13]开发的算法。Crispim和Brandao[7]使用元启发式方法第一次在同时交付/拾取VRP解决方案中，XP ij-XP ji¼ pi8i ¼ 1;：; n是的。[11]李和，李和。j¼0nj¼0n的模型，并尝试用粒子群优化算法（PSO）首先，他们比较了XD ij-XD ji¼ d i8i ¼ 1;：; n他们提出要满足物流世界的当前需求，j¼0j¼0Solomon[38]的试验数据，并得到了成功的结果，然后又产生了新的比较问题。当Yousefikhoshbakht等人。P ij<$D ij≤Q8i¼ 1;：;n8j1;：;nPij;Dij≥0 8i<$1;：;n8j<$1;：;nx ij2 f 0; 1 g8i¼ 1;：;n8j1;：：：：;n目标函数（1）给出了车辆的总成本之和。约束（2）意味着每个客户只能退出一个弧。车辆的最大数量由约束条件（3）保证。约束（ 4）表明每个客户的退出弧和进入弧的数量是相同的。等式（5）、（6）确保每一位客户的提货数量在一次拜访中得到充分满足。约束条件（7）规定车辆容量永远不会被超过。约束（8）迫使流保持非负，最后，约束（9）描述网络中的每个弧如果被使用则具有值1，否则具有值0。送货和取货活动在路线上指定为“停靠点”的每个节点同时进行。由于解空间随着节点的数量呈指数扩展[41]研究了为VRPSDP开发的解决方案，他们意识到元启发式解决方案更成功，并通过将改进的TS和精英蚂蚁系统算法结合起来形成了一个混合系统，用于解决此类问题。Mancini[29]论证了同时交付和拾取运输系统，该系统采用了现实生活中可能遇到的多仓库，多周期异构容量运输车队Man-cini提出了一种混合整数规划公式在这样的网络，并提出了一种基于元分析的适应宽邻域搜索方法。Salhi等人[36]解决了一个类似的问题，并致力于一个可变邻域搜索应用程序，除了邻域和局部搜索算子外，还具有新的特征。在文献中发表的26个样本中，有23个样本的求解结果较为成功在为VRP解决方案开发的另一项研究中，Hosseinabadi等人。[17]提出了一种新的元启发式优化算法，该算法基于引力定律和组相互作用。他们提出的算法基于随机搜索和搜索代理的概念，使用物理学中四个基本参数中的两个F. Simsir，D.Ekmekci/工程科学与技术，国际期刊22（2019）727729它们是基于牛顿引力和运动定律Hosseinabadi等人[18]提出了一种新的组合算法OVRP_- GELS，它是基于引力模拟局部搜索算法来求解OVRP的。Kalayci和Kaya[21]开发了一种基于蚁群系统（ACS）和可变邻域搜索（VNS）的混合元启发式方法。该方法利用蚁群算法的强记忆结构来增强VNS的局 部 搜 索 能 力 ， 从 而 增 强 了 算 法 Avci 和 Topaloglu[3] 认 为 ，VRPSDP 的 解 决 方 案 也 适 用 于 混 合 接 送 车 辆 路 径 问 题（VRPMPD）。他们开发了一种混合方法，使用模拟退火（SA）算法和可变邻域下降（VND）算法在一起。Rieck等人[34]开发了两种混合整数线性模型公式，他们称为了加强模型，Rieck概述了域缩减预 处 理 技 术 和 有 效 切 割 平 面 。 采 用 多 邻 域 引 导 局 部 搜 索 算 法（MN_GLS），朱等。[44]设计了一个三阶段模型首先，他们使用最近邻方法来创建初始解。他们在第二阶段的初始解中使用了多个算子，他们试图找到具有不同目标函数和罚点值的局部搜索的最优解，在第三阶段，他们从局部最优解中选择了最成功的解。Sayyah等人。[37]使用了一种有效的蚁群优化（EACO）算法，包括加法，跳跃和2-Opt移动，而不是经典的蚁群优化（ACO）。他们提出的方法已被证明是成功的，与文献的例子进行测试时，它也被证明，他们可以与其他元启发式算法，如TS，大邻域搜索（LNS），PSO和GA竞争。当研究文献摘要时，已经确定-我们发现，虽然元启发式方法通常是VRPSDP解决方案中的首选方法，但可以在短时间内执行详细搜索的ABC方法没有被使用。ABC算法是一种元启发式方法，即使在大容量优化问题中，也可以产生具有大参数值的成功解。在本研究中，ABC算法被选择为符合侦察蜂：蜜蜂出去觅食，随机分散，开始搜寻过程。当食物来源被确定后，这些蜜蜂就充当服务蜂。蜜蜂工作：它们负责从发现的源头运送花蜜，也负责在食物源周围寻找其他来源，因为它们根据邻里原则履行职责。这些蜜蜂的另一个职责如果被雇佣的蜜蜂携带食物的食物来源已经耗尽，这只蜜蜂开始作为侦察蜂工作，并分散寻找新的食物来源。旁观者蜜蜂：这群蜜蜂在蜂巢中等待，观察其他蜜蜂的振动，以传递食物位置信息。他们根据所获得的食物质量和数量信息，选择自己侦察蜂控制探索过程，而被雇佣的蜜蜂和旁观者侦察蜂的百分比根据进入巢的信息从5%到30%不等在自然条件下，侦察兵的平均数量约为10%[20]。蜜蜂世界中的食物来源对应于ABC算法中的任何因此，食物来源的质量与测定溶液的价值有关[24]。ABC算法的基本步骤可以根据蜜蜂在自然生活中的行为列出如下[24]：第一组食物来源确定重复被雇用的蜜蜂被送到确定的食物来源根据工作人员带来的花蜜质量计算出选择食物来源的可能性值旁观的蜜蜂使用可能性值来● 侦察蜂分散寻找新的食物来源● 直到满足算法数学表达式中使用的变量考虑了其在组合优化问题中的效率。该方法可以详细跟踪ABC算法在最优解搜索过程中得到的解路径以及这些路径的图形绘制文章的以下部分设计如下：在第2中，描述了ABC算法在第三中，详细介绍了将ABC算法应用于VRPSDP求解的方法在第四节中，我们设计了所提方法的参数集，并在基准问题上对所提方法进行了测试。在第5节中，所提出的方法在VRPSDP测试问题的结果进行了比较，在文献中观察到最后，在第6中，对所开发的方法和文献比较的结果进行了解释和讨论，以提高性能。2. ABC算法ABC由Dervish Karaboga[23]于2005年开发，其基于自然生活中蜜蜂群体的觅食行为开发用于实际参数优化算法已成功应用于不同工程学科的不同领域[26，27，25，30，22]。根据Karaboga的说法，蜜蜂根据群体生活中的分工分为三组[24]：r ab：r表示食物来源，a表示来源编号，b表示相应的参数编号se：随机选择的源/ab：随机选择的加权数[-1，1]ta：发现新的来源如果我们假设以蜂巢为中心的最大区域，蜜蜂可以分散寻找食物来源（r）作为搜索空间，算法开始在这个区域中随机选择点。当选择随机点时，这些点必须在相关区域内选择，如等式所示。（十）、换句话说，在生成集合的随机位置时，点，所需参数的下限和上限必须”[25]见。在所提出的VRPSPD解决方案中，下限为1，上限为要访问的节点数。rab<$rminb最大值0;1ωrmaxb-xminb最大值10被引导到食物来源的蜜蜂也访问附近的食物来源。在ABC算法上下文中，可以使用各种方法来实现这种访问行为。如果通过这种方法或类似方法产生的新资源更合格，●●●●●●●●730F. Simsir，D.Ekmekci/工程科学与技术，国际期刊22（2019）727图1.一、为VRPSDP开发的ABC算法。F. Simsir，D.Ekmekci/工程科学与技术，国际期刊22（2019）727731图二. 一个例子的解决方案所提出的方法。图三. 用OX交叉法导出新的解。比现有的资源，这个新的资源被存储。在源的邻域中注意到的这个新的源由以下等式表示：（十一）：从源头上获益更长在ABC算法中，耗尽的源由故障计数器确定。当源搜索中的所有蜜蜂返回蜂巢时（当一个周期结束时），塔布 公司简介抗/抗阿布尔公司-SEB Þð11Þ将找到的新来源与当前来源进行比较，以更新“无法开发”的值在表达式（2）中，源ra的b参数、源se的b参数、/ab参数都是在范围[1.D]。参数b之间的差异R是源，而随机选择的S是源B。用fab参数的值对食物来源的参数进行加权。然后这个差异被用来寻找一个新的资源。的Ra源的b参数与另一个Se源的b参数之间的差被fab参数加权以找到新的Ta源。如果新发现的tab源比ra源更合格，则从此将使用此源。所有值班的蜜蜂，把他们的信息传给蜂巢里的蜜蜂会根据它们收到的信息选择一个来源，并向那个来源前进该算法模型根据表达花蜜质量的拟合度值来在ABC算法中，轮盘赌轮方法通常用于这种选择。使用轮盘赌轮的表达式由等式（1）（12）.fitnesS我解决方案当不能开发蜜蜂的解决方案计数器超过预定的极限值时，该蜜蜂离开它一直访问的源，承担侦察蜂角色并开始随机搜索新的源[24]。3. 拟定方法：VRPSDP在第2节中，ABC步骤中的操作被描述为数值优化问题的原始设计。在该方法中，设计了ABC算法来确定集疏运同时进行的不同多点网络结构中运输车辆的最小费用。ABC算法的构造如图所示。 1对于VRPSDP这类离散问题。在ABC算法中，访问所有节点以满足期望条件的每个解被视为在这种情况下，因此，我们设计了寻找“最优nec-tar”的算法的数量Pi¼P拉吉吉ð12Þ被雇佣的蜜蜂和被引导到食物SN配件S1/1当花蜜在资源搜索过程中被消耗时，蜜蜂离开它们访问的资源。一个来源的花蜜耗尽意味着蜜蜂不能使用这个来源见图4。 CON3.1问题的应用结果。每个周期的食物来源数量等于第一个周期的食物来源数量。定的。此外，该算法的极限值RITHM将结束循环，并且要放弃馈送源的极限值是可以由用户确定的其它参数。3.1. 生成初始解该算法首先根据确定的食物来源数量创建随机解。在应用范围内创建的解决方案是以最小数量创建的车辆路线集群为目标。在VRPSDP中，第一个节点（用“0”表示）是仓库;其他节点是客户节点。因此，车辆路线是从0开始并持续到下一个0的数字序列。在这种情况下，每个解决方案是一系列数字，其中包含“车辆数量+1”乘以0和所有其他节点编号，每个节点编号仅使用一次。因此，在创建随机解或从现有解导出新解时，不应忽视这种情况。在图2中，呈现了示例解决方案。3.2. 蜜蜂阶段在这个阶段中，通过改变初始解中节点的顺序来得到新的解。在所提出的方法中，新的解决方案是通过顺序交叉（OX）技术，732F. Simsir，D.Ekmekci/工程科学与技术，国际期刊22（2019）727由戴维斯开发的nique[10]。在这个范围内，每个现有的解决方案都通过OX技术与通过轮盘赌轮从现有解决方案中选择的另一个解决方案交叉。OX算法首先选择两条解路由，并在每条解路由上随机选择两个截止点，在它们之间保留相等数量的节点。当导出新解时，断点之间的节点相互移位，其余节点按当前解的顺序排列。图3显示了用于新解推导的双点OX交叉方法。如果在新解决方案的推导中使用的现有解决方案未能推导出更成功的这些解决方案的价值增加。解决方案，删除已达到极限值的故障计数器值，创建新解决方案代替这些解决方案，这些新生成的解决方案的值设置为0。3.3. 围观蜜蜂相在迭代阶段，当生成新的解时，再次使用OX方法可替代地，要用于交换的两个解决方案由轮盘赌轮随机选择。如果在新解决方案的推导中使用的现有解决方案未能推导出更成功的解决方案，则这些解决方案的图五. 应用程序的CON3.1测试问题的解决方案图图六、应 用 程序的CON 3 -1测试问题的解决方案路线上的运输车辆占用率。F. Simsir，D.Ekmekci/工程科学与技术，国际期刊22（2019）727733解决方案增加了。解决方案，删除达到极限值的失败计数器值，创建新的解决方案来代替这些解决方案，并且将这些新生成的解决方案的失败计数器值设置为0。3.4. 侦察蜂阶段在侦察蜂阶段，其故障计数器值达到极限值的解决方案被删除，新的解决方案被创建，而不是这些解决方案。新生成的解决方案的故障计数器值设置为0。新解决方案的创建是在类似于最初的操作。表1CON和SCA问题的文献研究LNS（大邻域搜索）[35]ACS（蚁群系统）[14]PILS（并行迭代局部搜索）（Subramanian等人，2010年AMM（自适应记忆方法）[43]h_PSO（混合粒子群优化）[16]MTSEAS（Modified Tabu Search and Elite Ant System）ACSEVNS（蚁群系统增强的可变邻域搜索）[21]自适应局部搜索（Adaptive Local Search，ALS）[3]MILP（混合线性规划）[34]MN_GLS（多邻域引导局部搜索）[44]EACO（有效蚁群优化）[37]4. 计算研究该算法在.NET平台上使用C #编程语言实现应用程序运行在具有8GB RAM，i7- 4710 MQ 2.50处理器和Windows 7操作系统的机器当测试问题作为广泛的文献搜索的结果，旨在最小化基于距离的路线成本的测试问题进行检查，CON和SCA的例子引起了人们的注意，特别是因为他们的不同的变化。自从他们第一次准备以来，已经观察到为这些例子产生成功解决方案的算法对于其他类似问题也是成功的。出于这个原因，已经针对这些测试问题对开发CON和SCA测试问题是由Dethloff为VRPSDP设计和开发的。虽然在两种情况下都有50个客户，但在SCA模型中，客户随机分布到地理区域，而在CON模型中，一半的客户随机分布，另一半则集中在特定区域[16]。在这两个模型中，两种不同的车辆类型被用于不同的容量。当对CON 3.1问题的求解结果与算法的参数值进行比较时，发现当食物源和极限参数的值增大、极限值增大以及迭代减少 了表2CON和SCA问题的文献研究及其最佳解决方案测试问题LNSACSPilsAMMh_PSOMTSEAS联系我们ALSMILPMN_GLS选管SCA3-0636.10635.62635.62635.62635.62635.62635.62635.62677.35635.66635.93SCA3-1697.84697.84697.84697.84697.84697.84697.84697.84758.90697.84697.84SCA3-2659.30659.34659.34659.34659.34659.34659.34659.34735.18659.34659.34SCA3-3680.60680.04680.04680.04680.04680.04680.04680.04735.79680.04680.04SCA3-4690.50690.50690.50690.50690.50690.50690.50690.50741.75690.50690.50SCA3-5659.90659.90659.90659.90659.90659.91659.91659.90702.45659.96659.90SCA3-6651.10651.09651.09651.09651.09651.09651.09651.09707.72651.09651.09SCA3-7666.10659.17659.17659.17659.17659.17659.17659.17708.24659.17659.17SCA3-8719.50719.47719.48719.47719.47719.48719.48719.47771.94719.47719.47SCA3-9681.00681.00681.00681.00681.00681.00681.00681.00726.77681.00681.00SCA8-0975.10961.50961.50961.50961.50961.50961.50961.501026.79961.50964.81SCA8-11052.401049.651049.651049.651049.651052.041049.651049.651127.411049.651049.65SCA8-21044.501042.691039.641039.641039.641039.641039.641039.641126.121039.641042.64SCA8-3999.10983.34983.34983.34983.34983.34983.34983.341062.99983.34983.34SCA8-41065.501065.491065.491065.491065.491065.491065.491065.491114.121065.491065.49SCA8-51027.101027.081027.081027.081027.081027.081027.081027.081085.961027.081027.08SCA8-6977.00971.82971.82971.82971.82971.82971.82971.821038.59971.82975.19SCA8-71061.001052.171051.281051.281051.281061.001051.281051.281114.171051.281051.28SCA8-81071.201071.181071.181071.181071.181071.181071.181071.181165.081071.181071.18SCA8-91060.501060.501060.501060.501060.501060.501060.501060.501145.711060.501062.34公司简介616.50616.52616.52616.52616.52616.52616.52616.52667.46616.52616.52公司简介554.50554.47554.47554.47554.47554.47554.47554.47590.82554.47554.47公司简介521.40518.00518.00518.00518.00518.01518.00518.00558.89518.00519.89公司简介591.20591.19591.19591.19591.19591.19591.19591.19634.93591.19591.19CON3-4588.80588.79588.79588.79588.79588.79588.79588.79627.95588.79588.79公司简介563.70563.70563.70563.70563.70563.70563.70563.70603.56563.70563.70公司简介500.80499.05499.05499.05499.05500.80499.05499.05539.58499.05500.21公司简介576.50576.48576.48576.48576.48576.48576.48576.48627.05576.48576.48公司简介523.10523.05523.05523.05523.05523.05523.05523.05561.65523.05523.05公司简介586.40578.25578.25578.25578.25578.25578.25578.25619.95578.25578.25公司简介857.20857.17857.17857.17857.17857.17857.17857.17918.21857.23859.93公司简介740.90740.85740.85740.85740.85740.85740.85740.85772.44740.85740.85公司简介716.00712.89712.89712.89712.89712.89712.89712.89738.99712.89712.89公司简介811.10811.07811.07811.07811.07811.07811.07811.07857.35811.07811.07公司简介772.30772.25772.25772.25772.25772.25772.25772.25816.81772.25772.25公司简介755.70754.88754.88754.88754.88755.70754.88754.88798.07754.88754.88公司简介693.10678.92678.92678.92678.92678.92678.92678.92718.36678.92678.92公司简介814.80811.96811.96811.96811.96814.80811.96811.96863.39811.96812.55公司简介774.00767.53767.53767.53767.53767.53767.53767.53808.17767.53767.79CON8-9809.30809.00809.00809.00809.00809.00809.00809.00843.84809.00809.00734F. Simsir，D.Ekmekci/工程科学与技术，国际期刊22（2019）727表3ABC结果与文献中最成功的解决方案的比较ABC最好的AVG。标准偏差% GAP（与Dethloff相比，ABC最佳）% GAP（与文献相比，ABC最佳）640.55 684.05 27.88 7.03-0.78697.84 735.60 22.16 8.85-0.01659.30 725.43683.11 731.93 27.40 7.34-0.45692.57 738.13 23.09 7.30-0.30659.90 706.73 32.18 15.87 0.00678.07 35.17 9.62 0.00666.54 717.83 35.17 5.84-1.12723.44 762.13 19.10 10.38-0.55685.16 734.50 31.51 10.33-0.61961.50 1015.6515.13 0.001060.63一千一百三十一点八18.60 7.84-1.051045.121092.2016.37 5.06-0.53983.34 1051.938.47 11.86 0.001072.391131.1313.73 13.19-0.651027.08一千零九点七三16.61 0.00980.71 1049.4015.43 7.70-0.911059.28一千一百三十六点二四24.11 12.99-0.761080.02一千一百四十一点五十三分12.53 12.31-0.831060.50一千一百三十二点九七19.59 10.5519.19 8.31 0.00582.47 8.26 2.83 0.00523.47 538.97 7.35 2.12-1.06595.46 619.33 14.75 9.35-0.72591.37 620.73 15.75 7.63-0.4416.42 6.78 0.00502.63 527.43 14.34 3.58-0.72580.87 621.87 16.70 3.64-0.76523.94 547.03 17.76 5.80-0.17578.25 610.90 21.94864.52 895.77 10.12 10.63-0.86745.91 773.03 6.76 9.99-0.68712.89 749.77 7.44 0.00816.38 860.58 16.29 9.96-0.65774.90 801.80 7.66 11.62-0.34758.33 779.83 5.68 12.52-0.46683.21 717.87 5.41 8.80-0.63844.77 8.78 12.67 0.00771.19 796.90 5.26 7.43-0.48834.70 4.88 7.79 0.00表4关于Dethloff VRPSPD实例的文献与ABC的比较[11]。测试问题文献ABC平均最佳解决方案平均最佳解决方案SCA3SCA8 1028.15560.95 563.07CON8 771.655. 计算结果和比较对于该算法的CON3.1问题解，在1500次迭代中获得的值，其中食物源的参数值为1300，限制的参数值为250，如图所示。 四、最成功的结果记录为554.47单位，其解如下：电话：+86-17 - 12 -47-21-23-18 -35-50-7-49-43-9-3-20-8-15-32-42-1-0 -33-6-37-48-40-44-41-5-11-36-31-34-38-13-27-29-0-2-16-45-39-19-4-24-10-25-46-30-0-26-22-14-0图图5是所得到的解决方案路线的图示，示出了在解决方案路线中，需要四辆运输车辆进行运输。图6示出了这四个运输车辆的926.2573单位容量的更新数量，其在路线上的每个节点处的递送/拾取之后更新。作为CON 31问题的算法输出的详细分析的解释，所有其他CON和SCA的例子的解决方案，寻求使用ABC算法以及CON 31问题。所获得的结果进行了比较，这些测试问题的解决方案，获得的文献研究的最成功的结果。表1中列出了CON和SCA示例的不同方法以及应用这些方法的机器的硬件功能。表2列出了通过测试CON和SCA的不同方法而改进的解决方案的最成功的结果。在表3中，将VRPSDP解决方案开发方法的CON和SCA问题解决方案的最成功结果与ABC结果进行了比较。表3还显示了ABC对每个问题获得的平均值、标准差数据、寻找最佳结果所花费的CPU时间以及解决每个问题所花费的平均CPU时间。从表3中可以看出，所提出的方法可以产生比Dethloff低得多的成本路线，并且它落后于文献中最成功的结果，直到最近，其百分比高达1.12%。考虑到时间和标准差数据，ABC似乎能够在合理的时间产生解决方案，在低标准差下。测试问题德特洛夫文学最佳SCA3-0689.00635.62SCA3-1765.60697.80SCA3-2742.80659.30SCA3-3737.20680.04SCA3-4747.10690.50SCA3-5784.40659.90SCA3-6720.40651.09SCA3-7707.90659.17SCA3-8807.20719.47SCA3-9764.10681.00SCA8-01132.90961.50SCA8-11150.901049.65SCA8-21100.801039.64SCA8-31115.60983.34SCA8-41235.401065.49SCA8-51231.601027.08SCA8-61062.50971.82SCA8-71217.401051.28SCA8-81231.601071.18SCA8-91185.601060.50公司简介672.40616.50公司简介570.60554.47公司简介534.80518.00公司简介656.90591.19CON3-4640.20588.79公司简介604.70563.70公司简介521.30499.05公司简介602.80576.48公司简介556.20523.05公司简介612.80578.25公司简介967.30857.17公司简介828.70740.85公司简介770.20712.89公司简介906.70811.07公司简介876.80772.25公司简介866.90754.88公司简介749.10678.92公司简介929.80811.96公司简介833.10767.53CON8-9877.30809.00F. Simsir，D.Ekmekci/工程科学与技术，国际期刊22（2019）727735当检查比较数据（表3）时，可以看出，ABC算法获得的最成功结 果 的 平 均 值 （ 761.73 ） 仅 比 文 献 中 最 成 功 结 果 的 平 均 值（758.53）低3.2分（0.4%）表4列出了ABC算法获得的最成功结果的平均值和文献中针对每个问题组获得的最成功结果的平均值。6. 结论在这项研究中，一个新的解决方案VRPSDP建议使用ABC算法。所开发的算法运行为公知的相关基准问题，并将结果与迄今为止文献中最成功的结果进行比较。作为结果，已经观察到ABC算法适用于不同波动水平的组合优化问题，例如VRPSDP。ABC算法也产生近似的结果，其他元启发式方法。当分析应用程序的结果值时为了增加在现实生活中的物流领域的适用性，元启发式方法可以开发，它可以调度灵活的ARP模型与不同数量和容量的车辆，也可以产生动态的解决方案，在旅行中遇到的意外问题。此外，通过使用从物流公司获得的数据，并倾向于引用[1] 王志忠，基于粒子群算法的车辆路径优化问题研究，北京交通大学学报，2000。 操作员Res. 36（5）（2009）1693-1702。[2] D.L. Applegate ， W.J. Cook ， S. Dash ， D.S. Johnson ， A Practical Guide toDiscrete Optimization，Dynamic Programming，第7章，2014年，pp.44比47[3] M. Avci，S. Topaloglu，同时和混合取货和