Abstract
The rescue problem is an adaptation of a standard Vehicle Routing Problem where a set of patients suffering from various medical conditions has to be picked up by a set of ambulances and brought back to the hospital. Optimizing this problem is important to improve the use of life emergency vehicles in daily or disaster situations. Although this problem is usually modeled as a Capacitated Vehicle Routing Problem, different formulations are proposed in the literature including multi-objective optimization with shortest route and maximization of the number of patients that will survive or remain stable. Ant Colony Optimization (ACO) and Genetic Algorithms (GA) are frequently used, where ACO performs better on objectives specific to the rescue problem. We model the problem as a single-objective Vehicle Routing Problem with Time Windows (VRPTW) using hard time windows. Each patient is assigned a degree of injury and a corresponding maximum time window. An immediate return to the hospital for critically injured patients is also introduced. The rescue problem turns to a VRPTW with hard time windows for different problem sizes and is solved with ACO. The results suggest that with a sufficiently large fleet, it can be ensured that critically injured patients are reached in good time.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Wang X, Choi T-M, Liu H, Yue X (2018) A novel hybrid ant colony optimization algorithm for emergency transportation problems during post-disaster scenarios. IEEE Trans Syst Man Cybern Syst 48(4):545–556. https://doi.org/10.1109/TSMC.2016.2606440
Rabbani M, Oladzad-Abbasabady N, Akbarian-Saravi N (2021) Ambulance routing in disaster response considering variable patient condition: NSGA-II and MOPSO algorithms. J Ind Manag Optim 18(2):1035. https://doi.org/10.3934/jimo.2021007
El Fallahi A, Sefrioui I (2019) A linear programming model and memetic algorithm for the emergency vehicle routing. In: 2019 4th world conference on complex systems (WCCS), p 1–5. https://doi.org/10.1109/ICoCS.2019.8930750
Talarico L, Meisel F, Sörensen K (2015) Ambulance routing for disaster response with patient groups. Comput Oper Res 56:120–133. https://doi.org/10.1016/J.COR.2014.11.006
Tlili T, Abidi S, Krichen S (2018) A mathematical model for efficient emergency transportation in a disaster situation. Am J Emerg Med 36(9):1585–1590. https://doi.org/10.1016/J.AJEM.2018.01.039
Zhu L, Gong Y, Xu Y, Gu J (2019) Emergency relief routing models for injured victims considering equity and priority. Ann Oper Res 283(1–2):1573–1606. https://doi.org/10.1007/s10479-018-3089-3
Graf M, Poy M, Bischof S, Dornberger R, Hanne T (2018) Rescue path optimization using ant colony systems. In: Proceedings of the 2017 IEEE symposium series on computational intelligence (SSCI 2018), vol 2018, p 1–7. https://doi.org/10.1109/SSCI.2017.8280873
Dorigo M., Di Caro G (1999) Ant colony optimization: a new meta-heuristic. In: Proceedings of the 1999 congress on evolutionary computation (CEC 1999), vol 2, p 1470–1477. https://doi.org/10.1109/CEC.1999.782657
Othman WAF, Abd Wahab AA, Alhady SS, Wong HN (2018) Solving vehicle routing problem using ant colony optimisation (ACO) algorithm. Int J Res Eng 5(9):500–507. https://doi.org/10.21276/ijre.2018.5.9.2
Gulden L (2015) ACO_CVRP. GitHub repository. https://github.com/LucGulden/ACO_CVRP. Accessed 15 May 2021
Shen Y, Liu M, Yang J, Shi Y, Middendorf M (2020) A hybrid swarm intelligence algorithm for vehicle routing problem with time windows. IEEE Access 8:93882–93893. https://doi.org/10.1109/ACCESS.2020.2984660
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Suppan, M., Hanne, T., Dornberger, R. (2022). Ant Colony Optimization to Solve the Rescue Problem as a Vehicle Routing Problem with Hard Time Windows. In: Uddin, M.S., Jamwal, P.K., Bansal, J.C. (eds) Proceedings of International Joint Conference on Advances in Computational Intelligence. Algorithms for Intelligent Systems. Springer, Singapore. https://doi.org/10.1007/978-981-19-0332-8_5
Download citation
DOI: https://doi.org/10.1007/978-981-19-0332-8_5
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-19-0331-1
Online ISBN: 978-981-19-0332-8
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)