×

Simultaneous location of trauma centers and helicopters for emergency medical service planning. (English) Zbl 1302.90102

Summary: This paper studies the problem of simultaneously locating trauma centers and helicopters. The standard approach to locating helicopters involves the use of helicopter busy fractions to model the random availability of helicopters. However, busy fractions cannot be estimated a priori in our problem because the demand for each helicopter cannot be determined until the trauma center locations are selected. To overcome this challenge, we endogenize the computation of busy fractions within an optimization problem. The resulting formulation has nonconvex bilinear terms in the objective, for which we develop an integrated method that iteratively solves a sequence of problem relaxations and restrictions. Specifically, we devise a specialized algorithm, called the shifting quadratic envelopes algorithm, that (1) generates tighter outer approximations than linear McCormick envelopes and (2) outperforms a Benders-like cut generation scheme. We apply our integrated method to the design of a nationwide trauma care system in Korea. By running a trace-based simulation on a full year of patient data, we find that the solutions generated by our model outperform several benchmark heuristics by up to 20%, as measured by an industry-standard metric: the proportion of patients successfully transported to a care facility within one hour. Our results have helped the Korean government to plan its nationwide trauma care system. More generally, our method can be applied to a class of optimization problems that aim to find the locations of both fixed and mobile servers when service needs to be carried out within a certain time threshold.

MSC:

90B80 Discrete location and assignment
90C10 Integer programming

References:

