基于人工蜂群算法与自适应大邻域搜索的方法在星环网络设计问题中的应用

《Applied Soft Computing》：Artificial bee colony and adaptive large neighborhood search based approaches for the star-ring network design problem

　　苏达卡尔·奇蒂马达|文卡特什·潘迪里，计算机科学与工程系，混合智能实验室

摘要
本文提出了一种新的网络设计问题变体，即星环网络设计问题（SRNDP）。这是一种两级网络设计问题，第一级是通过星形拓扑将中心枢纽与其他枢纽相连，第二级是通过环形拓扑将每个枢纽与非枢纽相连，从而形成多个不相交的环。SRNDP的目标是最小化上述两级结构所需的总成本（即所有边成本之和）。该问题在电信、交通和物流等多个领域都有应用。为了解决SRNDP问题，我们提出了两种元启发式方法，第一种是基于群体智能的方法，即人工蜂群算法（ABC），另一种则基于自适应大邻域搜索算法（ALNS）。在所提出的ABC方法中，我们设计了四种基于特定问题的局部搜索策略，包括交换、重新定位、置换和2-opt操作。而在所提出的ALNS方法中，则根据问题特点设计了三种破坏操作和两种修复操作。通过标准TSPLIB实例对这两种方法的性能进行了测试。计算结果及详细分析表明了所提方法的有效性。尤其是ALNS在解决方案质量和计算时间方面始终优于ABC，在所有基准实例中平均成本降低了约14.46%。通过威尔科克森符号秩检验进行的统计验证进一步证实，ALNS所带来的改进具有统计学显著性。

