Abstract
In this chapter, we investigate the well-studied evacuation planning problem, in which vehicles use the available road transportation network to reach safe areas (shelters) in the face of an upcoming disaster. To successfully evacuate these vehicles located in danger zones, our evacuation process needs to be fast, safe, and seamless. We enable the first two criteria by developing a macroscopic, time-dynamic evacuation model that aims to maximize a reward function, based on the number of people in relatively safer areas of the network at each time point. The third criterion is achieved by constructing an evacuation tree, where vehicles are evacuated using a single path to safety at each intersection. We extend on the definition of the evacuation tree by allowing for divergence and contraflow policies. Divergence enables specific nodes to diverge their flows into two or more streets, while contraflow allows certain streets to reverse their direction, effectively increasing their capacity. We investigate the performance of these policies in the evacuation networks obtained, and present results on two benchmark networks of Sioux Falls and Chicago.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Andreas, A.K., Smith, J.C.: Decomposition algorithms for the design of a nonsimultaneous capacitated evacuation tree network. Networks 53(2), 91–103 (2009)
Bayram, V.: Optimization models for large scale network evacuation planning and management: a literature review. Surv. Oper. Res. Manag. Sci. 21(2), 63–84 (2016)
Beckmann, M.J., McGuire, C.B., Winsten, C.B.: Studies in the Economics of Transportation. Yale University, New Haven (1956)
Cova, T.J., Johnson, J.P.: A network flow model for lane-based evacuation routing. Transp. Res. A Policy Pract. 37(7), 579–604 (2003)
Daganzo, C.F.: The cell transmission model: a dynamic representation of highway traffic consistent with the hydrodynamic theory. Transp. Res. B Methodol. 28(4), 269–287 (1994)
Daganzo, C.F.: The cell transmission model, Part II: network traffic. Transp. Res. B Methodol. 29(2), 79–93 (1995)
Department of Homeland Security: U S Department of Homeland Security, W.D., National response framework, 2013. https://www.fema.gov/media-library-data/20130726-1914-25045-1246/final_national_response_framework_20130501.pdf
Dosa, D.M., Grossman, N., Wetle, T., Mor, V.: To evacuate or not to evacuate: lessons learned from Louisiana nursing home administrators following Hurricanes Katrina and Rita. J. Am. Med. Dir. Assoc. 8(3), 142–149 (2007)
Fleischer, L., Tardos, É.: Efficient continuous-time dynamic network flow algorithms. Oper. Res. Lett. 23(3-5), 71–80 (1998)
Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Can. J. Math. 8(3), 399–404 (1956)
Gale, D.: Transient flows in networks. Tech. rep., DTIC Document (1958)
Gurobi Optimization Inc.: Gurobi Optimizer Reference Manual (2016). http://www.gurobi.com
Hagberg, A., Swart, P., S Chult, D.: Exploring network structure, dynamics, and function using networkx. Tech. rep., Los Alamos National Lab. (LANL), Los Alamos (2008)
Hamacher, H., Tjandra, S.: Mathematical modelling of evacuation problems: a state of art. Tech. Rep. 24, Fraunhofer (ITWM) (2001). http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:hbz:386-kluedo-12873
He, X., Zheng, H., Peeta, S.: Model and a solution algorithm for the dynamic resource allocation problem for large-scale transportation network evacuation. Transp. Res. C Emerg. Technol. 59, 233–247 (2015)
Hoppe, B., Tardos, É.: Polynomial time algorithms for some evacuation problems. In: SODA, vol. 94, pp. 433–441 (1994)
Hoppe, B., Tardos, É.: The quickest transshipment problem. Math. Oper. Res. 25(1), 36–62 (2000)
IRFC: The Red Cross Red Crescent Approach To Disaster and Crisis Management (2011). http://www.ifrc.org
Kalafatas, G., Peeta, S.: Planning for evacuation: insights from an efficient network design model. J. Infrastruct. Syst. 15(1), 21–30 (2009)
Kim, S., Shekhar, S.: Contraflow network reconfiguration for evacuation planning: a summary of results. In: Proceedings of the 13th Annual ACM International Workshop on Geographic Information Systems, pp. 250–259. ACM, New York (2005)
Kim, S., Shekhar, S., Min, M.: Contraflow transportation network reconfiguration for evacuation route planning. IEEE Trans. Knowl. Data Eng. 20(8), 1115–1129 (2008)
Lu, Q., George, B., Shekhar, S.: Capacity constrained routing algorithms for evacuation planning: a summary of results. In: Advances in Spatial and Temporal Databases, pp. 291–307. Springer, Berlin (2005)
Marianov, V.: Location models for emergency service applications. In: Leading Developments from INFORMS Communities, pp. 237–262. INFORMS (2017)
Occupational Safety and Health Administration: Emergency preparedness and response: getting started. Evacuation & shelter-in-place. https://www.osha.gov/SLTC/emergencypreparedness/gettingstarted_evacuation.html. Accessed 1 May 2018
Peeta, S., Ziliaskopoulos, A.K.: Foundations of dynamic traffic assignment: the past, the present and the future. Netw. Spat. Econ. 1(3–4), 233–265 (2001)
Pyakurel, U., Dhamala, T.N.: Continuous time dynamic contraflow models and algorithms. Adv. Oper. Res. 2016, 7902460 (2016)
Pyakurel, U., Dhamala, T.N.: Continuous dynamic contraflow approach for evacuation planning. Ann. Oper. Res. 253(1), 573–598 (2017)
Rebennack, S., Arulselvan, A., Elefteriadou, L., Pardalos, P.M.: Complexity analysis for maximum flow problems with arc reversals. J. Comb. Optim. 19(2), 200–216 (2010)
Sheffi, Y.: Urban transportation networks, vol. 6. Prentice-Hall, Englewood Cliffs (1985)
Sheu, J.B., Pan, C.: A method for designing centralized emergency supply network to respond to large-scale natural disasters. Transp. Res. B Methodol. 67, 284–305 (2014)
Shinouda, M.M.R.: Study of contraflow operations for hurricane evacuation. Ph.D. thesis, University of Alabama at Birmingham, Graduate School (2009)
Stepanov, A., Smith, J.M.: Multi-objective evacuation routing in transportation networks. Eur. J. Oper. Res. 198(2), 435–446 (2009)
Transportation Networks for Research Core Team: Transportation networks for research. https://github.com/bstabler/TransportationNetworks. Accessed 1 Dec 2017
Transportation Research Board: The Role of Transit in Emergency Evacuation. Transportation Research Board Special Report 294 (2008). http://onlinepubs.trb.org/onlinepubs/sr/sr294.pdf
Tuydes, H., Ziliaskopoulos, A.: Tabu-based heuristic approach for optimization of network evacuation contraflow. Transp. Res. Rec. J. Transp. Res. Board (1964), 157–168 (2006)
Urbina, E., Wolshon, B.: National review of hurricane evacuation plans and policies: a comparison and contrast of state practices. Transp. Res. A Policy Pract. 37(3), 257–275 (2003)
Vogiatzis, C., Pardalos, P.M.: Evacuation modeling and betweenness centrality. In: International Conference on Dynamics of Disasters, pp. 345–359. Springer, Berlin (2016)
Vogiatzis, C., Walteros, J.L., Pardalos, P.M.: Evacuation through clustering techniques. In: Models, Algorithms, and Technologies for Network Analysis, pp. 185–198. Springer, Berlin (2013)
Wolshon, B.: “One-Way-Out”: contraflow freeway operation for hurricane evacuation. Nat. Hazard. Rev. 2(3), 105–112 (2001)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Achrekar, O., Vogiatzis, C. (2018). Evacuation Trees with Contraflow and Divergence Considerations. In: Kotsireas, I., Nagurney, A., Pardalos, P. (eds) Dynamics of Disasters. DOD 2017. Springer Optimization and Its Applications, vol 140. Springer, Cham. https://doi.org/10.1007/978-3-319-97442-2_1
Download citation
DOI: https://doi.org/10.1007/978-3-319-97442-2_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-97441-5
Online ISBN: 978-3-319-97442-2
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)