Variable neighborhood search. (English) Zbl 0889.90119

Summary: Systematic change of neighborhood within a local search algorithm yields a simple and effective metaheuristic for combinatorial optimization. We present a basic scheme for this purpose which can be implemented easily using any local search algorithm as a subroutine. Its effectiveness is illustrated by improvements in the GENIUS algorithm for the traveling salesman problem, without and with backhauls.


90C27 Combinatorial optimization
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI


[1] Gendreau, M.; Hertz, A.; Laporte, G., New insertion and postoptimization procedures for the traveling salesman problem, Operations Research, 40, 1086-1094 (1992) · Zbl 0767.90087
[2] Gendreau, M.; Hertz, A.; Laporte, G., The traveling salesman problem with backhauls, Computers and Operations Research, 23, 501-508 (1996) · Zbl 0847.90135
[3] (Reeves, C., Modern Heuristic Techniques for Combinatorial Problems (1993), Blackwells: Blackwells Oxford) · Zbl 0942.90500
[4] Osman, I. H.; Laporte, G., Metaheuristics. A bibliography, Annals of Operational Research, 63, 513-628 (1996) · Zbl 0849.90097
[5] Glover, F., Tabu Search-Part I, ORSA Journal of Computing, 1, 190-206 (1989) · Zbl 0753.90054
[6] Glover, F., Tabu Search-Part II, ORSA Journal of Computing, 2, 4-32 (1990) · Zbl 0771.90084
[7] Hansen, P.; Jaumard, B., Algorithms for the maximum satisfiability problem, Computing, 44, 279-303 (1990) · Zbl 0716.68077
[8] Johnson, D. S.; McGeoch, L. A., The traveling salesman problem, a case study in local optimization, (Aarts, E. H.L.; Lenstra, J. K., Local search in combinatorial optimization (1997), Wiley: Wiley New York), (to appear) · Zbl 0845.90123
[9] Bentley, J. L., Fast algorithms for geometric traveling salesman problem, ORSA Journal of Computing, 4, 387-411 (1992) · Zbl 0758.90071
[10] Erlenkotter, D., A dual-based procedure for uncapacitated facility location, Operations Research, 26, 992-100911 (1978) · Zbl 0422.90053
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.