An online real-time matheuristic algorithm for dispatch and relocation of ambulances

Abstract: The Medical System of Transportation deals with two online real-time decisions: ambulance dispatching and relocation. Dispatching consists of selecting which ambulance to send to an emergency call; relocation consists of determining how to modify the location of available ambulances in response to changes in the system’s state. Although the literature regarding this problem is extensive, only a limited number of online real-time approaches for ambulance management have been proposed, much less one taking into consideration different types of emergencies and vehicles. This paper proposes an online real-time matheuristic algorithm that combines: i) a new preparedness index defined as the availability probability of a multi-server queue model which is used as an optimization objective and as a control variable for relocation strategies, ii) two mathematical models to solve the relocation problem, one oriented to the maximization of coverage and other to the minimization of the maximum relocation time, and iii) two heuristic algorithms oriented to the maximization of the preparedness level, one to solve the dispatch problem and other to solve the location problem of one ambulance. The computational experiments, based on discrete event simulation and historical data of Bogotá, Colombia, have shown their capability to adequately respond to the necessities of real-time operation.

How to cite this paper

 Roa, J., Escobar, J & Moreno, C. (2020). An online real-time matheuristic algorithm for dispatch and relocation of ambulances.International Journal of Industrial Engineering Computations , 11(3), 443-468.

Refrences

