Ambulance routing in disaster response scenario considering different types of ambulances and semi soft time windows

Document Type : Research Paper

Authors

Department of Industrial Engineering, K.N. Toosi University of Technology, Tehran, Iran

Abstract

This paper studies the ambulance routing problem (ARP) in disaster situations when a large number of injured people from various locations require receiving treatments and medical aids. In such circumstances, many people summoning the ambulances but the capacity and number of emergency vehicles are not sufficient to visit all the patients at the same time. Therefore, a pivotal issue is to manage the fleet of ambulances to meet all the requests promptly and consequently mitigate human suffering. We considered three different categories of patients with various requirements. Moreover, the support ambulances are segmented into various classes based on their capabilities. A mathematical formulation is presented to obtain route plans with the aim of minimizing the latest service completion time among the patients. Since the patient’s condition gets worse and becomes life ­threatening over the time, semi-soft time window constraint is incorporated to reflect the penalties on late arrivals using survival function. Since the presented model belongs to the class of NP-hard problems, two efficient meta-heuristic algorithms based on genetic algorithm and tabu search are proposed to cope with real size problems. The experiments show that the proposed model could present proper routes and adopt the types of ambulances with the patients’ needs to increase the service quality. Moreover, the proposed metaheuristics are capable to find acceptable solutions for the problem in reasonable computational times.
 

Keywords

Main Subjects

References

Abounacer, R., Rekik, M., & Renaud, J. (2014). An exact solution approach for multi-objective location–transportation problem for disaster response. Computers & Operations Research, 41, 83-93.
 
Andersson, T., & Värbrand, P. (2007). Decision support tools for ambulance dispatch and relocation. Journal of the Operational Research Society, 58(2), 195-201.
 
Barbarosoǧlu, G., & Arda, Y. (2004). A two-stage stochastic programming framework for transportation planning in disaster response. Journal of the operational research society, 55(1), 43-53.
 
Berkoune, D., Renaud, J., Rekik, M., & Ruiz, A. (2012). Transportation in disaster response operations. Socio-Economic Planning Sciences, 46(1), 23-32.
 
Bozorgi-Amiri, A., Tavakoli, S., Mirzaeipour, H., & Rabbani, M. (2017). Integrated locating of helicopter stations and helipads for wounded transfer under demand location uncertainty. The American journal of emergency medicine, 35(3), 410-417.
 
Brandão, J. (2016). A deterministic iterated local search algorithm for the vehicle routing problem with backhauls. TOP, 24(2), 445-465.
 
Bräysy, O., & Gendreau, M. (2002). Tabu search heuristics for the vehicle routing problem with time windows. Top, 10(2), 211-237.
 
Brotcorne, L., Laporte, G., & Semet, F. (2003). Ambulance location and relocation models. European journal of operational research, 147(3), 451-463.
 
Camacho-Vallejo, J. F., González-Rodríguez, E., Almaguer, F. J., & González-Ramírez, R. G. (2015). A bi-level optimization model for aid distribution after the occurrence of a disaster. Journal of Cleaner Production, 105, 134-145.
 
Campbell, A. M., Vandenbussche, D., & Hermann, W. (2008). Routing for relief efforts. Transportation Science, 42(2), 127-145.
 
Carnes, T. A., Henderson, S. G., Shmoys, D. B., Ahghari, M., & MacDonald, R. D. (2013). Mathematical programming guides air-ambulance routing at ornge. Interfaces, 43(3), 232-239.
 
Caunhye, A. M., Nie, X., & Pokharel, S. (2012). Optimization models in emergency logistics: A literature review. Socio-economic planning sciences, 46(1), 4-13.
 
Coppi, A., Detti, P., & Raffaelli, J. (2013). A planning and routing model for patient transportation in health care. Electronic notes in discrete mathematics, 41, 125-132.
 
Detti, P., Papalini, F., & de Lara, G. Z. M. (2017). A multi-depot dial-a-ride problem with heterogeneous vehicles and compatibility constraints in healthcare. Omega, 70, 1-14.
 
Edrissi, A., Poorzahedy, H., Nassiri, H., & Nourinejad, M. (2013). A multi-agent optimization formulation of earthquake disaster prevention and management. European Journal of Operational Research, 229(1), 261-275.
 
Edrissi, A., Nourinejad, M., & Roorda, M. J. (2015). Transportation network reliability in emergency response. Transportation research part E: logistics and transportation review, 80, 56-73.
 
Farahani, R. Z., Asgari, N., Heidari, N., Hosseininia, M., & Goh, M. (2012). Covering problems in facility location: A review. Computers & Industrial Engineering, 62(1), 368-407.
 
Gholami-Zanjani, S. M., Pishvaee, M. S., & Torabi, S. A. (2018). OR Models for Emergency Medical Service (EMS) Management. In Operations Research Applications in Health Care Management (pp. 395-421). Springer, Cham.
 
Gennarelli, T. A., & Wodzin, E. (2008). Abbreviated injury scale 2005: update 2008. Russ Reeder.
 
Gong, Q., & Batta, R. (2007). Allocation and reallocation of ambulances to casualty clusters in a disaster relief operation. IIE Transactions, 39(1), 27-39.
 
Holland, J. H. (1992). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press.
 
Huang, M., Smilowitz, K., & Balcik, B. (2012). Models for relief routing: Equity, efficiency and efficacy. Transportation research part E: logistics and transportation review, 48(1), 2-18.
 
Knight, V. A., Harper, P. R., & Smith, L. (2012). Ambulance allocation for maximal survival with heterogeneous outcome measures. Omega, 40(6), 918-926.
 
