VNS

Home /
Methods /
VNS

Variable Neighborhood Search (VNS)

Variable Neighborhood Search (VNS) is a powerful metaheuristic introduced by Mladenović and Hansen (1997) for solving combinatorial and global optimization problems. The main idea is simple but effective: systematically change the neighborhood structures within a local search to escape local optima and explore the search space more thoroughly.

Core Idea of VNS

Traditional Local Search uses a fixed neighborhood and often gets trapped in a local optimum. VNS addresses this by changing the neighborhood dynamically during the search process.

VNS consists of three main components:

Shaking – Randomly move to a new solution in a different neighborhood.
Local Search – Perform local search from the shaken solution.
Neighborhood Change – Decide whether to change or expand the neighborhood.

Basic VNS Algorithm

function VNS(S, k_max):
    repeat:
        k ← 1
        while k ≤ k_max:
            S' ← Shake(S, k)
            S'' ← LocalSearch(S')
            if S'' better than S:
                S ← S''
                k ← 1
            else:
                k ← k + 1
    until stopping criterion met
    return S

k is the current neighborhood index.
k_max is the number of different neighborhood structures.
Shake(S, k) perturbs the current solution in the k-th neighborhood.
LocalSearch(S') tries to improve the shaken solution.

Neighborhood Structures

In VNS, you define a set of neighborhood structures:

$$ \mathcal{N}1, \mathcal{N}2, …, \mathcal{N}{k{\max}} $$

Each 𝒩_k(S) represents a different way of modifying a solution S, often with increasing size or complexity. For example, in the Traveling Salesman Problem (TSP):

𝒩₁: Swap two cities (2-opt)
𝒩₂: Reverse a segment (3-opt)
𝒩₃: Insert a city in a new position

This allows the algorithm to escape local optima by making larger or fundamentally different changes when needed.

Variants of VNS

VNS is highly flexible, and several variants have been proposed:

1. Basic VNS (BVNS)

Uses systematic change of neighborhoods without memory.
Local Search is applied after every shake.

2. Reduced VNS (RVNS)

No local search is performed.
Only the shaking phase is used.
Much faster, useful for large-scale or real-time problems.

function RVNS(S, k_max):
    repeat:
        k ← 1
        while k ≤ k_max:
            S' ← Shake(S, k)
            if S' better than S:
                S ← S'
                k ← 1
            else:
                k ← k + 1
    until stopping criterion met
    return S

3. General VNS (GVNS)

Combines RVNS and BVNS.
Uses RVNS as diversification and BVNS for intensification.

4. Skewed VNS

Accepts worse solutions if they are far enough from the current one.
Promotes diversification.

if f(S') < f(S) or distance(S, S') > threshold:
    S ← S'

5. Variable Neighborhood Descent (VND)

A deterministic version of VNS.
Applies a sequence of local searches in increasing neighborhoods.

function VND(S, k_max):
    k ← 1
    while k ≤ k_max:
        S' ← LocalSearch_k(S)
        if S' better than S:
            S ← S'
            k ← 1
        else:
            k ← k + 1
    return S

Strategic Schemes in VNS

VNS offers several strategic enhancements:

1. Deterministic vs. Probabilistic Neighborhood Changes

Use randomization to select or switch neighborhoods.
Helps prevent cycling and promotes exploration.

2. Adaptive Neighborhood Selection

Dynamically adjust which neighborhoods to explore more based on past performance.

3. Intensification and Diversification Balance

Shake function (exploration/diversification)
Local Search (exploitation/intensification)

4. Hybridization

Combine VNS with:
- GRASP
- Tabu Search
- Genetic Algorithms
Useful for multi-objective or dynamic problems.

Applications of VNS

VNS has been successfully applied to a wide range of problems:

Traveling Salesman Problem (TSP)
Vehicle Routing Problems (VRP)
Job Shop Scheduling
Knapsack Problems
Network Design
Facility Location
Clustering and Data Mining

Advantages of VNS

Simple yet powerful: The framework is easy to understand and implement.
Flexible: Customizable neighborhood structures for any problem.
Efficient: Capable of escaping local optima quickly.
Scalable: Works well on large and complex problem instances.

References

Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research.
Hansen, P., Mladenović, N., & Pérez, J. A. M. (2010). Variable neighbourhood search: Methods and applications. Annals of Operations Research.
Hansen, P., & Mladenović, N. (2001). J-Measures and Variable Neighborhood Search. Journal of Heuristics.

Conclusion

Variable Neighborhood Search (VNS) is a versatile metaheuristic that systematically explores the solution space using multiple neighborhood structures. Its ability to balance diversification and intensification, along with its flexibility and simplicity, makes it an essential tool for solving hard optimization problems.

Whether you’re solving routing, scheduling, or clustering problems, VNS offers a robust and efficient way to reach high-quality solutions.

VNS