A stochastic programming approach for shelter location and evacuation planning.

*(English)*Zbl 1405.90083Summary: Shelter location and traffic allocation decisions are critical for an efficient evacuation plan. In this study, we propose a scenario-based two-stage stochastic evacuation planning model that optimally locates shelter sites and that assigns evacuees to nearest shelters and to shortest paths within a tolerance degree to minimize the expected total evacuation time. Our model considers the uncertainty in the evacuation demand and the disruption in the road network and shelter sites. We present a case study for a potential earthquake in Istanbul. We compare the performance of the stochastic programming solutions to solutions based on single scenarios and mean values.

##### MSC:

90C11 | Mixed integer programming |

90C15 | Stochastic programming |

90B06 | Transportation, logistics and supply chain management |

##### Keywords:

disaster management; evacuation traffic management; shelter location; constrained system optimal; two-stage stochastic programming; second order cone programming
PDF
BibTeX
XML
Cite

\textit{V. Bayram} and \textit{H. Yaman}, RAIRO, Oper. Res. 52, No. 3, 779--805 (2018; Zbl 1405.90083)

Full Text:
DOI

##### References:

[1] | L. Alçada-Almeida, L. Tralhão, L. Santos and J. Coutinho-Rodrigues, A multiobjective approach to locate emergency shelters and identify evacuation routes in urban areas. Geographical Anal. 41 (2009) 9-29 |

[2] | ARC Standards for hurricane evacuation shelter selection, arc 4496. Technical report, American Red Cross (2002) |

[3] | S.A. Ardekani and A.G. Hobeika, Logistics problems in the aftermath of the 1985 mexico city earthquake. In vol. 42 of Transportation Quarterly 1988 |

[4] | E.J. Baker, Hurricane evacuation behavior. Inter. J. Mass Emergencies Disasters. 9 (1991) 287-310 |

[5] | B. Balç“i”k and B.M. Beamon, Facility location in humanitarian relief. Inter. J. Logistics11 (2008) 101-121 |

[6] | G. Barbarosoğlu and Y. Arda, A two-stage stochastic programming framework for transportation planning in disaster response. J. Oper. Res. Soc. 55 (2004) 43-53 · Zbl 1095.90586 |

[7] | V. Bayram, Optimization models for large scale network evacuation planning and management: A literature review. Surv. Oper. Res. Manag. Sci. 21 (2016) 63-84 |

[8] | V. Bayram, B.Ç. Tansel and H. Yaman, Compromising system and user interests in shelter location and evacuation planning. Trans. Res. B: Methodol. 72 (2015) 146-163 |

[9] | V. Bayram and H. Yaman, Shelter location and evacuation route assignment under uncertainty: A benders decomposition approach. Trans. Sci. 52 (2017) 416-436 |

[10] | S. Belardo, J. Harrald, W.A. Wallace and J. Ward, A partial covering approach to siting response resources for major maritime oil spills. Manag. Sci. 30 (1984) 1184-1196 |

[11] | N. Berktaş, B.Y. Kara and O.E. Karaşan, Solution methodologies for debris removal in disaster response. EURO J. Comput. Optimiz. 4 (2016) 403-445 · Zbl 1349.90643 |

[12] | O. Berman, R. Huang, S. Kim and M.B. Menezes, Locating capacitated facilities to maximize captured demand. IIE Trans. 39 (2007a) 1015-1029 |

[13] | O. Berman and D. Krass, Facility location problems with stochastic demands and congestion. Facility Location Applications and Theory (2002) · Zbl 1061.90068 |

[14] | O. Berman, D. Krass and M.B. Menezes, Facility reliability issues in network p-median problems: Strategic centralization and co-location effects. Oper. Res. 55 (2007b) 332-350 · Zbl 1167.90466 |

[15] | O. Berman, D. Krass and M.B. Menezes, Locating facilities in the presence of disruptions and incomplete information. Decision Sci. 40 (2009) 845-868 |

