Large neighborhood local search for the p-median problem
DOI:
https://doi.org/10.2298/YJOR0501053KKeywords:
large neighborhood, Lagrangean relaxations, ant colony, p-median, benchmarksAbstract
In this paper we consider the well known p-median problem. We introduce a new large neighborhood based on ideas of S.Lin and B.W. Kernighan for the graph partition problem. We study the behavior of the local improvement and Ant Colony algorithms with new neighborhood. Computational experiments show that the local improvement algorithm with the neighborhood is fast and finds feasible solutions with small relative error. The Ant Colony algorithm with new neighborhood as a rule finds an optimal solution for computationally difficult test instances.References
Ahuja, R.K., James, O.E., Orlin, B., Punnen, A.P. (2002) A survey of very large-scale neighborhood search techniques. Discrete Applied Mathematics, 123, 75-102
Barahona, F., Anbil, R. (2000) The volume algorithm: Producing primal solutions with a sub gradient method. Mathematical Programming, Ser. A, 87, 385-399
Barahona, F., Chudak, F.A. (1999) Solving large scale incapacitated facility location problems. u: Pardalos P.M. [ur.] Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems, Kluwer Academic Publishers
Beasley, J.E. (1990) OR-Library: Distributing test problems by electronic mail. Journal of the Operational Research Society, 41, 11, 1069-1072
Colorny, A., Dorigo, M., Maniezzo, V. (1991) Distributed optimization by ant colonies. u: Proceedings of the European Conference on Artificial Life, 134-142
Erlenkotter, D. (1978) A dual-based procedure for uncapacitated facility location. Operations Research, 26, 992-1009
Hall, M.Jr. (1967) Combinatorial theory. Waltham: Blaisdell Publ. Co
Hansen, P., Mladenović, N. (1998) An introduction to variable neighborhood search. u: Voss S., i dr. [ur.] Metaheuristics, Advances and Trends in Local Search Paradigms for Optimization, Dorchester, UK: Kluwer Academic Publishers
Kernighan, B.W., Lin, S. (1970) An effective heuristic procedure for partitioning graphs. Bell System Technical Journal, 49, 291-307
Krotov, D.S. (2000) Lower bounds for number of m- quasi groups of order 4 and number of perfect binary codes. Discrete Analysis and Operations Research, Ser. 1, 7, 2, 47-53,in Russian
Mirchandani, P.B., Francis, R.L., ur. (1990) Discrete location theory. Wiley-Interscience
Nemhauser, G.L., Wolsey, L.A. (1988) Integer and combinatorial optimization. New York, itd: Wiley
Resende, M.G.C., Werneck, R.F. (2003) On the implementation of a swap-based local search procedure for the p-median problem. u: Lander R. E. [ur.] Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments, ALENEX'03, SIAM, 119-127
Tovey, C.A. (1997) Local improvement on discrete structures. u: Aarts E. H. L., Lenstra J. K. [ur.] Local Search in Combinatorial Optimization, New York, itd: Wiley
Yannakakis, M. (1997) Computational complexity. u: Aarts E. H. L., Lenstra J. K. [ur.] Local Search in Combinatorial Optimization, New York, itd: Wiley
Downloads
Published
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
