Abstract
This paper considers the problem faced by a group of evacuees who must leave from an affected area as quickly as possible. We seek the strategies that achieve a bounded ratio of evacuation path length without any boundary information to that with. We restrict the affected area to a convex region in the plane, and investigate the problem in two scenarios: general plane and plane in grid network. In these two scenarios, we first present efficient strategies with one or two groups and analyze the competitive ratios of them. In general plane, we give a 30.47-competitive strategy for one group evacuation and a 15.58- competitive strategy for two groups evacuation. In grid network, we give a 33- competitive strategy for one group evacuation and a 19-competitive strategy for two groups evacuation.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Hoffmann, F., Icking, C., Klein, R., Kriegel, K.: The polygon exploration problem. SIAM J. Comput. 31(2), 577–600 (2002)
Chen, X., Zhan, F.B.: Agent-based simulation of evacuation strategies under different road network structures. Journal of the Operational Research Society 59, 25–33 (2008)
Lu, Q., George, B., Shekhar, S.: Capacity constrained routing algorithms for evacuation planning: A summary of results. In: Medeiros, C.B., Egenhofer, M.J., Bertino, E. (eds.) SSTD 2005. LNCS, vol. 3633, pp. 291–307. Springer, Heidelberg (2005)
Shekhar, S., Yang, K., Gunturi, V.M.V., Manikonda, L., et al.: Experiences with evacuation route planning algorithms. International Journal of Geographical Information Science 26(12), 2253–2265 (2012)
Berman, P.: On-line searching and navigation. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms 1996. LNCS, vol. 1442, pp. 232–241. Springer, Heidelberg (1998)
Burgard, W., Moors, M., Fox, D., Simmons, R., Thrum, S.: Collaborative multirobot exploration. In: Proceedings 2000 ICRA, Millennium Conference, IEEE International Conference on Robotics and Automation, Symposia Proceedings, vol. 1, pp. 476–481 (2000)
Xu, Y., Qin, L.: Strategies of groups evacuation from a convex region in the plane. In: Fellows, M., Tan, X., Zhu, B. (eds.) FAW-AAIM 2013. LNCS, vol. 7924, pp. 250–260. Springer, Heidelberg (2013)
Wei, Q., Wang, L.J., Jiang, B.: Tactics for evacuating from an affected area. Proceedings 2013 ICCCI, IJMLC 3(5), 435–439 (2013)
Miyazaki, S., Morimoto, N., Okabe, Y.: The online graph exploration problem on restricted graphs. IEICE, Trans. Inf. & Syst. E92-D(9), 1620–1627 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Wei, Q., Shi, Y., Jiang, B., Wang, L. (2014). Strategies for Evacuating from an Affected Area with One or Two Groups. In: Sun, Xh., et al. Algorithms and Architectures for Parallel Processing. ICA3PP 2014. Lecture Notes in Computer Science, vol 8630. Springer, Cham. https://doi.org/10.1007/978-3-319-11197-1_29
Download citation
DOI: https://doi.org/10.1007/978-3-319-11197-1_29
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11196-4
Online ISBN: 978-3-319-11197-1
eBook Packages: Computer ScienceComputer Science (R0)