《Swarm and Evolutionary Computation》：Learning to sample in variable neighborhood search algorithm for urban cable routing optimization
编辑推荐：
城市地下电缆建设对于提升电网可靠性至关重要，但高昂的建设成本要求进行系统性优化。受道路网络基础设施约束，该优化问题不仅要考虑变电站之间的连通关系，还需考虑沿道路网络的具体路由策略，构成大规模双层组合优化（Combinatorial Optimization P
城市地下电缆建设对于提升电网可靠性至关重要，但高昂的建设成本要求进行系统性优化。受道路网络基础设施约束，该优化问题不仅要考虑变电站之间的连通关系，还需考虑沿道路网络的具体路由策略，构成大规模双层组合优化（Combinatorial Optimization Problem, COP）问题。传统研究对具体路由子问题关注不足，且算法设计过于简单，难以应对大规模组合优化，使得这一复杂优化挑战仍有较大提升空间。为应对巨大的组合搜索空间，研究人员提出了一种学习辅助变邻域搜索（Learning-assisted Variable Neighborhood Search, L-VNS）算法，集成了四个关键组件。首先，一个专注于上层连通性子问题的辅助任务，通过采用混合遗传搜索（Hybrid Genetic Search, HGS）进行连接优化和A*算法进行详细路径路由，生成高质量初始解。随后，该算法利用配备三种互补算子的变邻域搜索迭代优化连通拓扑。一个多智能体深度强化学习（Deep Reinforcement Learning, DRL）模块通过联合编码上层连通模式和下层路由结构，自适应引导概率邻域采样，有效利用问题结构。最后，一个改进的A*算子重新规划受邻域修改影响的下层路径，以确保可行性和解的完整性。在12个基准实例和3个GIS导出实例上的综合实验证明了L-VNS的优越性，相比代表性方法实现了0.92%—73.72%的总建设成本降低。消融研究和敏感性分析进一步验证了所提算法的有效性和鲁棒性。
这篇论文发表在《Swarm and Evolutionary Computation》期刊上，研究主题为城市地下电缆路由优化问题，提出了一种学习辅助变邻域搜索（L-VNS）算法。
## 一、研究背景与问题
随着经济发展和可靠性要求的提高，越来越多的城市计划在其核心区域全面将传统架空线路替换为地下电缆，以减轻台风、冰暴等极端天气事件的影响。然而，鉴于该举措涉及的巨大成本，从零开始以经济且全面的方式系统规划区域电缆路由成为一个关键的优化挑战。在城市配电系统中，从110/10 kV主变电站（即高压变电站）经过10 kV馈线到10/0.4 kV配电变压器（即中压变电站）的 segments 构成中压配电网（Medium-Voltage Distribution Network, MV DN）。相关电缆基础设施通常采用闭环馈线配置、开环运行的设计，使得在需要时可以从多个电源进行反向供电，支持灵活切换并在任何单故障N?1条件下保持正常服务连续性，从而 compare 增强可靠性和运行弹性。
电缆路由问题通常被建模为双层组合优化问题，其中上层问题寻求优化变电站之间的互连拓扑，而下层问题则确定给定连通配置决策后的详细电缆路由路径。与风电场和农村地区的电缆路由挑战不同，城市电缆只能安装在道路下方而不能穿过现有建筑物。这一限制使决策复杂化体现在两个关键方面：一是电缆长度考量，变电站之间馈线长度不能直接用欧几里得距离计算，而是取决于严格沿道路的具体电缆路径；二是通过电缆重叠实现成本降低，建设成本不仅包括电缆采购成本，还包括更为昂贵的道路沟槽开挖成本。因此，两个变电站之间的最短路径路由不一定产生最低的总建设成本。在许多情况下，沿同一路段平行部署多条馈线可以通过重叠降低总成本，即使这会增加安装的电缆总长度。这些因素使问题变得极为复杂：决策空间从2
Ns2扩展到2
(Nr+Ns)2，其中Ns为变电站数量，Nr为道路交叉口数量，通常Nr比Ns高出一到两个数量级。
尽管电缆路由问题已有数十年的研究，但大多数研究主要集中在设备之间的连接关系上，通过仅基于地理坐标间的欧几里得距离简化电缆长度的计算。此类简化在海上风电场和老城区等较不拥挤的环境中较为典型，大大降低了问题求解难度。然而，这种简化在城市中不合理，因为电缆只允许在道路下铺设。已有研究进一步在优化电缆路由时考虑了地理信息系统（Geographic Information System, GIS），但道路信息的纳入显著复杂化了问题，使得精确规划方法难以直接应对。此外，当前算法设计存在精度不足的问题，主要依赖多阶段分解策略与简单启发式集成，表现出过度贪婪性，限制了优化精度，尤其对于大规模实例。同时，现有前沿搜索算法主要强调邻域算子设计或参数调优，缺乏有效的搜索空间缩减策略，而这对解决具有指数级大规模搜索空间的双层组合优化问题具有重要价值。
## 二、主要技术方法
该研究所用样本队列来源包括：12个不同规模的基准实例和3个基于真实GIS数据导出的实例。主要关键技术方法包括：（1）混合遗传搜索（HGS）结合A*算法的辅助任务初始化，生成高质量可行初始解；（2）上层变邻域搜索（U-VNS）模块，配备三种互补邻域算子（破坏算子、馈线内2-opt算子、馈线间2-opt算子）；（3）多智能体深度强化学习（DRL）模块，三个预训练智能体分别对应上述三种邻域算子，基于当前解状态计算位置概率向量，以知识驱动的策略采样替代随机采样；（4）改进的A*重规划模块，考虑沟槽共享经济性，对受邻域修改影响的下层路径进行增量式重规划。
## 三、研究结果
**上层辅助任务生成初始解**：研究人员将上层连通性子问题作为辅助任务，采用HGS算法迭代优化获得仅含上层信息的解，随后使用改进A*算法确定具体电缆路由路径，从而获得高质量可行初始解。
**上层变邻域搜索优化连通拓扑**：从初始解出发，L-VNS利用配备三种邻域算子的变邻域搜索迭代优化变电站互连：破坏算子通过移除并重新插入馈线段实现拓扑重构，馈线内2-opt算子在单条馈线内部进行边交换优化路径顺序，馈线间2-opt算子在不同馈线之间交换边以优化全局拓扑。算子选择和破坏范围大小基于历史性能指标和停滞程度自适应调整。
**多智能体DRL引导邻域采样**：三个预训练的DRL智能体分别对应上述三种邻域算子，计算基于位置的邻域操作概率向量。这些概率向量指导概率采样生成邻域范围，以知识驱动的策略选择替代均匀随机探索，有效利用问题结构信息。
**下层A*重规划确保可行性**：邻域探索后，改进A*算子重规划受邻域修改影响的下层路径，通过显式建模沟槽共享经济性确保结果解的可行性和完整性。
**有效性比较实验**：在12个基准实例和3个GIS导出实例上，L-VNS相比前沿对比算法实现0.92%—73.72%的成本降低。统计显著性检验表明L-VNS在绝大多数实例上显著优于基准算法。
**消融实验**：分别移除DRL模块、辅助任务初始化模块以及将改进A*替换为标准A*的变体实验表明，各组件均对整体性能有显著贡献，完整L-VNS框架具有明显优势。
**敏感性分析**：针对不同参数设置（如DRL采样温度、邻域搜索迭代次数等）的系统性测试验证了算法在不同配置下的鲁棒性。
## 四、讨论与结论
从方法论角度，城巿地下电缆路由的关键难点在于连通性决策与道路约束路径实现之间的强双层耦合性。L-VNS通过以下方式应对：通过辅助上层任务生成高质量连通性"锚点"；利用邻域转移的局部性避免完整的下层重新优化；通过改进A*显式建模沟槽共享经济性。该研究的贡献在于：将城市电缆路由问题建模为双层优化框架；构建保留必要约束的辅助优化任务；开发双层邻域搜索框架减少冗余下层计算；集成多智能体DRL模块以知识驱动方式引导邻域采样。
研究人员得出结论：该工作通过显式考虑道路约束路由和溶槽共享成本节约，将城市电缆路由问题建模为双层优化框架，提出L-VNS算法层次化优化变电站连通性和详细电缆路径。框架集成四个关键组件：基于辅助任务的初始化获得高质量初始解、变邻域搜索进行连通性优化、多智能体深度强化学习引导策略性邻域采样、改进A*重规划确保解的完整性和可行性。全面实验验证了L-VNS的有效性和鲁棒性，为城市配电网基础设施规划提供了高效的优化工具。