Andersson, T., & Värbrand, P. (2007). Decision support tools for ambulance dispatch and relocation. Journal of the Operational Research Society, 58(2), 195-201.
Aringhieri, R., Bruni, M. E., Khodaparasti, S., & van Essen, J. T. (2017). Emergency medical services and beyond: Addressing new challenges through a wide literature review. Computers & Operations Research, 78, 349-368.
Aringhieri, R., Bocca, S., Casciaro, L., & Duma, D. (2018). A simulation and online optimization approach for the real-time management of ambulances. In Proceedings of the 2018 Winter Simulation Conference (pp. 2554-2565). IEEE Press.
Bagherinejad, J., & Shoeib, M. (2018). Dynamic capacitated maximal covering location problem by considering dynamic capacity. International Journal of Industrial Engineering Computations, 9(2), 249-264.
Başar, A., Çatay, B., & Ünlüyurt, T. (2012). A taxonomy for emergency service station location problem. Optimization letters, 6(6), 1147-1160.
Bélanger, V., Ruiz, A., Soriano, P., & Lanzarone, E. (2015). The ambulance relocation and dispatching problem. CIRRELT.
Bélanger, V., Kergosien, Y., Ruiz, A., & Soriano, P. (2016). An empirical comparison of relocation strategies in real-time ambulance fleet management. Computers & Industrial Engineering, 94, 216-229.
Bélanger, V., Ruiz, A., & Soriano, P. (2019). Recent optimization models and trends in location, relocation, and dispatching of emergency medical vehicles. European Journal of Operational Research, 272(1), 1-23.
Daskin, M. S. (1983). A maximum expected covering location model: formulation, properties and heuristic solution. Transportation science, 17(1), 48-70.
Enayati, S., Mayorga, M. E., Rajagopalan, H. K., & Saydam, C. (2018, a). Real-time ambulance redeployment approach to improve service coverage with fair and restricted workload for EMS providers. Omega, 79, 67-80.
Enayati, S., Özaltın, O. Y., Mayorga, M. E., & Saydam, C. (2018, b). Ambulance redeployment and dispatching under uncertainty with personnel workload limitations. IISE Transactions, 50(9), 777-788.
Enayati, S., Mayorga, M. E., Toro‐Díaz, H., & Albert, L. A. (2019). Identifying trade‐offs in equity and efficiency for simultaneously optimizing location and multipriority dispatch of ambulances. International Transactions in Operational Research, 26(2), 415-438.
Gendreau, M., Laporte, G., & Semet, F. (1997). Solving an ambulance location model by tabu search. Location Science, 5(2), 75-88.
Gendreau, M., Laporte, G., & Semet, F. (2001). A dynamic model and parallel tabu search heuristic for real-time ambulance relocation. Parallel computing, 27(12), 1641-1653.
Goldberg, J. B. (2004). Operations research models for the deployment of emergency services vehicles. EMS management Journal, 1(1), 20-39.
Haghani, A., & Yang, S. (2007). Real-time emergency response fleet deployment: Concepts, systems, simulation & case studies. In Dynamic fleet management (pp. 133-162). Springer, Boston, MA.
Hakimi, S. L. (1964). Optimum locations of switching centers and the absolute centers and medians of a graph. Operations research, 12(3), 450-459.
Jagtenberg, C. J., Bhulai, S., & Van der Mei, R. D. (2015). An efficient heuristic for real-time ambulance redeployment. Operations Research for Health Care, 4, 27-35.
Karimi, A., Gendreau, M., & Verter, V. (2018). Performance Approximation of Emergency Service Systems with Priorities and Partial Backups. Transportation Science, 52(5), 1235-1252.
Kergosien, Y., Bélanger, V., Soriano, P., Gendreau, M., & Ruiz, A. (2015). A generic and flexible simulation-based analysis tool for EMS management. International Journal of Production Research, 53(24), 7299-7316.
Lee, S. (2011). The role of preparedness in ambulance dispatching. Journal of the Operational Research Society, 62(10), 1888-1897.
Maxwell, M. S., Restrepo, M., Henderson, S. G., & Topaloglu, H. (2010). Approximate dynamic programming for ambulance redeployment. INFORMS Journal on Computing, 22(2), 266-281.
Maxwell, M. S., Henderson, S. G., & Topaloglu, H. (2013). Tuning approximate dynamic programming policies for ambulance redeployment via direct search. Stochastic Systems, 3(2), 322-361.
Maxwell, M. S., Ni, E. C., Tong, C., Henderson, S. G., Topaloglu, H., & Hunter, S. R. (2014). A bound on the performance of an optimal ambulance redeployment policy. Operations Research, 62(5), 1014-1027.
McCormack, R., & Coates, G. (2015). A simulation model to enable the optimization of ambulance fleet allocation and base station location for increased patient survival. European Journal of Operational Research, 247(1), 294-309.
Nasrollahzadeh, A. A., Khademi, A., & Mayorga, M. E. (2018). Real-time ambulance dispatching and relocation. Manufacturing & Service Operations Management, 20(3), 467-480.
Pinto, L. R., Silva, P. M., et al. (2015). A generic method to develop simulation models for ambulance systems. Simulation Modelling Practice and Theory, 51, 170-183.
Schmid, V. (2012). Solving the dynamic ambulance relocation and dispatching problem using approximate dynamic programming. European Journal of Operational Research, 219(3), 611-621.
Sudtachat, K., Mayorga, M. E., & Mclay, L. A. (2016). A nested-compliance table policy for emergency medical service systems under relocation. Omega, 58, 154-168.
Sung, I., & Lee, T. (2018). Scenario-based approach for the ambulance location problem with stochastic call arrivals under a dispatching policy. Flexible Services and Manufacturing Journal, 30(1-2), 153-170.
van Barneveld, T. C., Bhulai, S., & van der Mei, R. D. (2016). The effect of ambulance relocations on the performance of ambulance service providers. European Journal of Operational Research, 252(1), 257-269.
van Barneveld, T. C., Bhulai, S., & van der Mei, R. D. (2017, a). A dynamic ambulance management model for rural areas. Health care Management Science, 20(2), 165-186.
van Barneveld, T. C., van der Mei, R. D., & Bhulai, S. (2017, b). Compliance tables for an EMS system with two types of medical response units. Computers & Operations Research, 80, 68-81.
van Barneveld, T., Jagtenberg, C., Bhulai, S., & van der Mei, R. (2018). Real-time ambulance relocation: Assessing real-time redeployment strategies for ambulance relocation. Socio-Economic Planning Sciences, 62, 129-142.
van den Berg, P. L., Fiskerstrand, P., Aardal, K., Einerkjær, J., Thoresen, T., & Røislien, J. (2019). Improving ambulance coverage in a mixed urban-rural region in Norway using mathematical modeling. PloS one, 14(4), e0215385.