引言
一些组合优化问题可以转化为网络设计问题（NDP）。一般来说，NDP是在给定约束条件下寻找无向图的最优子图。文献中一些著名的NDP问题包括旅行商问题（TSP）和最小生成树问题（MSTP）[1]。TSP和MSTP可归类为单级NDP问题。TSP是一种具有环形拓扑的NDP问题，而MSTP则是一种具有树形拓扑的NDP问题。本文介绍了一种两级NDP问题，即星环网络设计问题（SRNDP）。与TSP和MSTP不同，SRNDP包含两个层级。第一级是通过星形拓扑将中心枢纽与其他枢纽相连，第二级则是通过环形拓扑将每个枢纽与剩余的非枢纽相连，从而形成多个不相交的环。给定一个包含节点的图，以及中心枢纽、预定义的枢纽数量、预定义的环容量以及每对节点之间的距离/边成本，SRNDP的任务是从给定的节点中选出若干个枢纽（不包括中心枢纽），并通过星形拓扑将它们与中心枢纽相连，作为第一级的内容。在第二级中，这些枢纽各自通过环形拓扑与其他非枢纽相连，从而形成多个不相交的环。表示环的容量，即一个环中所含节点数不能超过该值。SRNDP的目标是最小化上述两级结构中的总成本，也就是边成本之和。相比单级NDP，这种两级NDP具有更大的优势，包括更好的可扩展性、更高的单点故障容忍度以及更优的成本。图1展示了在包含29个节点的bayg29实例上SRNDP问题的解。图1(a)中，中心枢纽用红色方块表示，其余节点用黑色点表示；图1(b)则展示了一个可行的SRNDP解，其中选出的枢纽用绿色方块表示，非枢纽用蓝色点表示。提出SRNDP问题的灵感来源于Andrade等人的研究[2]，他们提出了多仓库多旅行商问题（-IMDMTSP）。对于一组城市，-IMDMTSP的任务是选出若干个仓库，旅行商从这些仓库出发并返回，访问其他城市。每个城市只能被访问一次。这些仓库之间还需要通过环形拓扑连接，称为内圈，而每个旅行商的行程也构成一个环，称为外圈。-IMDMTSP的目标是最小化内外圈的总成本。本质上，-IMDMTSP也是一个在两个层级上都应用环形拓扑的两级问题。尽管-IMDMTSP和SRNDP在结构上具有相似性，但它们的拓扑组成有所不同。SRNDP的结构如下：第一级（枢纽的星形拓扑）：星形拓扑确保了中心枢纽与其余枢纽之间的连通性。第二级（非枢纽的环形拓扑）：第二级的环形拓扑则为非枢纽形成了局部环结构。除了中心枢纽外，每个枢纽都应与恰好一个环相连，从而形成多个不相交的环。SRNDP在需要从中心枢纽快速向其他枢纽传输信息或进行通信时具有优势，因为它们通过星形拓扑直接相连。第二级的环则具备单链路故障容忍能力。不过SRNDP也存在一些局限性，尤其是在中心枢纽与其他枢纽之间发生故障时。SRNDP与类似-IMDMTSP的两级路由问题相关，因为它既涉及枢纽选择，又涉及环的容量问题。由于其特定的拓扑结构，以及存在固定的中心枢纽、所有枢纽之间的星形连接和非枢纽之间的环形连接，其决策结构也有所不同。这种集中式结构将枢纽选择、环的可行性以及整体连通性联系在一起，带来了传统两级路由模型所没有的新交互模式，适用于那些需要通过中心枢纽进行传输或中转的应用场景。不过，关于SRNDP的理论研究仍有很大空间，还需要为其提出精确的数学建模方法。在设计强大的环形网络以应对单链路故障等导致的通信故障方面，这一问题具有重要的应用价值。根据Andrade等人的研究[2]，该问题也与那些需要跨越多个层级运行的运输网络十分相似，而这些网络各自都面临诸如运输规定、车辆类型和服务水平协议等多种约束。据作者所知，这是第一篇探讨星环网络设计问题（SRNDP）的论文。与之密切相关的问题是-IMDMTSP[2]，而NDP的应用则由[1]等人进行了研究，此外，调度、网络、路由以及TSP的各类变体等问题也具有类似特征[3]等。关于基于TSP的调度和优化问题的元启发式算法的综述进一步凸显了人们对混合式及针对特定问题的启发式方法的日益关注[4]。最近，Wen等人[5]提出了一种拓扑对齐策略，用于解决异构多无人机配送问题（HD-DPP），这是一种路由问题的变体，旨在协调一架大型无人机，让它派遣多架小型无人机到各个子区域，由这些小型无人机负责包裹的配送和取回任务。该问题被构建为一个开放式的两级路由和网络设计问题。此外，Ali Ala等人[6]提出了一种混合整数线性规划方法，用于解决血液供应链网络设计问题，该方法旨在在减少血液制品运输过程中所需固定和临时设施的成本的同时，尽量降低供应短缺的情况。根据Kubat和Smith的研究[7]，在电信领域，网络设计问题旨在最小化整个网络的互连成本，在光纤到户（FTTH）、无源光网络（PONs）以及5G网络等应用中，具备最优布线成本且能保持不间断通信的架构尤为重要。这正是SRNDP的一个应用场景。因此，SRNDP在确保系统具备抗单点故障能力方面也发挥着关键作用，比如在光纤链路出现故障时，仍能以最低的布线成本保持通信的顺畅。已有许多关于SRNDP的研究，涵盖了具有容量限制、约束条件、动态车辆路径规划以及路由问题等不同场景下的网络设计问题[8]、[9]、[10]。Koubaa等人[11]将多机器人巡逻问题建模为多仓库多旅行商问题（MD-MTSP）。这种方法对于各种移动机器人应用尤为适用，能够帮助实现多个仓库和目的地之间的高效任务分配与协调。他们为那些需要反复访问一组目标地点并返回初始位置的自主机器人设计了一种分布式解决方案，其目标是在不同条件下最小化总行驶距离、最大行程长度以及目标重叠程度。该方法包括四个阶段：(1)目标分配，(2)路线规划，(3)冲突解决，(4)方案优化。为了设计出能够解决像SRNDP这类问题的算法，需要考虑多个方面的因素。算法的各个组成部分必须针对具体问题进行设计，同时还要避免陷入局部最优解，能够高效地收敛到最优解。在这方面，一些近期研究提出了多种高效的元启发式方法，用于解决复杂的优化问题，包括旅行商问题[4]、[12]、[13]、[14]，最小顶点覆盖问题[15]，逻辑综合问题[16]以及电路优化问题[17]。在本文中，我们提出了两种元启发式方法，分别是基于人工蜂群算法（ABC）和自适应大邻域搜索算法（ALNS）的方法。这两种方法的各个组成部分都是根据SRNDP问题的特点来设计的。选择ABC和ALNS是因为它们符合SRNDP的结构特征。SRNDP的可行解取决于枢纽的选择、根据环的容量来确定非枢纽的分配方式，以及每个环内节点的排序/排列方式，即便是很小的变化都可能对总成本产生显著影响。ALNS的破坏与修复机制非常适合SRNDP的结构，它能够通过删除和重新插入节点来修改解决方案的某些部分，从而有效地探索不同的环结构。同样，ABC也为结合分配和排序决策与针对特定问题的局部搜索操作提供了灵活的框架，有助于优化环的排列方式，因此非常适用于处理SRNDP中那些紧密关联的决策问题。我们使用TSPLIB的基准实例对所提方法的性能进行了评估。计算结果表明，无论是在解决方案质量还是计算时间方面，ALNS都优于ABC。本文的结构如下：第2节对SRNDP问题给出了正式的定义。第3节介绍了为解决SRNDP问题而提出的ABC方法，第4节则介绍了ALNS方法。第5节讨论了在基准实例上的计算结果。最后，第6节总结了本文的主要内容，并提出了未来研究的方向。

