×

The probabilistic \(p\)-center problem: planning service for potential customers. (English) Zbl 1375.90167

Summary: This work deals with the probabilistic \(p\)-center problem, which aims at minimizing the expected maximum distance between any site with demand and its center, considering that each site has demand with a specific probability. The problem is of interest when emergencies may occur at predefined sites with known probabilities. For this problem, we propose and analyze different formulations as well as a variable neighborhood search heuristic. Computational tests are reported, showing the potentials and limits of each formulation, the impact of their enhancements, and the effectiveness of the heuristic.

MSC:

90B80 Discrete location and assignment
90C11 Mixed integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albareda-Sambola, M.; Fernández, E.; Saldanha da Gama, F., The facility location problem with Bernoulli demands, Omega, 39, 3, 335-345 (2011)
[2] Berman, O.; Krass, D.; Wang, G., Stochastic analysis in location research, (Eiselt, H. A.; Marianov, V., Foundations of location analysis, chapter 11. Foundations of location analysis, chapter 11, International Series in Operations Research and Management Science (2011), Springer-Verlag), 241-272 · Zbl 1387.90120
[3] Berman, O.; Krass, D.; Menezes, M., Facility reliability issues in network p-median problems: strategic centralization and co-location effects, Operations Research, 55, 332-350 (2007) · Zbl 1167.90466
[4] Calik, H.; Labbé, M.; Yaman, H., \(p\)-Center problems, (Laporte, G.; Nickel, S.; Saldanha da Gama, F., Location science (2015), Springer), 79-92
[5] Calik, H.; Tansel, B., Double bound method for solving the \(p\)-center location problem, Computers & Operations Research, 40, 2991-2999 (2013) · Zbl 1348.90384
[6] Daskin, M., Network and discrete location: Models, algorithms, and applications (1995), Wiley · Zbl 0870.90076
[7] Daskin, M. S., A new approach to solving the vertex p-center problem to optimality: Algorithm and computational results, Communications of the Operations Research Society of Japan, 45, 9, 428-436 (2000)
[8] Domínguez-Marín, P.; Nickel, S.; Hansen, P.; Mladenović, N., Heuristic procedures for solving the discrete ordered median problem, Annals of Operations Research, 136, 145-173 (2005) · Zbl 1105.90332
[9] Drezner, Z.; Hamacher, H., Facility location: Applications and theory (2002), Springer Verlag · Zbl 0988.00044
[10] Espejo, I.; Marín, A.; Rodríguez-Chía, A. M., Closest assignment constraints in discrete location problems, European Journal of Operational Research, 219, 49-58 (2012) · Zbl 1244.90127
[11] Espejo, I.; Marín, A.; Rodríguez-Chía, A. M., Capacitated \(p\)-center problem with failure foresight, European Journal of Operational Research, 247, 1, 229-244 (2015) · Zbl 1346.90488
[12] Halpern, J., Finding minimal center-median convex combination (cent-dian) of a graph, Management Science, 24, 535-544 (1978) · Zbl 0371.90120
[13] Huang, R.; Kim, S.; Menezes, M. B.C., Facility location for large-scale emergencies, Annals of Operations Research, 181, 271-286 (2010) · Zbl 1209.90236
[14] Irawan, C.; Salhi, S.; Drezner, Z., Hybrid meta-heuristics with VNS and exact methods: application to large unconditional and condicional vertex p-centre problems, Journal of Heuristics, 22, 507-537 (2015)
[15] Kariv, O.; Hakimi, S., An algorithmic approach to network location problems I: The \(p\)-centers, SIAM Journal on Applied Mathematics, 37, 3, 513-538 (1979) · Zbl 0432.90074
[16] Kouvelis, P.; Yu, G., Robust discrete optimization and its applications, 356 (1997), Dordrecht: Kluwer Academic Publishers. xvi · Zbl 0873.90071
[17] Laporte, G.; Nickel, S.; Saldanha da Gama, F., Location science (2015), Springer · Zbl 1329.90003
[18] Lu, C.-C., Robust weighted vertex p-center model considering uncertain data: An application to emergency management, European Journal of Operational Research, 230, 1, 113-121 (2013) · Zbl 1317.90166
[19] Lu, C.-C.; Sheu, J.-B., Robust vertex p-center model for locating urgent relief distribution centers, Computers & Operations Research, 40, 8, 2128-2137 (2013) · Zbl 1348.90405
[20] Marín, A.; Nickel, S.; Puerto, J.; Velten, S., A flexible model and efficient solution strategies for discrete location problems, Discrete Applied Mathematics, 157, 1128-1145 (2009) · Zbl 1163.90609
[21] Mladenović, N.; Hansen, P., Variable neighbourhood search, Computers & Operation Research, 24, 1097-1100 (1997) · Zbl 0889.90119
[22] Nickel, S.; Puerto, J., Facility location: A unified approach (2005), Springer
[23] Ogryczak, W., On cent-dians of general networks, Location Science, 5, 15-28 (1997) · Zbl 0930.90057
[24] O’Hanley, J.; Scaparra, M.; García, S., Probability chains: A general linearization technique for modeling reliability in FLP, European Journal of Operational Research, 230, 63-75 (2013) · Zbl 1317.90210
[25] Puerto, J.; Pérez-Brito, D.; García-González, C. G., A modified variable neighborhood search for the DOMP, European Journal of Operational Research, 234, 1, 61-76 (2014) · Zbl 1305.90257
[26] Puerto, J.; Rodríguez-Chía, A. M., Robust positioning of service units, Stochastic Models, 19, 1, 125-147 (2003) · Zbl 1060.90054
[27] Snyder, L., Facility location under uncertainty: a review, IIE Transactions, 38, 537-554 (2006)
[28] Snyder, L.; Daskin, M., Reliability models for facility location: the expected failure cost case, Transportation Science, 39, 400-416 (2005)
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.