Online algorithms for ambulance routing in disaster response with time-varying victim conditions. (English) Zbl 07924479
Summary: 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.
MSC:
| 90B06 | Transportation, logistics and supply chain management |
| 68W27 | Online algorithms; streaming algorithms |
References:
| [1] | Akbari, V.; Shiri, D., Weighted online minimum latency problem with edge uncertainty, Eur J Oper Res, 295, 1, 51-65, 2021 · Zbl 1487.90614 · doi:10.1016/j.ejor.2021.02.038 |
| [2] | Akbari, V.; Shiri, D., An online optimization approach for post-disaster relief distribution with online blocked edges, Comput Op Res, 137, 2022 · Zbl 1511.90022 · doi:10.1016/j.cor.2021.105533 |
| [3] | Akbari, V.; Shiri, D.; Sibel Salman, F., An online optimization approach to post-disaster road restoration, Trans Res Part B: Methodol, 150, 1-25, 2021 · doi:10.1016/j.trb.2021.05.017 |
| [4] | Anuar, Wadi Khalid, Lee, Lai Soon, Pickl, Stefan, & Seow, Hsin-Vonn. 2021. Vehicle Routing Optimisation in Humanitarian Operations: A Survey on Modelling and Optimisation Approaches. Appl Sci 11(2) |
| [5] | Aringhieri, R.; Bruni, ME; Khodaparasti, S.; van Essen, JT, Emergency medical services and beyond: Addressing new challenges through a wide literature review, Comput Op Res, 78, 349-368, 2017 · Zbl 1391.90366 · doi:10.1016/j.cor.2016.09.016 |
| [6] | Aringhieri, R.; Bigharaz, S.; Duma, D.; Guastalla, A., Fairness in ambulance routing for post disaster management, CEJOR, 30, 189-211, 2022 · Zbl 07597431 · doi:10.1007/s10100-021-00785-y |
| [7] | Ausiello, G.; Feuerstein, E.; Leonardi, S.; Stougie, L.; Talamo, M., Algorithms for the on-line travelling salesman, Algorithmica, 29, 4, 560-581, 2001 · Zbl 0985.68088 · doi:10.1007/s004530010071 |
| [8] | Brown, LC; David, B.; Smith, LC; Micah, J.; Chibi, LC; Tazi, M.; Hassani, N.; Lotfi, CB, Minimizing postdisaster fatalities, Fed Pract, 34, 2, 10, 2017 |
| [9] | Bélanger, V.; Ruiz, A.; Soriano, P., Recent optimization models and trends in location, relocation, and dispatching of emergency medical vehicles, Eur J Oper Res, 272, 1, 1-23, 2019 · Zbl 1403.90469 · doi:10.1016/j.ejor.2018.02.055 |
| [10] | Büttner, S.; Krumke, SO, The Canadian Tour Operator Problem on paths: tight bounds and resource augmentation, J Comb Optim, 32, 842-854, 2016 · Zbl 1354.90151 · doi:10.1007/s10878-015-9905-7 |
| [11] | CRED (2013) People affected by conflict: Humanitarian needs in numbers. Tech. rept, Centre for Research on the Epidemiology of Disasters, Brussels |
| [12] | CRED, & UNDRR. 2020. Human cost of disasters: An overview of the last twenty years 2000-2019. Tech. rept. Centre for Research on the Epidemiology of Disasters and UN Office for Disaster Risk Reduction |
| [13] | Daud, SM; Mohd, S.; Yusof, MY; Mohd, P.; Heo, CC; Khoo, LS; Singh, MK; Chainchel, M.; Shah, M.; Nawawi, H., Applications of drone in disaster management: A scoping review, Sci Justice, 62, 1, 30-42, 2022 · doi:10.1016/j.scijus.2021.11.002 |
| [14] | De la Torre, Luis E., Dolinskaya, Irina S., & Smilowitz, Karen R. 2012. Disaster relief routing: Integrating research and practice. Socio-Economic Planning Sciences, 46(1), 88-97. Special Issue: Disaster Planning and Logistics: Part 1 |
| [15] | Dukkanci, O.; Koberstein, A.; Kara, BY, Drones for relief logistics under uncertainty after an earthquake, Eur J Oper Res, 310, 1, 117-132, 2023 · Zbl 07709807 · doi:10.1016/j.ejor.2023.02.038 |
| [16] | Farahani, RZ; Lotfi, MM; Baghaian, A.; Ruiz, R.; Rezapour, S., Mass casualty management in disaster scene: A systematic review of OR & MS research in humanitarian operations, Eur J Oper Res, 287, 3, 787-819, 2020 · Zbl 1487.90098 · doi:10.1016/j.ejor.2020.03.005 |
| [17] | Ghiani, G.; Guerriero, F.; Laporte, G.; Musmanno, R., Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies, Eur J Oper Res, 151, 1, 1-11, 2003 · Zbl 1033.90014 · doi:10.1016/S0377-2217(02)00915-3 |
| [18] | Jaillet, P.; Wagner, MR, Generalized Online Routing: New Competitive Ratios, Resource Augmentation, and Asymptotic Analyses, Oper Res, 56, 745-757, 2008 · Zbl 1167.90381 · doi:10.1287/opre.1070.0450 |
| [19] | Jat, MN; Rafique, RA, Mass-Casualty distribution for emergency healthcare: a simulation analysis, Int J Disaster Risk Sci, 11, 3, 364-377, 2020 · doi:10.1007/s13753-020-00260-3 |
| [20] | Khoshgehbari, Farnaz, Al-e, S Mohammad J Mirzapour, et al. 2023. Ambulance Location Routing Problem Considering all Sources of Uncertainty: Progressive Estimating Algorithm. Comput Op Res, 106400 · Zbl 07764435 |
| [21] | Lee, Y-C; Chen, Y-S; Chen, AY, Lagrangian dual decomposition for the ambulance relocation and routing considering stochastic demand with the truncated Poisson, Trans Res Part B: Methodol, 157, 1-23, 2022 · doi:10.1016/j.trb.2021.12.016 |
| [22] | Letchford Adam N, Salazar-González, & Juan-José. (2006) Projection results for vehicle routing. Math Progr 105(2):251-274 · Zbl 1085.90032 |
| [23] | Liang, N-J; Shih, Y-T; Shih, F-Y; Wu, H-M; Wang, H-J; Shi, S-F; Liu, M-Y; Wang, BB, Disaster epidemiology and medical response in the Chi-Chi earthquake in Taiwan, Ann Emerg Med, 38, 5, 549-555, 2001 · doi:10.1067/mem.2001.118999 |
| [24] | Lu, Lili, & Wang, Shuaian. 2019. Literature Review of Analytical Models on Emergency Vehicle Service: Location, Dispatching, Routing and Preemption Control. Pages 3031-3036 of: 2019 IEEE Intelligent Transportation Systems Conference (ITSC) |
| [25] | Ma, W.; Simchi-Levi, D., Algorithms for online matching, assortment, and pricing with tight weight-dependent competitive ratios, Oper Res, 68, 6, 1787-1803, 2020 · Zbl 1457.90129 · doi:10.1287/opre.2019.1957 |
| [26] | Ma, W.; Simchi-Levi, D.; Teo, C-P, On policies for single-leg revenue management with limited demand information, Oper Res, 69, 1, 207-226, 2021 · Zbl 1467.91049 · doi:10.1287/opre.2020.2048 |
| [27] | Najafi, M.; Eshghi, K.; de Leeuw, S., A dynamic dispatching and routing model to plan/ re-plan logistics activities in response to an earthquake, OR Spectrum, 36, 2, 323-356, 2014 · Zbl 1290.90015 · doi:10.1007/s00291-012-0317-0 |
| [28] | Rios, O.; Humberto, B.; Xavier, EC; Miyazawa, FK; Amorim, P.; Curcio, E.; Santos, MJ, Recent dynamic vehicle routing problems: A survey, Comput Indus Eng, 160, 2021 · doi:10.1016/j.cie.2021.107604 |
| [29] | Oksuz, MK; Satoglu, SI, A two-stage stochastic model for location planning of temporary medical centers for disaster response, Int J Disaster Risk Reduct, 44, 2020 · doi:10.1016/j.ijdrr.2019.101426 |
| [30] | Pillac, V.; Gendreau, M.; Guéret, C.; Medaglia, AL, A review of dynamic vehicle routing problems, Eur J Oper Res, 225, 1, 1-11, 2013 · Zbl 1292.90203 · doi:10.1016/j.ejor.2012.08.015 |
| [31] | Rabbani, M.; Oladzad-Abbasabady, N.; Akbarian-Saravi, N., Ambulance routing in disaster response considering variable patient condition: NSGA-II and MOPSO algorithms, J Indus Manag Optim, 18, 2, 1035-1062, 2022 · Zbl 1499.90032 · doi:10.3934/jimo.2021007 |
| [32] | Ritzinger, U.; Puchinger, J.; Rudloff, C.; Hartl, RF, Comparison of anticipatory algorithms for a dial-a-ride problem, Eur J Oper Res, 301, 2, 591-608, 2022 · Zbl 1506.90058 · doi:10.1016/j.ejor.2021.10.060 |
| [33] | Salman, FS; Gül, S., Deployment of field hospitals in mass casualty incidents, Comput Indus Eng, 74, 37-51, 2014 · doi:10.1016/j.cie.2014.04.020 |
| [34] | Schilde, M.; Doerner, KF; Hartl, RF, Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports, Comput Oper Res, 38, 12, 1719-1730, 2011 · Zbl 1215.90014 · doi:10.1016/j.cor.2011.02.006 |
| [35] | Shiri, D.; Salman, FS, Online Optimization of First-responder Routes in Disaster Response Logistics, IBM J Res Dev, 64, 1-9, 2020 · doi:10.1147/JRD.2019.2947002 |
| [36] | Shiri, D.; Akbari, V.; Salman, FS, Online routing and scheduling of search-and-rescue teams, OR Spectrum, 42, 3, 755-784, 2020 · doi:10.1007/s00291-020-00594-w |
| [37] | Shiri, Davood, Akbari, Vahid, & Tozan, Hakan. 2023. Online optimisation for ambulance routing in disaster response with partial or no information on victim conditions. Comput Oper Res, 106314 · Zbl 1543.90050 |
| [38] | Sleator, D.; Tarjan, R., Amortized efficiency of list update and paging rules, Commun ACM, 28, 202-208, 1985 · doi:10.1145/2786.2793 |
| [39] | Soeffker, N.; Ulmer, MW; Mattfeld, DC, Stochastic dynamic vehicle routing in the light of prescriptive analytics: A review, Eur J Oper Res, 298, 3, 801-820, 2022 · Zbl 1490.90069 · doi:10.1016/j.ejor.2021.07.014 |
| [40] | Talarico Luca, Meisel Frank, Sörensen Kenneth (2015) Ambulance routing for disaster response with patient groups. Comput Opera Res 56:120-133 · Zbl 1348.90133 |
| [41] | Talebi, E.; Shaabani, M.; Rabbani, M., Bi-objective model for ambulance routing for disaster response by considering priority of patients, Int J Supply Oper Manag, 9, 1, 80-94, 2022 |
| [42] | Tiedemann, Morten, Ide, Jonas, & Schöbel, Anita. 2015. Competitive analysis for multi-objective online algorithms. Pages 210-221 of: International Workshop on Algorithms and Computation. Springer · Zbl 1390.68773 |
| [43] | Tikani, H.; Setak, M., Ambulance routing in disaster response scenario considering different types of ambulances and semi soft time windows, J Indus Syst Eng, 12, 1, 95-128, 2019 |
| [44] | Tippong, D.; Petrovic, S.; Akbari, V., A review of applications of operational research in healthcare coordination in disaster management, Eur J Oper Res, 301, 1, 1-17, 2022 · Zbl 1506.90154 · doi:10.1016/j.ejor.2021.10.048 |
| [45] | Tlili, Takwa, Harzi, Marwa, & Krichen, Saoussen. 2017. Swarm-based approach for solving the ambulance routing problem. Procedia Computer Science, 112, 350-357. Knowledge-Based and Intelligent Information & Engineering Systems: Proceedings of the 21st International Conference, KES-20176-8 September 2017, Marseille, France |
| [46] | Tlili, T.; Abidi, S.; Krichen, S., A mathematical model for efficient emergency transportation in a disaster situation, Am J Emerg Med, 36, 9, 1585-1590, 2018 · doi:10.1016/j.ajem.2018.01.039 |
| [47] | Yao, Andrew Chi-Chih. (1977) Probabilistic computations: Towards a unified measure of complexity. Proceedings of the 18th Annual IEEE Symposium on the Foundations of Computer Science, 222-227 |
| [48] | Yao, C.; Chen, S.; Yang, Z., Online distributed routing problem of electric vehicles, IEEE Trans Intell Transp Syst, 23, 9, 16330-16341, 2022 · doi:10.1109/TITS.2022.3149942 |
| [49] | Yazdani, M.; Haghani, M., Optimisation-based integrated decision model for ambulance routing in response to pandemic outbreaks, Progr Disaster Sci, 18, 2023 · doi:10.1016/j.pdisas.2023.100288 |
| [50] | Yoon, S.; Albert, LA, A dynamic ambulance routing model with multiple response, Trans Res Part E: Logist Trans Rev, 133, 2020 · doi:10.1016/j.tre.2019.11.001 |
| [51] | Zhang, H.; Tong, W.; Lin, G.; Xu, Y., Online minimum latency problem with edge uncertainty, Eur J Oper Res, 273, 418-429, 2019 · doi:10.1016/j.ejor.2018.08.017 |
| [52] | Zidi, Issam, Al-Omani, Mohammad, & Aldhafeeri, Karim. 2019. A New Approach Based On the Hybridization of Simulated Annealing Algorithm and Tabu Search to Solve the Static Ambulance Routing Problem. Procedia Computer Science, 159, 1216-1228. Knowledge-Based and Intelligent Information & Engineering Systems: Proceedings of the 23rd International Conference KES2019 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
