×

zbMATH — the first resource for mathematics

The stratified \(p\)-center problem. (English) Zbl 1458.90407
Summary: This work presents an extension of the discrete \(p\)-center problem. In this new model, called stratified \(p\)-center problem (S\(p\)CP), the demand is concentrated in a set of sites and the population of these sites is divided into different strata depending on the kind of service that they require. The aim is to locate \(p\) centers to cover the different types of services demanded minimizing the weighted average of the largest distances associated with each of the different strata. In addition, it is considered that more than one stratum can be present at each site. Different formulations, valid inequalities and preprocessings are developed and compared for this problem. An application of this model is presented in order to implement a heuristic approach based on the sample average approximation method (SAA) for solving the probabilistic \(p\)-center problem in an efficient way.

MSC:
90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Albareda-Sambola, M.; Díaz, J.; Fernández, E., Lagrangean duals and exact solution to the capacitated p-center problem, Eur. J. Oper. Res., 201, 1, 71-81, (2010) · Zbl 1177.90241
[2] Averbakh, I.; Berman, O., Minimax regret p-center location on a network with demand uncertainty, Locat. Sci., 5, 4, 247-254, (1997) · Zbl 0928.90042
[3] Balinski, M., Integer programming: methods uses, computation, Manage. Sci., 12, 253-313, (1965) · Zbl 0129.12004
[4] Calik, H.; Labbé, M.; Yaman, H., p-center Problems, Location Science, 79-92, (2015), Springer
[5] Calik, H.; Tansel, B. C., Double bound method for solving the p-center location problem, Comput. Oper. Res., 40, 12, 2991-2999, (2013) · Zbl 1348.90384
[6] Callaghan, B.; Salhi, S.; Nagy, G., Speeding up the optimal method of Drezner for the p-centre problem in the plane, Eur. J. Oper. Res., 257, 3, 722-734, (2017) · Zbl 1394.90383
[7] Chen, D.; Chen, R., Optimal algorithms for the α-neighbor p-center problem, Eur. J. Oper. Res., 225, 1, 36-43, (2013) · Zbl 1292.90159
[8] Contardo, C.; Iori, M.; Kramer, R., A scalable exact algorithm for the vertex p-center problem, Comput. Oper. Res., 103, 211-220, (2019) · Zbl 1458.90423
[9] Daskin, M., Network and Discrete Location: Models, Algorithms, and Applications, (1995), Wiley: Wiley New York · Zbl 0870.90076
[10] Dobson, G.; Karmarkar, U., Competitive location on a network, Oper. Res., 35, 565-574, (1987) · Zbl 0636.90025
[11] Drezner, Z., Conditional p-center problems, Transp. Sci., 23, 1, 51-53, (1989) · Zbl 0675.90025
[12] Elloumi, S.; Labbé, M.; Pochet, Y., A new formulation and resolution method for the p-center problem, INFORMS J. Comput., 16, 1, 84-94, (2004) · Zbl 1239.90103
[13] Elshaikh, A.; Salhi, S.; Brimberg, J.; Mladenović, N.; Callaghan, B.; Nagy, G., An adaptive perturbation-based heuristic: an application to the continuous p-centre problem, Comput. Oper. Res., 75, 1-11, (2016) · Zbl 1349.90583
[14] Espejo, I.; Marín, A.; Rodríguez-Chía, A. M., Closest assignment constraints in discrete location problems, Eur. J. Oper. Res., 219, 49-58, (2012) · Zbl 1244.90127
[15] Espejo, I.; Marín, A.; Rodríguez-Chía, A. M., Capacitated p-center problem with failure foresight, Eur. J. Oper. Res., 247, 1, 229-244, (2015) · Zbl 1346.90488
[16] García, S.; Labbé, M.; Marín, A., Solving large p-median problems with a radius formulation, INFORMS J. Comput., 23, 4, 546-556, (2011) · Zbl 1243.90091
[17] Garfinkel, R.; Neebe, A.; Rao, M., The m-center problem: minimax facility location, Manage. Sci., 23, 10, 1133-1142, (1977) · Zbl 0369.90125
[18] Homem-de-Mello, T.; Bayraksan, G., Monte carlo sampling-based methods for stochastic optimization., Surv. Oper. Res. Manage.Sci., 19, 1, 56-85, (2014)
[19] Irawan, C.; Salhi, S.; Drezner, Z., Hybrid meta-heuristics with VNS and exact methods: application to large unconditional and condicional vertex p-centre problems, J. Heuristics, 22, 4, 507-537, (2016)
[20] Jeger, M.; Kariv, O., Algorithms for finding p-centers on a weighted tree (for relatively small p), Networks, 15, 3, 381-389, (1985) · Zbl 0579.90024
[21] Kariv, O.; Hakimi, S., An algorithmic approach to network location problems i: the p-centers, SIAM J. Appl. Math., 37, 3, 513-538, (1979) · Zbl 0432.90074
[22] Kleywegt, A.; Shapiro, A.; Homem-de Mello, T., The sample average approximation method for stochastic discrete optimization., SIAM J. Optim., 12, 2, 479-502, (2002) · Zbl 0991.90090
[23] Linderoth, J.; Shapiro, A.; Wright, S., The empirical behavior of sampling methods for stochastic programming, Ann. Oper. Res., 142, 1, 215-241, (2006) · Zbl 1122.90391
[24] Lu, C.-C.; Sheu, J.-B., Robust vertex p-center model for locating urgent relief distribution centers, Comput. Oper. Res., 40, 8, 2128-2137, (2013) · Zbl 1348.90405
[25] Marín, A.; Nickel, S.; Puerto, J.; Velten, S., A flexible model and efficient solution strategies for discrete location problems, Discrete Appl. Math., 157, 5, 1128-1145, (2009) · Zbl 1163.90609
[26] Martínez-Merino, L. I.; Albareda-Sambola, M.; Rodríguez-Chía, A. M., The probabilistic p-center problem: planning service for potential customers, Eur. J. Oper. Res., 262, 2, 509-520, (2017) · Zbl 1375.90167
[27] Özsoy, F. A.; Pınar, M.Ç., An exact algorithm for the capacitated vertex p-center problem, Comput. Oper. Res., 33, 5, 1420-1436, (2006) · Zbl 1126.90039
[28] Quevedo-Orozco, D. R.; Ríos-Mercado, R. Z., Improving the quality of heuristic solutions for the capacitated vertex p-center problem through iterated greedy local search with variable neighborhood descent, Comput. Oper. Res., 62, 133-144, (2015) · Zbl 1348.90412
[29] Revelle, C.; Hogan, K., The maximum reliability location problem and α-reliablep-center problem: derivatives of the probabilistic location set covering problem, Ann. Oper. Res., 18, 1, 155-173, (1989) · Zbl 0707.90063
[30] Robinson, S. M., Analysis of sample-path optimization., Math. Oper. Res., 21, 3, 513-528, (1996) · Zbl 0868.90087
[31] Rubinstein, R. Y.; Shapiro, A., Optimization of static simulation models by the score function method., Math. Comput. Simul., 32, 4, 373-392, (1990)
[32] Schilling, D.; Elzinga, D. J.; Cohon, J.; Church, R.; ReVelle, C., The team/fleet models for simultaneous facility and equipment siting, Transp. Sci., 13, 2, 163-175, (1979)
[33] Shapiro, A., Sample average approximation, Encyclopedia of Operations Research and Management Science, 1350-1355, (2013), Springer
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.