Optimal-Repair Large Neighborhood Search for the Planning of Extensive Fault-Tolerant Distribution Networks

Abstract

Background: Planning power distribution networks is crucial in contemporary infrastructure development. Current distribution paradigms require not only cost minimization but also reliability and fault tolerance. However, designing meshed network topologies is a computationally demanding combinatorial optimization problem, especially for large instances. Methods: We reframe this problem as a multi-depot vehicle routing problem in which electrical substations act as depots and power lines represent routes. We develop a four-phase Large Neighborhood Search (LNS) that combines geographically-based destroy operators with a topology-specific MILP repair operator. Each repair subproblem is solved to optimality under the adopted topological, flow conservation, and line capacity constraints. Results: Experiments on realistic medium-voltage distribution network instances with up to 1150 nodes show that the proposed method handles cases that are beyond the reach of exact global optimization. Compared with a greedy constructive heuristic, the best LNS solution achieves an average cost reduction of 28.5%. Ablation and sensitivity analyses support the algorithmic design and show stable behavior under reasonable parameter variations. AC power flow analyses on the largest instance confirm electrical consistency under the tested single-branch outage scenarios, with a maximum voltage deviation of 5.1%. Conclusions: The proposed optimal-repair LNS provides a scalable approach for planning large fault-tolerant distribution networks under topology and line capacity constraints.