Metaheuristics for the stochastic post-disaster debris clearance problem

Post-disaster debris clearance is of utmost importance in disaster response and recovery. The goal in planning debris clearance operations in emergency response is to maximize road network accessibility and enable transport of casualties to medical facilities, primary relief distribution to survivors, and evacuation of survivors from the affected region. We develop a novel stochastic mathematical model to represent the debris clearance scheduling problem with multiple cleaning crews. The inherent uncertainty in the debris clearance planning problem lies in the estimation of clearance times for road debris. The durations required to clear road segments are estimated by helicopter surveys and satellite imagery. The goal is to maximize network accessibility throughout the clearance process. The model creates a schedule that takes all clearing time scenarios into consideration. To enable the usage of the model in practice, we also propose a rolling horizon approach to revise the initial schedule based on updated clearance time estimates received from the field. We use the Sample Average Approximation method to determine the number of scenarios required to adequately represent the problem. Since the resulting mathematical model is intractable for large-scale networks, we design metaheuristics that utilize Biased Random Sampling, Tabu Search, Simulated Annealing, and Variable Neighborhood Search algorithms.