Authors: Michael A. Walliser; Walter D. Potter; Pete Bettinger
Addresses: PowerPlan, Inc., Atlanta, Georgia 30339, USA ' Institute for Artificial Intelligence, University of Georgia, Athens, Georgia 30602, USA ' School of Forestry and Natural Resources, University of Georgia, Athens, Georgia 30602, USA
Abstract: This research represents a novel application of operations research methodology to a form of a hierarchical open vehicle routing problem. In our case study, a road network was divided into priority sets such that each set needed to be completely addressed before work could begin on the next. Rule-based heuristics and adaptations of local beam search heuristics were tested in various combinations, viable solutions were developed, and results were evaluated based on the time required to clear the entire road network of storm-generated debris. The results were also compared against a theoretical lower bound on the time required to clear all roads. The best routes were generated using a combination of constant time beam search and a rule-based heuristic, 12.4% greater than the lower bound, yet understandable for the case study area that contained numerous dead-ends and disconnected road priority sets.
Keywords: shortest paths; forestry; heuristics; artificial intelligence; natural disasters; emergency response; emergency recovery; severe winds; severe storms; hierarchical routing; open vehicle routing; disaster response; disaster recovery; operations research; road networks; roads; storm debris; road clearances; transport disruption; forest damage; infrastructure damage; emergency planning; emergency management; relief distribution; logistics coordination; travel route blockages; tropical cyclones; forest debris.
International Journal of Emergency Management, 2015 Vol.11 No.1, pp.20 - 45
Accepted: 16 Dec 2014
Published online: 19 May 2015 *