Ambulance location routing problem considering all sources of uncertainty: progressive estimating algorithm. (English) Zbl 07764435
Summary: The main concern of any emergency medical services (EMS) in the world is to provide quality services to emergency calls in the shortest possible time. In this paper, the Ambulance Location Routing problem (ALRP) is proposed that is a mathematical attempt to obtain optimal cost-oriented strategic decisions (locating EMS centers and allocating ambulance fleet) in a way that guarantees service quality factors like response time, service level, and definite treatment time through optimal ambulance routing. In response to the concerns that emergency medical services deal with, in this research, a novel mixed-integer two-stage stochastic programming model is developed that can consider the uncertain nature of parameters like emergency calls, travel times, and pathways, simultaneously. Considering a heterogeneous fleet of ambulances to provide specialized out-of-hospital services and to use the treatment golden time, and considering different types of patients in terms of the need to be transferred to the hospital, are among the most vital innovations of the proposed ALRP. To tackle the computational complexity, a new decomposition-based heuristic method called the Progressive Estimating Algorithm (PEA) is developed. PEA is a modified version of the classic PHA and solves its drawbacks, like the possibility of being placed in a loop or prolonging the solution time by changing the method of calculating the first stage variables in each iteration. Therefore, by considering a large number of scenarios, PEA can reach feasible near-optimal solutions more efficiently. We have employed the actual data of a city with nearly \(800.000\) population, as a case study to validate the proposed ALRP model and the PEA method. The obtained results demonstrate that the proposed ALRP solution is valid, and the PEA can reach the near-optimal solution, in a very reasonable time, and with no exception, outperform the PHA. The results also show that the ALRP model reduces costs on average by 30% compared to a benchmark model. In addition, it is found that the solution obtained for the case study can reduce costs by 58% compared to the current state of the EMS in this city while guaranteeing the quality of services. Furthermore, the need to use a heterogeneous fleet of ambulances and scattered stations in the region is recommended to improve the performance of EM services. Finally, the unique way of looking at the integrated problem of location, allocation, and routing in the proposed ALRP and the idea of PEA are attractive for further studies in the field of EMS planning and other optimization problems, and several suggestions for future studies are mentioned in Conclusion Section.
MSC:
| 90Bxx | Operations research and management science |
Keywords:
ambulance location-routing problem; emergency medical services; transportation in healthcare; treatment golden time; progressive estimating algorithmReferences:
| [1] | Akıncılar, A.; Akıncılar, E., A new idea for ambulance location problem in an environment under uncertainty in both path and average speed: Absolutely robust planning, Comput. Ind. Eng., 137, Article 106053 pp. (2019) |
| [2] | Alamatsaz, K.; Ahmadi, A.; Mirzapour Al-e-hashem, S. M.J., A multiobjective model for the green capacitated location-routing problem considering drivers’ satisfaction and time window with uncertain demand, Environ. Sci. Pollut. Res., 29, 4, 5052-5071 (2022) |
| [3] | Araz, C.; Selim, H.; Ozkarahan, I., A fuzzy multi-objective covering-based vehicle location model for emergency services, Comput. Oper. Res., 34, 3, 705-726 (2007) · Zbl 1120.90352 |
| [4] | Asghari, M.; Mirzapour Al-e-hashem, S. M.J., Green vehicle routing problem: A state-of-the-art review, Int. J. Prod. Econ., 231, Article 107899 pp. (2021) |
| [5] | Asghari, M.; MirzapourAl-e-hashem, S. M.J., New Advances in Vehicle Routing Problems: A Literature Review to Explore the Future, (Derbel, H.; Jarboui, B.; Siarry, P., Green Transportation and New Advances in Vehicle Routing Problems (2020), Springer International Publishing: Springer International Publishing Cham), 1-42 |
| [6] | Aytug, H.; Saydam, C., Solving large-scale maximum expected covering location problems by genetic algorithms: A comparative study, Eur. J. Oper. Res., 141, 3, 480-494 (2002) · Zbl 1081.90573 |
| [7] | Ball, M. O.; Lin, F. L., A Reliability Model Applied to Emergency Service Vehicle Location, Oper. Res., 41, 1, 18-36 (1993) · Zbl 0775.90264 |
| [8] | Bareilles, G.; Laguel, Y.; Grishchenko, D.; Iutzeler, F.; Malick, J., Randomized Progressive Hedging methods for multi-stage stochastic programming, Ann. Operations Res., 295, 2, 535-560 (2020) · Zbl 1467.90024 |
| [9] | Batta, R.; Dolan, J. M.; Krishnamurthy, N. N., The Maximal Expected Covering Location Problem: Revisited, Transp. Sci., 23, 4, 277-287 (1989) · Zbl 0692.90040 |
| [10] | 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 |
| [11] | Bélanger, V.; Lanzarone, E.; Nicoletta, V.; Ruiz, A.; Soriano, P., A recursive simulation-optimization framework for the ambulance location and dispatching problem, Eur. J. Oper. Res., 286, 2, 713-725 (2020) · Zbl 1443.90237 |
| [12] | Beraldi, P.; Bruni, M. E.; Conforti, D., Designing robust emergency medical service via stochastic programming, Eur. J. Oper. Res., 158, 1, 183-193 (2004) · Zbl 1066.90063 |
| [13] | Berman, O.; Hajizadeh, I.; Krass, D., The maximum covering problem with travel time uncertainty, IIE Trans., 45, 1, 81-96 (2013) |
| [14] | Boujemaa, R.; Jebali, A.; Hammami, S.; Ruiz, A.; Bouchriha, H., A stochastic approach for designing two-tiered emergency medical service systems, Flex. Serv. Manuf. J., 30, 1-2, 123-152 (2018) |
| [15] | Boutilier, J. J.; Chan, T. C.Y., Ambulance Emergency Response Optimization in Developing Countries, Oper. Res., 68, 5, 1315-1334 (2020) · Zbl 1455.90019 |
| [16] | Brotcorne, L.; Laporte, G.; Semet, F., Ambulance location and relocation models, Eur. J. Oper. Res., 147, 3, 451-463 (2003) · Zbl 1037.90554 |
| [17] | Burwell, T. H.; McKnew, M. A.; Jarvis, james P., An application of a spatially distributed queuing model to an ambulance system, Socioecon. Plann. Sci., 26, 4, 289-300 (1992) |
| [18] | Canbolat, M. S.; von Massow, M., Locating emergency facilities with random demand for risk minimization, Expert Syst. Appl., 38, 8, 10099-10106 (2011) |
| [19] | Cheraitia, M.; Salhi, A.; Haddadi, S., A two-phase heuristic for set covering, Int. J. Math. Oper. Res., 13, 1, 61 (2018) · Zbl 1452.90221 |
| [20] | Chuang, C.-L.; Lin, R.-H., A Maximum expected covering model for an ambulance location problem, J. Chinese Inst. Ind. Eng., 24, 6, 468-474 (2007) |
| [21] | Church, R.; ReVelle, C., The maximal covering location problem, Papers Regional Sci. Assoc., 32, 1, 101-118 (1974) |
| [22] | Crawford, B., Soto, R., Cabrera, G., Salas-Fernández, A., & Paredes, F. (2019). Using a Social Media Inspired Optimization Algorithm to Solve the Set Covering Problem. In Lecture Notes in Computer Science: Vol. 11578 LNCS (pp. 43-52). 10.1007/978-3-030-21902-4_4. |
| [23] | Daskin, M. S., A Maximum Expected Covering Location Model: Formulation, Properties and Heuristic Solution, Transp. Sci., 17, 1, 48-70 (1983) |
| [24] | Daskin, M. S.; Stern, E. H., A Hierarchical Objective Set Covering Model for Emergency Medical Service Vehicle Deployment, Transp. Sci., 15, 2, 137-152 (1981) |
| [25] | Davis, S. G., Analysis of the deployment of emergency medical services, Omega, 9, 6, 655-657 (1981) |
| [26] | Farghadani-Chaharsooghi, P.; Kamranfar, P.; Mirzapour Al-e-Hashem, M. S.; Rekik, Y., A joint production-workforce-delivery stochastic planning problem for perishable items, Int. J. Prod. Res., 60, 20, 6148-6172 (2022) |
| [27] | Fitzsimmons, J. A.; Srikar, B. N., Emergency ambulance location using the contiguous zone search routine, J. Oper. Manag., 2, 4, 225-237 (1982) |
| [28] | Gade, D.; Hackebeil, G.; Ryan, S. M.; Watson, J. P.; Wets, R.-J.-B.; Woodruff, D. L., Obtaining lower bounds from the progressive hedging algorithm for stochastic mixed-integer programs, Math. Program., 157, 1, 47-67 (2016) · Zbl 1338.90282 |
| [29] | Galvão, R. D.; Morabito, R., Emergency service systems: The use of the hypercube queueing model in the solution of probabilistic location problems, Int. Trans. Oper. Res., 15, 5, 525-549 (2008) · Zbl 1172.90361 |
| [30] | Gendreau, M.; Laporte, G.; Semet, F., Solving an ambulance location model by tabu search, Locat. Sci., 5, 2, 75-88 (1997) · Zbl 0930.90053 |
| [31] | Goldberg, J.; Dietrich, R.; Chen, J. M.; Mitwasi, M.; Valenzuela, T.; Criss, E., A simulation model for evaluating a set of emergency vehicle base locations: Development, validation, and usage, Socioecon. Plann. Sci., 24, 2, 125-141 (1990) |
| [32] | Goldberg, J.; Dietrich, R.; Ming Chen, J.; Mitwasi, M. G.; Valenzuela, T.; Criss, E., Validating and applying a model for locating emergency medical vehicles in Tuczon, AZ, Eur. J. Oper. Res., 49, 3, 308-324 (1990) |
| [33] | Goldberg, J.; Paz, L., Locating Emergency Vehicle Bases When Service Time Depends on Call Location, Transp. Sci., 25, 4, 264-280 (1991) · Zbl 0825.90649 |
| [34] | Hogan, K.; ReVelle, C., Concepts and Applications of Backup Coverage, Manag. Sci., 32, 11, 1434-1444 (1986) |
| [35] | Ingolfsson, A.; Budge, S.; Erkut, E., Optimal ambulance location with random delays and travel times, Health Care Manag. Sci., 11, 3, 262-274 (2008) |
| [36] | Jabalameli, M. S.; Bankian Tabrizi, B.; Moshref Javadi, M., A Simulated Annealing method to solve a generalized maximal covering location problem, Int. J. Ind. Eng. Comput., 2, 2, 439-448 (2011) |
| [37] | Jánošíková, Ľ.; Jankovič, P.; Kvet, M.; Zajacová, F., Coverage versus response time objectives in ambulance location, Int. J. Health Geogr., 20, 1, 32 (2021) |
| [38] | Karasakal, O.; Karasakal, E. K., A maximal covering location model in the presence of partial coverage, Comput. Oper. Res., 31, 9, 1515-1526 (2004) · Zbl 1107.90028 |
| [39] | Larson, R. C., A hypercube queuing model for facility location and redistricting in urban emergency services, Comput. Oper. Res., 1, 1, 67-95 (1974) |
| [40] | Larson, R. C., APPROXIMATING THE PERFORMANCE OF URBAN EMERGENCY SERVICE SYSTEMS, Oper. Res., 23, 5, 845-868 (1975) · Zbl 0326.60117 |
| [41] | Li, X.; Zhao, Z.; Zhu, X.; Wyatt, T., Covering models and optimization techniques for emergency response facility location and planning: a review, Math. Methods Oper. Res., 74, 3, 281-310 (2011) · Zbl 1261.90011 |
| [42] | Loscalzo, J. M., Harrison’s Cardiovascular Medicine (2016), McGraw Hill/Medical |
| [43] | Majidi, A.; Farghadani-Chaharsooghi, P.; Mirzapour Al-e-Hashem, S. M.J., Sustainable Pricing-Production-Workforce-Routing Problem for Perishable Products by Considering Demand Uncertainty; A Case Study from the Dairy Industry, Transp. J., 61, 1, 60-102 (2022) |
| [44] | Mandell, M. B., Covering models for two-tiered emergency medical services systems, Locat. Sci., 6, 1-4, 355-368 (1998) |
| [45] | Marianov, V.; Revelle, C., The queuing probabilistic location set covering problem and some extensions, Socioecon. Plann. Sci., 28, 3, 167-178 (1994) |
| [46] | Marianov, V.; ReVelle, C., The Queueing Maximal availability location problem: A model for the siting of emergency vehicles, Eur. J. Oper. Res., 93, 1, 110-120 (1996) · Zbl 0912.90195 |
| [47] | Memari, P.; Tavakkoli-Moghaddam, R.; Navazi, F.; Jolai, F., Air and ground ambulance location-allocation-routing problem for designing a temporary emergency management system after a disaster, Proc. Inst. Mech. Eng. [H], 234, 8, 812-828 (2020) |
| [48] | Mirzapour Al-e-hashem, S. M.J.; Baboli, A.; Sazvar, Z., A stochastic aggregate production planning model in a green supply chain: Considering flexible lead times, nonlinear purchase and shortage cost functions, Eur. J. Oper. Res., 230, 1, 26-41 (2013) · Zbl 1317.90051 |
| [49] | Mirzapour Al-e-hashem, S. M.J.; Amoozadkhalili, H.; Khazaei Kouhpar, R., An Ambulance Routing Problem in Organ Transplant Supply Chain Considering Traffic Congestion Effect. Journal of Industrial Management, Perspective, 12, 45, 261-290 (2021) |
| [50] | Mohammadi, S.; Al-e-Hashem, S. M.J. M.; Rekik, Y., An integrated production scheduling and delivery route planning with multi-purpose machines: A case study from a furniture manufacturing company, Int. J. Prod. Econ., 219, 347-359 (2020) |
| [51] | Mohri, S. S.; Haghshenas, H., An ambulance location problem for covering inherently rare and random road crashes, Comput. Ind. Eng., 151, Article 106937 pp. (2021) |
| [52] | Naoum-Sawaya, J.; Elhedhli, S., A stochastic optimization model for real-time ambulance redeployment, Comput. Oper. Res., 40, 8, 1972-1978 (2013) · Zbl 1348.90447 |
| [53] | Nazari-Ganje, N.; Hashem, M.-E.; S. m. j., An Integrated Location-Inventory Routing Problem for ATMs in Banking Industry: A Green Approach, (Derbel, H.; Jarboui, B.; Siarry, P., Modeling and Optimization in Green Logistics (2020), Springer International Publishing), 27-52 |
| [54] | Nickel, S.; Reuter-Oppermann, M.; Saldanha-da-Gama, F., Ambulance location under stochastic demand: A sampling approach, Operations Res. Health Care, 8, 24-32 (2016) |
| [55] | Noyan, N., Alternate risk measures for emergency medical service system design, Ann. Operations Res., 181, 1, 559-589 (2010) · Zbl 1209.90118 |
| [56] | Olsson, A.; Sandberg, G.; Dahlblom, O., On Latin hypercube sampling for structural reliability analysis, Struct. Saf., 25, 1, 47-68 (2003) |
| [57] | ReVelle, C.; Hogan, K., The Maximum Availability Location Problem, Transp. Sci., 23, 3, 192-200 (1989) · Zbl 0681.90036 |
| [58] | Schilling, D.; Elzinga, D. J.; Cohon, J.; Church, R.; ReVelle, C., The Team/Fleet Models for Simultaneous Facility and Equipment Siting, Transp. Sci., 13, 2, 163-175 (1979) |
| [59] | Sorensen, P.; Church, R., Integrating expected coverage and local reliability for emergency medical services location problems, Socioecon. Plann. Sci., 44, 1, 8-18 (2010) |
| [60] | Soto, R.; Crawford, B.; Olivares, R.; Barraza, J.; Figueroa, I.; Johnson, F.; Paredes, F.; Olguín, E., Solving the non-unicost set covering problem by using cuckoo search and black hole optimization, Nat. Comput., 16, 2, 213-229 (2017) · Zbl 1415.68206 |
| [61] | Sung, I.; Lee, T., Scenario-based approach for the ambulance location problem with stochastic call arrivals under a dispatching policy, Flex. Serv. Manuf. J., 30, 1-2, 153-170 (2018) |
| [62] | Talarico, L.; Meisel, F.; Sörensen, K., Ambulance routing for disaster response with patient groups, Comput. Oper. Res., 56, 120-133 (2015) · Zbl 1348.90133 |
| [63] | Tlili, T.; Harzi, M.; Krichen, S., Swarm-based approach for solving the ambulance routing problem, Procedia Comput. Sci., 112, 350-357 (2017) |
| [64] | Toregas, C.; Swain, R.; ReVelle, C.; Bergman, L., The Location of Emergency Service Facilities, Oper. Res., 19, 6, 1363-1373 (1971) · Zbl 0224.90048 |
| [65] | van Essen, J. T.; Hurink, J. L.; Nickel, S.; Reuter-Oppermann, M., Models for ambulance planning on the strategic and the tactical level (WP-434), WP-, 434, 27 (2013) |
| [66] | Vasko, F. J.; Knolle, P. J.; Spiegel, D. S., An empirical study of hybrid genetic algorithms for the set covering problem, J. Oper. Res. Soc., 56, 10, 1213-1223 (2005) · Zbl 1081.90072 |
| [67] | Wang, J.; Wang, Y.; Yu, M., A multi-period ambulance location and allocation problem in the disaster, J. Comb. Optim., 43, 5, 909-932 (2022) · Zbl 1495.90113 |
| [68] | Watson, J.-P.; Woodruff, D. L., Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems, CMS, 8, 4, 355-370 (2011) · Zbl 1225.91032 |
| [69] | Yang, W.; Su, Q.; Zhou, M.; Qin, X., Ambulance allocation considering the spatial randomness of demand, Comput. Ind. Eng., 139, Article 106202 pp. (2020) |
| [70] | Zhang, Z.-H.; Jiang, H., A robust counterpart approach to the bi-objective emergency medical service design problem, App. Math. Model., 38, 3, 1033-1040 (2014) · Zbl 1427.90194 |
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.
