A decomposition-based heuristic for stochastic emergency routing problems

Abstract This paper proposes a decomposition-based heuristic for a network delivery problem in which relief workers acquire valuable emergency supplies from relief warehouses, and transport them to meet the urgent needs of distressed population centres. The problem context dictates that the relief items reach these population centres before critical deadlines. However, co-ordination challenges and random disruptions introduce uncertainty in both network travel times and the destination deadlines. Hence, relief workers have to negotiate the tension between ensuring a high probability of punctual delivery and maximising the combined value of the relief supplies delivered. For an arbitrary routing scheme which guarantees punctual delivery in an uncertainty-free state of nature, the heuristic yields an upper bound on the probability that, under uncertainty, the routing scheme described will lead to tardy delivery. We demonstrate our solution approach on a small numerical example and glean insights from experiments on a realistically sized problem. Overall, our central model and proposed solution approach are useful to managers who need to evaluate routing options and devise effective operational delivery plans in humanitarian crisis situations.