Randomized Adaptive Vehicle Decomposition for Large-Scale Power Restoration

Author:

Simon, Ben; Coffrin, Carleton; Van Hentenryck, Pascal

Date of Publication:

2012-05-28

Publication Type:

Conference Material

Conference Name:

International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR)

Conference Location:

Nantes, France

Pages:

379-394

Abstract:

This paper considers the joint repair and restoration of the electrical power system after significant disruptions caused by natural disasters. This problem is computationally challenging because, when the goal is to minimize the size of the blackout, it combines a routing and a power restoration component, both of which are difficult on their own. The joint repair/restoration problem has been successfully approached with a 3-stage decomposition, whose last step is a multiple-vehicle, pickup-and-delivery routing problem with precedence and capacity constraints whose goal is to minimize the sum of the delivery times (PDRPPCCDT). Experimental results have shown that the PDRPPCCDT is a bottleneck and this paper proposes a Randomized Adaptive Vehicle Decomposition (RAVD) to scale to very large power outages. The RAVD approach is shown to produce significant computational benefits and provide high-quality results for infrastructures with more than 24000 components and 1200 damaged items, giving rise to PDRPPCCDT with more than 2500 visits.

URL:

http://www.emn.fr/z-info/cpaior-2012/

Identifier:

nicta:5863

Attribution Statement:

Simon, Ben; Coffrin, Carleton; Van Hentenryck, Pascal. Randomized Adaptive Vehicle Decomposition for Large-Scale Power Restoration. In: International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR); Nantes, France. 2012-05-28. 379-394. nicta:5863. http://hdl.handle.net/102.100.100/100682?index=1