An Algorithm for the Multi-Stage Stochastic Relief Routing Problem

Document Type : Research Paper


1 Department of Industrial Engineering, Shahed University

2 Department of Industrial Engineering, Shahed University, Tehran, Iran


There is usually uncertainty in the information during a disaster. These uncertainties are revealed in different stages during the time, but they still exist. Therefore, when information is appeared over the time, it is necessary to model and solve the problem in a multi-stage stochastic programming to make more real decisions. In this paper, a multi-stage relief routing model is presented for a disaster problem. It is assumed that the routing plan can be rerouted in each stage according to new received information. Also, an approximation algorithm is presented based on the two-stage stochastic programming. It is shown that the proposed algorithm is an appropriate approximation of the multi-stage model. Comparison of results with the deterministic model
indicates that more survivors will be achieved by the proposed model comparing to the deterministic one and it shows effectiveness of the proposed approach.


Main Subjects

  1. Luis, E., Dolinskaya, I. S. And Smilowitz, K. R., (2012). "Disaster Relief Routing: Integrating Research and Practice", Socio-Economic Planning Sciences, Vol. 46, No. 1, PP. 88-97.
  2. Hoyos, M. C., Morales, R. S., and Akhavan Tabatabaei, R., (2015). "OR Models With Stochastic Components in Disaster Operations Management: A Literature Survey", Computers and Industrial Engineering, Vol. 82, No. 1, PP. 183-197.
  3. Https://En.Wikipedia.Org/Wiki/2003_Bam_Earthquake//.
  4. Https://En.Wikipedia.Org/Wiki/2010_Haiti_Earthquake//.
  5. Fiedrich, F., Gehbauer, F., and Rickers, U., (2000). "Optimized Resource Allocation for Emergency Response After Earthquake Disasters", Safety Science, Vol. 35, No. 1, PP. 41-57.
  6. Chen, L., and Miller-Hooks, E., (2012)."Optimal Team Deployment in Urban Search And Rescue", Transportation Research Part B: Methodological, Vol. 46, No. 8, PP. 984-999.
  7. Tofighi, S., Torabi, S. A., and Mansouri, S. A., (2016). "Humanitarian Logistics Network Design Under Mixed Uncertainty", European Journal of Operational Research, Vol. 250, No. 1, PP. 239-250.
  8. Alem, D., Clark, A., and Moreno, A., (2016). "Stochastic Network Models for Logistics Planning in Disaster Relief", European Journal of Operational Research, Vol. 255, No. 1, PP. 187-206.
  9. Errico, F. et al. (2016). "A Priori Optimization with Recourse for the Vehicle Routing Problem with Hard Time Windows and Stochastic Service Times", European Journal of Operational Research, Vol. 249, No. 1, PP. 55-66.
  10. Hong, X., Lejeune, M. A., and Noyan, N., (2015). "Stochastic Network Design for Disaster Preparedness", IIE Transactions, Vol. 47, No. 4, PP. 329-357.
  11. Rennemo, S. J. et al. (2014). "A Three-Stage Stochastic Facility Routing Model for Disaster Response Planning", Transportation Research Part E: Logistics and Transportation Review, Vol. 62, No. 1, PP. 116-135.
  12. Verma, A., and Gaukler, G. M., (2015). "Pre-Positioning Disaster Response Facilities at Safe Locations: An Evaluation of Deterministic and Stochastic Modeling Approaches", Computers and Operations Research, Vol. 62, No. 1, PP. 197-209.
  13. Davis, L. B. et al. (2013). "Inventory Planning and Coordination in Disaster Relief Efforts", International Journal of Production Economics, Vol. 141, No. 2, PP. 561-573.
  14. Bozorgi Amiri, A. et al. (2012). "A Modified Particle Swarm Optimization for Disaster Relief Logistics Under Uncertain Environment", The International Journal of Advanced Manufacturing Technology, Vol. 60, No. 1, PP. 357-371.
  15. Salmerón, J., and Apte, A., (2010)."Stochastic Optimization for Natural Disaster Asset Prepositioning", Production and Operations Management, Vol. 19, No. 5, PP. 561-574.
  16. Gendreau, M., Jabali, O., and Rei, W. (2016). "50th Anniversary Invited Article—Future Research Directions in Stochastic Vehicle Routing". Transportation Science, Vol. 50, No. 4, PP. 1163-1173.
  17. Birge, J. R., and Louveaux, F., (2011). "Introduction to Stochastic Programming", Springer Science and Business Media.
  18. Https://Www.Sintef.No/Projectweb/Top/Vrptw/Solomon-Benchmark//.