×

zbMATH — the first resource for mathematics

The complete vertex \(p\)-center problem. (English) Zbl 1452.90224
Summary: The vertex \(p\)-center problem consists of locating \(p\) facilities among a set of \(M\) potential sites such that the maximum distance from any demand to its closest located facility is minimized. The complete vertex \(p\)-center problem solves the \(p\)-center problem for all \(p\) from 1 to the total number of sites, resulting in a multi-objective trade-off curve between the number of facilities and the service distance required to achieve full coverage. This trade-off provides a reference to planners and decision makers, enabling them to easily visualize the consequences of choosing different coverage design criteria for the given spatial configuration of the problem. We present two fast algorithms for solving the complete \(p\)-center problem: one using the classical formulation but trimming variables while still maintaining optimality and the other converting the problem to a location set covering problem and solving for all distances in the distance matrix. We also discuss scenarios where it makes sense to solve the problem via brute-force enumeration. All methods result in significant speedups, with the set covering method reducing computation times by many orders of magnitude.
MSC:
90C10 Integer programming
90C11 Mixed integer programming
90C27 Combinatorial optimization
90C90 Applications of mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Balinski, ML, Integer programming: methods, uses, computations, Manag Sci, 12, 253-313 (1965) · Zbl 0129.12004
[2] Calik, H.; Tansel, BC, Double bound method for solving the p-center location problem, Comput Oper Res, 40, 2991-2999 (2013) · Zbl 1348.90384
[3] Calik, H.; Labbé, M.; Yaman, H.; Laporte, G.; Nickel, S.; da Gama, SF, p-Center problems, Location science, 79-92 (2015), Berlin: Springer, Berlin
[4] Chen, D.; Chen, R., New relaxation-based algorithms for the optimal solution of the continuous and discrete p-center problems, Comput Oper Res, 36, 1646-1655 (2009) · Zbl 1177.90246
[5] Church, RL, BEAMR: an exact and approximate model for the p-median problem, Comput Oper Res, 35, 417-426 (2008) · Zbl 1141.90463
[6] Church, RL, Tobler’s law and spatial optimization why bakersfield?, Int Reg Sci Rev, 41, 3, 287-310 (2016)
[7] Church, RL; Gerrard, RA, The multi-level location set covering model, Geogr Anal, 35, 277-289 (2003)
[8] Church, R.; Medrano, F., AM-46-location-allocation modeling, Geogr Inf Sci Technol Body Knowl (2018)
[9] Church, R.; ReVelle, CR, The maximal covering location problem, Pap Reg Sci, 32, 101-118 (1974)
[10] Church, RL; Roberts, KL, Generalized coverage models and public facility location, Pap Reg Sci Assoc, 53, 117-135 (1983)
[11] Church, R.; Weaver, J., Theoretical links between median and coverage location problems, Ann Oper Res, 6, 1-19 (1986)
[12] 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
[13] Daskin MS (2013) Center problems. In: Network and discrete location: models, algorithms, and applications. 2nd edn. Wiley, New York, pp 193-234. 10.1002/9781118537015.ch05
[14] Daskin MS, Maass KL (2015) The p-median problem. In: Location science. Springer, Berlin, pp 21-45
[15] Daskin, MS; Owen, SH, Two new location covering problems: the partial p-center problem and the partial set covering problem, Geogr Anal, 31, 217-235 (1999)
[16] Drezner, Z., The planar two-center and two-median problems, Transp Sci, 18, 351-361 (1984)
[17] Dzator, M.; Dzator, J., An effective heuristic for the p-median problem with application to ambulance location, Opsearch, 50, 60-74 (2013) · Zbl 1353.90179
[18] Elloumi, S.; Labbé, M.; Pochet, Y., A new formulation and resolution method for the p-center problem, INFORMS J Comput, 16, 84-94 (2004) · Zbl 1239.90103
[19] Fo, A.; da Silva, Mota I., Optimization models in the location of healthcare facilities: a real case in Brazil, J Appl Oper Res, 4, 37-50 (2012)
[20] Gadegaard, SL; Klose, A.; Nielsen, LR, An improved cut-and-solve algorithm for the single-source capacitated facility location problem, EURO J Comput Optim, 6, 1-27 (2018) · Zbl 1390.90008
[21] García, S.; Labbé, M.; Marín, A., Solving large p-median problems with a radius formulation, INFORMS J Comput, 23, 546-556 (2011) · Zbl 1243.90091
[22] Hakimi, SL, Optimum locations of switching centers and the absolute centers and medians of a graph, Oper Res, 12, 450-459 (1964) · Zbl 0123.00305
[23] Kariv, O.; Hakimi, SL, An algorithmic approach to network location problems. I: the p-centers, SIAM J Appl Math, 37, 513-538 (1979) · Zbl 0432.90074
[24] Marianov, V.; ReVelle, C., Siting emergency services, Facil Locat Surv Appl Methods, 1, 199-223 (1995)
[25] Medrano FA (2019) p-center. https://github.com/antoniomedrano/p-center. Accessed 25 Sept 2019
[26] Minieka, E., The m-center problem, SIAM Rev, 12, 138-139 (1970) · Zbl 0193.24204
[27] Mladenović, N.; Labbé, M.; Hansen, P., Solving the p-center problem with tabu search and variable neighborhood search, Networks, 42, 48-64 (2003) · Zbl 1036.90046
[28] Niblett, MR; Church, RL, The disruptive anti-covering location problem, Eur J Oper Res, 247, 764-773 (2015) · Zbl 1346.90512
[29] Reinelt, G., TSPLIB—a traveling salesman problem library, ORSA J Comput, 3, 376-384 (1991) · Zbl 0775.90293
[30] ReVelle, C., Facility siting and integer-friendly programming, Eur J Oper Res, 65, 147-158 (1993) · Zbl 0776.90047
[31] Rosing, KE; ReVelle, C.; Rosing-Vogelaar, H., The p-median and its linear programming relaxation: an approach to large problems, J Oper Res Soc, 30, 815-823 (1979) · Zbl 0422.90049
[32] Salazar-Aguilar, MA; Ríos-Mercado, RZ; González-Velarde, JL, GRASP strategies for a bi-objective commercial territory design problem, J Heuristics, 19, 179-200 (2013)
[33] Schilling, DA, Strategic facility planning: the analysis of options, Decis Sci, 13, 1-14 (1982)
[34] Shier, D., A min-max theorem for p-center problems on a tree, Transp Sci, 11, 243 (1977)
[35] Snyder, LV; Daskin, MS, Stochastic p-robust location problems, IIE Trans, 38, 971-985 (2006)
[36] Solanki, R., Generating the noninferior set in mixed integer biobjective linear programs: an application to a location problem, Comput Oper Res, 18, 1-15 (1991) · Zbl 0737.90056
[37] Suzuki, A.; Drezner, Z., The p-center location problem in an area, Locat Sci, 4, 69-82 (1996) · Zbl 0917.90233
[38] Swain RW (1971) A decomposition algorithm for a class of facility location problems. (No. 71-24530 UMI)
[39] Teitz, MB; Bart, P., Heuristic methods for estimating the generalized vertex median of a weighted graph, Oper Res, 16, 5, 955-961 (1968) · Zbl 0165.22804
[40] Tutunchi, GK; Fathi, Y., Effective methods for solving the Bi-criteria p-Center and p-Dispersion problem, Comput Oper Res, 101, 43-54 (2019) · Zbl 1458.90440
[41] Wei H (2008) Solving continuous space location problems. Dissertation, The Ohio State University
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.