[16] | O. Berman and A.R. Odoni, Locating mobile servers on a network with markovian properties. Networks12 (1982) 73-86 · Zbl 0478.90016 |

[17] | Berman, O. and Wang, J., The 1-median and 1-antimedian problems with uniform distributed demands. Technical report, Working paper, Rotman School of Management, University of Toronto, Toronto, Canada (2004) |

[18] | J.R. Birge and F. Louveaux, Introduction to stochastic programming. Springer (1997) · Zbl 0892.90142 |

[19] | D. Bish, H. Sherali and A. Hobeika, Optimal evacuation planning using staging and routing. J. Oper. Res. Soc. 65 (2013) 124-140 |

[20] | S. Bretschneider, Mathematical models for evacuation planning in urban areas, vol. 659. Springer (2013) · Zbl 1255.90001 |

[21] | S. Bretschneider and A. Kimms, A basic mathematical model for evacuation problems in urban areas. Trans. Res. part A: Policy and Practice45 (2011) 523-539 |

[22] | M. Bundschuh, D. Klabjan and D.L. Thurston, Modeling robust and reliable supply chains. Optimization Online Available at: (2003) |

[23] | T.H. Byers and M.S. Waterman, Technical note, Determining all optimal and near-optimal solutions when solving shortest path problems by dynamic programming. Oper. Res. 32 (1984)1381-1384 · Zbl 0553.90101 |

[24] | A.M. Caunhye, X. Nie and S. Pokharel, Optimization models in emergency logistics: A literature review. Socio-Econ. Plan. Sci. 46 (2012) 4-13 |

[25] | M. Çelik, Ö. Ergun and P. Keskinocak, The post-disaster debris clearance problem under incomplete information. Oper. Res. 63 (2015) 65-85 · Zbl 1327.90349 |

[26] | Y. Chan, W.B. Carter and M.D. Burnes, A multiple-depot, multiple-vehicle, location-routing problem with stochastically processed demands. Comput. Oper. Res. 28 (2001) 803-826 · Zbl 1027.90034 |

[27] | M.-S. Chang, Y.-L. Tseng and J.-W. Chen, A scenario planning approach for the flood emergency logistics preparation problem under uncertainty. Transp. Res. Part E: Logistics Trans. Rev. 43 (2007) 737-754 |

[28] | N.-B. Chang and S. Wang, A locational model for the site selection of solid waste management facilities with traffic congestion constraints. Civil Engineering Syst. 11 (1995) 287-306 |

[29] | G. Chen, M.S. Daskin, Z.-J.M. Shen and S. Uryasev, The α-reliable mean-excess regret model for stochastic facility location modeling. Nav. Res. Logist. (NRL)53 (2006) 617-626 · Zbl 1106.90050 |

[30] | Y.C.Chiu, H. Zheng, J. Villalobos and B. Gautam, Modeling no-notice mass evacuation using a dynamic traffic flow optimization model. IIE Trans. 39 (2007) 83-94 |

[31] | CNN Cnn live at daybreak: Escaping a hurricane. (2001) |

[32] | L. Cooper, A random locational equilibrium problem. J. Regional Sci. 14 (1974) 47-54 |

[33] | J. Coutinho-Rodrigues, L. Tralhão and L. Alçada-Almeida, Solving a location-routing problem with a multiobjective approach: the design of urban evacuation plans. J. Transp. Geography22 (2012) 206-218 |

[34] | T.J. Cova and J.P. Johnson, A network flow model for lane-based evacuation routing. Transp. Res. Part A: Policy and Practice37 (2003) 579-604 |

[35] | T. Cui, Y. Ouyang and Z.-J.M. Shen, Reliable facility location design under the risk of disruptions. Oper. Res. 58 (2010) 998-1011 · Zbl 1231.90266 |

[36] | N. Dash and H. Gladwin, Evacuation decision making and behavioral responses: Individual and household. Natural Hazards Rev. 8 (2007) 69-77 |

[37] | M.S.Daskin, C.R. Coullard and Z.-J.M. Shen, An inventory-location model: Formulation, solution algorithm and computational results. Ann. Oper. Res. 110 (2002).83-106 · Zbl 1013.90001 |

