Scheduling Post-Disaster Repairs in Electricity Distribution Networks

Recent years have seen an increase in natural disasters impacting power infrastructure, prompting research into optimal repair scheduling. Prior work includes MILP models by Coffrin and Van Hentenryck, and heuristic approaches like Nurret et al., but these often lack scalability or theoretical guarantees. The evolution of smart grid technologies and data-driven methods has spurred interest in mathematically rigorous, scalable algorithms capable of handling complex, real-time repair scenarios. Despite progress, existing solutions struggle with balancing computational efficiency and solution quality, especially in multi-crew, large-scale settings. This paper builds on these foundations, aiming to develop algorithms with provable approximation bounds suitable for practical deployment.

The core challenge is to schedule repairs of damaged distribution network components with multiple crews, considering the radial topology and soft precedence constraints, to minimize total community outage harm. The problem is NP-hard, compounded by the need for rapid decision-making post-disaster. Existing methods either oversimplify the problem or lack theoretical performance guarantees, limiting their practical utility. The difficulty lies in balancing repair sequence complexity, resource constraints, and the urgency of restoring critical loads, all within a computationally feasible framework.

Key innovations include: 1) modeling the repair scheduling as a soft precedence multi-machine problem, capturing concurrent repairs and partial dependencies; 2) integrating ILP with valid inequalities to strengthen the relaxation; 3) proposing a list scheduling algorithm based on LP midpoints with a proven 2-approximation ratio; 4) developing a conversion algorithm from single to multi-crew schedules, validated through theoretical bounds; 5) introducing ρ-factor based dispatch rules for rapid decision-making. These contributions collectively advance the state-of-the-art by providing scalable, theoretically grounded algorithms for complex disaster repair scheduling.

• �� Model the damaged distribution network as a graph with damaged and intact edges, constructing damaged component graph G′ and soft precedence graph P. • Formulate the problem as a time-indexed ILP with variables for repair completion, energization, and crew assignment, incorporating valid inequalities for efficiency. • Develop three algorithms:
• LP list scheduling: solve LP relaxation, generate priority list, assign jobs sequentially.
• Conversion algorithm: derive multi-crew schedule from single-crew optimal sequence.
• ρ-factor dispatch: compute component importance, prioritize repairs accordingly.
• �� Theoretically analyze approximation bounds, proving 2-approximation for list scheduling and equivalence of conversion and dispatch algorithms. • Validate through extensive simulations on IEEE test feeders, comparing with baseline heuristics.

Experiments utilize IEEE 13-node and 123-node test feeders, simulating damage scenarios with varying repair times and crew numbers. Metrics include average repair time, maximum outage duration, and computational time. Baselines involve heuristic and MILP-based methods. Sensitivity analyses assess algorithm robustness under different damage levels and resource constraints. Results demonstrate consistent improvements in outage duration reduction, with the LP-based list scheduling achieving up to 40% faster community recovery, validating theoretical guarantees in practical settings.

The LP list scheduling algorithm consistently outperforms heuristics, reducing average outage duration by approximately 40% in IEEE 13-node networks. The conversion approach closely matches optimal solutions, with less than 10% deviation. The ρ-factor heuristic offers rapid, near-optimal scheduling, suitable for real-time applications. Across all tests, the algorithms scale well, maintaining solution quality and computational efficiency even in larger networks. These findings confirm the practical relevance of the theoretical bounds and demonstrate the algorithms' robustness.

The proposed algorithms are directly applicable for utility companies managing post-disaster restoration, enabling rapid, near-optimal repair scheduling. They can incorporate real-time damage assessments and resource availability, facilitating automated decision support. Long-term, these methods can be integrated into smart grid resilience frameworks, supporting proactive planning and adaptive response strategies for future natural disasters, ultimately reducing societal and economic impacts.

Assumptions of uniform repair times and minimal travel times limit model realism. Scalability may be challenged in extremely large or highly complex networks. The current framework does not explicitly handle repair time variability or dynamic updates during repair processes. Future work should address these limitations by incorporating stochastic repair durations, real-time data integration, and multi-objective optimization to enhance robustness and applicability.