A decomposition-based heuristic for stochastic emergency routing problems

• Published in: Expert systems with applications 2016-10, Vol.59, p.47-59
• Main Authors: Fontem, Belleh, Melouk, Sharif H., Keskin, Burcu B., Bajwa, Naeem
• Format: Article
• Language: English
• Subjects: Computer networks; Crisis management; Decomposition; Decomposition-based algorithms; Emergency vehicles; Expert systems; Heuristic; Mathematical models; Robust emergency planning; Routing (telecommunications); Routing under uncertainty; Uncertainty
• ISSN: 0957-4174; 1873-6793
• DOI: 10.1016/j.eswa.2016.04.002

•We consider a network delivery problem under travel-time and deadline uncertainty.•We propose a heuristic procedure which uses decomposition to address the problem.•The heuristic allows for flexible decision-making based on risk appetite.•We experiment on three uncertainty regimes: low, medium, and high.•Results suggest that greater uncertainty enhances the heuristic’s reliability. 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.