Hypercube queuing models in emergency service systems: A state-of-the-art review

Document Type : Article


1 Department of Industrial Engineering, University of Kurdistan, Sanandaj, Iran.

2 School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran.; Arts et Metiers ParisTech, LCFC, Metz, France.


This study provides a review of hypercube queuing models (HQMs) in emergency service systems (ESSs). This survey presents a comprehensive review and taxonomy of models, solutions and applications related to the HQM after Larson [12]. In addition, the structural aspects of HQMs are examined. Important contributions of the existing research are addressed by taking into account multiple factors. In particular, the integration of location decisions with HQMs for designing an ESS is discussed. Finally, a list of issues for future studies are presented.


Main Subjects

1. Galvao, R.D. and Morabito, R. Emergency service  systems: The use of the hypercube queueing model  in the solution of probabilistic location problems",  International Transactions in Operational Research,  15(5), pp. 525-549 (2008).  2. Larson, R.C. A hypercube queuing model for facility  location and redistricting in urban emergency  services", Computers & Operations Research, 1(1), pp.  67-95 (1974).  3. Chiyoshi, F.Y. and Morabito, R.A. Tabu search  algorithm for solving the extended maximal availability  location problem", International Transactions in  Operational Research, 18(6), pp. 663-678 (2011).  4. Chaiken, J.M., Hypercube Queuing Model: Executive  Summery, Department of Housing and Urban Development,  Santa Monica, CA: RAND Corporation (1975).  5. Larson, R.C., Hypercube Queuing Model: User's Manual,  New York City Rand Institute (1975).  6. Larson, R.C., Hypercube Queuing Model: Program  Description, New York City Rand Institute (1975)  7. Sacks, S.R. Optimal spatial deployment of police  patrol cars", Social Science Computer Review, 18(1),  pp. 40-55 (2000).  8. Sacks, S. Evaluation of police patrol patterns", Economics  Working Papers, p. 200317 (2003).  9. Larson, R., OR Models for Homeland Security,  OR/MS Today, 31(5), pp. 22-29 (2004).  10. Larson, R.C. and Franck, E.A. Evaluating dispatching  consequences of automatic vehicle location in emergency  services", Computers & Operations Research,  5(1), pp. 11-30 (1978).  11. Larson, R.C. and Odoni, A.R., Urban Operations  Research, Prentice Hall, Englewood Cli_s, N.J. (1981).  12. Brandeau, M.L. and Larson, R.C. Extending and  applying the hypercube queueing model to deploy  ambulances in Boston", Management Science, 22, pp.  121-153 (1986). 13. Budge, S., Ingolfsson, A., and Erkut, E. Approximating  vehicle dispatch probabilities for emergency  service systems with location-speci_c service times  and multiple units per location", Operations Research,  75(1), pp. 251-255 (2009).  14. Larson, R.C. Approximating the performance of urban  emergency service systems", Operations Research,  23(5), pp. 845-868 (1975).  15. Jarvis, J.P. Approximating the balance behavior  of multi-server loss systems", Management Science,  31(2), pp. 235-239 (1985).  16. Jarvis, J.P. Optimization in stochastic service systems  with distinguishable servers", Ph.D. Dissertation,  Massachusetts Institute of Technology (1975).  17. Chelst, K.R. and Jarvis, J.P. Estimating the probability  distribution of travel times for urban emergency  service systems", Operations Research, 27(1), pp. 199-  204 (1979).  18. Larson, R.C. and Rich, T.F. Travel-time analysis of  New York city police patrol cars", Interfaces, 17(2),  pp. 15-20 (1987).  19. Souza, R.M., Morabito, R. and Chiyoshi, F.Y. Incorporating  priorities for waiting customers in the hypercube  queuing model with application to an emergency  medical service system in Brazil", European Journal of  Operational Research, 242(1), pp. 274-285 (2015).  20. Larsen, R.C. and Odoni, A.R., Urban Operation Research:  Logistical and Transportation Planning Methods,  2nd Ed., Dynamic Ideas (2007).  21. Takeda, R.A., Widmer, J.A., and Morabito, R. Analysis  of ambulance decentralization in an urban emergency  medical service using the hypercube queueing  model", Computers and Operations Research, 34(3),  pp. 727-741 (2007).  22. Berman, O., Larson, R.C., and Odoni, A.R. Developments  in network location with mobile and congested  facilities", European Journal of Operational Research,  6(2), pp. 104-116 (1980).  23. Berman, O. and Larson, R.C. The median problem  with congestion", Computers and Operations Research,  9(2), pp. 119-126 (1982).  24. Daskin, M.S. A maximal expected covering location  model: formulation, properties, and heuristic solution",  Transportation Science, 17(1), pp. 48-70 (1983).  25. Batta, R., Dolan, J.M., and Krishnamurthy, N.N.  The maximal expected covering location problem:  Revisited", Transportation Science, 23(4), pp. 277-287  (1989).  26. Chiyoshi, F.Y., Galvao, R.D., and Morabito, R. A  note on solutions to the maximal expected covering location  problem", Computers and Operations Research,  30(1), pp. 87-96 (2002).  27. Galvao, R.D., Chiyoshi, F.Y., and Morabito, R.  Towards uni_ed formulations and extensions of two  classical probabilistic location models", Computers  and Operations Research, 32(1), pp. 15-33 (2005).  28. ReVelle, C.S. and Hogan, K. The maximum availability  location problem", Transportation Science, 23(3),  pp. 192-200 (1989).  29. Glover, F. and Laguna, M., Tabu Search, Kluwer  Academic Publishers (1997).  30. Goldberg, J., Dietrich, R., Chen, J.M., and Mitwasi,  M.G. Validating and applying a model for locating  emergency medical vehicles in Tucson, Az", European  Journal of Operational Research, 49(3), pp. 308-324  (1990).  31. McLay, L.A. and Mayorga, M.E. Evaluating emergency  medical service performance measures", Health  Care Management Science, 13(2), pp. 124-136 (2010).  32. Toro-Diaz, H., Mayorga, M.E., Chanta, S., and McLay,  L.A. joint location and dispatching decisions for emergency  medical services", Computers and Industrial  Engineering, 64(4), pp. 917-928 (2013).  33. Rajagopalan, H.K., Saydam, C., and Xiao, J. A multiperiod  expected covering location model for dynamic  redeployment of ambulances", EuroWorking Group on  Transportation (2005).  34. Saydam, C., Rajagopalan, H.K., Sharer, E., and  Lawrimore-Belanger, K. The dynamic redeployment  coverage location model", Health Systems, 2(2), pp.  1-17 (2013).  35. Sudtachat, K., Mayorga, M.E., and Mclay, L.A. A  nested-compliance table policy for emergency medical  service systems under relocation", Omega, 58, pp. 154-  168 (2016).  36. Halpern, J. The accuracy of estimates for the performance  criteria in certain emergency service queuing  systems", Transportation Science, 11(3), pp. 223-242  (1977).  37. Larson, R.C. and McKnew, M.A. Police patrolinitiated  activities within a systems queueing model",  Management Science, 28(7), pp. 759-774 (1982).  38. McKnew, M.A. An approximation to the hypercube  model with patrol-initiated activities: an application  to police", Decision Sciences, 14(3), pp. 408-418  (1983).  39. Burwell, T.H. A spatially distributed queuing model  for ambulance systems", Ph.D. Dissertation, Clemson  University, Clemson, S.C. (1986).  40. Burwell, T.H., Jarvis, J.P., and McKnew, M.A. Modeling  co-located servers and dispatch ties in the hypercube  model", Computers and Operations Research,  20(2), pp. 113-119 (1993). 41. Budge, S., Ingolfsson, A., and Zerom, D. Empirical  analysis of ambulance travel times: The case  of Calgary emergency medical services", Management  Science, 56(4), pp. 716-723 (2010).  42. Toro-D__az, H., Mayorga, M.E., McLay, L.A., Rajagopalan,  H.A., and Saydam, C. Reducing disparities  in large-scale emergency medical service systems",  Journal of the Operational Research Society, 66(7), pp.  1-13 (2014).  43. Ansari, S., McLay, L.A., and Mayorga, M.E. A maximum  expected covering problem for district design",  Transportation Science, 51(1), pp. 376-390 (2015).  44. Boyaci, B. and Geroliminis, N. Extended hypercube  models for large scale spatial queuing systems", 90th  Annual Meeting of the Transportation Research Board,  Washington D.C. (2011).  45. Boyaci, B. and Geroliminis, N. Facility location  problem for emergency and on-demand transportation  systems", 91th Annual Meeting of the Transportation  Research Board, Washington D.C. (2012).  46. Boyaci, B. and Geroliminis, N. Approximation methods  for large-scale spatial queueing systems", Transportation  Research Part B, 74, pp. 151-181 (2015).  47. Baptista, S. and Oliveira, R.C. A case study on  the application of an approximated hypercube model  to emergency medical systems management", Central  European Journal of Operations Research, 20(4), pp.  559-581 (2012).  48. Iannoni, A.P., Chiyoshi, F.Y., and Morabito, R. A  spatially distributed queuing model considering dispatching  policies with server reservation", Transportation  Research Part E, 75, pp. 49-66 (2015).  49. Goldberg, J. and Paz, L. Locating emergency vehicle  bases when service time depends on call location",  Transportation Science, 25(4), pp. 264-280 (1991).  50. Zhu, Z. and McKnew, A. A goal programming  workload balancing optimization model for ambulance  allocation: An application to Shanghai, P.R. China",  Socio-Economic Planning Sciences, 27(2), pp. 137-148  (1993).  51. Lei, H., Wang, R., and Laporte, G. Solving a multiobjective  dynamic stochastic districting and routing  problem with a co-evolutionary algorithm", Computers  & Operations Research, 67, pp. 12-24 (2016).  52. Geroliminis, N., Karlaftis, M.G., Stathopoulos, A., and  Kepaptsoglou, K. A districting and location model  using spatial queues", 83rd Transportation Research  Board Annual Meeting, at Washington DC, USA  (2004).  53. Geroliminis, N., Karlaftis, M.G. and Skabardonis, A.  A spatial queuing model for the emergency vehicle  districting and location problem", Transportation Research  Part B, 43(7), pp. 798-811 (2009).  54. Geroliminis, N., Kepaptsoglou, K., and Karlaftis, M.G.  A hybrid hypercube-genetic algorithm approach for  deploying many emergency response mobile units in  an urban network", European Journal of Operational  Research, 210(2), pp. 287-300 (2011).  55. Erkut, E., Ingolfsson, A., and Erdogan, G. Ambulance  location for maximum survival", Naval Research  Logistics (NRL), 55(1), pp. 42-58 (2007).  56. Ingolfsson, A., Budge, S., and Erkut, E. Optimal  ambulance location with random delays and travel  times", Health Care Management Science, 11(3), pp.  262-274 (2008).  57. McLay, L.A. A maximum expected covering location  model with two types of servers", IIE Transactions,  41(8), pp. 730-741 (2009).  58. Rajagopalan, H.K. and Saydam, C. A minimum expected  response model: formulation, heuristic solution  and application", Socio-Economic Planning Sciences,  43(4), pp. 253-262 (2009).  59. Marianov, V. and ReVelle, C. The queueing maximal  availability location problem: a model for siting of  emergency vehicles", European Journal of Operational  Research, 93(1), pp. 110-120 (1996).  60. Mendonca, F.C. and Morabito, R. Analysing emergency  medical service ambulance deployment on a  Brazilian highway using the hypercube model", Operational  Research Society, 52, pp. 261-270 (2001).  61. Atkinson, J.B., Kovalenko, I.N., Kuznetsov, N.Y., and  Mikhalevich, K.V. Heuristic methods for the analysis  of a queuing system describing emergency medical  service deployed along a highway", Cybernetics and  Systems Analysis, 42(3), pp. 379-391 (2006).  62. Mendonca, F.C. and Morabito, R. Analysing emergency  medical service ambulance deployment on a  brazilian highway using the hypercube model", Operational  Research Society, 52, pp. 261-270 (2001).  63. Atkinson, J.B., Kovalenko, I.N., Kuznetsov, N.Y.,  and Mikhalevich, K.V. A hypercube queueing loss  model with customer-dependent service rates", European  Journal of Operational Research, 191(1), pp. 223-  239 (2008).  64. Iannoni, A.P., Morabito, R., and Saydam, C. Optimizing  large-scale emergency medical system operations  on highways using the hypercube queuing  model", Socio-Economic Planning Sciences, 45(3), pp.  105-117 (2011).  65. Morabito, R., Chiyoshi, F.Y., and Galvao, R.D. Nonhomogeneous  servers in emergency medical systems:  Practical applications using the hypercube queueing  model", Socio-Economic Planning Sciences, 42(4), pp.  255-270 (2008).  66. Kim, S.H. and Lee, Y.H. Iterative optimization algorithm  with parameter estimation for the ambulance  location problem", Health Care Management Science,  19(4), pp. 362-382 (2016).  67. ReVelle, C. and Hogan, K. A reliability-constrained  siting model with local estimates of busy fractions",  Environment and Planning B: Planning and Design,  15(2), pp. 143-152 (1988).  68. Chelst, K.R. and Barlach, Z. Multiple unit dispatches  in emergency services: Models to estimate system  performance", Management Science, 27(12), pp. 1390-  1409 (1981).  69. Davoudpour, H., Mortaz, E., and Hosseinijou, S.A. A  new probabilistic coverage model for ambulances deployment  with hypercube queuing approach", International  Journal of Advanced Manufacturing Technology,  70, pp. 1157-1168 (2014).  70. Sudtachat, K., Mayorga, M.E., and McLay, L.A.  Recommendations for dispatching emergency vehicles  under multi-tiered response via simulation", International  Transactions in Operational Research, 21(4),  pp. 581-617 (2014).  71. Iannoni, A.P. and Morabito, R. A multiple dispatch  and partial backup hypercube queuing model  to analyze emergency medical systems on highways",  Transportation Research Part E, 43(6), pp. 755-771  (2007).  72. Iannoni, A.P., Morabito, R., and Saydam, C. A  hypercube queueing model embedded into a genetic  algorithm for ambulance deployment on highways",  Annals of Operations Research, 157(1), pp. 207-224  (2008).  73. Iannoni, A.P., Morabito, R., and Saydam, C. An  optimization approach for ambulance location and the  districting of the response segments on highways",  European Journal of Operational Research, 195(2), pp.  528-542 (2009).