问题定义
SRNDP问题的正式定义如下。给定一个完整的无向带权图，其节点集为，边集为，其中节点的编号从开始，表示的元素个数为（即）。每条连接两个顶点的边都对应一个权重。此外，还给定了中心枢纽、包括中心枢纽在内的枢纽总数以及环的容量。SRNDP问题需要解决以下任务：确定一个由节点组成的子集，即和，满足给定的条件。

用于SRNDP问题的人工蜂群算法
本节概述了为解决SRNDP问题而提出的人工蜂群算法（ABC）的完整结构。ABC是一种极为强大的基于群体的元启发式方法，最初由karaboga在2005年提出，其灵感来源于蜜蜂的觅食行为。该算法模仿了蜜蜂如何分工协作，高效地寻找食物来源。这种有趣的自然现象被加以利用，用于解决各种现实世界的工程问题[19]。

用于SRNDP问题的自适应大邻域搜索算法
自适应大邻域搜索算法（ALNS）最初由Ropke和Pisinger在2024年提出，它已成为解决复杂组合优化问题的强大工具。该算法在对基本的大邻域搜索算法（LNS）[25]进行改进，解决了其一个主要缺陷，即过度依赖单一的破坏与修复策略。ALNS并非依赖固定的破坏与修复流程，而是采用了多种相互竞争的破坏与修复算法，每种算法都有相应的计算结果。为给所提出的ABC算法和ALNS方法提供更广泛的实证依据，本文采用遗传算法作为代表性的进化算法基准，并在后续小节中进行探讨。

结论
在本文中，我们提出了一种新的问题，即星环网络设计问题（SRNDP），它是网络设计问题的一个变体。SRNDP属于两级网络设计问题，第一级是通过星型拓扑将中心节点与其他节点相连，第二级则是通过环型拓扑将每个节点与非节点相连。针对SRNDP，我们已经提出了两种元启发式算法，即人工蜂群算法（ABC）和自适应大邻域搜索算法。

CRediT作者贡献说明
Sudhakar Chittimadha：撰写——初稿、可视化、验证、软件、方法论、研究、概念设计。Venkatesh Pandiri：撰写——审阅与编辑、验证、监督、软件、方法论、研究、资金获取、概念设计。

利益冲突声明
作者声明不存在任何可能影响本文所述工作的已知财务利益或个人关系。

致谢
第二作者衷心感谢印度科学与工程研究委员会（SERB）提供的启动研究资助，资助编号为SRG/2021/002235。