Algorithmic Study for Power Restoration in Electrical Distribution Networks



Published Sep 4, 2023
Jun Kawahara Chuta Yamaoka Takehiro Ito Akira Suzuki Daisuke Iioka Shuhei Sugimura Seiya Goto Takayuki Tanabe


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.

Abstract 98 | PDF Downloads 121



algorithm, combinatorial reconfiguration, electrical distribution network, power restoration

Hayashi, Y., Kawasaki, S., Matsuki, J., Matsuda, H., Sakai, S., Miyazaki, T., & Kobayashi, N. (2006). Establishment of a standard analytical model of distribution network with distributed generators and development of multi evaluation method for network configuration candidates. IEEJ Transactions on Power and Energy, 126(10), 1013–1022.

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.
Special Session Papers