An Introduction to Variable Neighborhood Search

A relatively unexplored approach to the design of heuristics, the guided change of neighborhood in the search process, is examined, which leads to a new metaheuristic, which is widely applicable.

Abstract

In this paper we examine a relatively unexplored approach to the design of heuristics, the guided change of neighborhood in the search process. Using systematically this idea and very little more, i.e., only a local search routine, leads to a new metaheuristic, which is widely applicable. We call this approach Variable Neighborhood Search (VNS).