Lai, D. S., Demirag, O. C., & Leung, J. M. (2016). A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph. Transportation Research Part E: Logistics and Transportation Review, 86, 32-52.
 
Lam, S. S. W., Nguyen, F. N. H. L., Ng, Y. Y., Lee, V. P. X., Wong, T. H., Fook-Chong, S. M. C., & Ong, M. E. H. (2015). Factors affecting the ambulance response times of trauma incidents in Singapore. Accident Analysis & Prevention, 82, 27-35.
 
Luis, E., Dolinskaya, I. S., & Smilowitz, K. R. (2012). Disaster relief routing: Integrating research and practice. Socio-economic planning sciences, 46(1), 88-97.
 
Marcon, E., Chaabane, S., Sallez, Y., Bonte, T., & Trentesaux, D. (2017). A multi-agent system based on reactive decision rules for solving the caregiver routing problem in home health care. Simulation Modelling Practice and Theory, 74, 134-151.
 
Nable, J. V., Lawner, B. J., & Brady, W. J. (2016). 2016: emergency medical services annotated literature in review. The American journal of emergency medicine, 34(11), 2193-2199.
 
Najafi, M., Eshghi, K., & Dullaert, W. (2013). A multi-objective robust optimization model for logistics planning in the earthquake response phase. Transportation Research Part E: Logistics and Transportation Review, 49(1), 217-249.
 
Özdamar, L., & Ertem, M. A. (2015). Models, solutions and enabling technologies in humanitarian logistics. European Journal of Operational Research, 244(1), 55-65.
 
Özdamar, L., & Demir, O. (2012). A hierarchical clustering and routing procedure for large scale disaster relief logistics planning. Transportation Research Part E: Logistics and Transportation Review, 48(3), 591-602.
 
Özdamar, L., Ekinci, E., & Küçükyazici, B. (2004). Emergency logistics planning in natural disasters. Annals of operations research, 129(1-4), 217-245.
 
Parragh, S. N. (2011). Introducing heterogeneous users and vehicles into models and algorithms for the dial-a-ride problem. Transportation Research Part C: Emerging Technologies, 19(5), 912-930.
 
Parragh, S. N., Cordeau, J. F., Doerner, K. F., & Hartl, R. F. (2012). Models and algorithms for the heterogeneous dial-a-ride problem with driver-related constraints. OR spectrum, 34(3), 593-633.
 
Pedraza-Martinez, A. J., & Van Wassenhove, L. N. (2012). Transportation and vehicle fleet management in humanitarian logistics: challenges for future research. EURO Journal on Transportation and Logistics, 1(1-2), 185-196.
 
Qureshi, A. G., Taniguchi, E., & Yamada, T. (2010). Exact solution for the vehicle routing problem with semi soft time windows and its application. Procedia-Social and Behavioral Sciences, 2(3), 5931-5943.
 
Rath, S., & Gutjahr, W. J. (2014). A math-heuristic for the warehouse location–routing problem in disaster relief. Computers & Operations Research, 42, 25-39.
 
Roy, R. K. (2010). A primer on the Taguchi method. Society of Manufacturing Engineers.
 
Schmid, V., & Doerner, K. F. (2010). Ambulance location and relocation problems with time-dependent travel times. European journal of operational research, 207(3), 1293-1303.
 
Schmid, V. (2012). Solving the dynamic ambulance relocation and dispatching problem using approximate dynamic programming. European journal of operational research, 219(3), 611-621.
 
Setak, M., Habibi, M., Karimi, H., & Abedzadeh, M. (2015). A time-dependent vehicle routing problem in multigraph with FIFO property. Journal of Manufacturing Systems, 35, 37-45.
 
Shahriari, M., Bozorgi-Amiri, A., Tavakoli, S., & Yousefi-Babadi, A. (2017). Bi-objective approach for placing ground and air ambulance base and helipad locations in order to optimize EMS response. The American journal of emergency medicine, 35(12), 1873-1881.
 
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2), 254-265.
 
Talarico, L., Meisel, F., & Sörensen, K. (2015). Ambulance routing for disaster response with patient groups. Computers & Operations Research, 56, 120-133.
 
Tikani, H., Honarvar, M., & Mehrjerdi, Y. Z. (2018). Developing an integrated hub location and revenue management model considering multi-classes of customers in the airline industry. Computational and Applied Mathematics, 37(3), 3334-3364.
 
Tlili, T., Harzi, M., & Krichen, S. (2017). Swarm-based approach for solving the ambulance routing problem. Procedia Computer Science, 112, 350-357.
 
Toro-DíAz, H., Mayorga, M. E., Chanta, S., & Mclay, L. A. (2013). Joint location and dispatching decisions for emergency medical services. Computers & Industrial Engineering, 64(4), 917-928.
 
Toth, P., & Vigo, D. (2002). The vehicle routing problem, Philadelphia: society for industrial and applied mathematics.
 
Yi, W., & Özdamar, L. (2007). A dynamic logistics coordination model for evacuation and support in disaster response activities. European Journal of Operational Research, 179(3), 1177-1193.
 
Zhang, Z., Liu, M., & Lim, A. (2015). A memetic algorithm for the patient transportation problem. Omega, 54, 60-71.
 
Zheng, Y. J., Chen, S. Y., & Ling, H. F. (2015). Evolutionary optimization for disaster relief operations: A survey. Applied Soft Computing, 27, 553-566.
Journal of Industrial and Systems Engineering
Volume 12, Issue 1 - Serial Number 1
January 2019
Pages 95-128

Files

History

  • Receive Date: 18 August 2018
  • Revise Date: 19 September 2018
  • Accept Date: 31 October 2018

Share

How to cite

Statistics