Group for Research in Decision Analysis


Variable Neighbourhood Search


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

This cahier was revised in June 1997