1231. Theoretical complexity and a graph-based feasibility algorithm for maximising power restoration in electricity distribution grids
Invited abstract in session TC-44: Approaches for handling computational complexity, stream Energy Economics & Management.
Tuesday, 12:30-14:00Room: Newlyn 1.01
Authors (first author is the speaker)
| 1. | Andrew Eliseev
|
| Research Training Group KRITIS, Technical University of Darmstadt | |
| 2. | Florian Steinke
|
| Technical University of Darmstadt |
Abstract
Distribution grids (DGs) deliver electricity from high-voltage networks to end customers, such as households and factories, on a municipal level. A DG is called resilient if it can quickly restore service after a blackout. One way to improve the resilience of modern DGs that has received attention in the literature is through Distribution Service Restoration with Microgrids (DSRM).
DSRM divides a DG into smaller microgrids that can restart independently using generators installed in them. These microgrids can then gradually expand by launching additional generators and restoring power to more customers.
In this study, we assign weights to customers in the DG based on their importance for power restoration and aim to maximise the total weight of supplied customers, calling this problem MaxSupDSRM.
Finding a solution quickly is crucial in an emergency, however, we show that MaxSupDSRM is NPO-complete w.r.t. E-reductions, meaning that it is generally hard to find even a feasible solution for it in polynomial time. We also show that the problem remains difficult under various natural parameterisations relevant to real-world DGs. We then identify a practically relevant special case of MaxSupDSRM for which a polynomial-time algorithm for finding a feasible solution can be presented.
Keywords
- Disaster and Crisis Management
- Graphs and Networks
- Complexity and Approximation
Status: accepted
Back to the list of papers