×

Dominant, an algorithm for the \(p\)-center problem. (English) Zbl 1035.90037

Summary: In this paper we present \(Dominant\), an algorithm for the \(p\)-center problem, that is the problem of locating p facilities on a network so as to minimise the maximum distance from each customer to his nearest facility. The algorithm \(Dominant\) solves a series of set covering problems, according to a predefined maximum distance: it has four versions, two of which can solve optimally problems with up to 900 demand points. A set of 45 test problems taken from literature is solved, and results are reported.

MSC:

90B80 Discrete location and assignment
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beasley, J. E., A note on solving large \(p\)-median problems, European Journal of Operational Research, 21, 270-273 (1985) · Zbl 0569.90021
[2] Beasley, J. E., OR-library: Distributing test problems by electronic mail, Journal of the Operational Research Society, 41, 1069-1072 (1990)
[3] Chandrasekaran, R.; Tamir, A., Polynomially bounded algorithms for locating \(p\)-centers on a tree, Mathematical Programming, 22, 304-315 (1982) · Zbl 0486.90036
[4] Christofides, N.; Korman, S., A computational survey of methods for the set covering problem, Management Science, 21, 591-599 (1975) · Zbl 0314.65029
[5] Daskin, M. S., Network and Discrete Location: Models, Algorithms and Applications (1995), John Wiley and Sons, Inc: John Wiley and Sons, Inc New York · Zbl 0870.90076
[6] Drezner, Z., The \(p\)-center problem: Heuristic and optimal algorithms, Journal of the Operational Research Society, 35, 741-748 (1984) · Zbl 0544.90024
[7] Garey, M.; Johnson, D., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman & Company: Freeman & Company New York · Zbl 0411.68039
[8] Hakimi, S. L., Optimal location of switching centers and the absolute centers and medians of a graph, Operations Research, 12, 450-459 (1964) · Zbl 0123.00305
[9] Handler, G. Y., Finding two-centers of a tree: The continuos case, Transportation Science, 12, 93-106 (1978)
[10] Handler, G. Y., \(P\)-center Problems, in Discrete Location Theory, (Mirchandani, P. B.; Francis, R. L. (1990), John Wiley Inc: John Wiley Inc New York), 305-347
[11] Handler, G. Y.; Mirchandani, P. B., Location on Networks (1979), M.I.T. Press: M.I.T. Press Cambridge, MA · Zbl 0533.90026
[12] Ho, A. C., Worst case analysis of a class of set covering heuristics, Mathematical Programming, 23, 170-180 (1982) · Zbl 0489.90066
[13] Jaeger, M.; Kariv, I., Algorithms for finding \(p\)-centers on a weighted tree, Networks, 15, 381-389 (1985) · Zbl 0579.90024
[14] Kariv, O.; Hakimi, S. L., An algorithmic approach to network location problems. Part 1. The \(p\)-centers, SIAM Journal on Applied Mathematics, 37, 513-538 (1979) · Zbl 0432.90074
[15] Klein, C. M.; Kincaid, R. K., The discrete anti-\(p\)-center problem, Transportation Science, 28, 77-79 (1994) · Zbl 0802.90064
[16] Minieka, E., The \(m\)-center problem, SIAM Review, 12, 138-139 (1970) · Zbl 0193.24204
[17] Minieka, E., Conditional centers and medians on a graph, Networks, 10, 265-272 (1980)
[18] Pelegrin, B., Heuristic methods for the \(p\)-center problem, RAIRO Recherche Operationelle, 25, 65-72 (1991) · Zbl 0732.90056
[19] Vasko, F. J.; Wilson, G. R., An efficient heuristic for large set covering problems, Naval Research Logistics Quarterly, 31, 163-171 (1984) · Zbl 0534.90064
[20] Vasko, F. J.; Wilson, G. R., Hybrid heuristics for minimum cardinality set covering problems, Naval Research Logistics Quarterly, 33, 241-249 (1986) · Zbl 0592.90065
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.