Ambulance Deployment and Shift Scheduling: An Integrated Approach

Hari K. Rajagopalan, Cem Saydam, Hubert Setzler, Elizabeth Sharer

.

DOI: 10.4236/jssm.2011.41010                

Abstract

Emergency medical response providers’ primary responsibility is to deploy an adequate number of ambulances in a manner that will yield the best service to a constituent population. In this paper we develop a two-stage integrated solution for complex ambulance deployment and crew shift scheduling. In the first stage we develop a dynamic expected coverage model to determine the minimum number of ambulances and their locations for each time interval and solve via a tabu search. For the second stage, we develop an integer programming model which uses the solution obtained from the first stage to determine optimal crew schedules. We present computational statistics and demonstrate the efficacy of our two-stage solution approach using a case study.

Keywords

Ambulance Location, Dynamic Relocation, Shift Scheduling, Hypercube

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	NFPA 1720. “Standard for the organization and deployment of fire suppression operations, emergency medical operations and special operations to the public by volunteer fire departments,” 2010 Ed., NFPA, Quincy, MA, 2010.
[2]	D. M. Williams and M. Ragone, “2009 JEMS 200-City Survey: Zeroing in on What Matters,” Journal of Emergency Medical Services, Vol. 34, No. 2, 2010, pp. 38-42.
[3]	H. Setzler, C. Saydam and S. Park, “EMS Call Volume Predictions: A Comparative Study,” Computers & Operations Research, Vol. 36, No. 6, 2009, pp. 1843-1851. doi:10.1016/j.cor.2008.05.010
[4]	ILOG, “ILOG Cplex 7.0 Reference Manual,” ILOG, 2000.
[5]	R. D. Galvao, F. Y. Chiyoshi and R. Morabito, “Towards Unified Formulations and Extensions of Two Classical Probabilistic Location Models,” Computers & Operations Research, Vol. 32, No. 1, 2005, pp. 15-33. doi:10.1016/S0305-0548(03)00200-4
[6]	O. Karasakal and E. K. Karasakal, “A Maximal Covering Location Model in the Presence of Partial Coverage,” Computers & Operations Research, Vol. 31, No. 9, 2004, pp. 1515-1526. doi:10.1016/S0305-0548(03)00105-9
[7]	J. B. Goldberg, “Operations Research Models for the Deployment of Emergency Services Vehicles,” EMS Management Journal, Vol. 1, No. 1, 2004, pp. 20-39.
[8]	L. Brotcorne, G. Laporte and F. Semet, “Fast Heuristics for Large Scale Covering Location Problems,” Computers & Operations Research, Vol. 29, No. 6, 2002, pp. 651-665. doi:10.1016/S0305-0548(99)00088-X
[9]	H. Aytug and C. Saydam, “Solving Large-Scale Maximum Expected Covering Location Problems by Genetic Algorithms: A Comparative Study,” European Journal of Operational Research, Vol. 141, No. 3, 2002, pp. 480-494. doi:10.1016/S0377-2217(01)00260-0
[10]	C. Saydam and H. Aytug, “Accurate Estimation of Expected Coverage: Revisited,” Socio-Economic Planning Sciences, Vol. 37, No. 1, 2003, pp. 69-80. doi:10.1016/S0038-0121(02)00004-6
[11]	M. Gendreau, G. Laporte and F. Semet, “A Dynamic Model and Parallel Tabu Search Heuristic for Real Time Ambulance Relocation,” Parallel Computing, Vol. 27, No. 12, 2001, pp. 1641-1653. doi:10.1016/S0167-8191(01)00103-X
[12]	D. A. Schilling, V. Jayaraman and R. Barkhi, “A Review of Covering Problems in Facility Location,” Location Science, Vol. 1, No. 1, 1993, pp. 25-55.
[13]	S. H. Owen and M. S. Daskin, “Strategic Facility Location: A Review,” European Journal of Operational Research, Vol. 111, No. 3, 1998, pp. 423-447. doi:10.1016/S0377-2217(98)00186-6
[14]	L. Brotcorne, G. Laporte and F. Semet, “Ambulance Location and Relocation Models,” European Journal of Operational Research, vol. 147, No. 3, 2003, pp. 451-463. doi:10.1016/S0377-2217(02)00364-8
[15]	M. S. Daskin, “A Maximal Expected Covering Location Model: Formulation, Properties and Heuristic Solution,” Transportation Science, Vol. 17, No. 1, 1983, pp. 48-69. doi:10.1287/trsc.17.1.48
[16]	C. ReVelle and K. Hogan, “The Maximum Availability Location Problem,” Transportation Science, Vol. 23, No. 3, 1989, pp. 192-200. doi:10.1287/trsc.23.3.192
[17]	M. O. Ball and L. F. Lin, “A Reliability Model Applied to Emergency Service Vehicle Location,” Operations Research, Vol. 41, No. 1, 1993, pp. 18-36. doi:10.1287/opre.41.1.18
[18]	C. ReVelle and K. Hogan, “The Maximum Reliability Location Problem and Alpha-Reliable P-Center Problems: Derivatives of the Probabilistic Location Set Covering Problem,” Annals of Operations Research, Vol. 18, No. 1, 1989, pp. 155-174. doi:10.1007/BF02097801
[19]	V. Marianov and C. ReVelle, “The Queuing Probabilistic Location Set Covering Problem and Some Extensions,” Socio-Economic Planning Sciences, Vol. 28, No. 3, 1994, pp. 167-178. doi:10.1016/0038-0121(94)90003-5
[20]	R. C. Larson, “A Hypercube Queuing Model for Facility Location and Redistricting in Urban Emergency Services,” Computers & Operations Research, Vol. 1, No. 1, 1974, pp. 67-95. doi:10.1016/0305-0548(74)90076-8
[21]	A. S. Zaki, H. K. Cheng and B. R. Parker, “A Simulation Model for the Analysis and Management of An Emergency Service System,” Socio-Economic Planning Sciences, Vol. 31, No. 3, 1997, pp. 173-189. doi:10.1016/S0038-0121(97)00013-X
[22]	R. C. Larson, “Approximating the Performance of Urban Emergency Service Systems,” Operations Research, Vol. 23, No. 5, 1975, pp. 845-868. doi:10.1287/opre.23.5.845
[23]	R. Batta, J. M. Dolan, and N. N. Krishnamurthy, “The Maximal Expected Covering Location Problem: Revisited,” Transportation Science, Vol. 23, No. 4, 1989, pp. 277-287. doi:10.1287/trsc.23.4.277
[24]	Y. Chan, “Location Theory and Decision Analysis,” South Western College Publishing, Cincinnati, 2001.
[25]	M. S. Daskin, “Network and Discrete Location,” John Wiley & Sons Inc., New York, 1995.
[26]	R. C. Larson and A. R. Odoni “Urban Operations Research.” N.J: Prentice-Hall, Englewood Cliffs, 1981.
[27]	C. ReVelle, “Review, Extension and Prediction in Emergency Siting Models,” European Journal of Operational Research, Vol. 40, No. 1, 1989, pp. 58-69. doi:10.1016/0377-2217(89)90272-5
[28]	C. Saydam, J. Repede and T. Burwell, “Accurate Estimation of Expected Coverage: A Comparative Study,” Socio-Economic Planning Sciences, Vol. 28, No. 2, 1994, pp. 113-120. doi:10.1016/0038-0121(94)90010-8
[29]	T. H. Burwell, J. P. Jarvis and M. A. McKnew, “Modeling Co-located Servers and Dispatch Ties in the Hypercube Model,” Computers & Operations Research, Vol. 20, No. 1993, pp. 113-119.
[30]	R. A. Takeda, J. A. Widmer and R. Morabito, “Analysis of Ambulance Decentralization in an Urban Medical Emergency Service Using the Hypercube Queuing Model.,” Computers & Operations Research, Vol. 34, No. 3, 2007, pp. 727-741. doi:10.1016/j.cor.2005.03.022
[31]	J. P. Jarvis, “Approximating the Equilibrium Behavior of Multi-Server Loss Systems,” Management Science, Vol. 31, No. 2, 1985, pp. 235-239. doi:10.1287/mnsc.31.2.235
[32]	J. Penner, “Interview with the Charlotte MEDIC Director,” H. K. Rajagopalan, 2004.
[33]	J. Repede and J. Bernardo, “Developing and Validating a Decision Support System for Locating Emergency Mdeical Vehichles in Lousville, Kentucky,” European Journal of Operational Research, Vol. 75, No. 3, 1994, pp. 567-581. doi:10.1016/0377-2217(94)90297-6
[34]	P. Trudeau, J. M. Rousseau, J. A. Ferland and J. Choquette, “An Operations Research Approach for the Planning and Operation of an Ambulance Service,” INFOR, Vol. 27, No. 1, 1989, pp. 95-113.
[35]	G. Erdogan, E. Erkut, A. Ingolfsson and G. Laporte, “Scheduling Ambulance Crews for Maximum Coverage,” Journal of Operational Research Society, Vol. 61, No. 4, 2010, pp. 543-550. doi:10.1057/jors.2008.163
[36]	Y. Li and E. Kozan, “Rostering Ambulance Services,” Industrial Engineering and Management Society, Kitakyushu, Japan, 2009, pp. 14-16.
[37]	V. Marianov and C. ReVelle, “The Queueing Maximal Availability Location Problem: A Model for Siting of Emergency Vehicles,” European Journal of Operational Research, Vol. 93, No. 1, 1996, pp. 110-120. doi:10.1016/0377-2217(95)00182-4
[38]	J. E. Beasley and P. C. Chu, “A Genetic Algorithm for the Set Covering Problem,” European Journal of Operational Research, Vol. 94, No. 2, 1996, pp. 392-404. doi:10.1016/0377-2217(95)00159-X
[39]	S. Benati and G. Laporte, “Tabu Search Algorithms for the (r|Xp)-Medianoid and (r|p) Centroid Problems,” Location Science, Vol. 2, No. 4, 1994, pp. 193-204.
[40]	M. Gendreau, G. Laporte and F. Semet, “Solving an Ambulance Location Model by Tabu Search,” Location Science, Vol. 5, No. 2, 1997, pp. 75-88. doi:10.1016/S0966-8349(97)00015-6
[41]	J. Jaramillo, J. Bhadury and R. Batta, “On the Use of Genetic Algorithms to Solve Location Problems,” Computers & Operations Research, Vol. 29, No. 6, 2002, pp. 761-779. doi:10.1016/S0305-0548(01)00021-1
[42]	H. K. Rajagopalan, F. E. Vergara, C. Saydam and J. Xiao, “Developing Effective Meta-Heuristics For A Probabilistic Location Model Via Experimental Design,” European Journal of Operational Research, Vol. 177, No. 2, 2007, pp. 365-377.
[43]	R. Battiti and G. Tecchiolli, “The Reactive Tabu Search,” Journal on Computing, Vol. 6, No. 2, 1994, pp. 126-140.
[44]	F. S. Hillier and G. J. Lieberman, “Introduction to Operations Research,” 8th Ed. New York: McGraw Hill, 2005.