[38] | S. Duran, M.A. Gutierrez and P. Keskinocak, Pre-positioning of emergency items for care international. Interfaces41 (2011) 223-237 |

[39] | H.A. Eiselt, M. Gendreau and G. Laporte, Location of facilities on a network subject to a single-edge failure. Networks22 (1992) 231-246 · Zbl 0766.90052 |

[40] | FEMA Handbook for the seismic evaluation of buildings, fema 310. Technical report, Federal Emergency Management Agency (1988) |

[41] | FEMA Risk management series, safe rooms and shelters: Protecting people against terrorist attacks, fema 453. Technical report, Federal Emergency Management Agency (2006) |

[42] | FEMA Public assistance debris management guide, Technical report, Federal Emergency Management Agency (2007) |

[43] | FEMA Design and construction guidance for community safe rooms, fema p-361, second edition. Technical report, Federal Emergency Management Agency (2008) |

[44] | H. Frank, Optimum locations on a graph with probabilistic demands. Oper. Res. 14 (1966) 409-421 · Zbl 0142.17704 |

[45] | G. Galindo and R. Batta, Review of recent developments in OR/MS research in disaster operations management. Eur. J. Oper. Res. (2013) |

[46] | N. Görmez, M. Köksalan and F. Salman, Locating disaster response facilities in istanbul. J. Oper. Res. Soc. 62 (2011) 1239-1252. |

[47] | D. Günneç and F.S. Salman, Assessing the reliability and the expected performance of a network under disaster risk. OR Spectrum33 (2011) 499-523 · Zbl 1231.90150 |

[48] | H.W. Hamacher and S.A. Tjandra, Mathematical modelling of evacuation problems-a state of the art. Pedestr. Evac. Dyn. 2002 (2002) 227-266 · Zbl 1048.90041 |

[49] | R. Hasegawa, Disaster evacuation fromjapans 2011 tsunami disaster and the fukushima nuclear accident. IDDRI Study No5 2013 |

[50] | A.G. Hobeika, Transportation evacuation planning under natural disasters. In 10th International Road Federation World Meeting, Rio de Janerio (1984) |

[51] | R. Huang, S. Kim and M.B. Menezes, Facility location for large-scale emergencies. Ann. Oper. Res. 181 (2010) 271-286 · Zbl 1209.90236 |

[52] | O. Huibregtse, S. Hoogendoorn and M.C. Bliemer, Optimization of evacuation measures under uncertainty. In Transportation Research Board 89th Annual Meeting, number (2010) 10-2550 |

[53] | IMM-JICA. The study on a disaster prevention / mitigation basic plan in Istanbul including seismic microzonation in the Republic of Turkey. Technical report, The Istanbul Metropolitan Municipality Japan International Cooperation Agency (2002) |

[54] | A. Ingolfsson, S. Budge and E. Erkut, Optimal ambulance location with random delays and travel times. Health Care Manag. Sci. 11 (2008) 262-274 |

[55] | O. Jahn, R.H. Möhring, A.S. Schulz and N.E. Stier-Moses, System-optimal routing of traffic flows with user constraints in networks with congestion. Oper. Res. 53 (2005) 600-616 · Zbl 1165.90499 |

[56] | G. Kalafatas and S. Peeta, Planning for evacuation: insights from an efficient network design model. J. Infrastructure Syst. 15 (2009) 21-30 |

[57] | J. Kim and S.S. Oh, Confidence, knowledge, and compliance with emergency evacuation. J. Risk Res. 18 (2015) 111-126 |

[58] | C. K“i“r”i”kç”i”, Determination of shelter locations and evacuation routes for a possible earthquake in the city of Istanbul. Master’s thesis, Department of Industrial Engineering, Bilkent University (2012) |

[59] | S. Kongsomsaksakul, C. Yang and A. Chen, Shelter location-allocation model for flood evacuation planning. J. East. Asia Soc. Transp. Stud. 6 (2005) 4237-4252 |

