Decision Support for Disaster Management Through Hybrid Optimization


Carleton Coffrin


Brown University


Pascal Van Hentenryck
Russell Bent


Recent natural disasters, such as Hurricane Katrina in 2005 and the Japan earthquake in 2011, have demonstrated that situational awareness, the focus of much research in disaster management, is not sufficient to provide effective mitigation, response, and recovery. The United States government has recognized the need for decision support to enhance the cognitive abilities of decision makers. Developing such tools is particularly challenging because they require modeling complex interdependent infrastructure systems and must operate under aggressive runtime constraints.

This thesis demonstrates that hybrid optimization technology can produce decision support tools for delivery of relief supplies, restoration of the electrical power infrastructure alone, and joint restoration of interdependent natural gas and electrical power infrastructures. These hybrid methods use mixed integer programming for infrastructure modeling, large neighborhood search for routing of repair crews, and randomized adaptive decomposition for scaling the optimization algorithms to practical sizes. The proposed hybrid methods increase the restoration quality significantly over current field practices and outperform traditional technologies, which cannot find feasible solutions within the runtime constraints.

The optimization algorithms must rely on linear approximations of the nonlinear AC power flow equations to meet the runtime constraints of these applications. Unfortunately, the accuracy of the traditional linearized DC model degrades significantly as network disruptions increase. This thesis also proposes novel linear approximations that are shown to provide significant improvements in accuracy under disruptions.



Components of this thesis appear in the conference proceedings of CPAIOR '10 '11, PSCC '11, PES '11 '12, AAAI '12, and received the following accolades:
Northeastern INFORMS 2011, Student Poster Competition, First Place, for "Vehicle Routing for the Last Mine of Power System Restoration"; INFORMS 2010 Doing Good with Good OR Competition finalist (1 of 6), for "Strategic Planning for Disaster Recovery with Stochastic Last Mile Distribution"; Los Alamos National Laboratory 2010 LAAP Award, Outstanding Summer Research for "Power Grid Restoration for Disaster Recovery".