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., and Punnen, A.P., "A survey of very large-scale neighborhood search techniques", Discrete Applied Mathematics, 123 (2002) 75–102.
Barahona, F., and Anbil, R., "The volume algorithm: producing primal solutions with a subgradient method", Mathematical Programming, Ser.A, 87 (2000) 385–399.
Barahona, F., and Chudak, F.A., "Solving large scale uncapacitated facility location problems", in: Pardalos P.M. (ed.), Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems, Kluwer Academic Publishers, 1999.
Beasley, J.E., "OR-Library: Distributing test problems by electronic mail", Journal of the Operational Research Society, 41(11) (1990) 1069-1072.
Colorny, A., Dorigo, M., and Maniezzo, V., "Distributed optimization by ant colonies", Proceedings of the 1991 European Conference on Artificial Life, 1991, 134-142.
Erlenkotter, D., "A dual-based procedure for uncapacitated facility location", Operations Research, 26 (1978) 992–1009.
Hansen, P., and Mladenović, N., "An introduction to variable neighborhood search", in: S.Voss et al. (eds.), Metaheuristics, Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic Publishers, Dorchester, 1998.
Hall, M. Jr., Combinatorial Theory, Blaisdell, Waltham, MA, 1967.
Kernighan, B.W., and Lin, S., "An effective heuristic procedure for partitioning graphs", Bell System Technical Journal, 49 (1970) 291–307.
Krotov, D.S., "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) (2000) 47-53. (in Russian)
Mirchandani, P.B., and Francis, R.L. (eds.), Discrete Location Theory, Wiley-Interscience, 1990.
Resende, M.G.C., and Werneck, R.F., "On the implementation of a swap-based local search procedure for the p-median problem", in: R.E. Lander (ed.), Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments (ALENEX’03), SIAM, 2003, 119-127.
Nemhauser, G.L., and Wolsey, L.A., Integer and Combinatorial Optimization, John Wiley & Sons, 1988.
Tovey, C.A., "Local improvement on discrete structures", in: E.H.L. Aarts, J.K. Lenstra (eds.), Local Search in Combinatorial Optimization, Wiley, Chichester, 1997.
Yannakakis, M., "Computational complexity", in: E.H.L.Aarts, J.K.Lenstra (eds.), Local Search in Combinatorial Optimization, Wiley, Chichester, 1997.
Downloads
Published
Issue
Section
License
Copyright (c) 2005 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
