Variable Neighbourhood Search, Live

The genetic algorithm kept a whole population, so one individual getting stuck didn't matter. Simulated annealing tolerated bad moves while it was hot, the ant colony let old trails evaporate, and the particle swarm carried enough momentum to sail over a dip before it noticed. This fifth one runs without a temperature schedule, a population, a pheromone trail, or a velocity. When it gets stuck, it changes what "nearby" means. This one hits home because, like many of the algorithms I am blogging about, I am making use of code I wrote years ago - but this one is special, because I used VNS for my first ever published research paper.

What does 'stuck' mean?

The playing field is the same Travelling Salesman Problem as the annealing post: a scatter of cities, and we want the shortest round trip that visits each city once.

Local search on the TSP is very simple: take any tour, try a small edit, keep the edit if the tour got shorter, repeat. The classic small edit is 2-opt: snip two edges, reconnect them the other way, which reverses a stretch of the tour and uncrosses one of those ugly X shapes. Do that greedily and a random tangle collapses into something pretty good, pretty quickly.

But, inevitably, it stops. You reach a tour where no single 2-opt move helps, a local optimum, and are unable to move. In the annealing post I treated that as a fact about the tour: it's stuck. What is stuck is the tour plus this particular definition of nearby.

A 2-opt local optimum only means that none of the roughly n² tours reachable by one segment reversal is shorter. Offer a different move, say lifting three consecutive cities out and reinserting them elsewhere (Or-opt), and the same tour suddenly has a completely different set of neighbours, some of which may well be better.

Mladenović and Hansen built this idea in 1997^[1], called it variable neighbourhood search, and it has been a fixture of the routing and scheduling literature ever since.

A local optimum is a property of the neighbourhood, not of the solution.

I'm gonna need a bigger hammer.

Basic VNS keeps a list of neighbourhood structures, ordered from smallest to largest, and climbs that list on an "as needed" basis. Here is one VNS setup:

• N1, 2-opt kick: reverse one random segment. The lightest nudge.
• N2, Or-opt: pull out a chain of one to three cities and reinsert it somewhere else.
• N3, segment exchange: swap two short segments of the tour with each other.
• N4, double bridge: cut the tour in four places and reassemble the quarters in a different order. A big kick. It changes four edges at once.

That is to say: descend with plain first-improvement 2-opt until you hit a local optimum. That's your incumbent, so set k to 1. Now: shake the incumbent with a random move from neighbourhood N_k, descend again with 2-opt from wherever that landed, and compare. If the re-descended tour beats the incumbent, move there and reset k to 1. If it doesn't, throw it away and increment k, up to k_max, then wrap back round.

This runs without a temperature, an acceptance probability, or a crossover operator. Hansen and Mladenović later distilled the design principles in a survey which is a great starting point ^[2].

This means the algorithm, by its very nature, will reach for a bigger hammer, as needed. The moment anything works, it drops straight back to the smallest hammer.

Watch it climb the ladder

Below, VNS is solving a seeded random TSP instance live, and the lit badge under the map is the neighbourhood currently in use. Watch it during a rough patch. N1 lights, fails. N2 lights, fails. N3 lights, and then an escape lands, and it snaps straight back to N1. The right-hand chart records that as a sawtooth: every tooth is the search getting stuck, escalating, and being rescued. Amber flashes on the map are the edges the latest shake or improvement just changed.

The Sliders

Tick "plain local search". This switches the shaking off entirely: descend with 2-opt, then stop, and the tour untangles, hits its first local optimum, and freezes there forever, while the k chart flatlines like in that medical drama my partner watches.

Set k max to 1. Now the search still shakes, but only ever with the smallest kick, a single random segment reversal. Watch the escapes counter crawl: a small kick barely leaves the current basin, so the 2-opt descent usually slides straight back into the tour it just left.

The gap stat twitches and recovers, twitches and recovers, going nowhere. It is all motion and no progress.

Now give it the full ladder, k max at 4, and watch the cost side. Every time N4 fires, the gap stat spikes hard, because a double bridge tears four edges out of a good tour, and the descent then spends a long run of moves stitching the damage back together.

That work is only worth it when nothing smaller can move the search, so VNS keeps the big hammer as a last resort.

Change what nearby means

I like the contrast with the earlier posts in this series: simulated annealing keeps one move type and varies when it will accept a worse solution. The genetic algorithm keeps a population, so the question of any one solution being stuck barely arises.

VNS, in its basic form, never accepts a worse solution at all, runs a single solution, and the only thing it varies is the move set. Three completely different answers to the same trap.

References

1. Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24(11), 1097–1100. https://doi.org/10.1016/S0305-0548(97)00031-2
2. Hansen, P., & Mladenović, N. (2001). Variable neighborhood search: Principles and applications. European Journal of Operational Research, 130(3), 449–467. https://doi.org/10.1016/S0377-2217(00)00100-4