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

Document Type : Research Paper


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


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.


Main Subjects

Abounacer, R., Rekik, M., & Renaud, J. (2014). An exact solution approach for multi-objective location–transportation problem for disaster response. Computers & Operations Research41, 83-93.
Andersson, T., & Värbrand, P. (2007). Decision support tools for ambulance dispatch and relocation. Journal of the Operational Research Society58(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 society55(1), 43-53.
Berkoune, D., Renaud, J., Rekik, M., & Ruiz, A. (2012). Transportation in disaster response operations. Socio-Economic Planning Sciences46(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 medicine35(3), 410-417.
Brandão, J. (2016). A deterministic iterated local search algorithm for the vehicle routing problem with backhauls. TOP24(2), 445-465.
Bräysy, O., & Gendreau, M. (2002). Tabu search heuristics for the vehicle routing problem with time windows. Top10(2), 211-237.
Brotcorne, L., Laporte, G., & Semet, F. (2003). Ambulance location and relocation models. European journal of operational research147(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 Production105, 134-145.
Campbell, A. M., Vandenbussche, D., & Hermann, W. (2008). Routing for relief efforts. Transportation Science42(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. Interfaces43(3), 232-239.
Caunhye, A. M., Nie, X., & Pokharel, S. (2012). Optimization models in emergency logistics: A literature review. Socio-economic planning sciences46(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 mathematics41, 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. Omega70, 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 Research229(1), 261-275.
Edrissi, A., Nourinejad, M., & Roorda, M. J. (2015). Transportation network reliability in emergency response. Transportation research part E: logistics and transportation review80, 56-73.
Farahani, R. Z., Asgari, N., Heidari, N., Hosseininia, M., & Goh, M. (2012). Covering problems in facility location: A review. Computers & Industrial Engineering62(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 Transactions39(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 review48(1), 2-18.
Knight, V. A., Harper, P. R., & Smith, L. (2012). Ambulance allocation for maximal survival with heterogeneous outcome measures. Omega40(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 Review86, 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 & Prevention82, 27-35.
Luis, E., Dolinskaya, I. S., & Smilowitz, K. R. (2012). Disaster relief routing: Integrating research and practice. Socio-economic planning sciences46(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 Theory74, 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 medicine34(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 Review49(1), 217-249.
Özdamar, L., & Ertem, M. A. (2015). Models, solutions and enabling technologies in humanitarian logistics. European Journal of Operational Research244(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 Review48(3), 591-602.
Özdamar, L., Ekinci, E., & Küçükyazici, B. (2004). Emergency logistics planning in natural disasters. Annals of operations research129(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 Technologies19(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 spectrum34(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 Logistics1(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 Sciences2(3), 5931-5943.
Rath, S., & Gutjahr, W. J. (2014). A math-heuristic for the warehouse location–routing problem in disaster relief. Computers & Operations Research42, 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 research207(3), 1293-1303.
Schmid, V. (2012). Solving the dynamic ambulance relocation and dispatching problem using approximate dynamic programming. European journal of operational research219(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 Systems35, 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 medicine35(12), 1873-1881.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research35(2), 254-265.
Talarico, L., Meisel, F., & Sörensen, K. (2015). Ambulance routing for disaster response with patient groups. Computers & Operations Research56, 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 Mathematics37(3), 3334-3364.
Tlili, T., Harzi, M., & Krichen, S. (2017). Swarm-based approach for solving the ambulance routing problem. Procedia Computer Science112, 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 Engineering64(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 Research179(3), 1177-1193.
Zhang, Z., Liu, M., & Lim, A. (2015). A memetic algorithm for the patient transportation problem. Omega54, 60-71.
Zheng, Y. J., Chen, S. Y., & Ling, H. F. (2015). Evolutionary optimization for disaster relief operations: A survey. Applied Soft Computing27, 553-566.