×

A novel probabilistic formulation for locating and sizing emergency medical service stations. (English) Zbl 1318.90046

Summary: The paper proposes a novel probabilistic model with chance constraints for locating and sizing emergency medical service stations. In this model, the chance constraints are approximated as second-order cone constraints to overcome computational difficulties for practical applications. The proposed approximations associated with different estimation accuracy of the stochastic nature are meaningful on a practical uncertainty environment. Then, the model is transformed into a conic quadratic mixed-integer program by employing a conic transformation. The resulting model can be efficiently addressed by a commercial optimization package. A special case is also considered and a class of valid inequalities is introduced to improve computational efficiency. Lastly, computational experiences on real data and randomly generated data are reported to illustrate the validity of the program.

MSC:

90B80 Discrete location and assignment
90C11 Mixed integer programming
90C20 Quadratic programming

Software:

CPLEX
Full Text: DOI

References:

[1] Aly, A. A., & White, J. A. (1978). Probabilistic formulation of the emergency service location problem. The Journal of the Operational Research Society, 29(12), 1167-1179. · Zbl 0388.90047
[2] Aringhieri, R., Carello, G., & Morale, D. (2013). Supporting decision making to improve the performance of an italian emergency medical service. Annals of Operations Research pp 1-18. · Zbl 1120.90009
[3] Atamtürk, A., & Narayanan, V. (2008). Polymatroids and mean-risk minimization in discrete optimization. Operations Research Letters, 36(5), 618-622. · Zbl 1210.90127 · doi:10.1016/j.orl.2008.04.006
[4] Baptista, S., & Oliveira, R. C. (2012). A case study on the application of an approximated hypercube model to emergency medical systems management. Central European Journal of Operations Research, 20(4), 559-581. · Zbl 1339.90207 · doi:10.1007/s10100-010-0187-y
[5] Baron, O., Milner, J., & Naseraldin, H. (2011). Facility location: A robust optimization approach. Production and Operations Management, 20(5), 772-785. · doi:10.1111/j.1937-5956.2010.01194.x
[6] Ben-Tal, A., El Ghaoui, L., & Nemirovski, A. (2009). Robust optimization. Princeton: Princeton University Press. · Zbl 1221.90001 · doi:10.1515/9781400831050
[7] Beraldi, P., Bruni, M. E., & Conforti, D. (2004). Designing robust emergency medical service via stochastic programming. European Journal of Operational Research, 158(1), 183-193. · Zbl 1066.90063 · doi:10.1016/S0377-2217(03)00351-5
[8] Beraldi, P., & Bruni, M. E. (2009). A probabilistic model applied to emergency service vehicle location. European Journal of Operational Research, 196(1), 323-331. · Zbl 1156.90405 · doi:10.1016/j.ejor.2008.02.027
[9] Bonami, P., & Lejeune, M. (2009). An exact solution approach for portfolio optimization problems under stochastic and integer constraints. Operations research, 57(3), 650-670. · Zbl 1226.90049 · doi:10.1287/opre.1080.0599
[10] Brotcorne, L., Laporte, G., & Semet, F. (2003). Ambulance location and relocation models. European Journal of Operational Research, 147(3), 451-463. · Zbl 1037.90554 · doi:10.1016/S0377-2217(02)00364-8
[11] Chanta, S., Mayorga, M., & McLay, L. (2011). Improving emergency service in rural areas: a bi-objective covering location model for ems systems. Annals of Operations Research pp 1-27. · Zbl 1301.90054
[12] Coskun, N., & Erol, R. (2010). An optimization model for locating and sizing emergency medical service stations. Journal of medical systems, 34(1), 43-49. · doi:10.1007/s10916-008-9214-0
[13] Daskin, M. S. (1983). A maximum expected covering location model: formulation, properties and heuristic solution. Transportation Science, 17(1), 48-70. · doi:10.1287/trsc.17.1.48
[14] Davoudpour, H., Mortaz, E., & Hosseinijou, S. (2014). A new probabilistic coverage model for ambulances deployment with hypercube queuing approach. The International Journal of Advanced Manufacturing Technology, 70(5-8), 1157-1168. · doi:10.1007/s00170-013-5336-8
[15] Edmonds, J. (1970). Submodular functions, matroids, and certain polyhedra. Combinatorial Structures and Their Applications pp 69-87. · Zbl 0268.05019
[16] Essen, J. T., Hurink, J. L., Nickel, S., & Reuter, M. (2013). Models for ambulance planning on the strategic and the tactical level.
[17] Galvão, R. D., & Morabito, R. (2008). Emergency service systems: The use of the hypercube queueing model in the solution of probabilistic location problems. International Transactions in Operational Research, 15(5), 525-549. · Zbl 1172.90361 · doi:10.1111/j.1475-3995.2008.00654.x
[18] Geroliminis, N., Karlaftis, M. G., & Skabardonis, A. (2009). A spatial queuing model for the emergency vehicle districting and location problem. Transportation Research Part B: Methodological, 43(7), 798-811. · doi:10.1016/j.trb.2009.01.006
[19] Geroliminis, N., Kepaptsoglou, K., & Karlaftis, M. G. (2011). A hybrid hypercube-genetic algorithm approach for deploying many emergency response mobile units in an urban network. European Journal of Operational Research, 210(2), 287-300. · Zbl 1210.91029 · doi:10.1016/j.ejor.2010.08.031
[20] Haneveld, W., & van der Vlerk, M. (2006). Integrated chance constraints: reduced forms and an algorithm. Computational Management Science, 3(4), 245-269. · Zbl 1136.90424 · doi:10.1007/s10287-005-0007-3
[21] Hong, X., Lejeune, M. A., Noyan, N. (2014). Stochastic network design for disaster preparedness. IIE Transactions (just-accepted):00-00.
[22] Iannoni, A. P., Morabito, R., & Saydam, C. (2008). A hypercube queueing model embedded into a genetic algorithm for ambulance deployment on highways. Annals of Operations Research, 157(1), 207-224. · Zbl 1151.90360 · doi:10.1007/s10479-007-0195-z
[23] Iannoni, A. P., Morabito, R., & Saydam, C. (2009). An optimization approach for ambulance location and the districting of the response segments on highways. European Journal of Operational Research, 195(2), 528-542. · Zbl 1156.90406 · doi:10.1016/j.ejor.2008.02.003
[24] Iannoni, A., Morabito, R., & Saydam, C. (2010). Optimizing large scale emergency medical system operations on highways using the hypercube queuing model. Socio-Economic Planning Sciences.
[25] Jain, A. (2007). Value of capacity pooling in supply chains with heterogeneous customers. European journal of operational research, 177(1), 239-260. · Zbl 1102.90344 · doi:10.1016/j.ejor.2005.12.006
[26] Jia, H., Ordonez, F., & Dessouky, M. (2007). A modeling framework for facility location of medical services for large-scale emergencies. IIE Transactions, 39(1), 41-55. · doi:10.1080/07408170500539113
[27] Klein Haneveld, W. (1986). Duality in stochastic linear and dynamic programming. In: Lecture notes in economics and mathematical systems, Vol 274. · Zbl 0598.90062
[28] Kou, G., & Wu, W. (2014). Multi-criteria decision analysis for emergency medical service assessment. Annals of Operations Research pp 1-16. · Zbl 1306.90063
[29] Lejeune, M. A. (2013). Probabilistic modeling of multiperiod service levels. European Journal of Operational Research, 230(2), 299-312. · Zbl 1317.90219 · doi:10.1016/j.ejor.2013.04.028
[30] Li, X., Zhao, Z., Zhu, X., & Wyatt, T. (2011). Covering models and optimization techniques for emergency response facility location and planning: a review. Mathematical Methods of Operations Research, 74(3), 281-310. · Zbl 1261.90011 · doi:10.1007/s00186-011-0363-4
[31] Marianov, V., & ReVelle, C. (1995). Siting emergency services. Facility Location: a survey of applications and methods, 1, 199-223. · doi:10.1007/978-1-4612-5355-6_11
[32] Marianov, V., & ReVelle, C. (1996). The queueing maximal availability location problem: a model for the siting of emergency vehicles. European Journal of Operational Research, 93(1), 110-120. · Zbl 0912.90195 · doi:10.1016/0377-2217(95)00182-4
[33] McLay, L. A. (2009). A maximum expected covering location model with two types of servers. IIE Transactions, 41(8), 730-741. · doi:10.1080/07408170802702138
[34] Murali, P., Ordóñez, F., & Dessouky, M. M. (2012). Facility location under demand uncertainty: Response to a large-scale bio-terror attack. Socio-Economic Planning Sciences, 46(1), 78-87. · doi:10.1016/j.seps.2011.09.001
[35] Noyan, N. (2010). Alternate risk measures for emergency medical service system design. Annals of Operations Research pp 1-31. · Zbl 1209.90118
[36] Ozbay, K., Iyigun, C., Baykal-Gursoy, M., & Xiao, W. (2013). Probabilistic programming models for traffic incident management operations planning. Annals of Operations Research, 203(1), 389-406. · Zbl 1269.90072 · doi:10.1007/s10479-012-1174-6
[37] Popescu, I. (2005). A semidefinite programming approach to optimal-moment bounds for convex classes of distributions. Mathematics of Operations Research pp 632-657. · Zbl 1082.60011
[38] Prekopa, A., Vizvari, B., & Badics, T. (1998). Programming under probabilistic constraint with discrete random variable. In: F. Giannessi, S. Komlósi & T. Rapcsák (Eds.), New trends in mathematical programming, (pp. 235-255). Springer. · Zbl 0907.90215
[39] Rajagopalan, H. K., & Saydam, C. (2009). A minimum expected response model: Formulation, heuristic solution, and application. Socio-Economic Planning Sciences, 43(4), 253-262. · doi:10.1016/j.seps.2008.12.003
[40] ReVelle, C. (1989). Review, extension and prediction in emergency service siting models. European Journal of Operational Research, 40(1), 58-69. · Zbl 0667.90033 · doi:10.1016/0377-2217(89)90272-5
[41] ReVelle, C., & Hogan, K. (1989). The maximum availability location problem. Transportation Science, 23(3), 192-200. · Zbl 0681.90036 · doi:10.1287/trsc.23.3.192
[42] Schrijver, A. (2003). Combinatorial optimization: polyhedra and efficiency (Vol. 24). Berlin: Springer. · Zbl 1041.90001
[43] Silva, F., & Serra, D. (2007). Locating emergency services with different priorities: the priority queuing covering location problem. Journal of the Operational Research Society, 59(9), 1229-1238. · Zbl 1176.90363 · doi:10.1057/palgrave.jors.2602473
[44] Snyder, L. (2006). Facility location under uncertainty: A review. IIE Transactions, 38(7), 547-564. · doi:10.1080/07408170500216480
[45] Takeda, R. A., Widmer, J. A., & Morabito, R. (2007). Analysis of ambulance decentralization in an urban emergency medical service using the hypercube queueing model. Computers & Operations Research, 34(3), 727-741. · Zbl 1120.90009 · doi:10.1016/j.cor.2005.03.022
[46] Toro-Díaz, H., Mayorga, M. E., Chanta, S., & McLay, L. A. (2013). Joint location and dispatching decisions for emergency medical services. Computers & Industrial Engineering, 64(4), 917-928. · doi:10.1016/j.cie.2013.01.002
[47] Wolsey, L., & Nemhauser, G. (1999). Integer and Combinatorial Optimization. Wiley Series in Discrete Mathematics and Optimization: Wiley. · Zbl 0944.90001
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.