[1] Aboolian R, Berman O, Drezner Z (2008) Location and allocation of service units on a congested network. IIE Trans. 40(4):422-433.
[2] Ball MO, Lin LF (1993) A reliability model applied to emergency service vehicle location. Oper. Res. 41(1):18-36. [Abstract] · Zbl 0775.90264
[3] Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4(1):238-252. · Zbl 0109.38302
[4] Berman O, Krass D (2002) Facility location problems with stochastic demands and congestion. Drezner Z, Hamacher HW, eds. Facility Location: Applications and Theory (Springer, Berlin), 329-371. · Zbl 1061.90068
[5] Berman O, Vasudeva S (2005) Approximating performance measures for public services. IEEE Trans. Systems, Man, and Cybernetics 35(4):583-591.
[6] Borras F, Pastor JT (2002) The ex-post evaluation of the minimum local reliability level: An enhanced probabilistic location set covering model. Ann. Oper. Res. 111:51-74. · Zbl 1013.90049
[7] Branas CC, ReVelle C (2001) An iterative switching heuristics to locate hospitals and helicopters. Socio-Econom. Planning Sci. 35(1):11-30.
[8] Brotcorne L, Laporte G, Semet F (2003) Ambulance location and relocation models. Eur. J. Oper. Res. 147(3):451-463. · Zbl 1037.90554
[9] Burwell TH, McKnew MA, Jarvis JP (1992) An application of a spatially distributed queueing model to an ambulance system. Socio-Econom. Planning Sci. 26:289-300.
[10] Centers for Disease Control and Prevention (2013) Injury Prevention & Control. Accessed September 9. http://www.cdc.gov/TraumaCare/.
[11] Chapman S, White J (1974) Probabilistic Formulations of Emergency Service Facilities Location Problems. Paper Presented at the ORSA/TIMS Conf., San Juan, Puerto Rico.
[12] Church R, ReVelle C (1974) The maximal covering location problem. Papers in Regional Sci. 32(1):101-118.
[13] Daskin MS (1983) A maximum expected covering location model: Formulation, properties, and heuristic solution. Transportation Sci. 17(1):48-70. [Abstract]
[14] Daskin MS, Dean LK (2004) Location of health care facilities. Brandeau ML, Sainfort F, Pierskalla WP, eds. Operations Research and Health Care: A Handbook of Methods and Applications (Kluwer Academic, Norwell, MA), 43-76.
[15] Floudas CA, Pardalos PM, eds. (1996) State of the Art in Global Optimization: Computational Methods and Applications (Kluwer Academic, Norwell, MA).
[16] Gendreau M, Laporte G, Semet F (1997) Solving an ambulance location model by tabu search. Location Sci. 5(2):75-88. · Zbl 0930.90053
[17] Geoffrion AM (1972) Generalized Benders decomposition. J. Optim. Theory Appl. 10(4):237-260. · Zbl 0229.90024
[18] Geromel JC, Belloni MR (1986) Nonlinear programs with complicating variables: Theoretical analysis and numerical experience. IEEE Trans. Systems, Man and Cybernetics 16(2):231-239. · Zbl 0601.90069
[19] Goldberg J, Dietrich R, Chen J, Mitwasi G, Valenzuela T, Criss L (1990) A simulation model for evaluating a set of emergency vehicle base locations: Development, validation, and usage. Socio-Econom. Planning Sci. 24:125-141.
[20] Görmez N, Köksalan M, Salman FS (2011) Locating disaster response facilities in Istanbul. J. Oper. Res. Soc. 62:1239-1252.
[21] Hogan K, ReVelle C (1986) Concepts and applications of backup coverage. Management Sci. 32(11):1434-1444. [Abstract]
[22] Kim Y, Kang DW, Rho YS, Park SB, Park JH, Park CB, Shin SD (2011) Study on an Implementation Plan for Trauma Care System. Report to the Korean Ministry of Health and Welfare. Accessed May 31, 2014, http://www.prism.go.kr/homepage/researchCommon/downloadResearchAttachFile.do?work_key=001&file_type=CPR&seq_no=001&pdf_conv_yn=N&research_id=1351000-201100048.
[23] Larson RC (1975) Approximating the performance of urban emergency service systems. Oper. Res. 23(5):845-868. [Abstract] · Zbl 0326.60117
[24] Li X, Zhao Z, Zhu X, Wyatt T (2011) Covering models and optimization techniques for emergency response facility location and planning: A review. Math. Methods Oper. Res. 74(3):281-310. · Zbl 1261.90011
[25] Mandell M (1998) Covering models for two-tiered emergency medical services systems. Location Sci. 6:355-368.
[26] Marianov V, ReVelle C (1994) The queueing probabilistic location set covering problem and some extensions. Socio-Econom. Planning Sci. 28(3):167-178.
[27] Marianov V, ReVelle C (1996) The queueing maximal availability location problem: A model for the siting of emergency vehicles. Eur. J. Oper. Res. 93:110-120. · Zbl 0912.90195
[28] Marianov V, Serra D (1998) Probabilistic maximal covering location-allocation for congested system. J. Regional Sci. 38(3):401-424.
[29] Marianov V, Serra D (2001) Hierarchical location-allocation models for congested systems. Eur. J. Oper. Res. 135:195-208. · Zbl 1077.90548
[30] McCormick GP (1976) Computability of global solutions to factorable nonconvex programs: Part I–Convex underestimating problems. Math Programming 10:147-175. · Zbl 0349.90100
[31] Nagy G, Salhi S (2007) Location-routing: Issues, models and methods. Eur. J. Oper. Res. 177:649-672. · Zbl 1109.90056
[32] Owen SH, Daskin MS (1998) Strategic facility location: A review. Eur. J. Oper. Res. 111(3):423-447. · Zbl 0938.90048
[33] Peleg K, Aharonson-Daniel L, Stein M, Kluger Y, Michaelson M, Rivkind A, Boyko V, The Israel Trauma Group (2004) Increased survival among severe trauma patients. ARCH SURG 139(November):1231-1236.
[34] Pirkul H, Schilling DA (1991) The maximal covering location problem with capacities on total workload. Management Sci. 37(2):233-248. [Abstract] · Zbl 0732.90045
[35] Prodhon C, Prins C (2014) A survey of recent research on location-routing problems. Eur. J. Oper. Res. 238(1):1-17. · Zbl 1338.90223
[36] Repede J, Bernardo J (1994) Developing and validating a decision support system for locating emergency medical vehicles in Louisville, Kentucky. Eur. J. Oper. Res. 75:567-581.
[37] ReVelle C, Eiselt HA (2005) Location analysis: A synthesis and survey. Eur. J. Oper. Res. 165(1):1-19. · Zbl 1112.90362
[38] ReVelle C, Hogan K (1989) The maximal availability location problem. Transportation Sci. 23(3):192-200. [Abstract] · Zbl 0681.90036
[39] Sahinidis NV, Grossman IE (1991) Convergence properties of generalized Benders decomposition. Comput. Chemical Engrg. 15(7):481-491.
[40] Schilling DA, Elzinga DJ, Cohon J, Church R, ReVelle C (1979) The team/fleet models for simultaneous facility and equipment siting. Transportation Sci. 13(2):163-175. [Abstract]
[41] Sorensen P, Church R (2010) Integrating expected coverage and local reliability for emergency medical services location problems. Socio-Econom. Planning Sci. 44:8-18.
[42] Tawarmalani M, Sahinidis NV (2005) A polyhedral branch-and-cut approach to global optimization. Math. Programming 103(2):225-249. · Zbl 1099.90047
[43] Toregas C, Swain R, ReVelle C, Bergman L (1971) The location of emergency service facilities. Oper. Res. 19(6):1363-1373. [Abstract] · Zbl 0224.90048
[44] Zhang Y, Berman O, Marcotte P, Verter V (2010) A bilevel model for preventive healthcare facility network design with congestion. IIE Trans. 42(12):865-880.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.