Variable Neighborhood Search (VNS) is a metaheuristic framework proposed by Nenad Mladenović and Pierre Hansen in 1997. Its central insight is deceptively simple: a solution that is locally optimal with respect to one neighborhood structure may not be locally optimal with respect to another. By systematically changing the neighborhood structure during search, VNS escapes local optima without needing the explicit memory of tabu search or the temperature schedule of simulated annealing.
VNS distinguishes itself from other metaheuristics through its elegance and parsimony. The basic algorithm has essentially no parameters beyond the set of neighborhoods and the stopping criterion. There are no cooling schedules, tabu tenures, or population sizes to tune. This makes VNS remarkably easy to implement and adapt to new problem domains, while still being competitive with — or superior to — more complex methods on many benchmarks.
The method has been successfully applied to hundreds of combinatorial and continuous optimization problems: facility location, graph partitioning, clustering, vehicle routing, scheduling, telecommunications network design, and more. Hansen’s group at GERAD/HEC Montréal has published extensive surveys documenting VNS applications across operations research and computer science.
Consider a traveling salesman problem (TSP). A 2-opt local search checks all pairs of edges and swaps them if it shortens the tour. A tour that is 2-optimal (no improving 2-opt swap exists) may still be improved by a 3-opt move — because the 3-opt neighborhood is strictly larger. The key insight of VNS: instead of defining one neighborhood and getting trapped at its local optimum, define a sequence of increasingly large (or structurally different) neighborhoods and use them systematically.
Observation 1: A local minimum with respect to one neighborhood structure is not necessarily a local minimum with respect to another. Observation 2: A global minimum is a local minimum with respect to all possible neighborhood structures. Observation 3: For many problems, local minima with respect to one or several neighborhoods are relatively close to each other — local optima cluster in the search space. This last observation justifies searching in progressively larger neighborhoods around the current best.
The basic VNS algorithm alternates between a shaking phase (random perturbation in a neighborhood) and a local search phase (descent to the nearest local optimum):
def basic_vns(initial_solution, neighborhoods, local_search,
evaluate, max_time):
"""
neighborhoods: list of N_1, N_2, ..., N_kmax
(increasingly large/diverse)
local_search: any descent method (e.g., best-improvement)
"""
x = initial_solution
k_max = len(neighborhoods)
while not time_exceeded(max_time):
k = 0 # Start with the smallest neighborhood
while k < k_max:
# 1. SHAKING: pick a random solution from N_k(x)
x_prime = neighborhoods[k].random_neighbor(x)
# 2. LOCAL SEARCH: descend to a local optimum
x_double_prime = local_search(x_prime)
# 3. NEIGHBORHOOD CHANGE: accept or move to next
if evaluate(x_double_prime) < evaluate(x):
x = x_double_prime
k = 0 # Improvement found → restart from N_1
else:
k += 1 # No improvement → try larger neighborhood
return xThe logic is intuitive: start by shaking the solution gently (small neighborhood). If local search from the shaken solution finds an improvement, accept it and go back to gentle shaking. If not, shake harder (larger neighborhood). If all neighborhoods fail to improve, the current solution has survived increasingly aggressive perturbations and is likely of high quality.
The shaking step generates a random point in the k-th neighborhood of the current solution. For a TSP, typical neighborhoods might be:
N_1: Random 2-opt move (swap one pair of edges)N_2: Random double-bridge move (remove and reconnect four edges)N_3: Random segment reversal + insertion of a removed cityN_4: Random Or-opt move (relocate a segment of 1–3 cities)The neighborhoods should be ordered so that N_1 makes the smallest changes and N_kmax makes the most disruptive ones. This ensures the search intensifies before it diversifies.
VND is a deterministic variant that uses the neighborhood change idea purely for local search (no shaking). It cycles through neighborhoods, applying a descent method in each. When one neighborhood finds an improvement, it resets to the first:
def vnd(x, neighborhoods, evaluate):
k = 0
while k < len(neighborhoods):
x_prime = neighborhoods[k].best_improvement(x)
if evaluate(x_prime) < evaluate(x):
x = x_prime
k = 0 # Restart from first neighborhood
else:
k += 1
return xVND is often used as the local search subroutine inside BVNS, creating the General VNS (GVNS) variant — arguably the most commonly used version in practice.
General VNS (GVNS) uses VND as the local search step within basic VNS. This means the algorithm exploits two sets of neighborhood structures: one for shaking (perturbation/diversification) and one for descent (intensification). The shaking neighborhoods are typically large and applied randomly; the VND neighborhoods are smaller and searched systematically. This combination is powerful because VND finds high-quality local optima, and shaking escapes their basins of attraction.
The p-median problem — placing p facilities to minimize total customer-to-facility distance — is a classic VNS success story. Hansen and Mladenović (1997) showed that VNS with simple swap neighborhoods (move one facility) outperformed dedicated branch-and-bound codes on large instances. The same framework applies to clustering: k-means as a local search within a VNS that perturbs cluster centers achieves better solutions than repeated random restarts.
VNS is widely used for vehicle routing variants, often combined with tabu search or large neighborhood search. The VNS framework naturally accommodates the diverse neighborhood structures needed for routing: intra-route moves (2-opt, Or-opt) as small neighborhoods and inter-route moves (cross-exchange, relocate) as larger ones. Kytöjoki et al. (2007) demonstrated that a simple VNS matched specialized algorithms on CVRP benchmarks with minimal implementation effort.
Graph coloring, maximum clique, minimum vertex cover, and graph partitioning have all been tackled with VNS. The method is particularly effective when multiple natural neighborhood structures exist (e.g., for graph coloring: change one vertex’s color, swap colors of two vertices, recolor an entire connected component).
Industrial scheduling problems — job-shop, flow-shop, nurse rostering, timetabling — benefit from VNS because they naturally admit hierarchical neighborhoods: move one task (small), swap two tasks (medium), shift an entire block (large). VNS has been used in hospital nurse scheduling systems and university timetabling competitions (ITC 2007, 2019).
For mixed discrete-continuous hyperparameter spaces where Bayesian optimization struggles with high dimensionality, VNS offers an alternative. Define neighborhoods over individual hyperparameters (change learning rate by ±δ, swap optimizer type, add/remove a layer) and use validation accuracy as the objective. The neighborhood change mechanism naturally handles the heterogeneous parameter types.