IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v36y2018i1d10.1007_s10878-018-0284-8.html
   My bibliography  Save this article

An improved online evacuation strategy from a convex region on grid networks

Author

Listed:
  • Guiqing Zhang

    (Xi’an Jiaotong University)

  • Yongxi Cheng

    (Xi’an Jiaotong University
    State Key Lab for Manufacturing Systems Engineering)

  • Lan Qin

    (Xi’an Jiaotong University
    State Key Lab for Manufacturing Systems Engineering)

Abstract

This study considers an evacuation problem where an evacuee tries to escape to the boundary of a convex affected area on a grid network. The boundary is unknown to the evacuee and cannot be identified until reaching an arbitrary point of it. We propose an online evacuation strategy with a competitive ratio less than 17.5, which improves the previously best result of 19.5.

Suggested Citation

  • Guiqing Zhang & Yongxi Cheng & Lan Qin, 2018. "An improved online evacuation strategy from a convex region on grid networks," Journal of Combinatorial Optimization, Springer, vol. 36(1), pages 44-54, July.
    • Handle: RePEc:spr:jcomop:v:36:y:2018:i:1:d:10.1007_s10878-018-0284-8
    DOI: 10.1007/s10878-018-0284-8
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-018-0284-8
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-018-0284-8?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Gino J. Lim & Mukesh Rungta & M. Reza Baharnemati, 2015. "Reliability analysis of evacuation routes under capacity uncertainty of road links," IISE Transactions, Taylor & Francis Journals, vol. 47(1), pages 50-63, January.
    2. X Chen & F B Zhan, 2008. "Agent-based modelling and simulation of urban evacuation: relative effectiveness of simultaneous and staged evacuation strategies," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(1), pages 25-33, January.
    3. Lan Qin & Yinfeng Xu, 2017. "Fibonacci helps to evacuate from a convex region in a grid network," Journal of Combinatorial Optimization, Springer, vol. 34(2), pages 398-413, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Zhengfeng Huang & Pengjun Zheng & Gang Ren & Yang Cheng & Bin Ran, 2016. "Simultaneous optimization of evacuation route and departure time based on link-congestion mitigation," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 83(1), pages 575-599, August.
    2. Kun Yang & Rachel A. Davidson & Humberto Vergara & Randall L. Kolar & Kendra M. Dresback & Brian A. Colle & Brian Blanton & Tricia Wachtendorf & Jennifer Trivedi & Linda K. Nozick, 2019. "Incorporating inland flooding into hurricane evacuation decision support modeling," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 96(2), pages 857-878, March.
    3. Nagarajan, Magesh & Shaw, Duncan & Albores, Pavel, 2012. "Disseminating a warning message to evacuate: A simulation study of the behaviour of neighbours," European Journal of Operational Research, Elsevier, vol. 220(3), pages 810-819.
    4. Jorge León & Alan March, 2016. "An urban form response to disaster vulnerability: Improving tsunami evacuation in Iquique, Chile," Environment and Planning B, , vol. 43(5), pages 826-847, September.
    5. Akiko Masuya & Ashraf Dewan & Robert Corner, 2015. "Population evacuation: evaluating spatial distribution of flood shelters and vulnerable residential units in Dhaka with geographic information systems," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 78(3), pages 1859-1882, September.
    6. Esposito Amideo, A. & Scaparra, M.P. & Kotiadis, K., 2019. "Optimising shelter location and evacuation routing operations: The critical issues," European Journal of Operational Research, Elsevier, vol. 279(2), pages 279-295.
    7. Pruttipong Apivatanagul & Rachel Davidson & Linda Nozick, 2012. "Bi-level optimization for risk-based regional hurricane evacuation planning," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 60(2), pages 567-588, January.
    8. Soga, Kenichi & Comfort, Louise & Zhao, Bingyu & Lorusso, Paola & Soysal, Sena, 2021. "Integrating Traffic Network Analysis and Communication Network Analysis at a Regional Scale to Support More Efficient Evacuation in Response to a Wildfire Event," Institute of Transportation Studies, Research Reports, Working Papers, Proceedings qt1z913878, Institute of Transportation Studies, UC Berkeley.
    9. Stephen D. Wong & Jacquelyn C. Broader & Joan L. Walker & Susan A. Shaheen, 2023. "Understanding California wildfire evacuee behavior and joint choice making," Transportation, Springer, vol. 50(4), pages 1165-1211, August.
    10. Thomas J. Cova & Philip E. Dennison & Frank A. Drews, 2011. "Modeling Evacuate versus Shelter-in-Place Decisions in Wildfires," Sustainability, MDPI, vol. 3(10), pages 1-26, September.
    11. Yu Song & Jia Liu & Qian Liu, 2021. "Dynamic Decision-Making Process of Evacuees during Post-Earthquake Evacuation near an Automatic Flap Barrier Gate System: A Broken Windows Perspective," Sustainability, MDPI, vol. 13(16), pages 1-19, August.
    12. Rui Ding, 2019. "The Complex Network Theory-Based Urban Land-Use and Transport Interaction Studies," Complexity, Hindawi, vol. 2019, pages 1-14, June.
    13. Ling Yin & Jie Chen & Hao Zhang & Zhile Yang & Qiao Wan & Li Ning & Jinxing Hu & Qi Yu, 2020. "Improving emergency evacuation planning with mobile phone location data," Environment and Planning B, , vol. 47(6), pages 964-980, July.
    14. Irena Ali & Mathew Zuparic & Iain Macleod & Phuong La & Yi Yue, 2017. "Complex socio-organisational phenomena and ill-defined problem spaces: a multi-method approach to the rescue," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(8), pages 919-934, August.
    15. Zhaoqi Zang & Xiangdong Xu & Kai Qu & Ruiya Chen & Anthony Chen, 2022. "Travel time reliability in transportation networks: A review of methodological developments," Papers 2206.12696, arXiv.org, revised Jul 2022.
    16. L Ferreira & D Borenstein, 2011. "Normative agent-based simulation for supply chain planning," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(3), pages 501-514, March.
    17. Galindo, Gina & Batta, Rajan, 2013. "Review of recent developments in OR/MS research in disaster operations management," European Journal of Operational Research, Elsevier, vol. 230(2), pages 201-211.
    18. Bretschneider, S. & Kimms, A., 2011. "A basic mathematical model for evacuation problems in urban areas," Transportation Research Part A: Policy and Practice, Elsevier, vol. 45(6), pages 523-539, July.
    19. Wang, Qingyi & Wallace, Stein W., 2022. "Non-compliance in transit-based evacuation pick-up point assignments," Socio-Economic Planning Sciences, Elsevier, vol. 82(PB).
    20. Marion Rauner & Michaela Schaffhauser-Linzatti & Helmut Niessner, 2012. "Resource planning for ambulance services in mass casualty incidents: a DES-based policy model," Health Care Management Science, Springer, vol. 15(3), pages 254-269, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:36:y:2018:i:1:d:10.1007_s10878-018-0284-8. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.