Variable Neighborhood Search (VNS)
Also known as: VNS, Değişken Komşuluk Araması (VNS), variable neighbourhood search
Variable Neighborhood Search (VNS) is a metaheuristic optimization framework introduced by Mladenović and Hansen in 1997. It escapes local optima by systematically switching among a predefined set of neighborhood structures — first perturbing the current solution (shaking) to reach a different region of the search space, then applying a local search within that region, and finally accepting the new solution only if it improves the incumbent. The method is flexible enough to handle combinatorial problems (routing, scheduling, graph problems) as well as continuous optimization, making it one of the most widely used neighborhood-based metaheuristics in operations research.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
VNS is well suited to any optimization problem where multiple neighborhood structures can be naturally defined — for instance, different swap, insert, or relocate moves in a routing problem, or different exchange operators in a scheduling problem. It works on both combinatorial and continuous variables, requires no normality assumption, and imposes no minimum dataset size because the algorithm operates on solutions rather than statistical samples. VNS is particularly effective when the search landscape is rugged and no single local search consistently finds good solutions. The key prerequisite is the ability to define at least two distinct neighborhood structures, each of which can be explored by a local search procedure.
Strengths & limitations
- Systematically covers the search space by using multiple neighborhood structures, greatly reducing the risk of being trapped in a single local optimum.
- The deterministic Variable Neighborhood Descent (VND) variant is available for problems where reproducibility matters.
- Applicable to both combinatorial (routing, scheduling, graph problems) and continuous optimization without modification to the core framework.
- No normality assumption and no minimum sample size — the method operates on solutions, not on statistical data.
- Modular design: the neighborhood structures and the inner local search can be swapped independently, making the algorithm straightforward to adapt to new problem types.
- Performance depends critically on the quality of the neighborhood structures chosen; poorly designed neighborhoods lead to slow or ineffective search.
- The number and ordering of neighborhoods (k_max) must be set by the practitioner — there is no universal rule, and a bad choice increases runtime without improving solution quality.
- Unlike population-based metaheuristics (genetic algorithms, particle swarm), VNS maintains only one incumbent solution, which may limit diversity in highly multi-modal landscapes.
- Computational cost scales with the cost of the inner local search; expensive evaluation functions can make each VNS iteration slow.
Frequently asked
How is VNS different from simulated annealing or tabu search?
All three are single-solution metaheuristics that escape local optima, but they use different mechanisms. Simulated annealing accepts worse solutions with a probability that decreases over time; tabu search forbids recently visited moves using a memory list. VNS is strictly improvement-based — it never accepts a worse solution — and instead relies on a structured family of neighborhoods of increasing size to explore different regions of the search space. This makes VNS more deterministic and easier to tune than simulated annealing.
What is Variable Neighborhood Descent (VND) and how does it relate to VNS?
VND is the deterministic inner-search component of VNS. It cycles through a set of neighborhood structures sequentially: if a move in neighborhood N_k improves the solution, it restarts from N_1; otherwise it moves to N_{k+1}. VND on its own is a local search procedure. When VND is used as the local search inside the shaking–local-search–accept loop, the combined algorithm is called General VNS (GVNS). VND can also be run standalone when a purely deterministic descent is acceptable.
How many neighborhood structures do I need?
A minimum of two distinct neighborhood structures is needed for VNS to offer any advantage over a simple iterated local search. In practice, three to five well-chosen neighborhoods cover most combinatorial problems effectively. The neighborhoods should be ordered from smallest (least disruptive) to largest, and each should be efficiently explorable by the inner local search. Quality matters far more than quantity: two well-designed neighborhoods outperform ten poorly designed ones.
Can VNS handle continuous (real-valued) optimization problems?
Yes. For continuous problems, neighborhoods are typically defined by perturbation radius or step size rather than discrete move operators. The core VNS loop — shake, local search, accept if better — operates identically. Continuous VNS has been applied to parameter calibration, regression, and engineering design problems.
Sources
- Mladenović, N. & Hansen, P. (1997). Variable Neighborhood Search. Computers & Operations Research, 24(11), 1097–1100. DOI: 10.1016/S0305-0548(97)00031-2 ↗
- Hansen, P., Mladenović, N., Brimberg, J. & Pérez, J.A.M. (2019). Variable Neighborhood Search: Basics and Variants. EURO Journal on Computational Optimization, 7(1), 3–56. DOI: 10.1007/978-3-319-91086-4_3 ↗
How to cite this page
ScholarGate. (2026, June 1). Variable Neighborhood Search (VNS). ScholarGate. https://scholargate.app/en/optimization/variable-neighborhood-search
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Genetic AlgorithmOptimization↔ compare
- Harmony SearchOptimization↔ compare
- Simulated AnnealingOptimization↔ compare
- Tabu SearchOptimization↔ compare