Abstract
When a disaster occurs, we need a routing plan to evacuate all the people in the affected area as soon as possible. For this purpose, we can model the transportation network as a graph of nodes and edges with occupancy on nodes and capacity and travel time on edges, where nodes represent places such as cities and edges represent roads. Given a transportation network graph, we can compute routes to evacuate all the people in the dangerous area by selecting paths from the source nodes (the nodes of which residents need to be evacuated) to the destination nodes (the nodes where the evacuees can be transported to). With capacity and travel time constraints on the roads (or edges), calculation of the evacuation time on the graph requires the use of time-expanded graphs. The use of time-expanded graphs, which are merely duplications of the given graph flagged with discrete time stamps, explodes the time and space complexities of the calculation of evacuation times. This drawback results in low scalability, especially when the evacuation time or the number of evacuees is relatively big compared to the size of the graph, such as the number of nodes, edges, and paths. In this paper, we present a scalable algorithm, SYNChronized FLOw Evacuation(SyncFloE), to plan the evacuation routes based on synchronized flows. The novel concept of synchronized flows replaces the use of time-expanded graphs and provides higher scalability in terms of the evacuation time or the number of evacuees. SyncFloE has computation time that only depends on the number of source nodes and the size of the graph itself, such as the number of nodes, edges, and paths. The computational results that support our claim are presented and discussed.
Research is partly supported by NSF Award CCF-0729182.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Cova, T.J., Johnson, J.P.: A network flow model for lane-based evacuation routing. Transportation Research Part A 37, 579–604 (2003)
Yang, F., Yan, X., Xu, K.: Evacuation Flow Assignment based on Improved MCMF Algorithm. In: Proc. First International Conference on Intelligent Networks and Intelligent Systems, pp. 637–640 (2008)
Fleischer, L.K.: Faster Algorithms For The Quickest Transshipment Problem. SIAM J. Optim. 12/1, 18–35 (2001)
Hamacher, H.W., Tjandra, S.A.: Mathematical Modelling of Evacuation Problems: A State of Art. Technical Report Nr. 24, Berichte des Fraunhofer ITWM (2001)
Kim, S., Shekhar, S.: Contraflow Network Reconfiguration for Evacuation Planning: A Summary of Results. In: Proc. Proceedings of the 13th ACM Symposium on Advances in Geographic Information Systems, pp. 250–259 (2005)
Kim, S., Shenkhar, S., Min, M.: Contraflow Transportation Network Reconfiguration for Evacuation Route Planning. IEEE Transactions on Knowledge and Data Engineering 20/8, 1115–1129 (2008)
Lu, Q., Huang, Y., Shekhar, S.: Evacuation Planning: A Capacity Constrained Routing Approach. In: Chen, H., Miranda, R., Zeng, D.D., Demchak, C.C., Schroeder, J., Madhusudan, T. (eds.) ISI 2003. LNCS, vol. 2665, pp. 111–125. Springer, Heidelberg (2003)
Lu, Q., George, B., Shekhar, S.: Capacity Constrained Routing Algorithms for Evacuation Planning: A Summary of Results. In: Medeiros, C.B., Egenhofer, M., Bertino, E. (eds.) SSTD 2005. LNCS, vol. 3633, pp. 291–307. Springer, Heidelberg (2005)
Lu, Q., George, B., Shekhar, S.: Evacuation Route Planning: Scalable Heuristics. In: Proc. 15th International Symposium on Advances in Geographic Information Systems (2007)
Min, M., Neupane, B.C.: An Evacuation Planner Algorithm in Flat Time Graphs. In: Proc. of ACM International Conference on Ubiquitous Information Management and Communication, ICUIMC (2011)
Yin, D.: A Scalable Heuristic for Evacuation Planning in Large Road Network. In: Proc. the Second International Workshop on Computational Transportation Science, pp. 19–24 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Min, M. (2012). Synchronized Flow-Based Evacuation Route Planning. In: Wang, X., Zheng, R., Jing, T., Xing, K. (eds) Wireless Algorithms, Systems, and Applications. WASA 2012. Lecture Notes in Computer Science, vol 7405. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31869-6_36
Download citation
DOI: https://doi.org/10.1007/978-3-642-31869-6_36
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31868-9
Online ISBN: 978-3-642-31869-6
eBook Packages: Computer ScienceComputer Science (R0)