L-VNS algorithm slashes urban cable routing costs by up to 73.72%

Researchers Wei Liu and colleagues have unveiled L-VNS (Learning-assisted Variable Neighborhood Search), a novel algorithm designed to drastically reduce the cost of urban underground cable construction. The problem is a massive bilevel combinatorial optimization: connecting substations (upper level) while planning specific routes along road networks (lower level). Traditional methods often treat these separately or use simplistic heuristics. L-VNS integrates four key components: hybrid genetic search with A* for initial high-quality solutions, variable neighborhood search for connectivity topology refinement, a multi-agent deep reinforcement learning module that jointly encodes upper- and lower-level structures to guide probabilistic sampling, and a modified A* operator to re-route paths after neighborhood changes, ensuring feasibility.

Comprehensive experiments on 12 benchmark instances and 3 real-world GIS-derived instances demonstrated L-VNS's superiority, achieving total construction cost reductions ranging from 0.92% to 73.72% compared to representative approaches like standard VNS and genetic algorithms. Ablation studies and sensitivity analyses validated the effectiveness and robustness, particularly highlighting the multi-agent RL component as key to navigating the enormous combinatorial search space. Accepted by Swarm and Evolutionary Computation (June 2026), this work offers a practical AI solution for urban infrastructure planning, potentially saving millions in cable routing costs.