[60] | A. Kulshrestha, D. Wu, Y. Lou and Y. Yin, Robust shelter locations for evacuation planning with demand uncertainty. J. Transp. Safety Secur. 3 (2011) 272-288 |

[61] | G. Laporte, F. Louveaux and H. Mercure, Models and exact solutions for a class of stochastic location-routing problems. Eur. J. Oper. Res. 39 (1989) 71-78 · Zbl 0676.90019 |

[62] | A.C.Y. Li, L. Nozick, N. Xu and R. Davidson, Shelter location and transportation planning under hurricane conditions. Transp. Res. Part E: Logist. Transp. Rev. 48 (2012) 715-729 |

[63] | X. Li and Y. Ouyang, A continuum approximation approach to reliable facility location design under correlated probabilistic disruptions. Transp. Res. Part B: Methodological44 (2010) 535-548 |

[64] | M. Lim, M.S. Daskin, A. Bassamboo and S. Chopra, A facility reliability problem: formulation, properties, and algorithm. Nav. Res. Logist. (NRL)57 (2010) 58-70 · Zbl 1180.90090 |

[65] | M.K. Lindell and C.S. Prater, Critical behavioral assumptions in evacuation time estimate analysis for private vehicles: Examples from hurricane research and planning. J. Urban Plan. Dev. 133 (2007) 18-29 |

[66] | F. Louveaux, Discrete stochastic location models. Ann. Oper. Res. 6 (1986) 21-34 |

[67] | L. Luther, Disaster debris removal after hurricane katrina: status and associated issues. Congressional Research Service, Library of Congress (2006) |

[68] | A. Madansky, Inequalities for stochastic linear programming problems. Manag. Sci. 6 (1960) 197-204 · Zbl 0995.90601 |

[69] | K.D. Marano, D.J. Wald and T.I. Allen, Global earthquake casualties due to secondary effects: a quantitative analysis for improving rapid loss analyses. Nat. Hazards52 (2010) 319-328 |

[70] | A.R. Mawson, Understanding mass panic and other collective responses to threat and disaster. Psychiatry: Interpers. Biol. Process. 68 (2005) 95-113 |

[71] | H.O. Mete and Z.B. Zabinsky, Stochastic optimization of medical supply location and distribution in disaster management. Inter. J. Prod. Econ. 126 (2010) 76-84 |

[72] | P.B. Mirchandani and A.R. Odoni, Locations of medians on stochastic networks. Trans. Sci. 13 (1979) 85-97 |

[73] | P.B. Mirchandani and A. Oudjit, Localizing 2-medians on probabilistic and deterministic tree networks. Networks10 (1980) 329-350 · Zbl 0452.90026 |

[74] | P. Murray-Tuite and B. Wolshon, Evacuation transportation modeling: An overview of research, development, and practice. Transp. Res. Part C: Emerging Technologies27 (2013) 25-45 |

[75] | L.D. Nel and C.J. Colbourn, Locating a broadcast facility in an unreliable network. INFOR28 (1990) 363-379 · Zbl 0718.90052 |

[76] | A. Nemirovski and A.B. Tal, Lectures on modern convex optimization: Analysis, algorithms, and engineering applications. MPS-SIAM Series on Optimization (2001) · Zbl 0986.90032 |

[77] | M. Ng and S.T. Waller, Reliable evacuation planning via demand inflation and supply deflation. Transp. Res. Part E: Logistics and Transp. Rev. 46 (2010) 1086-1094 |

[78] | N. Noyan, Risk-averse two-stage stochastic programming with an application to disaster management. Comput. Oper. Res. 39 (2012) 541-559 · Zbl 1251.90251 |

[79] | A.J. Pel, M.C.J. Bliemer and S.P. Hoogendoorn, A review on travel behaviour modelling in dynamic traffic simulation models for evacuations. Transp.39 (2012) 97-123 |

