多目标容量约束多分配枢纽选址问题的多算法比较研究

工程科学与技术，国际期刊29（2022）101032完整文章多目标容量约束多分配枢纽选址问题I_ brahim Demira，Berna Kirazb，Bella，Fatma Corut Erginaa土耳其伊斯坦布尔马尔马拉大学工程系计算机工程系b土耳其伊斯坦布尔苏丹穆罕默德·瓦基夫大学工程学院计算机工程系阿提奇莱因福奥文章历史记录：收到2021年2021年6月1日修订2021年6月19日接受在线预订2021年保留字：容量约束枢纽选址问题的元启发式算法多目标优化路由和网络设计A B S T R A C T多目标容量约束多分配枢纽选址问题（MOCMAHLP）是一类枢纽选址问题的变形，它涉及网络设计，既考虑枢纽的数量和位置，也考虑枢纽与辐条之间的连接，以及网络上的流路由。在这项研究中，我们提供了两个元启发式方法的基础上的非支配排序遗传算法（NSGA-II）和存档的多目标模拟退火方法（AMOSA）来解决MOCMAHLP。我们调整了基于AMOSA的方法来获得问题的可行解，并在该方法中开发了五种不同的邻域算子此外，基于NSGA-II的方法，我们开发了两个新的问题特定的变异算子。为了统计分析这两种算法的行为，我们在两个著名的数据集上进行了实验，即土耳其和澳大利亚邮政（AP）。超卷指标被用作性能指标来衡量这两种方法在给定数据集上的有效性 在实验研究中，进行了全面的测试，微调NSGA-II和AMOSA建议的邻域算子的突变类型。微调测试表明，对于NSGA-II，突变概率对土耳其数据集没有实际影响，而较低的突变概率对AP数据集稍好。此外，在基于AMOSA的邻域算子中，根据温度增加/删除特定数量的链接的邻域算子（NS-5）对于两个数据集的性能优于其他邻域在分析了两种算法的不同操作符后，我们的NSGA-II和AMOSA的方法之间的比较进行最佳设置。因此，我们得出结论，我们的算法都能够找到可行的解决方案的问题。此外，NSGA-II表现更好的较大，而AMOSA表现更好的较小规模的网络。©2021 Karabuk University. Elsevier B.V.的出版服务。这是CCBY-NC-ND许可证（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍轴辐式网络构成了一种主要由运输服务适应的分销网络。在轴辐式网络中，集线器是用于收集、处理和分配流的节点，而辐条是分配给集线器的集线器定位问题（HLP）涉及到定位集线器，分配辐条到集线器，并在网络中的每个节点对之间的路由流HLP有几种变体[19]。在本文中，我们处理的多目标容量限制的多重分配HLP。我们假设在这个问题中枢纽的数目是不确定的*通讯作者。电子邮件地址：bkiraz@fsm.edu.tr（B.Kiraz），fatma. marmara.edu.tr（F.CorutErgin）。定义和集线器没有完全互连。这两个目标是最小化成本建立轴辐式网络和最小化所需的最大旅行时间路由所有节点对之间的流量在这个问题中，必须确定枢纽节点的数量和位置，进行枢纽间和枢纽-辐条连接的网络设计，以及确定流量的路由多目标容量约束多分配枢纽选址问题（MOCMAHLP ）的数学模型和基于非支配排序遗传算法（NSGA-II）的基本元启发式方法可以在[11]中找到。与单目标优化问题类似，多目标优化问题也可以用精确方法求解.然而，对于NP完全问题，这些方法很难解决大规模系统另一方面，Meta启发式算法，如模拟退火，蚁群优化，https://doi.org/10.1016/j.jestch.2021.06.0122215-0986/©2021 Karabuk University.出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表工程科学与技术国际期刊杂志主页：www.elsevier.com/locate/jestchI_. 德米尔湾Kiraz和F.科鲁特·埃尔金工程科学与技术，国际期刊29（2022）1010322遗传算法是解决这些问题的有效方法[22模拟退火（SA）[21]是一种受金属退火过程启发的并行算法。模拟退火算法已成功地应用于许多组合优化问题，包括单目标和多目标问题[4，28，32]。文献[4]中有大量的多目标模拟退火方法。归档多目标模拟退火算法（AMOSA）[5]是多目标模拟退火算法的一种改进算法。它是一个单点搜索算法，利用档案，其中非支配的解决方案存储供以后使用。另一方面，NSGA-II是多目标优化问题最常用的遗传算法方法之一[22，27]。本文提出了基于NSGA-II和基于AMOSA的多目标优化算法，并对这些算法进行了实验选择这些算法是因为它们是组合优化中众所周知的多目标启发式方法。在MOCMAHLP中，有三个设计标准：（1）枢纽节点的数量在本研究中，对于NSGA-II和AMOSA，我们使用[11]中提出的解决方案表示，该解决方案为前两个设计标准提供了解决方案。此解决方案表示包含两个数组，一个用于集线器决策，另一个用于网络设计。对于最后一个设计标准，即，流的路由，应用A* 算法。为了探索新的解空间，变异算子用于NSGA-II和邻域算子用于AMOSA。在这项研究中，我们提出了两个新的特定问题的变异算子NSGA-II和五个特定问题的邻域算子AMOSA。为了验证算法的有效性，我们在土耳其和澳大利亚邮政（AP）数据集上进行了实验，以统计分析两种算法的行为我们研究了不同参数设置下算子的效果，以确定两种算法的最佳设置此外，在不同规模的网络上，对最佳设置下的两种算法的性能进行了检验。本文的主要贡献如下：针对NSGA-II提出了两种新的问题特异性变异算子，AMOSA适合于为MOCMAHLP找到可行的解决方案我们设计了五个特 定的邻 域算子的 问题， 并选 择性能 最好的邻 域算子 的AMOSA。这两种方法进行了全面的实验分析本文的其余部分组织如下：下一节提供了一个简短的文献综述的研究Meta选址和路由问题。第三节描述了本文所研究的多目标容量约束的多分配枢纽选址问题。在第4节中，详细介绍了所采用的启发式方法。实验设计和实验结果分别在第5节和第6节中给出。最后，第7节总结了本文的结论和未来的工作。2. 相关工作枢纽选址问题（HLP）是一个NP完全的组合优化问题[20];因此，许多元启发式在文献中已经提出了解决HLP的方法[9，12，13，15，19，25，30，34，35]。在本文中，我们专注于最近发表的模拟退火（SA）和进化算法为基础的方法的位置和路由问题。Geramianfar等人。[17]提出了一个拥挤情况下的多目标枢纽覆盖选址问题。 该问题涉及两个目标函数：（1）最小化总运输费用和（2）最小化总等待时间。将模拟退火算法应用于该问题，并与粒子群优化算法和NSGA-Ⅱ进行了比较。他们使用了四种不同的指标，即，质量度量、平均理想距离、多样性度量和间隔度量来比较算法的性能。基于结果，SA在质量度量方面产生了更好的性能;然而，在其他度量方面获得了类似的结果Alizadeh等人[2]提出了一个多目标模型，用于求解有容量约束的多分配枢纽最大覆盖问题，其目标是最大化枢纽覆盖，最小化枢纽的最大容量，最小化总费用。他们应用了两种多目标遗传算法，即NSGA-II和非支配排序遗传算法（NRGA）的问题。实验结果表明，NSGA-II在解的质量和计算时间方面优于NRGA。文献[1]提出了一种结合遗传算法和模拟退火算法的混合算法该混合算法是基于遗传算法，包括父选择，交叉和变异操作。然而，基于SA中的移动接受步骤来更新最佳解决方案总是接受改进的移动，而以一定概率接受非改进的移动。将该混合算法与遗传算法进行了比较。实验结果表明，该混合算法比遗传算法具有更好的性能.Rayat等人。[26]提出了一个考虑中断风险的双目标、多产品和多周期位置-库存-路由问题他们提出了一种基于归档多目标模拟退火（AMOSA）的算法来解决这个问题。在算法中，六个不同的数组被用来代表一个解决方案。该方法进行了比较，三个著名的多目标进化算法。结果表明，AMOSA在质量度量方面表现更好在文献[18]中，给出了双寡头市场中竞争性单分配和多分配HLP的数学模型。为了解决单分配和多分配情况下的问题，提出了一种基于模拟退火的方法。对于多分配SA，使用两个不同的交换算子来生成相邻解。另一方面，作者使用三种不同的操作符用于单个分配SA。实验结果表明，该方法能够在较短的时间内得到最优解。在文献[16]中，作者提出了两种模拟退火方法来解决有能力约束的定位-路由问题。在这两种方法中使用相同的初始化过程，邻域结构和多样化过程初始解采用贪婪随机化方法，将用户分配到最近的设施点。他们考虑了基于插入和交换移动的四种不同的邻域结构在多样化阶段，改变设施的状态（打开/关闭）。第一种方法还包括局部搜索过程。结果表明，所提出的方法产生更好的性能，根据目标函数和计算时间。Rathore等人。[25]提出了一种在模拟退火中使用基于多样化的学习来该方法利用基于多样性的学习邻域，●●●I_. 德米尔湾Kiraz和F.科鲁特·埃尔金工程科学与技术，国际期刊29（2022）1010323XXX1/2双头一8><一KP一hood结构以生成新的候选解。结果表明，所提出的方法能够找到更大的HLP实例的精确解。3. 多目标容量约束多分配枢纽选址问题在这项研究中，我们提出了元启发式技术来解决[11]中提出的多目标容量限制多分配枢纽选址问题（简称MOCMAHLP）。该问题被认为是一个双目标离散优化问题。在这个问题中，集线器的数量和位置、集线器级网络的设计（集线器之间的连接）以及辐条节点到集线器节点的分配（集线器和辐条之间的连接）与流的路由一起确定。问题的特点如下：该问题是一个离散选址问题。给出了网络中节点的集合。在优化过程开始时，没有预先确定要构建的集线器的数量利用HLP的多分配版本，即辐条可以连接到多个集线器。● 在建立中心时考虑到固定费用Fig. 1. 以集线器网络为例。并在网络中形成弧线。●最小值XFaCavx0xaaxadxax0不允许辐条之间的连接，即，的流动请求必须经由至少一个集线器路由一个uv一XX一uvu的vð1Þ集线器之间的图（即，网络（网络）不是一个网络。基本完成，前提是枢纽级网络形成þminimizemaxXkaZa一1/1 jixi2连通图● 每个节点都必须满足流量平衡约束。KP受TaAkp进入节点的总流量必须等于总流量流量离开它。所有集线器和弧都有容量限制。因此，在容量溢出的情况下，可以将起点-目的地对（称为商品）之间的需求分成几个包，使得其可以遵循不同的路径。图1示出了示例集线器网络。这个网络包括三个中心和七个辐条。两个辐条之间的路径包含三个部分：收集（辐条到集线器）、传输（集线器之间）和分发（集线器到辐条）。由于容量的限制，商品可以分成几个包装。如图所示，从节点2到节点10的商品被分成两个包裹：第一个和第二个包裹接着16xi6N3我F a6Q a8a2E104F a6Q h8小时2小时50分钟a2V电 压DkpDkk6pKP 6x avQ h;av- j k;8k70 6f k6F a8a 2 E2080对于每种商品k路径分别由绿色和蓝色表示由于问题的目标和特点是fk-Xfk¼Dk;如果v<$ik-D k;如果v ½jKð9Þ同样，在本研究中，我们考虑了[11].a2Vva一a2V- 100 V>：0; 否则设au和av是弧a2E的初始和终端节点;Fa;Ca和Ta分别是穿过弧a的流的总量、弧a上的递送的单位成本和在弧a上转移所需的时间;Ka是固定成本，Qa是弧a的容量;ik和jk分别是商品k的源节点和目的地节点;对于商品k;Dk是流的总需求，而这两个目标，在Eqs。（1）和（2）分别是在所有节点对之间路由流所需的总成本的最小化和最大旅行时间的最小化。总成本包括运输成本（即，收集、转移和分配成本的总和）以及建立枢纽和操作链路（ARC）的成本。Dkp 是包p的流量需求;fk是commod的流量约束条件在方程中给出（3）第一个约束（Eq.（3））确保在网络中建立至少一个集线器弧a上的ityk;jh为固定成本，Qh为枢纽容量h、v、a、d分别为托收、转帐、贴现的贴现系数;若使用弧a，则Za¼如果节点i是集线器，则xi1/4 1，否则为0;如果节点i是辐条，则x0i 1/41否则为0; A a 如果商品k的包装p处的流量为1/4，通过弧a，Za1/4，否则为0;Dkp 1/4n，其中06n6Dk。MOCMAHLP的数学公式如下：[11]：而第二和第三约束（等式10）是：（4）和（5））分别是弧和毂的容量约束。确定商品k的所有包装的流量需求之和相等到商品的总流动需求与下一个约束（方程。（6））。在Eq.（7）保证只有集线器用于路由需求和方程。（8）将弧A上的商品K的流量限制为小于穿过弧A的流量的总量。最后，在Eq.（9）加强流量平衡约束。●●●●N●●一一XI_. 德米尔湾Kiraz和F.科鲁特·埃尔金工程科学与技术，国际期刊29（2022）1010324FG×4. 解决MOCMAHLP问题的建议技术在这项研究中，存档的多目标模拟退火（AMOSA）[5]和非支配排序遗传算法（NSGA-II）[10]被用来解决MOCMAHLP。在本节中，这些算法的细节。这两种算法都考虑了相同的解表示和修复函数，并在相关小节中给出。此外，在评估新的候选解决方案，A* 算法应用于路由在两个算法。4.1. 解表示和约束处理本研究中使用了[11]中为MOCMAHLP设计的解表示。每个候选解使用两个长度等于网络中节点数的数组。用于中心决定的第一个数组包含0第二个数组称为链路决策数组，表示包括集线器间连接和辐条到集线器连接的网络设计。它是一种邻接列表表示，其中数组中的每个条目表示与相应节点相邻的节点列表图1给出了一个10节点网络的示例。该网络有三个枢纽（节点5、6和7）和七个辐条节点。该网络由图1和图2中给出的集线器和链路决策阵列表示。分别为2和3。如图2所示，对于中心节点，该值为1，对于辐条节点，该值为0 对于图中给出的链路决策数组， 三、为举例来说，的月6 条目代表的列表的节点（2; 4; 5;7; 9）与节点6相邻。[11]中提出的修复算子用于由算子生成的该修复算子由两部分组成，一部分用于枢纽决策阵列，另一部分用于链路决策阵列。在给定的网络中，必须至少有一个集线器。因此，如果在候选解的枢纽决策阵列中没有枢纽，则拒绝该枢纽，并创建另一个随机阵列另一方面，对于链路决策阵列可能发生五种不同的修复情况：（1）如果两个节点之间的链路没有相互建立，则将对应的链路添加到网络;（2）如果集线器不具有到任何其他集线器的连接，则建立到最近集线器的链路;（3）如果两个辐条节点连接，则删除它们之间的链路;（4）如果辐条节点没有连接到任何集线器，则添加到最近集线器的连接;（5）在断开网络的情况下，连接所得网络的连接组件中的最近集线器节点4.2. 基于AMOSA的方法本研究中提出的基于AMOSA[5]的算法利用存档来存储非支配解和聚类技术来保持多样性。AMOSA的参数如下：硬限制（HL）是档案中非支配解的最大数量;软限制（SL）是在聚类之前可以包括在档案中的解的最大数量;a是冷却速率;tmax和tmin分别是初始和最终温度值算法中给出了AMOSA算法的伪代码1. 该算法从存档初始化过程开始（第1行）。在该过程中，在生成多个大小为cSL的随机初始解之后，对每个解应用爬山法。然后，将非支配解存储在存档中以供以后使用。如果非支配解的数量超过HL，则通过聚类将存档的大小减少到HL。的溶液从存档中随机选择作为初始解决方案，并命名为当前解决方案（第2行）。对于每个温度值，集线器图二.图中给出的网络的中心决策阵列。1.一、图三.图中给出的网络的链路决策数组。1.一、当前解的判定阵列被扰动一次（行4），而链路判定阵列被相应的邻域结构扰动一定次数的迭代（行6），以产生候选解，并且在外部循环结束时温度值被降低（行13）。扰动后，修复函数应用于候选解，使解决方案可行。A* 算法应用于路由，然后，候选解决方案进行评估。根据[5]中定义的接受规则，候选解决方案要么被接受（并替换为当前解决方案），要么被拒绝。这些验收规则包括三种不同的情况：案例1. 当前解支配候选解：根据候选解在存档中的解之间的然后，以计算出的概率将候选解作为当前解.案例2. 当前解和候选解彼此不占优势：测试候选解和存档中的解的占优势状态：a) 如果档案中的许多解决方案支配候选解决方案，则候选解决方案被接受为当前解决方案，具有平均支配量的概率。b) 如果存档中没有解决方案支配候选解决方案，则候选解决方案将成为当前解决方案并插入存档中。如果存档中的解决方案的数量达到SL，则应用聚类以将解决方案的数量减少到HL。c) 如果候选解决方案在存档中的多个解决方案中占主导地位，则接受该候选解决方案并将其插入存档中。这些劣解将从存档中删除案例3. 当前解被候选解支配：测试候选解和存档中的解的支配状态：a) 如果候选解被档案中的多个解支配，则档案中与候选解具有最小支配差的解被选为当前解。否则，候选解决方案将成为当前解决方案。I_. 德米尔湾Kiraz和F.科鲁特·埃尔金工程科学与技术，国际期刊29（2022）1010325一半]，，ÞNNb) 如果档案中没有解决方案优于候选解决方案，则接受候选解决方案并将其插入档案中。如果存档中包含当前解决方案，则将其删除;否则，如果归档（archive size>SL），聚类应用于减少解HL的个数c) 如果候选解决方案在存档中的多个解决方案中占主导地位，则接受候选解决方案并将其插入存档中。这些劣解将从存档中删除。算法1基于AMOSA的伪代码解决方案1：初始化归档2：从存档中选择解决方案，即，当前解决方案3：当未达到4：将邻域结构应用于当前解的枢纽决策数组并生成候选解5：当未达到最大迭代次数时6：通过使用7：应用修复函数8：应用A* 算法进行布线9：评估候选解决方案10：根据选择规则11：需要时更新存档12：结束时13： 更新温度14：结束时4.2.1. 邻域结构解决方案表示由枢纽决策和链接决策阵列组成，因此，我们考虑每个阵列的不同类型的邻域结构。我们提出了一个邻域结构的枢纽决策阵列和五个不同的邻域结构的链接决策阵列。枢纽决策阵列的邻域结构选择一个随机节点。如果选定的节点是中心节点，则它将成为辐条节点，反之亦然。如果中心决策数组中只有一个中心，则会随机选取一个轮辐节点并将其转换为中心节点。下面列出了为链路决策阵列设计的五个特定于问题的邻域结构（NS）交换所有链接（NS-1）：此方法随机选择一个节点。如果所选节点是集线器，则还随机选择另一个集线器节点。如果解决方案中没有其他集线器，则不应用此方法。如果选定的节点是一个分支，则会选择另一个分支节点。在选择两个中心/辐射节点之后，交换它们的所有链路。添加/删除K个链接（NS-2）：在这种方法中，首先，我们决定是否以相等的概率添加或删除链接基于根据该决定，预定数量（K）的链路被随机添加/删除K个链接（NS-4）：该方法与添加/删除K个链接相同，除了在每次迭代时在预定范围（Kmin;Kmax）内随机确定K的值。根据温度添加/删除K链接（NS-5）：K值从K的最大值开始根据温度值减小。在该方法中，首先，计算最高温度和最低温度之间的不同温度值（由t变化表示）的数量：t变化量：t最大值-t最小值= 100000然后，计算不同K值的数量K变化量为最大值的1/4K-最小值的1/11 K最后，对于每i次迭代，K的值减1t改变12K变了也就是说，对于K的最大（最小）值，温度处于其最大（最小）值。4.3. 基于NSGA-II的方法在这项研究中，两个新的问题特定的变异算子的NSGA-II为基础的算法在[11]中介绍。在我们的NSGA-II算法中，初始种群是随机创建的。将上述A* 算法应用于路由的每个候选解，然后计算每个候选解的目标值该算法使用基本的遗传算法算子来生成新的解，即，二进制锦标赛选择，一点交叉，位变异和交换变异分别为枢纽决策阵列和链接决策阵列本文中的变异算子包括位变异和交换变异，采用非支配距离和拥挤距离排序方法进行个体选择.在本文提出的新的变异算子，即单链接变异和基于中心性的变异，该算子适用于枢纽决策阵列和链接决策阵列中的所有在单链接变异中，将位翻转变异应用于枢纽决策阵列，将轮辐改变为枢纽或枢纽改变为轮辐。 对于链路决策阵列，链路以相等的概率被添加到要变异的节点或从要变异的节点移除。但如果没有可用链路（即，如果要改变的节点是一个集线器，可以连接中心节点或分支节点;否则，中心节点必须另一方面，如果没有可用的链接可以从节点中删除，则将向该节点添加链接在基于中心性的突变中，基于节点的中心性（中心决策阵列上的突变）来改变节点的状态（轮辐到中心或中心到轮辐）。节点i的中心性计算如下：首先，节点i到所有其他节点的平均距离（Disti）计算如下：P N伊季区添加到候选解决方案中或从候选解决方案中移除的K的值可以基于数量根据经验确定距离i¼第1页ð13Þ网络中的节点自适应添加/删除K个链接（NS-3）：此方法从K的初始值开始。在每一步中，K个链接被添加到候选解决方案中或从候选解决方案中删除K的值其中distij是节点i和节点j之间的距离。然后，根据最小值-最大值标准化将值标准化。节点i的平均需求（Wi）计算为：P N文义志如果没有固定数量的iter的改进否则，它会减少。 此外，它允许变化在预定范围内（1/2K min;Kmax]）。Wi ¼第1页ð14Þ●●●●●I_. 德米尔湾Kiraz和F.科鲁特·埃尔金工程科学与技术，国际期刊29（2022）1010326我我我我其中wij是节点i和节点j之间的流量需求。W值也根据最小-最大归一化进行归一化。最后，节点i的中心性为：中心度;中心性2½0;2]15在基于中心性的变异中，对于枢纽决策阵列，如果要变异的节点是枢纽，则随机选择另一个枢纽这两个枢纽根据其中心值进行比较然后，具有较低中心性值的枢纽成为轮辐。类似地，如果要变异的节点是辐条，则随机选择另一个辐条，并且具有更高中心性值的节点被改变为枢纽。另一方面，在链路决策数组中，对于要变异的节点，随机选择两个可用节点该节点要么连接到这两个节点中较近的一个，要么与较远的一个断开连接。5. 实验装置在本节中，我们介绍了性能评估指标和实验研究中使用的数据集。在真正的帕累托前沿未知的进化多目标优化问题中，最广泛使用的性能评估指标是超体积指标[36]。因此，我们使用超体积比来评估我们的解决方案方法的性能。超体积比被计算为由所获得的帕累托前沿覆盖的面积与覆盖所有可能的目标值的面积的比率。在进行实验研究之前，我们对每个数据集执行了10次所提出的方法，用于100000个适应度评估计数。选择这5次运行中获得的最差目标作为超容量指标的参考在实验中，对于每个参数设置，我们进行了30次独立运行。平均和标准。Dev.结果表中的列分别是这30次运行的超体积的平均值和标准偏差值。这些表中给出的超体积值小于[11]中的超体积值，因为超体积指示器的大小主要取决于所选的参考点[7]。这两种算法都是在开源Java库中实现的，即MOEA框架。算法的源代码是公开的。1实验是在8 GB内存和Intel Core i7- 2600 K处理器的计算机上进行的。5.1. 数据集在实验研究中，我们使用了两个数据集，即澳大利亚邮政（AP）[14]和土耳其数据集。选择这些数据集是因为它们是枢纽位置文献中两个常用的数据集。数据集可从OR库中获得[6]。在土耳其数据集中，土耳其的81个城市被列为节点。数据集介绍了节点之间的距离和旅行时间，固定枢纽成本[29]，固定链路成本[3]和流量数据[8]。数据集中没有集线器和链路容量信息，因此我们使用[11]中定义的容量。为了生成每个城市的枢纽容量，使用相应城市的人口规模，而根据相应链路的距离和旅行时间生成链路容量。AP数据集包含澳大利亚的200个邮政区。数据集包括地区坐标、固定枢纽成本、枢纽容量和流量数据。节点之间的欧氏距离使用坐标计算，并且根据节点之间的距离计算行进时间（平均速度为第1https://github.com/MOEAFramework/MOEAFramework/pull/22790 km/h被认为是在土耳其的数据集）。固定链路成本和链路容量不包括在数据集中。由于距离和链路成本之间的直接相关性，固定链路成本被设置为节点之间的距离。最后计算链路容量as，节点和链路之间的总直接流量的乘积能力倍增器我们将固定枢纽成本乘数设置为1，成本乘数为10，总转移成本乘数为10- 7。这些值是根据初步实验的结果确定的。AP数据集最初是一个200节点的网络，并且可以从原始数据集导出不同大小的网络。对于所有规模的网络，链路容量乘数选择为100在本文中，在我们的算法中的操作的微调和选择，我们提出了100节点的AP数据集获得的计算结果。土耳其和美联社的数据集，用于收集、转移和分配的折扣因子的值分别被设置为v/41、a/4 0：9和d/41。6. 结果和讨论在本节中，我们报告并讨论了实验结果实验研究分三个阶段进行在第一阶段，进行了为NSGA-II方法设计的变异算子的性能比较（见第4.3节）。在第二阶段，评估邻域算子（见4.2节）对AMOSA性能的影响，在第三阶段，比较NSGA-II和AMOSA的最佳设置我们还对三种不同网络规模的方法进行了可扩展性分析6.1. NSGA-Ⅱ变异算子在这部分实验中，我们在NSGA-II中测试了三种不同的突变算子。这些算子包括交换所有链接变异（SALM），单链接变异（SLM）和基于中心性的变异（CBM）。我们对每个突变算子进行了不同的突变概率设置实验，如下所示：● SALM：0： 005; 0： 01; 0： 02; 0： 05; 0： 1; 0： 2● SLM：0： 01; 0： 05; 0： 1; 0： 15; 0： 2; 0： 3● CBM：0： 01; 0： 05; 0： 1; 0： 15; 0： 2; 0： 3SLM和CBM使用更高的突变概率，因为与SALM相比，它们为个体提供了非常小的变化。NSGA-II中的其他参数如[11]中所建议的那样设置：交叉概率为0： 8，枢纽决策阵列的变异概率为1=n，种群大小为200，适应度函数评估的最大数量为20000。表1呈现了针对具有不同突变概率的3个不同突变算子中的每一个获得的超体积值的平均值和标准偏差。所有测试都是针对土耳其和100节点AP数据集进行的。如前所述，对于每个突变类型的每个概率值，该算法用不同的种子执行30次。我们还进行了Tukey的诚实显着差异（HSD）事后检验，以查看突变概率之间是否存在任何统计学差异。通过对土耳其数据集结果的统计分析，我们可以可以说：（1）对于SALM，高于0： 02的突变率比较小的突变率产生更好的性能。但在这些较高的突变率之间没有统计学上的显著差异。(2)对于SLM，当变异率为0： 01时，算法的性能最差。另一方面，高于0： 01的突变率具有相同的性能。(3)对于CBM，只有突变率0： 1的性能优于突变率0：01，其他对的性能都差不多。I_. 德米尔湾Kiraz和F.科鲁特·埃尔金工程科学与技术，国际期刊29（2022）1010327表1在土耳其和100节点AP数据集上，通过具有各种突变概率值的突变算子获得的平均超体积值和标准差突变pm土耳其数据条目AP数据集平均STD.Dev.平均STD.Dev.Salm零点零五分0.66380.00040.60030.01090点 01分0.66390.00030.60220.0160零点零二分0.66410.00020.59750.0130零点零五分0.66420.00020.58800.01340： 10.66420.00020.57860.01270： 20.66430.00010.56590.0130SLM0点 01分0.66290.00150.60190.0127零点零五分0.66370.00140.59280.01510： 10.66390.00060.58540.0171零点十五分0.66390.00060.57680.01860： 20.66380.00070.57020.01610： 30.66370.00040.56270.0170CBM0点 01分0.65640.00820.61510.0120零点零五分0.66120.00560.62670.01390： 10.66170.00520.63450.0122零点十五分0.66120.00680.63770.01250： 20.66030.00670.63750.01220： 30.65960.00720.64330.0118每个操作员的最佳设置以粗体标记。对于土耳其数据集，通常会产生更高的超体积值，突变率也更高。然而，突变率对超体积值没有实际影响。另一方面，当我们解释100节点AP数据集的统计分析结果时，我们可以得出以下结论：（1）对于SALM，较高的突变率总是比较小的突变率提供较差的性能。然而，0： 005、 0： 01和0： 02的突变率之间没有统计学显著差异。(2)对于SLM，较小的变异概率比较高的变异概率获得稍好的性能。(3)对于CBM，更高的突变率产生更好的性能，并且高于0： 1的突变率之间没有显著差异。考虑到表中给出的超体积值，对于AP数据集，我们可以说SALM和SLM产生的结果略好，突变概率较小。然而，对于CBM，超体积值随着突变率的增加而增加。这可能是因为CBM导致解决方案的小变化从表中给出的结果和统计分析，我们可以得出结论，对于这个问题，突变概率对超体积值没有内在影响大多数突变率具有相似的性能。这很可能是因为我们在每次变异操作后应用的修复函数导致了不可行的解决方案。我们还应用了统计分析，使用Tukey的诚实显著差异（HSD）事后检验来比较三种突变类型。在土耳其数据集的统计分析中，我们比较了所有三种类型突变的突变率为0：1对于AP数据集，另一方面，使用突变率为0： 01的 SLM和SALM以及突变率为0： 3的CBM的结果当我们检查Tukey事后检验的结果 这种观察可以在图中看到。图4给出了NSGA-II中三种突变算子在土耳其数据集上的超体积值的箱形图。对于AP数据集，图5中给出了不同突变算子的超体积值的箱形图。在这种情况下，CBM比其他突变类型具有更高的超体积值。因此，我们在实验研究结束时使用CBM比较NSGA-II和AMOSA6.2. AMOSA中邻域算子的比较在这一部分中，我们在AMOSA中尝试了五种邻域操作：交换所有链接（NS-1），添加/删除K个链接（NS-2），adap-见图4。土耳其数据集上NSGA-II中不同突变算子统计比较的超体积值箱形图。图五.超体积值的箱形图，用于在AP数据集上对NSGA-II中的不同突变算子进行统计比较。表2AMOSA的参数设置参数值每个温度的迭代软限制100硬限制10C2a0： 9882tmin10-7tmax200主动添加/移除K个链路（NS-3）、随机添加/移除K个链路（NS-4）以及根据温度添加/移除K个链路（NS-5）。我们进行了一些实验，以确定每个邻域算子的最佳参数设置。对于所有邻域算子，我们I_. 德米尔湾Kiraz和F.科鲁特·埃尔金工程科学与技术，国际期刊29（2022）1010328¼¼¼表3通过NS-2获得的平均超容值和标准差，土耳其和AP数据集上的KK土耳其数据条目AP数据条目表4通过土耳其和AP数据集NS土耳其数据条目AP数据条目平均STD.Dev.平均STD.Dev.平均STD.Dev.平均STD.Dev.10.57730.13430.48740.1453NS-10.40360.25340.17140.267750.62140.02300.58430.0551NS-20.61060.02750.59940.0463100.61060.02750.59940.0463NS-30.57710.10480.47590.1478150.59340.10730.58260.0375NS-40.60580.07990.60600.0440200.60780.06390.59290.0400NS-50.61770.03240.62390.0508300.59810.06570.57680.0373考虑表2中给出的AMOSA的参数设置。参数设置是根据[5]中建议的设置，根据一些初步实验确定的。对于NS-2，我们使用6个K值进行实验：1、 5、 10、 15、 20和30。表3显示了NS-2在土耳其和100节点AP数据集上使用不同K值的结果。结果表明，对于土耳其数据集，不同K值之间的差异不具有统计学意义。另一方面，对于AP数据集，除了K的设置之外，大多数情况下没有统计学显著差异1.我们可以得出结论，对参数不是很敏感。因此，我们使用K10，它为其余实验的两个数据集提供了可接受的性能。根据上一部分获得的结果（见表3），我们为NS-3、NS-4和NS-5设置kmin¼ 1和kmax¼20。此外，NS-3以k10的初始值开始。表4提供了土耳其和AP数据集上邻域结构的平均超体积结果和标准差NS- 1产生最差的性能为两个数据集，而最好的性能时，NS-5被用作邻域结构。图6显示了土耳其数据集上不同邻域算子的箱形图。基于土耳其数据集的统计结果，可以说：（1）NS-1明显优于所有其他方法。(2)在其余的邻域结构（NS-2到NS-5）中，NS-5似乎比其他邻域结构产生更好的结果;然而，性能差异在统计学上并不显著。另一方面，对于AP数据集，我们可以说：(1) NS-1再次成为性能最差的邻域结构。(2) NS-3的表现明显差于NS-2、NS-4和NS-5。(3) NS-2、NS-4和NS-5的结果之间没有统计学显著差异该结果被示出为图7中给出的超体积值的箱形图。如前所述，NS-5为两个数据集提供了更好的性能。在搜索开始时，NS-5以最高的K值会导致网络中的更多变化，从而导致多样化。在搜索过程中，降低K值（网络中的变化较小）提供了强化。这是NS-5成功的主要原因6.3. NSGA-Ⅱ与AMOSA在这一部分中，我们将NSGA-II和AMOSA的性能与前面章节中提供的最佳参数设置进行比较。在此基础上，选择概率为0： 2的SALM作为NSGA-II的变异算子，NS-5作为AMOSA的邻域结构。对另一方面，对于AP数据集，在AMOSA和NSGA-II中分别选择概率为0：3的NS-5和CBM。两个数据集的相应结果见表5。此外，图8显示了AP和土耳其语见图6。土耳其数据集上AMOSA中不同邻域算子的统计比较的超体积值箱形图。见图7。AMOSA中AP数据集上不同邻域算子的统计比较的超体积值箱形图。表5AMOSA和NSGA-II在土耳其和AP数据集上获得的平均超体积值和标准差Algorithms Turkish data set AP data set平均STD.Dev.平均STD.Dev.NSGA-II0.66430.00010.64330.0118AMOSA0.61770.03240.62390.0508数据集。基于结果，可以看出，NSGA-II的性能优于AMOSA。图9中给出了一个帕累托最优解的可视化，表示在基于AMOSA的方法产生的土耳其数据集上具有所有中心到中心和中心到辐射连接的网络。如图所示，枢纽被选为（伊斯坦布尔、安卡拉和迪亚巴克），它们是土耳其不同地理区域（马尔马拉、安纳托利亚中部和在数据集中，注意到东部城市的大部分流量都流向土耳其西部。因此，在该解决方案中，土耳其东部的城市大多连接到该解决方案中的两个或更多个枢纽作为实验研究的最后一部分，我们研究了所提出的方法在AP数据集上的可扩展性。我们使用不同数量的节点进行实验：50; 100;200。图图10呈现了用于分析节点数量对性能的影响的结果的具有误差条的条形图。结果表明，对于50节点的实