[Paper] 学习辅助的多算子可变邻域搜索用于城市电缆路由

Source: arXiv - 2512.19321v1

概述

城市地下电缆布线是一个高风险的规划问题：城市需要可靠的电力分配，但开挖新管道成本高昂，并且受到现有道路网络的严格限制。本文将该任务重新表述为连通性‑路径协同优化问题，并提出了一种**学习辅助多算子可变邻域搜索（L‑MVNS）**算法，该算法能够显著降低施工成本——相较于以往方法大约降低30‑50%——同时在大规模、真实的城市布局下仍保持求解过程的稳定性。

关键贡献

• 统一问题表述，同时优化变电站连通性（需要链接的节点）和电缆的精确几何路径。
• 混合初始解生成器：结合用于连通性的 Hybrid Genetic Search (HGS) 与用于可行路径的 A* 规划器，生成高质量的起始点。
• 多操作符可变邻域搜索 (MVNS) 框架，包括三种互补的破坏操作符、改进的 A* 修复操作符以及自适应邻域规模控制器。
• 深度强化学习 (DRL) 代理，学习在搜索过程中优先考虑最有前景的邻域，将 MVNS 转化为学习辅助的 L‑MVNS。
• 标准化、可扩展的基准套件，用于城市电缆布线，实现从小规模到城市规模实例的可复现评估。
• 广泛的实证验证，显示相较于最先进的启发式算法成本降低 30‑50%，且 L‑MVNS 在更大实例上带来额外收益并具有更好的解的稳定性。

方法论

1. 问题建模

   • 将城市地图抽象为平面图，顶点代表道路交叉口，边代表可能的电缆走廊。
   • 定义两个耦合的子问题：
     • 连通性 – 决定哪些变电站（或需求节点）必须相互连接。
     • 路径规划 – 为每条选定的连接寻找具体路线，遵循道路布局约束并避免冲突。

2. 辅助初始解任务

   • 使用 Hybrid Genetic Search (HGS) 通过针对网络拓扑定制的交叉/变异算子进化候选连通图。
   • 对每个连通候选，采用 A* 最短路径搜索（并加入地下设施可行性检查）生成具体路由。
   • 将最佳可行配对作为主搜索的种子。

3. 多算子可变邻域搜索 (MVNS)

   • 破坏算子（三种）有选择地移除当前解的部分：
     1. 随机边移除（打断若干链接）。
     2. 子树剪枝（移除连通图的整个分支）。
     3. 路径段切除（删除电缆路径的连续段）。
   • 修复算子 – 基于 修改版 A* 的重建过程，在保持剩余结构的前提下最小化增量成本。
   • 自适应邻域规模 – 算法根据近期改进率自动扩大或收缩“破坏”半径，以平衡探索与利用。

4. 学习辅助引导

   • 一个 多智能体深度强化学习 (DRL) 模型观察当前状态（图拓扑、成本指标、最近的操作），并输出对三种破坏算子的概率分布。
   • DRL 代理在一组合成实例上离线训练，奖励函数综合成本降低和解的可行性。
   • 在 L‑MVNS 过程中，代理的建议会偏向选择邻域，从而将计算资源集中在最有前景的搜索方向上。

5. 基准测试与评估

   • 作者发布了一个基准套件，涵盖 10 个城市规模场景（道路节点数量从 500 到 10 000），并提供真实的成本参数和设施约束。
   • 基线算法包括纯 HGS、经典 A*，以及近期的元启发式方法（如蚁群优化、模拟退火）。

结果与发现

• 成本节约：L‑MVNS 始终优于所有基线，在最大实例上实现了最高约 50 % 的总施工成本降低。
• 可扩展性：虽然运行时间随实例规模适度增长，但自适应邻域机制使得搜索在 >10 000 节点的情况下仍保持可处理。
• 稳定性：30 次独立运行的最终成本标准差显著下降，表明 DRL 引导的邻域选择降低了随机性导致的方差。
• 消融研究：去除 DRL 代理会使成本降低约 10 % 并增加方差，验证了其实际收益。

Practical Implications

• City Planning Departments 可以将 L‑MVNS 引擎接入现有的 GIS 流程，以生成成本最优的地下电缆布局，从而显著降低预算超支。
• Utility Companies 获得了一种决策支持工具，能够在尊重真实约束（例如现有公用走廊、道路封闭）的前提下，快速探索大量“如果…会怎样”的情景。
• Software Vendors 在构建土木工程或智慧城市平台时，可将多运营商搜索框架集成为模块化优化器，并提供自定义成本函数（如环境影响、扰动惩罚）的 API。
• Developers 可以复用基准套件来评估替代启发式算法，或针对特定地区的法规微调 DRL 代理，加速研究到部署的周期。
• learning‑assisted approach 展示了一套将经典组合启发式与现代强化学习相结合的具体方案——这一新兴模式可以复制到其他基础设施路由问题（如供水、光纤、燃气）。

限制与未来工作

• 模型简化：当前的图抽象假设道路网络是静态的，未考虑动态的施工约束（例如时间窗口限制、交通中断）。
• 训练数据依赖：DRL 代理在合成实例上进行训练；将其迁移到拓扑或成本结构显著不同的城市可能需要额外的微调。
• 可扩展性上限：虽然 L‑MVNS 能扩展到约 10 k 节点，但超大型都市网格（数十万节点）仍可能挑战内存和运行时间限制。
• 未来方向：
  • 融入 时间依赖约束 并进行多目标扩展（成本 vs. 施工时间 vs. 环境影响）。
  • 探索 在线学习，使 DRL 代理在实际搜索过程中针对每个实例进行自适应。
  • 将基准扩展至包含来自多个城市的 真实 GIS 数据，以测试跨区域的泛化能力。

底线：通过将连通性决策与具体路由紧密耦合，并在稳健的可变邻域搜索中加入学习到的邻域优先级，L‑MVNS 提供了一个实用且高影响力的工具，用于降低地下电缆部署成本——这对城市规划者和构建下一代城市基础设施软件的开发者都是双赢。

作者

• Wei Liu
• Tao Zhang
• Chenhui Lin
• Kaiwen Li
• Rui Wang

论文信息

• arXiv ID: 2512.19321v1
• 分类: cs.NE
• 出版日期: 2025年12月22日
• PDF: 下载 PDF