Online algorithms for ambulance routing in disaster response with time-varying victim conditions

Shiri, Davood; Akbari, Vahid; Salman, F. Sibel

Abstract

We present a novel online optimization approach to tackle the ambulance routing problem on a road network, specifically designed to handle uncertainties in travel times, triage levels, required treatment times of victims, and potential changes in victim conditions in post-disaster scenarios. We assume that this information can be learned incrementally online while the ambulances get to the scene. We analyze this problem using the competitive ratio criterion and demonstrate that, when faced with a worst-case instance of this problem, neither deterministic nor randomized online solutions can attain a finite competitive ratio. Subsequently, we present a variety of innovative online heuristics to address this problem which can operate with very low computational running times. We assess the effectiveness of our online solutions by comparing them with each other and with offline solutions derived from complete information. Our analysis involves examining instances from existing literature as well as newly generated large-sized instances. One of our algorithms demonstrates superior performance when compared to the others, achieving experimental competitive ratios that closely approach the optimal ratio of one.

Citation

Shiri, D., Akbari, V., & Salman, F. S. (2024). Online algorithms for ambulance routing in disaster response with time-varying victim conditions. OR Spectrum, 46(3), 785-819. https://doi.org/10.1007/s00291-024-00744-4

• Journal Article Type: Article
• Acceptance Date: Jan 4, 2024
• Online Publication Date: Feb 7, 2024
• Publication Date: Sep 1, 2024
• Deposit Date: Mar 15, 2024
• Publicly Available Date: Mar 15, 2024
• Journal: OR Spectrum
• Print ISSN: 0171-6468
• Electronic ISSN: 1436-6304
• Publisher: Springer Verlag
• Peer Reviewed: Peer Reviewed
• Volume: 46
• Issue: 3
• Pages: 785-819
• DOI: https://doi.org/10.1007/s00291-024-00744-4
• Keywords: Management Science and Operations Research; Business, Management and Accounting (miscellaneous)
• Public URL: https://nottingham-repository.worktribe.com/output/32466592
• Publisher URL: https://link.springer.com/article/10.1007/s00291-024-00744-4
• Additional Information: Received: 10 December 2022; Accepted: 4 January 2024; First Online: 7 February 2024