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

该NSF项目旨在开发变革性技术，以优化工作人员的调度，以便在大型风暴、冰暴或其他类型的自然灾害后修复和恢复配电网络。由于这些网络的性质，以及工作人员需要前往不同的地点进行维修，才能恢复向客户供电，因此这种优化特别复杂。然而，它可以被描述为一个边和结点加权图上的预算约束、利润最大化的多旅行商问题。这个经典旅行商问题的变种以前从未被研究过。该项目的主要智力优势包括开发出一种最优维修和恢复过程的公式，该公式不仅在数学上是严格的，而且包括了许多必须考虑的实际约束，从而使所产生的时间表可行；开发算法来实现该公式，该公式灵活且计算轻量级，从而支持在获得更多信息时容易进行重新优化；以及揭示了多旅行商问题的新变体，这将是计算机科学和运筹学等其他学科的研究人员独立感兴趣的。严重的天气事件可能会对配电网造成广泛的破坏，剥夺数千用户的光、热和电力。这种电力供应中断具有严重的社会和经济影响，并可能对脆弱人口的健康或生命造成严重后果。因此，电力公用事业公司必须尽快修复网络和恢复电力供应。因此，该项目具有以下更广泛的影响：(1)它将为这些公用事业公司提供工具，帮助他们最佳地派遣维修人员，减少恢复电力所需的时间，从而将对受影响社区的损害降至最低；(2)它还将帮助公用事业公司为他们的客户提供更准确的估计，以确定他们可能恢复电力的时间，从而帮助他们决定是留在原地还是到其他地方寻求庇护。这一裁决反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.