.png){kind=icon}
.png){kind=icon}
Return
Learning to sample in variable neighborhood search algorithm for urban cable routing optimization
.png){kind=icon}
PRE
AI
DOI：10.1016/j.swevo.2026.102432.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Urban underground cable construction is essential for enhancing power grid reliability, yet the high construction costs demand systematic optimization. Constrained by road network infrastructure, this optimization problem requires consideration not only of connectivity relationships between substations but also of specific routing strategies along road networks, constituting a large-scale bilevel combinatorial optimization problem. Insufficient attention to specific routing subproblems in traditional research and simplistic algorithmic designs that are ill-equipped for large-scale combinatorial optimization leave substantial room for advancement in addressing this complex optimization challenge. To navigate the enormous combinatorial search space, we propose a learning-assisted variable neighborhood search (L-VNS) algorithm integrating four key components. First, an auxiliary task focusing exclusively on the upper-level connectivity subproblem generates high-quality initial solutions by employing hybrid genetic search for connection optimization and A* for detailed path routing. Subsequently, the algorithm iteratively refines the connectivity topology using variable neighborhood search equipped with three complementary operators. A multi-agent deep reinforcement learning module adaptively guides probabilistic neighborhood sampling by jointly encoding both upper-level connectivity patterns and lower-level routing structures, effectively exploiting problem structure. Finally, a modified A* operator re-plans the lower-level paths affected by neighborhood modifications to ensure feasibility and solution completeness. Comprehensive experiments on 12 benchmark instances and 3 GIS-derived instances demonstrate the superiority of L-VNS, achieving total construction cost reductions of 0.92–73.72% compared to representative approaches. Ablation studies and sensitivity analyses further validate the effectiveness and robustness of the proposed algorithm.
Journal
IF:
8.5
Papers:
2.2K
Citations:
1.0W