Variable Neighborhood Search

Abstract

Variable neighborhood search (VNS) is a framework for building heuristics based upon systematic changes of neighborhoods both in a descent phase, to find a local minimum, and in a perturbation phase to emerge from the corresponding valley. In this chapter, we provide an overview of different VNS variants and describe how they can be used to solve diversity (dispersion) problems. More precisely, we present different neighborhood structures that may be exploited and show how they can be organized within variable neighborhood descent and variable neighborhood search heuristics. Finally, we provide insights on the performance of different VNS methodologies applied to two diversity problems: the maximum diversity problem and the capacitated dispersion problem.