Variable Neighborhood Search (VNS)
Variable Neighborhood Search (VNS) is a heuristic optimization method designed to improve solutions to difficult optimization problems by systematically exploring multiple neighborhoods. It extends the concept of local search by recognizing that different neighborhood structures can reveal different improvements. By alternating between neighborhoods of increasing size or complexity, VNS can escape local optima and explore new regions of the solution space.
Originally developed for combinatorial optimization, Variable Neighborhood Search (VNS) has since been applied to a wide range of problems, including routing, scheduling, clustering, and other discrete optimization tasks.
Problem Classes and Applicability
Variable Neighborhood Search (VNS) is well-suited for problems where solutions can be modified through well-defined operations, such as swaps, insertions, or reassignments. These operations naturally define neighborhoods around a current solution.
The method has been applied to many combinatorial optimization problems, including routing problems, timetabling, facility location, and scheduling. It can also be used for problems modeled as Mixed-Integer optimization or Constraint Programming models, particularly when exact methods such as Branch-and-Bound or Branch-and-Cut become computationally expensive.
Because of its flexibility, VNS is often used as a heuristic component within larger hybrid optimization frameworks.
Core Idea and Algorithmic Principle
The central idea of Variable Neighborhood Search (VNS) is that a solution that is locally optimal with respect to one neighborhood may not be optimal with respect to another. Instead of searching within a single neighborhood, the algorithm systematically changes the neighborhood structure during the search.
A typical VNS algorithm operates through three main steps:
Shaking: The algorithm randomly generates a new candidate solution within a larger neighborhood of the current solution. This step perturbs the solution and helps the search escape local optima.
Local improvement: A local search procedure is applied to the new solution in order to find a locally optimal solution within the chosen neighborhood.
Neighborhood change: If the new solution improves the objective value, it becomes the current solution, and the search returns to the smallest neighborhood. Otherwise, the algorithm moves to a larger neighborhood and repeats the process.
By gradually exploring larger neighborhoods when improvements are not found, VNS balances intensification (deep exploration near good solutions) with diversification (exploration of new regions of the search space).
Variants and Extensions
Several variants of Variable Neighborhood Search (VNS) have been developed. Basic VNS follows the shaking and local search procedure described above. General VNS (GVNS) integrates more complex neighborhood structures and local search procedures. Other variants incorporate adaptive strategies or combine VNS with exact optimization techniques.
Variable Neighborhood Search (VNS) is closely related to other neighborhood-based methods, such as local search and Large Neighborhood Search (LNS). While LNS focuses on partial reoptimization of large portions of a solution, VNS systematically changes the neighborhood structures used during the search.
Role in Modern Optimization Solvers
Variable Neighborhood Search (VNS) is widely used as a practical heuristic for large-scale optimization problems. Its ability to escape local optima and explore diverse solution regions makes it effective in many applications.
In modern optimization frameworks, VNS is often integrated with other techniques, including Constraint Programming (CP), Mixed-Integer Programming (MIP), and various metaheuristic approaches. These hybrid methods leverage the strengths of both exact and heuristic search strategies.
Further Reading and References
Mladenović, N., & Hansen, P. (1997). Variable Neighborhood Search. Computers & Operations Research.
The original paper introducing the Variable Neighborhood Search framework.
Hansen, P., Mladenović, N., & Pérez, J. A. M. (2010). Variable Neighbourhood Search: Methods and Applications. Annals of Operations Research.
A comprehensive survey of VNS techniques and their applications.
Aarts, E., & Lenstra, J. K. (2003). Local Search in Combinatorial Optimization. Princeton University Press.
A foundational reference on local search methods, including neighborhood-based heuristics such as VNS.