Optimal restoration of electricity distribution networks under rolling time windows and prediction of restoration time

点击翻译按钮获取中文摘要

This NSF project aims to develop transformative techniques to optimize the scheduling of crews to repair and restore electricity distribution networks following a large windstorm, an ice storm, or another type of natural disaster. Due to the nature of these networks and the need for crews to travel to different locations to perform repairs before power can be restored to customers, this optimization is particularly complex. However, it can be formulated as a budget-constrained, profit maximizing multiple traveling salesman problem on an edge and node weighted graph. This variant of the classical traveling salesman problem has not been studied before. The primary intellectual merits of the project include developing a formulation of the optimal repair and restoration process that is not only mathematically rigorous but also incorporates many practical constraints that must be considered for the resulting schedule to be feasible, developing algorithms to implement this formulation that are flexible and computationally lightweight and thus support easy re-optimization as additional information becomes available, and shedding light on novel variants of the multiple traveling salesman problem, which will be of independent interest to researchers in other disciplines such as computer science and operations research.Severe weather events can cause extensive damage to electricity distribution networks, depriving thousands of customers of light, heat, and power. Such disruptions in the supply of electricity have serious social and economic impacts and can have grave consequences for the health or life of vulnerable populations. It is thus imperative for electric utilities to repair their network and re-store power as soon as possible. This project thus has the following broader impacts: (1) it will provide these utilities with tools to help them optimally dispatch their repair crews, reduce the time required to restore power, and hence minimize the harm done to the affected communities, (2) it will also help utilities provide their customers with more accurate estimates of when they might expect power to be restored, thus helping them decide whether to stay put or seek shelter elsewhere.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.