Abstract
With emergencies being, unfortunately, part of our lives, it is crucial to efficiently plan and allocate emergency response facilities that deliver effective and timely relief to people most in need. Emergency Medical Services (EMS) allocation problems deal with locating EMS facilities among potential sites to provide efficient and effective services over a wide area with spatially distributed demands. It is often problematic due to the intrinsic complexity of these problems. This paper reviews covering models and optimization techniques for emergency response facility location and planning in the literature from the past few decades, while emphasizing recent developments. We introduce several typical covering models and their extensions ordered from simple to complex, including Location Set Covering Problem (LSCP), Maximal Covering Location Problem (MCLP), Double Standard Model (DSM), Maximum Expected Covering Location Problem (MEXCLP), and Maximum Availability Location Problem (MALP) models. In addition, recent developments on hypercube queuing models, dynamic allocation models, gradual covering models, and cooperative covering models are also presented in this paper. The corresponding optimization techniques to solve these models, including heuristic algorithms, simulation, and exact methods, are summarized.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aickelin U (2002) An indirect genetic algorithm for set covering problems. J Oper Res Soc 53: 1118–1126
Alsalloum OI, Rand GK (2003) A goal programming model applied to the ems system at riyadh city, saudi arabia, working Paper
Alsalloum OI, Rand GK (2006) Extensions to emergency vehicle location models. Comput Oper Res 33: 2725–2743
Aly AA, White JA (1978) Probabilistic formulation of the emergency service location problem. J Oper Res Soc 29: 1167–1179
Andersson T (2005) Decision support tools for dynamic fleet management. Ph.D. thesis, Department of Science and Technology, Linkoepings Universitet, Norrkoeping, Sweden
Andersson T, Vaerband P (2007) Decision support tools for ambulance dispatch and relocation. J Oper Res Soc 58: 195–201
Araz C, Selim H, Ozkarahan I (2007) A fuzzy multi-objective covering-based vehicle location model for emergency services. Comput Oper Res 34: 705–726
Arostegui MA, Kadipasaoglu SN, Khumawala BM (2006) An empirical comparison of tabu search, simulated annealing, and genetic algorithms for facilities location problems. Int J Prod Econ 103: 742–754
Aytug H, Saydam C (2002) Solving large-scale maximum expected covering location problems by genetic algorithms: a comparative study. Eur J Oper Res 141: 480–494
Ball M, Lin F (1993) A reliability model applied to emergency service vehicle location. Oper Res 41: 18–36
Basar A, Catay B, Unluyurt T (2008) A new model and tabu search approach for planning the emergency service stations. In: Operations research proceedings
Batta R, Dolan JM, Krishnamurthy NN (1989) The maximal expected covering location problem: revisited. Transport Sci 23: 277–287
Beasley J, Chu P (1996) A genetic algorithm for the set covering problem. Eur J Oper Res 94: 392–404
Berman O (1981) Dynamic repositioning of indistinguishable service units on transportation networks. Transport Sci 15: 115–136
Berman O (1981) Repositioning of distinguishable urban service units on networks. Comput Oper Res 8: 105–118
Berman O (1981) Repositioning of two distinguishable service vehicles on networks. IEEE Trans Syst Man Cybernet 11: 187–193
Berman O, Krass D (2002) Facility location problems with stochastic demands and congestion. In: Facility locations: application and theory. Springer, Berlin, pp 329–371
Berman O, Drezner Z, Krass D (2010) Discrete cooperative covering problems. J Oper Res Soc. Advance online publicatin 15 December 2010
Brandeau M, Larson R (1986) Extending and applying the hypercube queueing model to deploy ambulances in Boston. TIMS Stud Manage Sci 22: 121–153
Brotcorne L, Laporte G, Semet F (2002) Fast heuristics for large scale covering-location problems. Comput Oper Res 29: 651–665
Brotcorne L, Laporte G, Semet F (2003) Ambulance location and relocation models. Eur J Oper Res 147(4): 451–463
Burwell T (1986) A spatially distributed queuing model for ambulance systems. Ph.D. thesis, Clemson University, Clemson
Burwell T, Jarvis J, McKnew M (1993) Modeling co-located servers and dispatch ties in the hypercube model. Comput Oper Res 20: 113–119
Ceria S, Nobili P, Sassano A (1998) A lagrangian-based heuristic for large-scale set covering problems. Math Program 81: 215–228
Chan Y (2001) Location theory and decision analysis. South Western College Publishing, Cincinnati
Chung C (1986) Recent applications of the maximal covering location planning (M.C.L.P.) model. J Oper Res Soc 37: 735–746
Church RL, ReVelle CS (1974) The maximum covering location problem. Papers Reg Sci Assoc 32: 101–118
Cooper L (1964) Heuristic methods for location-allocation problems. Soc Indus Appl Math 6: 37–53
Cordeau J, Laporte G, Potvin J, Salvesbergh M (2007) Transportation on demand. In: Barnhart C, Laporte G (eds) Transportation, handbooks in operations research and management science. Elsevier, Amsterdam, pp 429–466
Coskun N, Erol R (2010) An optimization model for locating and sizing emergency medical service stations. J Med Syst 34: 43–49
Daskin M, Stern E (1981) A hierarchical objective set covermg model for emergency medical service deployment. Tansport Sci 15: 137–152
Daskin MS (1983) A maximum expected covering location model: Formulation, properties and heuristic solution. Trans Sci 17: 48–68
Daskin M, Hogan K, ReVelle C (1988) Integration of multiple, excess, backup and expected covering models. Environ Plan B 15: 13–35
Daskin M (1995) Network and discrete location. Wiley, New York
Dessouky M (2006) Rapid distribution of medical supplies. In: Patient flow: reducing delay in healthcare delivery. Springer, USA, pp 309–339
Diaz B, Rodriguez F (1997) A simple search heuristic for the mclp: Application to the location of ambulance based in a rural region. Int J Manage Sci 25: 181–187
Doerner K, Gutjahr W, Hartl R, Karall M, Reimann M (2005) Heuristic solution of an extended double-coverage ambulance location problem for austria. Cent Eur J Oper Res 13: 325–340
Doerner KF, Hartl RF (2008) Health care logistics, emergency preparedness, and disaster relief: New challenges for routing problems with a focus on the austrian situation. In: The vehicle rounting problem: lastest Advances and New Challenges. Springer, USA, pp 527–550
Drezner T, Drezner Z, Goldstein Z (2010) A stochastic gradual cover location problem. Naval Res Logist 57: 367–372
Eaton D, Church R, Bennett V, Hamon B, Lopez L (1981) On deployment of health resources in rural valle del cauca, colombia. TIMS Stud Manage Sci 17: 331–359
Eaton D, Daskin M, Simmons D, Bulloch B, Jansma G (1985) Determining emergency medical service vehicle deployment in austin, texas. Interfaces 15: 96–108
Eaton D, Sanchez H, Lantigua R, Morgan J (1986) Determining ambulance deployment in santo domingo, dominican republic. J Oper Res Soc 37: 113–126
Eiselt HA, Marianov V (2009) Gradual location set covering with service quality. Socio Econ Plan Sci 43: 121–130
Erkut E, Ingolfsson A, Erdogan G (2007) Ambulance location for maximum survival. Naval Res Logist 55: 42–58
Fujiwara O, Makjamroen T, Gupta K (1987) Ambulance deployment analysis: a case study of Bangkok. Eur J Oper Res 31(1): 9–18
Fujiwara O, Kachenchai K, Makjamroen T, Gupta K (1988) An efficient scheme for deployment of ambulances in metropolitan Bangkok. In: Rand GK (ed) Operational research ’87, pp 730–741
Galvao RD, ReVelle C (1996) A lagrangean heuristic for the maximal covering location problem. Eur J Oper Res 88: 114–123
Galvao RD, Chiyoshi FY, Morabito R (2005) Towards unified formulations and extensions of two classical probabilistic location models. Comput Oper Res 32: 15–33
Gendreau M, Laporte G, Semet F (1997) Solving an ambulance location model by tabu search. Location Sci 5(2): 77–88
Gendreau M, Laporte G, Semet F (2001) A dynamic model and parallel tabu search heuristic for real-time ambulance relocation. Parallel Comput 27: 1641–1653
Gendreau M, Laporte G, Semet F (2006) The maximal expected coverage relocation problem for emergency vehicles. J Oper Res Soc 57: 22–28
Geroliminis N, Karlaftis M, Skabardonis A (2006) A generalized hypercube queueing model for locating emergency response vehicles in urban transportation networks. TRB 2006 Annual Meeting CD-ROM
Geroliminis N, Karlaftis M, Stathopoulos A, Kepaptsoglou K (2004) A districting and location model using spatial queues. TRB 2004 Annual Meeting CD-ROM
Goldberg J (2004) Operations research models for the deployment of emergency services vehicles. EMS Manage J 1: 20–39
Goldberg J, Dietrich R, Chen J, Mitwasi M, Valenzuela T, Criss E (1990) A simulation model for valuating a set of emergency vehicle base location: development, validation, and usage. Socio Econ Plan Sci 24: 125–141
Goldberg J, Dietrich R, Chen J, Mitwasi M, Valenzuela T, Criss E (1990) Validating and applying a model for locating emergency medical vehicles in tucson, az. Eur J Oper Res 49: 308–324
Goldberg J, Szidarovszky F (1991) Methods for solving nonlinear equations used in evaluating vehicle busy probabilities. Oper Res 39: 903–916
Green L, Kolesar P (2004) Improving emergency responsiveness with management science. Manage Sci 50: 1001–1014
Harewood S (2002) Emergency ambulance deployment in barbados: a multi-objective approach. J Oper Res Soc 53: 185–192
Henderson S, Mason A (2004) Ambulance service planning: simulation and data visualization. In: Operations research and health care: a handbook of methods and applications. Kluwer, Boston, pp 77–102
Hogan K, ReVelle C (1986) Concepts and applications of backup coverage. Manage Sci 32: 1434–1444
Iannoni AP, Morabito R (2007) A multiple dispatch and partial backup hypercube queuing model to analyze emergency medical systems on highways. Trans Res Part E 43: 755–771
Iannoni AP, Morabito R, Saydam C (2008) A hypercube queueing model embedded into a genetic algorithm for ambulance depolyment on highways. Ann Oper Res 157: 207–224
Iannoni AP, Morabito R, Saydam C (2009) An optimization approach for ambulance location and the districting of the response segments on highways. Eur J Oper Res 195: 528–542
Jaramillo J, Bhadury J, Batta R (2002) On the use of genetic algorithms to solve location problems. Comput Oper Res 29: 761–779
Jarvis JP (1985) Approximating the equilibrium behavior of multi-server loss systems. Manage Sci 32: 235–239
Jia H, Ordonez F, Dessouky MM (2007) A modeling framework for facility location of medical service for large-scale emergency. IIE Trans 39(1): 35–41
Jia H, Ordonez F, Dessouky MM (2007) Solution approaches for facility location of medical supplies for large-scale emergecies. Comput Indus Eng 52(1): 257–276
Karasakal O, Karasakal EK (2004) A maximal covering location model in the presence of partial coverage. Comput Oper Res 31: 1515–1526
Laporte G, Louveaux FV, Semet F, Thirion A (2009) Application of the double standard model for ambulance location. In: Innovations in distribution logistics. Springer, Berlin, pp 235–249
Larson R, Odoni A (1981) Urban operations research. Prentice-Hall, Englewood Cliffs
Larson RC (1974) A hypercube queuing model for facility location and redistricting in urban emergency services. Comput Oper Res 1: 67–95
Larson RC (1975) Approximating the performance of urban emergency service systems. Oper Res 23: 845–867
Liu M, Lee J (1988) A simulation of a hospital emergency call system using slam ii. Simulation 51: 216–221
Mannino C, Sassano A (1995) Solving hard set covering problem. Oper Res Lett 18: 1–5
Marianov V, ReVelle C (1994) The queuing probabilistic location set covering problem and some extensions. Socio Econ Plan Sci 28: 167–178
Marianov V, ReVelle C (1995) Sitting emergency services. In: Facility location: a survey of appication and methods. Springer, New York, pp 199–223
Marianov V, ReVelle C (1996) The queueing maximal availability locationm problem: a model for the siting of emergency vehicles. Eur J Oper Res 93(1): 110–120
Marianov V, Serra D (1998) Probabilistic maximal covering location allocation models for congested systems. J Reg Sci 38: 401–424
Marianov V, Serra D (2002) Location problems in the public sector. In: Facility locations: application and theory. Springer, Berlin, pp 119–150
Maxwell MS, Henderson SG, Topalogu H (2009a) Ambulance redeployment: an approximate dynamic programming approach. In: Rossetti MD, Hill RR, Johansson B, Dunkin A, Ingalls R (eds) Proceedings of 2009 winter simulation conference
Maxwell MS, Restrepo M, Henderson SG, Topaloglu H (2009b) Approximate dynamic programming for ambulance redeployment (to appear)
McKnew MA (1983) An approximation to the hypercube model with patrol initiated activities: an application to police. Decis Sci 14: 408–418
McLay LA (2009) A maximum expected covering location model with two types of servers. IIE Trans 41: 730–741
Mendonca FC, Morabito R (2001) Analysing emergency medical service ambulance deployment on a brazilian highway using the hypercube model. J Oper Res Soc 52: 261–270
Nair R, Miller-Hooks E (2006) A case study of ambulance location and relocation. Presentation in INFORMS Annual Meeting, Pittsburgh Pennsylvania
Ohlsson M, Peterson C, Soderberg B (2001) An efficient mean field approach to the set covering problem. Eur J Oper Res 133: 583–595
Owen S, Daskin M (1998) Strategic facility location: a review. Eur J Oper Res 111: 423–447
Rajagopalan HK, Saydam C (2005) An effective and accurate hybrid meta heuristic for a probabilistic coverage location problem for dynamic deployment. In: Proceedings of 35th international coference on computers and industrial engineering
Rajagopalan HK, Saydam C, Xiao J (2005) A multiperiod expected covering location model for dynamic redeployment of ambulances. In: Proceedings of the joint conference-10th EWGT meeting and 16th Mini-EURO conference, Poznan, Poland
Rajagopalan HK, Saydam C, Xiao J (2008) A multiperiod set covering location model for dynamic redeployment of ambulances. Comput Oper Res 35: 814–826
Rajagopalan HK, Vergara FE, Saydam C, Xiao J (2007) Developing effective meta-heuristics for a probabilistic location model via experimental design. Eur J Oper Res 177: 83–101
Repede JF, Bernardo JJ (1994) Developing and validating a decision support system for locating emergenct medical vehicles in louisville kentucky. Eur J Oper Res 75(5): 567–581
Restrepo M (2008) Computational methods for static allocation and real-time redeployment of ambulances. Ph.D. thesis, Cornell University, Ithaca, New York
ReVelle C (1989) Review, extension and prediction in emergency siting models. Eur J Oper Res 40: 58–69
ReVelle C (1991) Siting ambulances and fire companies: new tools for planners. J Am Plan Assoc 57: 471–484
ReVelle C, Hogan K (1989) The maximum availability location problem. Trans Sci 23: 192–200
ReVelle C, Hogan K (1989) The maximum reliability location problem and alpha reliable p-center problems: derivatives of the probabilistic location set covering problem. Ann Oper Res 18: 155–174
Saydam AC, McKnew MA (1985) A separable programming approach to expected coverage: an application to ambulance location. Decis Sci 16: 381–398
Saydam C, Aytug H (2003) Accurate estimation of expected coverage: revisited. Socio Econ Plan Sci 37: 69–80
Schilling D (1980) Dynamic location modeling for public-sector facilities: a multicriteria approach. Decis Sci 11: 714–724
Schilling D, Elzinga D, Cohon J, Church RL, ReVelle C (1979) The teem/fleet models for simultaneous facility and equipment sitting. Trans Sci 13: 163–175
Schilling D, Jayaraman V, Barkhi R (1993) A review of covering problems in facility location. Locat Sci 1: 25–55
Scott A (1971) Dynamic location-allocation systems: some basic planning strategies. Environ Plan 3: 73–82
Shiah D-M, Chen S-W (2007) Ambulance allocation capacity model. In: e-Health networking, applications and services, 2007 9th international conference, Taipei,Taiwan
Sorensen P, Church R (2010) Integrating expected coverage and local reliability for emergency medical services location problems. Socio Econ Plan Sci 44: 8–18
Swoveland C, Uyeno D, Vertinsky I, Vickson R (1973) A simulation-based methodology for optimization of ambulance service policies. Socio Econ Plan Sci 7: 697–703
Takeda RA, Widmer JA, Morabito R (2007) Analysis of ambulance decentralization in an urban emergency medical service using the hypercube queueing model. Comput Oper Res 34: 727–741
Toregas C, Swain R, ReVelle C, Bergman L (1971) The location of emergency service facilities. Oper Res 19: 1363–1373
Wesolowsky G, Truscott W (1976) The multiperiod location-allocation problem with relocation of facilities. Manage Sci 22: 57–65
Zaki A, Cheng H, Parker B (1997) A simulation model for the analysis and management of an emergency service system. Socio Econ Plan Sci 31: 173–189
Zhang O, Mason AJ, Philpott AB (2008) Simulation and optimisation for ambulance logistics and relocation. Presentation in INFORMS Annual Meeting, Washington, DC
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Li, X., Zhao, Z., Zhu, X. et al. Covering models and optimization techniques for emergency response facility location and planning: a review. Math Meth Oper Res 74, 281–310 (2011). https://doi.org/10.1007/s00186-011-0363-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00186-011-0363-4