Is changing the random seed enough?

No. In this example, every one-bit shake returns to 000; changing the available move size is what enables the illustrated escape.

Must the neighborhoods be nested?

No. Here, exactly one-bit and exactly two-bit changes are distinct sets.

Can the intermediate candidate be worse?

Yes. The demonstrated basic-VNS step improves the candidate locally before comparing the result with the incumbent.

AI Glossary / Graphs and symbolic AI / Advanced

Variable neighborhood search

Definition

Variable neighborhood search (VNS) is an optimization framework that changes the kinds or sizes of moves used to explore candidate solutions. It combines these changes with improvement procedures to escape solutions that are best only within a restricted neighborhood.

What it means

A neighborhood specifies which alternatives a search can reach through a particular move. A solution may resist every single change while benefiting from coordinated changes. VNS makes that distinction operational. For a manager, the useful question is whether an apparent improvement limit comes from the business problem or from the limited adjustments the software has tried.

How it works

In basic VNS, choose an incumbent, several neighborhoods, and a stopping rule. Randomly select a candidate from the current neighborhood, then improve it through local search. If the resulting solution beats the incumbent, accept it and restart with the first neighborhood. Otherwise, try the next neighborhood. The temporary perturbation is called shaking. Variable neighborhood descent changes neighborhoods during improvement; reduced VNS omits the local-search stage. A finite run generally provides no certificate of global optimality.

Three practical examples

A fictional delivery planner initially relocates one customer at a time. When that produces no benefit, it tries exchanging groups between routes. Every resulting route still needs checks for capacity and delivery windows; fewer kilometers alone would not justify an infeasible plan.
A fictional factory changes one job's position before testing coordinated exchanges across two machines. Its evaluator includes setup time, so two individually unattractive changes might become attractive together. The neighborhood describes permitted schedule changes, not geographical proximity.
A fictional retailer evaluates combinations of three replenishment options. Switching one option may create a costly mismatch with the other two. Exploring coordinated switches could reveal a cheaper configuration, provided the evaluator includes the interaction costs that caused the mismatch.

Think of it this way

Imagine rearranging a crowded shelf. Moving one box may not create useful space, but moving two boxes together can open a new arrangement. VNS changes the rearrangements it is willing to try. The analogy does not imply that every larger rearrangement helps: moving more boxes can consume time and still lead back to the same layout.

Worked example

Consider an invented minimization problem with three binary settings. All eight configurations are feasible. Their costs are: 000 costs 8; 001 costs 12; 010 costs 13; 100 costs 14; 011 costs 9; 101 costs 10; 110 costs 11; and 111 costs 1.
Define neighborhood N1 as flipping exactly one bit and N2 as flipping exactly two bits. Local search repeatedly takes the cheapest strictly improving one-bit neighbor.
Starting at 000, local search stops: its three neighbors cost 12, 13, and 14, all worse than 8. Suppose the first shake chooses 001 from N1. Its one-bit neighbors are 000, 011, and 101, costing 8, 9, and 10. Descent therefore returns to 000. There is no incumbent improvement, so the search advances to N2.
Suppose the next shake chooses 011, costing 9. Its one-bit neighbors are 001, 010, and 111, costing 12, 13, and 1. Descent reaches 111 and stops. VNS accepts cost 1 instead of 8, an improvement of 7 cost units, and resets the neighborhood index.
The temporary cost increase from 8 to 9 was part of exploration, not acceptance of a worse incumbent. Enumerating this tiny table proves that 1 is the global minimum. That separate enumeration, rather than the VNS acceptance rule, supplies the proof.

Illustrative case study

In a fictional planning workshop, a retailer uses the eight-configuration example to compare search logs. Its original optimizer reports that 000 cannot improve, because it tests only individual changes. A reviewer interprets this as a statement about those moves, not a statement about every possible plan.
The revised experiment records the shaken candidate, the result after local improvement, and the retained incumbent separately. This makes the 011 candidate's cost of 9 understandable: it led to 111, costing 1. Rejecting every temporary candidate above 8 before local search would eliminate that route in this experiment.
The team also checks all possible shakes. Each one-bit shake descends back to 000, whereas each two-bit shake descends to 111 under the stated rule. This is a property of the invented table, not evidence that two-bit moves always outperform single-bit moves in retail planning.

Common misconceptions and mistakes

A local optimum is relative to the permitted moves. In the example, 000 is locally optimal under one-bit changes but globally inferior.
A shaken candidate and an accepted incumbent serve different roles; reporting their costs without labels can make a valid search trace look inconsistent.
Larger neighborhoods are not automatically better investments. The relevant comparison includes evaluation time and feasibility checks.
One successful run does not establish reliability across other starting points, instances, or time budgets. The example's exhaustive verification is practical only because there are eight configurations.

Business use

For an internal trial, keep the objective and feasibility rules identical across competing methods. Compare achieved cost at equal computing budgets, retain the original feasible plan as a fallback, and record variability over repeated runs when randomness matters. Report an optimality gap only when a justified bound or known optimum exists. In the toy example, the complete table provides that reference; a large production schedule usually requires separate evidence.

Check your understanding

Why does ordinary one-bit descent stop at 000?

Answer: All three immediate neighbors cost more than 8.

What follows the shake to 101?

Answer: Local search selects its neighbor 111, whose cost is 1.

What proves global optimality here?

Answer: Inspection of all eight stated costs, not the fact that the search stopped improving.

Related terms

Local search
Objective function
neighborhood structure
local optimum
metaheuristic
variable neighborhood descent
perturbation
feasibility
optimization benchmark

Learn next

Reproduce the eight-state trace, then change the cost of 111 from 1 to 15. Recompute the local-search paths before predicting whether the same two neighborhoods can improve 000. This separates an algorithm's rules from the particular landscape that made the original demonstration successful.

Local search

Sources

Hansen and Mladenovic, Variable Neighborhood Search, author tutorial, especially Sections 8.3–8.5: https://www.cs.uleth.ca/~benkoczi/OR/read/vns-tutorial.pdf The binary cost table, business scenarios, and enumerated search traces are original illustrations, not reported empirical results from the tutorial.

Previous: Variable-length encoding Next: Variable-order Bayesian network