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 easily be implemented using any local search algorithm as a subroutine. Its effectiveness is illustrated by improvements in the GENIUS algorithm for the traveling salesman problem (Gendreau et al., Operations Research 1992 ), without and with backhauls (Gendreau et al., Computers and Operations Research 1996 ).
Paru en septembre 1996 , 11 pages
Ce cahier a été révisé en juin 1997