×

zbMATH — the first resource for mathematics

New relaxation-based algorithms for the optimal solution of the continuous and discrete \(p\)-center problems. (English) Zbl 1177.90246
Summary: We present new relaxation algorithms for the uncapacitated continuous and discrete \(p\)-center problems. We have conducted an experimental study that demonstrated that these new algorithms are extremely efficient.

MSC:
90B80 Discrete location and assignment
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Handler, G.Y.; Mirchandani, P.B., Location on networks: theory and algorithms, (1979), MIT Press Cambridge, MA · Zbl 0533.90026
[2] Chen, R.; Handler, G.Y., Relaxation method for the solution of the minimax location – allocation problem in Euclidean space, Naval research logistics, 34, 775-787, (1987) · Zbl 0648.90026
[3] Drezner, Z., The p-center problem—heuristic and optimal algorithms, Journal of operation research, 8, 741-748, (1984) · Zbl 0544.90024
[4] Minieka, E., The m-center problem, SIAM reviews, 12, 139-140, (1970) · Zbl 0193.24204
[5] Megiddo, N.; Supowit, K.J., On the complexity of some common geometric location problems, SIAM journal on computation, 13, 182-196, (1984) · Zbl 0534.68032
[6] Hochbaum, D.S., When are NP-hard problems easy? annals of operations research, 1, 201-214, (1984)
[7] Chrystal, G., On the problem to construct the minimum circle enclosing n given points in the plane, Proceedings of the Edinburgh mathematical society, 3, 30-33, (1885) · JFM 17.0540.01
[8] Rademacher, H.; Toeplitz, O., The spanning circle of a finite set of points, (), 103-110
[9] Chen, R., Solution of minisum and minimax location – allocation problems with Euclidean distances, Naval research logistics quarterly, 30, 449-459, (1983)
[10] Drezner, Z., The planar two center and two Median problems, Transportation science, 18, 351-361, (1984)
[11] Watson-Gandy, C.D.T., The multi-facility min – max Weber problem, European journal of operational research, 18, 44-50, (1984) · Zbl 0542.90033
[12] Toregas, C.; Swain, R.; ReVelle, C.; Bergmann, L., The location of emergency service facilities, Operations research, 19, 1363-1373, (1971) · Zbl 0224.90048
[13] Hwang, R.Z.; Lee, R.C.T.; Cheng, R.C., The slab dividing approach to solve the Euclidean p-center problem, Algorithmica, 9, 1-22, (1993) · Zbl 0766.68136
[14] Suzuki, A.; Drezner, Z., The p-center location problem in the area, Location science, 4, 69-82, (1996) · Zbl 0917.90233
[15] Wei, H.; Murray, A.T.; Xiao, N., Solving the continuous space p-center problem: planning applications issues, IMA journal of management and mathematics, 17, 413-425, (2006) · Zbl 1126.90047
[16] Agarwal, P.K.; Sharir, M., Efficient algorithms for geometric optimization, ACM computing surveys, 30, 428-458, (1998)
[17] Hale, S.H.; Moberg, C.R., Location science research: a review, Annals of operations research, 123, 21-35, (2004) · Zbl 1137.90598
[18] Kariv, O.; Hakimi, S.L., An algorithmic approach to network location problems. part 1: p-centers, SIAM journal of applied mathematics, 37, 513-538, (1971) · Zbl 0432.90074
[19] Current, J.; Daskin, M.; Schilling, D., Facility location: applications and theory, (), 83-120
[20] 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)
[21] 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
[22] Elloumi, S.; Labbé, M.; Pochet, Y., A new formulation and resolution method for the p-center problem, INFORMS journal of computing, 16, 84-94, (2004) · Zbl 1239.90103
[23] Caruso, C.; Colorni, A.; Aloi, L., Dominant, an algorithm for the p-center problem, European journal of operational research, 149, 53-64, (2003) · Zbl 1035.90037
[24] Ilhan T, Özsoy FA, Pinar MC. An efficient exact algorithm for the vertex p-center problem and computational experiments for different set covering subproblems. Technical Report; 2002. Available at URL: ⟨http://www.optimization-online.org/DB_HTML/2002/12/588.html⟩.
[25] Beasley, J.E., A note on solving large p-Median problems, European journal of operational research, 21, 270-273, (1985), \(\langle\)http://people.brunel.ac.uk/mastjjb/jeb/orlib/pmedinfo.html⟩ · Zbl 0569.90021
[26] Reinelt G. TSP-Lib. URL: \(\langle\)http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html⟩.
[27] Daskin, M.S., Network and discrete location, models: algorithms and applications, (1995), Wiley Interscience Publications, Wiley New York · Zbl 0870.90076
[28] ILOG, Inc. Gentilly, France. ILOG CPLEX 7.5 User’s Manual; November 2001.
[29] Vijay, J., An algorithm for the p-center problem in the plane, Transportation science, 19, 235-245, (1985) · Zbl 0608.90020
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.