Abstract
This paper addresses the problem of scheduling ambulance crews in order to maximize the coverage throughout a planning horizon. The problem includes the subproblem of locating ambulances to maximize expected coverage with probabilistic response times, for which a tabu search algorithm is developed. The proposed tabu search algorithm is empirically shown to outperform previous approaches for this subproblem. Two integer programming models that use the output of the tabu search algorithm are constructed for the main problem. Computational experiments with real data are conducted. A comparison of the results of the models is presented.
Similar content being viewed by others
References
Brotcorne L, Laporte G and Semet F (2003). Ambulance location and relocation models. Eur J Opl Res 147: 451–463.
Budge S, Ingolfsson A and Erkut E (2008). Approximating vehicle dispatch probabilities for emergency service systems with location-specific service times and multiple units per location. Opns Res, forthcoming.
Daskin MS (1983). A maximum expected covering location model: Formulation, properties, and heuristic solution. Transport Sci 17: 48–70.
Daskin MS (1987). Location, dispatching, and routing model for emergency services with stochastic travel times. In: Ghosh A. and Rushton G. (eds). Spatial Analysis and Location Allocation Models. Van Nostrand Reinhold: New York, pp. 224–265.
Erkut E, Ingolfsson A, Sim T and Erdoğan G (2009). Computational comparison of five maximal covering models for locating ambulances. Geogr Anal 41: 43–65.
Ernst AT, Jiang H, Krishnamoorthy M and Sier D (2004). Staff scheduling and rostering: A review of applications, methods and models. Eur J Opl Res 153: 3–27.
Glover F and Laguna M (1997). Tabu Search . Kluwer Academic Publishers: Boston.
Goldberg JB (2004). Operations research models for the deployment of emergency services vehicles. EMS Mngt J 1: 20–39.
Goldberg JB and Paz L (1991). Locating emergency vehicle bases when service time depends on call location. Transport Sci 25: 264–280.
Green LV, Kolesar PJ and Soares J (2001). Improving the SIPP approach for staffing service systems that have cyclic demands. Opns Res 49: 549–564.
Ingolfsson A, Budge S and Erkut E (2008). Optimal ambulance location with random delays and travel times. Health Care Mngt Sci 11: 262–274.
Jia H, Ordonez F and Dessouky M (2007). A modeling framework for facility location of medical services for large-scale emergencies. IIE Trans 39: 41–55.
Koole G and van der Sluis E (2003). Optimal shift scheduling with a global service level constraint. IIE Trans 35: 1049–1055.
Larson RC (1975). Approximating the performance of urban emergency service systems. Opns Res 23: 845–868.
Marianov V and ReVelle CS (1995). Siting emergency services. In: Drezner Z. (ed). Facility Location: A Survey of Applications and Methods. Springer-Verlag: New York, pp. 199–222.
ReVelle CS and Hogan K (1989). The maximum availability location problem. Transport Sci 23: 192–200.
Saydam C and McKnew M (1985). A separable programming approach to expected coverage: an application to ambulance location. Decision Sci 16: 381–398.
Swersey AJ (1994). The deployment of police, fire, and emergency medical units. In: Barnett A., Pollock S.M. and Rothkopf M.H. (eds). Handbooks in Operations Research and Management Science, Operations Research and the Public Sector Vol. 6. North Holland: Amsterdam, pp. 151–200.
Thompson GM (1997). Labor staffing and scheduling models for controlling service levels. Nav Res Log 44: 719–740.
Acknowledgements
This work was partially funded by the Canadian Natural Sciences and Engineering Research Council under Grants 39682-05 and 203534-07. This support is gratefully acknowledged. We thank the Edmonton and Calgary EMS departments for providing access to data, and Dan Haight and Matt Stanton of the Centre for Excellence in Operations at the University of Alberta School of Business for their assistance with data preparation. Finally, thanks are due to two referees for their valuable comments.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Erdoğan, G., Erkut, E., Ingolfsson, A. et al. Scheduling ambulance crews for maximum coverage. J Oper Res Soc 61, 543–550 (2010). https://doi.org/10.1057/jors.2008.163
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2008.163