Skip to main content

Advertisement

SpringerLink
Log in

Covering models and optimization techniques for emergency response facility location and planning: a review

  • Original Article
  • Published:
Mathematical Methods of Operations Research Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Aickelin U (2002) An indirect genetic algorithm for set covering problems. J Oper Res Soc 53: 1118–1126

    Article  MATH  Google Scholar 

  • 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

    Article  MATH  Google Scholar 

  • Aly AA, White JA (1978) Probabilistic formulation of the emergency service location problem. J Oper Res Soc 29: 1167–1179

    MATH  Google Scholar 

  • 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

    MATH  Google Scholar 

  • 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

    Article  MATH  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  MathSciNet  MATH  Google Scholar 

  • Ball M, Lin F (1993) A reliability model applied to emergency service vehicle location. Oper Res 41: 18–36

    Article  MATH  Google Scholar 

  • 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

    Article  MathSciNet  MATH  Google Scholar 

  • Beasley J, Chu P (1996) A genetic algorithm for the set covering problem. Eur J Oper Res 94: 392–404

    Article  MATH  Google Scholar 

  • Berman O (1981) Dynamic repositioning of indistinguishable service units on transportation networks. Transport Sci 15: 115–136

    Article  Google Scholar 

  • Berman O (1981) Repositioning of distinguishable urban service units on networks. Comput Oper Res 8: 105–118

    Article  Google Scholar 

  • Berman O (1981) Repositioning of two distinguishable service vehicles on networks. IEEE Trans Syst Man Cybernet 11: 187–193

    Article  Google Scholar 

  • 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

    Google Scholar 

  • Brotcorne L, Laporte G, Semet F (2002) Fast heuristics for large scale covering-location problems. Comput Oper Res 29: 651–665

    Article  MathSciNet  MATH  Google Scholar 

  • Brotcorne L, Laporte G, Semet F (2003) Ambulance location and relocation models. Eur J Oper Res 147(4): 451–463

    Article  MathSciNet  MATH  Google Scholar 

  • 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

    Article  MATH  Google Scholar 

  • Ceria S, Nobili P, Sassano A (1998) A lagrangian-based heuristic for large-scale set covering problems. Math Program 81: 215–228

    MathSciNet  MATH  Google Scholar 

  • Chan Y (2001) Location theory and decision analysis. South Western College Publishing, Cincinnati

    Google Scholar 

  • Chung C (1986) Recent applications of the maximal covering location planning (M.C.L.P.) model. J Oper Res Soc 37: 735–746

    MATH  Google Scholar 

  • Church RL, ReVelle CS (1974) The maximum covering location problem. Papers Reg Sci Assoc 32: 101–118

    Article  Google Scholar 

  • Cooper L (1964) Heuristic methods for location-allocation problems. Soc Indus Appl Math 6: 37–53

    Google Scholar 

  • 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

    Google Scholar 

  • Coskun N, Erol R (2010) An optimization model for locating and sizing emergency medical service stations. J Med Syst 34: 43–49

    Article  Google Scholar 

  • Daskin M, Stern E (1981) A hierarchical objective set covermg model for emergency medical service deployment. Tansport Sci 15: 137–152

    Article  MathSciNet  Google Scholar 

  • Daskin MS (1983) A maximum expected covering location model: Formulation, properties and heuristic solution. Trans Sci 17: 48–68

    Article  Google Scholar 

  • Daskin M, Hogan K, ReVelle C (1988) Integration of multiple, excess, backup and expected covering models. Environ Plan B 15: 13–35

    Article  Google Scholar 

  • Daskin M (1995) Network and discrete location. Wiley, New York

    Book  MATH  Google Scholar 

  • 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

    Google Scholar 

  • 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

    MATH  Google Scholar 

  • 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

    MathSciNet  MATH  Google Scholar 

  • 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

    Google Scholar 

  • Eaton D, Daskin M, Simmons D, Bulloch B, Jansma G (1985) Determining emergency medical service vehicle deployment in austin, texas. Interfaces 15: 96–108

    Article  Google Scholar 

  • Eaton D, Sanchez H, Lantigua R, Morgan J (1986) Determining ambulance deployment in santo domingo, dominican republic. J Oper Res Soc 37: 113–126

    Google Scholar 

  • Eiselt HA, Marianov V (2009) Gradual location set covering with service quality. Socio Econ Plan Sci 43: 121–130

    Article  Google Scholar 

  • Erkut E, Ingolfsson A, Erdogan G (2007) Ambulance location for maximum survival. Naval Res Logist 55: 42–58

    Article  MathSciNet  Google Scholar 

  • Fujiwara O, Makjamroen T, Gupta K (1987) Ambulance deployment analysis: a case study of Bangkok. Eur J Oper Res 31(1): 9–18

    Article  Google Scholar 

  • 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

    Article  MATH  Google Scholar 

  • Galvao RD, Chiyoshi FY, Morabito R (2005) Towards unified formulations and extensions of two classical probabilistic location models. Comput Oper Res 32: 15–33

    Article  MathSciNet  MATH  Google Scholar 

  • Gendreau M, Laporte G, Semet F (1997) Solving an ambulance location model by tabu search. Location Sci 5(2): 77–88

    Article  Google Scholar 

  • 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

    Article  MATH  Google Scholar 

  • Gendreau M, Laporte G, Semet F (2006) The maximal expected coverage relocation problem for emergency vehicles. J Oper Res Soc 57: 22–28

    Article  MATH  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Goldberg J, Szidarovszky F (1991) Methods for solving nonlinear equations used in evaluating vehicle busy probabilities. Oper Res 39: 903–916

    Article  MATH  Google Scholar 

  • Green L, Kolesar P (2004) Improving emergency responsiveness with management science. Manage Sci 50: 1001–1014

    Article  Google Scholar 

  • Harewood S (2002) Emergency ambulance deployment in barbados: a multi-objective approach. J Oper Res Soc 53: 185–192

    Article  MATH  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  MATH  Google Scholar 

  • 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

    Article  MATH  Google Scholar 

  • Jaramillo J, Bhadury J, Batta R (2002) On the use of genetic algorithms to solve location problems. Comput Oper Res 29: 761–779

    Article  MathSciNet  MATH  Google Scholar 

  • Jarvis JP (1985) Approximating the equilibrium behavior of multi-server loss systems. Manage Sci 32: 235–239

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Karasakal O, Karasakal EK (2004) A maximal covering location model in the presence of partial coverage. Comput Oper Res 31: 1515–1526

    Article  MathSciNet  MATH  Google Scholar 

  • 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

    Google Scholar 

  • Larson RC (1974) A hypercube queuing model for facility location and redistricting in urban emergency services. Comput Oper Res 1: 67–95

    Article  MathSciNet  Google Scholar 

  • Larson RC (1975) Approximating the performance of urban emergency service systems. Oper Res 23: 845–867

    Article  MATH  Google Scholar 

  • Liu M, Lee J (1988) A simulation of a hospital emergency call system using slam ii. Simulation 51: 216–221

    Article  Google Scholar 

  • Mannino C, Sassano A (1995) Solving hard set covering problem. Oper Res Lett 18: 1–5

    Article  MathSciNet  MATH  Google Scholar 

  • Marianov V, ReVelle C (1994) The queuing probabilistic location set covering problem and some extensions. Socio Econ Plan Sci 28: 167–178

    Article  Google Scholar 

  • 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

    Article  MATH  Google Scholar 

  • Marianov V, Serra D (1998) Probabilistic maximal covering location allocation models for congested systems. J Reg Sci 38: 401–424

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • McLay LA (2009) A maximum expected covering location model with two types of servers. IIE Trans 41: 730–741

    Article  Google Scholar 

  • 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

    Article  MATH  Google Scholar 

  • 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

    Article  MathSciNet  MATH  Google Scholar 

  • Owen S, Daskin M (1998) Strategic facility location: a review. Eur J Oper Res 111: 423–447

    Article  MATH  Google Scholar 

  • 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

    Article  MATH  Google Scholar 

  • 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

    Article  MATH  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  MathSciNet  MATH  Google Scholar 

  • ReVelle C (1991) Siting ambulances and fire companies: new tools for planners. J Am Plan Assoc 57: 471–484

    Article  Google Scholar 

  • ReVelle C, Hogan K (1989) The maximum availability location problem. Trans Sci 23: 192–200

    Article  MathSciNet  MATH  Google Scholar 

  • 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

    Article  MathSciNet  MATH  Google Scholar 

  • Saydam AC, McKnew MA (1985) A separable programming approach to expected coverage: an application to ambulance location. Decis Sci 16: 381–398

    Article  Google Scholar 

  • Saydam C, Aytug H (2003) Accurate estimation of expected coverage: revisited. Socio Econ Plan Sci 37: 69–80

    Article  Google Scholar 

  • Schilling D (1980) Dynamic location modeling for public-sector facilities: a multicriteria approach. Decis Sci 11: 714–724

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Schilling D, Jayaraman V, Barkhi R (1993) A review of covering problems in facility location. Locat Sci 1: 25–55

    MATH  Google Scholar 

  • Scott A (1971) Dynamic location-allocation systems: some basic planning strategies. Environ Plan 3: 73–82

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  MATH  Google Scholar 

  • Toregas C, Swain R, ReVelle C, Bergman L (1971) The location of emergency service facilities. Oper Res 19: 1363–1373

    Article  MATH  Google Scholar 

  • Wesolowsky G, Truscott W (1976) The multiperiod location-allocation problem with relocation of facilities. Manage Sci 22: 57–65

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Zhang O, Mason AJ, Philpott AB (2008) Simulation and optimisation for ambulance logistics and relocation. Presentation in INFORMS Annual Meeting, Washington, DC

Download references

Author information

Authors and Affiliations

  1. Department of Industrial and Information Engineering, University of Tennessee, 416 East Stadium Hall, Knoxville, TN, 37919, USA

    Xueping Li, Zhaoxia Zhao & Xiaoyan Zhu

  2. College of Nursing, University of Tennessee, 200 Volunteer Boulevard, Knoxville, TN, 37996-4180, USA

    Tami Wyatt

Authors
  1. Xueping Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Zhaoxia Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xiaoyan Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Tami Wyatt
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xueping Li.

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00186-011-0363-4

Keywords

Search

Navigation