We study the automated power restoration in electrical distribution networks, from the algorithmic viewpoint. During power outages, blackout sections without faults may be able to be recovered early using the capacity margins of surrounding supply sources. However, remote supply sources must be utilized in cases where the capacity margins of the neighboring supply sources are insufficient for the scale of the power outage, which is called multi-stage power restoration. In multi-stage power restoration, the distribution network subject to control becomes broader, and in addition, even healthy sections are subjected to control. In this study, we give an efficient algorithm which determines whether multi-stage power restoration is needed for power restoration, and in either case, the algorithm calculates the switching procedure which recovers power with the minimum number of switch operations. Our algorithm employs a novel algorithmic technique of combinatorial reconfiguration, which enables to maintain power supply to the healthy sections.
algorithm, combinatorial reconfiguration, electrical distribution network, power restoration
Ito, T., Demaine, E. D., Harvey, N. J. A., Papadimitriou, C. H., Sideri, M., Uehara, R., & Uno, Y. (2011). On the complexity of reconfiguration problems. Theoretical Computer Science, 412(12–14), 1054–1065.
Ito, T., Kawahara, J., Nakahata, Y., Soh, T., Suzuki, A., Teruyama, J., & Toda, T. (2022). ZDD-based algorithmic framework for solving shortest reconfiguration problems. CoRR, abs/2207.13959.
Ito, T., Zhou, X., & Nishizeki, T. (2009). Partitioning graphs of supply and demand. Discrete Applied Mathematics, 157(12), 2620–2633.
Minato, S. (1993). Zero-suppressed BDDs for set manipulation in combinatorial problems. In A. E. Dunlop (Ed.), Proceedings of the 30th design automation conference. Dallas, Texas, USA, June 14–18, 1993 (pp. 272–277). ACM Press.
Nishimura, N. (2018). Introduction to reconfiguration. Algorithms, 11(4), paper id 52.
This work is licensed under a Creative Commons Attribution 3.0 Unported License.