Heuristic Selection in Disaster Recovery Sequencing

Abstract

Transportation network recovery after an extreme hazard or natural disaster is time sensitive and resource intensive, with hundreds or thousands of damaged links needing repair. The associated optimization problem is difficult, and experiments in the published literature are largely confined to smaller-scale instances. We aim to bridge this gap by comparing eight algorithms proposed for repair sequencing on larger-scale instances. These methods include algorithms proposed in prior literature, an improved bidirectional beam search heuristic, and a simulated annealing heuristic newly tailored for network repair sequencing. Our experiments involved over 1,900 random problem instances over two test networks with 8–64 broken links, significantly greater than what has been reported in past literature. We assessed the solution quality and computational needs of these methods. In particular, our simulated annealing heuristic offers high-quality solutions in less than a day for problems with up to 175 and 185 broken links on the Anaheim and Berlin-Mitte-Center test networks, respectively, corresponding to 18%–20% of network links. We also show transferability of the simulated annealing heuristic by tuning its parameters on the Anaheim network, then applying it without further tuning to Berlin-Mitte-Center. Comparable performance was obtained on both networks.