[80] | P. Peng, L.V. Snyder, A. Lim and Z. Liu, Reliable logistics networks design with facility disruptions. Transp. Res. Part B: Methodological45 (2011) 1190-1211 |

[81] | R.W. Perry, Evacuation decision-making in natural disasters. Mass Emergencies4 (1979) 25-38 |

[82] | R.W. Perry and M.K. Lindell, Preparedness for emergency response: guidelines for the emergency planning process. Disasters27 (2003) 336-350 |

[83] | H.N. Psaraftis, G.G. Tharakan and A. Ceder, Optimal response to oil spills: the strategic decision case. Oper. Res. 34 (1986) 203-217 |

[84] | C.G. Rawls and M.A. Turnquist, Pre-positioning of emergency supplies for disaster response. Trans. Res. Part B: Methodological44 (2010) 521-534 |

[85] | S. Rui, H. Shiwei and L. Zhang, Optimum transit operations during the emergency evacuations. J. Trans. Syst. Eng. Information Techn. 9 (2009) 154-160 |

[86] | S. Sen, Algorithms for stochastic mixed-integer programming models. Handbooks in Oper. Res. Manag. Sci. 12 (2005) 515-558 · Zbl 1172.90457 |

[87] | Y. Sheffi, Urban transportation networks: equilibrium analysis with mathematical programming methods. Prentice-Hall, Inc., Englewood Cliffs, N.J. 07632 (1985) |

[88] | Z.-J.M. Shen, J. Pannala, R. Rai and T.S. Tsoi, Modeling transportation networks during disruptions and emergency evacuations. University of California Transportation Center (2008) |

[89] | H.D. Sherali, T.B. Carter and A.G. Hobeika, A location-allocation model and algorithm for evacuation planning under hurricane/flood conditions. Trans. Res. Part B: Methodological25 (1991) 439-452 |

[90] | J.-B. Sheu and C. Pan, A method for designing centralized emergency supply network to respond to large-scale natural disasters. Trans. Res.Part B: Methodological67 (2014) 284-305 |

[91] | L.V. Snyder and M.S. Daskin, Reliability models for facility location: the expected failure cost case. Trans. Sci. 39 (2005) 400-416 |

[92] | L.V. Snyder and M.S. Daskin, Models for reliable supply chain network design. In Critical Infrastructure. Springer (2007) 257-289 |

[93] | L.V. Snyder, M.P. Scaparra, M.S.Daskin and R.L. Church, Planning for disruptions in supply chain networks. Tutorials Oper. Res. (2006) 234-257 |

[94] | A. Stepanov and J.M. Smith, Multi-objective evacuation routing in transportation networks. Eur. J. Oper. Res. 198 (2009) 435-446 · Zbl 1163.90374 |

[95] | TAM. Traffic Assignment Manual. Bureau of Public Roads, U.S. Department of Commerce (1964) |

[96] | TRB, Transportation Research Board of the National Academies, C. o. t. R. o. P. T. i. E.E. The role of transit in emergency evacuation. Special Report (2008) 294. |

[97] | H. Tüydeş, Network Traffic Management under Disaster Conditions. Ph.D. thesis, Field of Civil and Environmental Engineering, Northwestern University (2005) |

[98] | W. Wilhelm and A.V. Srinivasa, A strategic, area-wide contingency planning model for oil spill cleanup operations with application demonstrated to the galveston bay area. Decision Sci. 27 (1996) 767-799 |

[99] | T. Yamada, A network flow approach to a city emergency evacuation planning. Inter. J. Syst. Sci. 27 (1996) 931-936 · Zbl 0863.94040 |

[100] | T. Yao, S.R. Mandala and B. Do Chung Evacuation transportation planning under uncertainty: a robust optimization approach. Networks Spatial Econ. 9 (2009) 171-189 · Zbl 1170.90328 |

[101] | M.A. Yaz“i“c”i” and K. Özbay, Evacuation network modeling via dynamic traffic assignment with probabilistic demand and capacity constraints. Trans. Res. Record: J. Transp. Res. Board2196 (2010) 11-20 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.