[Paper] Learning-Assisted Multi-Operator Variable Neighborhood Search for Urban Cable Routing

Source: arXiv - 2512.19321v1

Overview

Urban underground cable routing is a high‑stakes planning problem: cities need reliable power distribution, but digging new conduits is expensive and tightly constrained by existing road networks. This paper reframes the task as a connectivity‑path co‑optimization problem and introduces a learning‑assisted multi‑operator variable neighborhood search (L‑MVNS) algorithm that dramatically cuts construction costs—by roughly 30‑50% compared with prior methods—while keeping the solution process stable even for large, realistic city layouts.

Key Contributions

• Unified problem formulation that simultaneously optimizes substation connectivity (which nodes must be linked) and the exact geometric routes of the cables.
• Hybrid initial‑solution generator: a combination of a Hybrid Genetic Search (HGS) for connectivity and an A* planner for feasible routes, producing high‑quality starting points.
• Multi‑Operator Variable Neighborhood Search (MVNS) framework with three complementary destruction operators, a modified A* repair operator, and an adaptive neighborhood‑size controller.
• Deep reinforcement‑learning (DRL) agent that learns to prioritize the most promising neighborhoods during search, turning MVNS into the learning‑assisted L‑MVNS.
• Standardized, scalable benchmark suite for urban cable routing, enabling reproducible evaluation across small to city‑scale instances.
• Extensive empirical validation showing 30‑50% cost reductions over state‑of‑the‑art heuristics, with L‑MVNS delivering extra gains on larger instances and superior solution stability.

Methodology

1. Problem Modeling

   • The city map is abstracted as a planar graph where vertices represent road intersections and edges represent possible cable corridors.
   • Two coupled sub‑problems are defined:
     • Connectivity – decide which substations (or demand nodes) must be linked.
     • Path Planning – find concrete routes for each selected link that respect road‑layout constraints and avoid conflicts.

2. Auxiliary Initial‑Solution Task

   • A Hybrid Genetic Search (HGS) evolves candidate connectivity graphs using crossover/mutation operators tailored to the network’s topology.
   • For each connectivity candidate, an A* shortest‑path search (augmented with feasibility checks for underground utilities) generates a concrete routing.
   • The best feasible pair becomes the seed for the main search.

3. Multi‑Operator Variable Neighborhood Search (MVNS)

   • Destruction Operators (three types) selectively remove parts of the current solution:
     1. Random edge removal (breaks a few links).
     2. Sub‑tree pruning (removes an entire branch of the connectivity graph).
     3. Route segment excision (deletes a contiguous segment of a cable path).
   • Repair Operator – a modified A* that rebuilds the destroyed portions while respecting the remaining structure and minimizing incremental cost.
   • Adaptive Neighborhood Sizing – the algorithm automatically expands or contracts the “damage” radius based on recent improvement rates, balancing exploration and exploitation.

4. Learning‑Assisted Guidance

   • A multi‑agent deep reinforcement learning (DRL) model observes the current state (graph topology, cost metrics, recent moves) and outputs a probability distribution over the three destruction operators.
   • The DRL agent is trained offline on a set of synthetic instances using a reward that combines cost reduction and solution feasibility.
   • During L‑MVNS, the agent’s suggestions bias the selection of neighborhoods, focusing computational effort on the most promising search directions.

5. Benchmark & Evaluation

   • The authors release a benchmark suite covering 10‑city‑scale scenarios (from 500 to 10 000 road nodes) with realistic cost parameters and utility constraints.
   • Baselines include pure HGS, classic A*, and recent meta‑heuristics (e.g., Ant Colony Optimization, Simulated Annealing).

Results & Findings

• Cost Savings: L‑MVNS consistently outperforms all baselines, achieving up to a 50 % reduction in total construction cost on the largest instances.
• Scalability: While runtime grows modestly with instance size, the adaptive neighborhood mechanism keeps the search tractable even for >10 000 nodes.
• Stability: The standard deviation of final costs across 30 independent runs drops dramatically, indicating that the DRL‑guided neighborhood selection reduces randomness‑induced variance.
• Ablation Study: Removing the DRL agent cuts the cost reduction by ~10 % and increases variance, confirming its practical benefit.

Practical Implications

• City Planning Departments can plug the L‑MVNS engine into existing GIS pipelines to generate cost‑optimal underground cable layouts, dramatically lowering budget overruns.
• Utility Companies gain a decision‑support tool that respects real‑world constraints (e.g., existing utility corridors, road closures) while exploring many “what‑if” scenarios quickly.
• Software Vendors building civil‑engineering or smart‑city platforms can integrate the multi‑operator search framework as a modular optimizer, exposing APIs for custom cost functions (e.g., environmental impact, disruption penalties).
• Developers can reuse the benchmark suite to benchmark alternative heuristics or to fine‑tune the DRL agent for region‑specific regulations, accelerating research‑to‑deployment cycles.
• The learning‑assisted approach demonstrates a concrete recipe for marrying classic combinatorial heuristics with modern reinforcement learning—an emerging pattern that can be replicated for other infrastructure routing problems (water, fiber‑optic, gas).

Limitations & Future Work

• Model Simplifications: The current graph abstraction assumes static road networks and does not account for dynamic construction constraints (e.g., time‑window restrictions, traffic disruptions).
• Training Data Dependency: The DRL agent is trained on synthetic instances; transferring it to cities with markedly different topology or cost structures may require additional fine‑tuning.
• Scalability Ceiling: Although L‑MVNS scales to ~10 k nodes, ultra‑large metropolitan grids (hundreds of thousands of nodes) may still challenge memory and runtime limits.
• Future Directions:
  • Incorporate time‑dependent constraints and multi‑objective extensions (cost vs. construction time vs. environmental impact).
  • Explore online learning where the DRL agent adapts during the actual search on a per‑instance basis.
  • Extend the benchmark to include real‑world GIS data from multiple cities to test cross‑regional generalization.

Bottom line: By tightly coupling connectivity decisions with concrete routing and augmenting a robust variable‑neighborhood search with learned neighborhood prioritization, L‑MVNS offers a practical, high‑impact tool for cutting underground cable deployment costs—a win for both city planners and the developers building the next generation of urban infrastructure software.

Authors

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

Paper Information

• arXiv ID: 2512.19321v1
• Categories: cs.NE
• Published: December 22, 2025
• PDF: Download PDF