Groupe d’études et de recherche en analyse des décisions

G-96-49

Variable Neighbourhood Search

et

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 [1]), without and with backhauls (Gendreau et al., Computers and Operations Research 1996 [2]).

, 11 pages

Ce cahier a été révisé en juin 1997