当前位置：首页 > news >正文

2026年ASOC SCI2区TOP，基于人工蜂群算法和自适应大邻域搜索的星环网络设计问题求解方法，深度解析+性能实测

news 2026/5/12 8:38:47

1.摘要

本文提出了星环网络设计问题（SRNDP），其结构为两层网络，上层采用星型连接中心枢纽与各枢纽，下层通过环形结构将枢纽与非枢纽连接，形成多个不相交的环，目标是最小化整个网络的总成本。针对该问题，本文提出了两种元启发式算法：人工蜂群算法（ABC）和自适应大邻域搜索（ALNS）。ABC结合了四种局部搜索策略（交换、重定位、互换、2-opt），ALNS设计了三种破坏算子和两种修复算子。

2.问题定义

SRNDP问题在一个完全图G = ( V , E ) G=(V,E)G=(V,E)上求解，图中每条边都有一个正权重。给定中心枢纽( h c ∈ V ) (hc\in V)(hc∈V)，枢纽数量( k ≤ n ) (k\leq n)(k≤n)及环的容量( C ) (C)(C)，目标是选择枢纽并设计网络结构，使得成本最小化
∑ e ∈ E [ S ] w e + ∑ i = 1 k − 1 ∑ e ∈ E [ R i ] w e \sum_{e\in E[S]}w_e+\sum_{i=1}^{k-1}\sum_{e\in E[R_i]}w_ee∈E[S]∑we+i=1∑k−1e∈E[Ri]∑we

其中，E [ S ] E[S]E[S]和E [ R i ] E[Ri]E[Ri]分别是星型拓扑和第i ii个环的边集，we 是边e ee的权重。

k = 1 k= 1k=1时，问题变为TSP。
k = 2 k=2k=2时，星型包含一条边，连接两个节点。
k = n k= nk=n时，只有星型存在，所有环为空。

3. ABC for SRNDP

SRNDP的搜索空间由三部分组成：

星型拓扑（C1）：
C 1 = ( n − 1 k − 1 ) C1 = \binom{n-1}{k-1}C1=(k−1n−1)
表示从n − 1 n-1n−1个节点中选择k − 1 k-1k−1个枢纽，确定星型拓扑的结构。
环分配（C2）：
C 2 = ( k − 1 ) n − k C2 = (k-1)^{n-k}C2=(k−1)n−k
每个非枢纽节点必须分配给一个枢纽，所有可能的分配方式为( k − 1 ) n − k (k-1)^{n-k}(k−1)n−k，其中n − k n-kn−k是非枢纽节点的数量。
环内排列（C3）：
C 3 = ∏ j = 1 k − 1 ( r j − 1 ) ! C3 = \prod_{j=1}^{k-1} (r_j - 1)!C3=j=1∏k−1(rj−1)!
在每个环中，枢纽节点是哈密顿回路的起始和终止节点，其他r j − 1 r_j - 1rj−1个节点可以在( r j − 1 ) ! (r_j - 1)!(rj−1)!种方式排列。

SRNDP的总搜索空间大小C α C\alphaCα为：
C α = ( n − 1 k − 1 ) ⋅ ( k − 1 ) n − k ⋅ ∏ j = 1 k − 1 ( r j − 1 ) ! C\alpha = \binom{n-1}{k-1} \cdot (k-1)^{n-k} \cdot \prod_{j=1}^{k-1} (r_j - 1)!Cα=(k−1n−1)⋅(k−1)n−k⋅j=1∏k−1(rj−1)!

初始解决方案生成

SRNDP初始解生成算法首先随机选择k − 1 k-1k−1个枢纽节点并与中心枢纽连接形成星型拓扑，使用增量最小成本启发式方法将剩余的非枢纽节点分配到每个环，确保环的容量不超过c cc。

生成邻域解

SRNDP通过四种局部搜索算子（交换、重定位、互换和2-opt）生成邻域解：

交换：交换同一环内两个非枢纽节点的位置，时间复杂度为O ( ( k − 1 ) ∗ C 2 ) O((k-1)^*C^2)O((k−1)∗C2)。
重定位：移除非枢纽节点并重新插入到环中最佳位置，时间复杂度为O ( ( k − 1 ) ∗ C 2 ) O((k-1)^*C^2)O((k−1)∗C2)。
互换：交换不同环中的节点，时间复杂度为O ( ( n − k ) 2 ) O((n-k)^2)O((n−k)2)。
2-opt: 移除环中的两条边并重新连接，时间复杂度为O ( ( k − 1 ) ∗ C 2 ) O((k-1)^*C^2)O((k−1)∗C2)。

4.ALNS for SRNDP

ALNS通过多个销毁和修复算子（随机移除、Shaw移除、最差移除）进行迭代优化，并通过SA接受准则控制探索过程。

销毁阶段：采用三种销毁算子(随机、Shaw、最差移除)，根据适应性权重选择操作，销毁的时间复杂度为O ( n 2 ) O(n^2)O(n2)。
修复阶段：使用贪心算子根据最低成本插入策略修复解，修复阶段的时间复杂度也是O ( n 2 ) O(n^2)O(n2)。
接受准则：结合模拟退火机制，有时接受较差的解以避免陷入局部最优。温度在每次迭代后降温，控制搜索范围。

5.结果展示

6.参考文献

[1] Chittimadha S, Pandiri V. Artificial bee colony and adaptive large neighborhood search based approaches for the star-ring network design problem[J]. Applied Soft Computing, 2026: 114962.