×

zbMATH — the first resource for mathematics

An exact algorithm for the capacitated vertex \(p\)-center problem. (English) Zbl 1126.90039
Summary: We develop a simple and practical exact algorithm for the problem of locating \(p\) facilities and assigning clients to them within capacity restrictions in order to minimize the maximum distance between a client and the facility to which it is assigned (capacitated \(p\)-center). The algorithm iteratively sets a maximum distance value within which it tries to assign all clients, and thus solves bin-packing or capacitated concentrator location subproblems using off-the-shelf optimization software. Computational experiments yield promising results.

MSC:
90B80 Discrete location and assignment
90C10 Integer programming
90C90 Applications of mathematical programming
Software:
OR-Library
PDF BibTeX Cite
Full Text: DOI
References:
[1] Ilhan T, Pınar MÇ. An efficient exact algorithm for the vertex \(p\)-center problem, http://www.optimization-online.org/DB-HTML/2001/09/376.html, 2001.
[2] Kariv, O.; Hakimi, S.L., An algorithmic approach to network location problems part ithe p-centers, SIAM journal of applied mathematics, 37, 513-538, (1979) · Zbl 0432.90074
[3] 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
[4] Elloumi S, Labbé M, Pochet Y. A new formulation and resolution method for the \(p\)-center problem. INFORMS Journal on Computing, 2001, to appear.
[5] Daskin, M.S., A new approach to solving the vertex \(p\)-center problem to optimalityalgorithm and computational results, Communications of the operations research society of Japan, 45, 428-436, (2000)
[6] Daskin, M.S., Network and discrete location, (1995), Wiley New York · Zbl 0870.90076
[7] Bar-Ilan, J.; Kortsarz, G.; Peleg, D., How to allocate network centers, Journal of algorithms, 15, 385-415, (1993) · Zbl 0784.68012
[8] Khuller, S.; Sussmann, Y.J., The capacitated K-center problem, SIAM journal on discrete mathematics, 13, 403-418, (2000) · Zbl 0947.05073
[9] Jaeger, M.; Goldberg, J., A polynomial algorithm for the equal capacity \(p\)-center problem on trees, Transportation science, 28, 167-175, (1994) · Zbl 0807.90076
[10] Pallottino, S.; Scappara, M.P.; Scutellà, M.G., Large scale local search heuristics for the capacitated vertex \(p\)-center problem, Networks, 43, 4, 241-255, (2002)
[11] Deng Q, Simchi-Levi D. Valid inequalities, facets and computational experience for the capacitated concentrator location problem. Rsearch report, Department of Industrial Engineering and Operations Research, Columbia University, New York, 1993.
[12] Martello, S.; Toth, P., Knapsack problemsalgorithms and implementations, (1990), Wiley New York
[13] Beasley, J.E., A note on solving large \(p\)-Median problems, European journal operational research, 21, 270-273, (1985) · Zbl 0569.90021
[14] Lorena, L.A.N.; Senne, E.L.F., A column generation approach to capacitated \(p\)-Median problems, Computers and operations research, 31, 6, 863-876, (2004) · Zbl 1048.90132
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.