×

zbMATH — the first resource for mathematics

Solving the \(p\)-center problem with tabu search and variable neighborhood search. (English) Zbl 1036.90046
In the \(p\)-center location problem, it is required to select \(p\) out of \(m\) given clients and assigning each client to one of the selected locations such that the maximum distance between any client and its associated selected locations in minimized. This problem is well-known to be NP-hard and has numerous applications.
The authors show that ideas from \(p\)-median problems can be carried over to the case of \(p\)-centers. A vertex substitution local search is used as building block in three metaheuristics: multistart local search, tabu search and variable neighbourhood search. Extensive numerical tests are performed using test instances from the OR-Lib and TSP-Lib sets. The tests confirm that the new heuristics are very powerful tools with provable optimality achieved by at least one of the heuristics even for large problem instances of more than 3000 clients.

MSC:
90B80 Discrete location and assignment
90C10 Integer programming
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Baum, Neural networks for computing (1986)
[2] Beasley, A note on solving large p-Median problems, Eur J Oper Res 21 pp 270– (1985) · Zbl 0569.90021
[3] Boese, A new adaptive multi-start technique for combinatorial global optimizations, Oper Res Lett 16 pp 101– (1994) · Zbl 0812.90126
[4] Brimberg, Improvements and comparison of heuristics for solving the multisource Weber problem, Oper Res 48 pp 444– (2000)
[5] Daskin, Network and discrete location (1995) · Zbl 0870.90076
[6] Drezner, The p-Center problem-heuristics and optimal algorithms, J Oper Res Soc 35 pp 741– (1984) · Zbl 0544.90024
[7] Dyer, A simple heuristic for the p-Center problem, Oper Res Lett 3 pp 285– (1985) · Zbl 0556.90019
[8] Glover, Tabu search-Part I, ORSA J Comput 1 pp 190– (1989) · Zbl 0753.90054
[9] Glover, Tabu search-Part II, ORSA J Comput 2 pp 4– (1990) · Zbl 0771.90084
[10] Hansen, Algorithms for the maximum satisfiability problem, Computing 44 pp 279– (1990) · Zbl 0716.68077
[11] Hansen, The p-Center-sum location problem, Cah CERO 36 pp 203– (1994) · Zbl 0840.90096
[12] Hansen, Variable neighborhood search for the p-Median, Locat Sci 5 pp 207– (1997) · Zbl 0928.90043
[13] Hansen, Metaheuristics, advances and trends in local search paradigms for optimization pp 433– (1999)
[14] Hansen, J-MEANS: A new local search heuristic for minimum sum-of-squares clustering, Pattern Recog 34 pp 405– (2001) · Zbl 1012.68873
[15] Hansen, Variable neighborhood decomposition search, J Heuristics 7 pp 335– (2001) · Zbl 1041.68623
[16] Hochbaum, A best possible heuristic for the k-Center problem, Math Oper Res 10 pp 180– (1985) · Zbl 0565.90015
[17] Kariv, An algorithmic approach to network location problems. Part 1: The p-Centers, SIAM J Appl Math 37 pp 513– (1979) · Zbl 0432.90074
[18] Martinich, A vertex-closing approach to the p-Center problem, Naval Res Log 35 pp 185– (1988) · Zbl 0696.90022
[19] Minieka, The m-Center problem, SIAM Rev 12 pp 138– (1970) · Zbl 0193.24204
[20] Mladenović, Variable neighborhood search, Comp Oper Res 24 pp 1097– (1997) · Zbl 0889.90119
[21] Mladenović, Tabu search in solving the p-facility location-allocation problems, Les Cahiers du GERAD G-95-38 (1995)
[22] Mladenović, A chain-interchange heuristic method, Yugoslav J Oper Res 6 pp 41– (1996)
[23] Plesnik, A heuristic for the p-Center problem in graphs, Discrete Appl Math 17 pp 263– (1987) · Zbl 0637.05020
[24] Reinelt, TSP-Lib-A traveling salesman library, ORSA J Comput 3 pp 376– (1991) · Zbl 0775.90293
[25] Voss, A reverse elimination approach for the p-Median problem, Stud Locat Anal 8 pp 49– (1996) · Zbl 1176.90365
[26] Whitaker, A fast algorithm for the greedy interchange for large-scale clustering and median location problems, INFOR 21 pp 95– (1983) · Zbl 0527.90017
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.