Tabu Search — An Interactive Route Optimisation Simulator

What this simulation shows

Simulated Annealing escapes a local optimum using controlled randomness. Tabu Search, developed by Fred Glover, escapes it using memory instead — and the difference in behaviour is larger than it sounds.

The failure it fixes is cycling. A local search swaps two customers because that improves the route. On the next iteration, from its new position, swapping them back also looks like an improvement. So it does. A few steps later it swaps them again. The search is busy, the cost graph twitches, and no progress is being made: it is working hard without learning anything.

Tabu Search records every move it makes in a short-term memory called the tabu list, and while a move sits on that list it is forbidden. The optimiser cannot immediately undo what it just did, so it is forced to evaluate moves it would otherwise have skipped — including ones that temporarily make the route worse.

This simulator runs both strategies over the same Camden County route so you can watch the difference directly.

How to use it

Select Greedy local search first and press Run search. Watch the Candidate moves panel and the route on the map. Fairly quickly you will see the same pair of moves alternating, the distance oscillating between two values, and the search achieving nothing further.

Now switch to Tabu Search and run it again. The Tabu memory panel fills with recently forbidden moves, and the Search diary records why each step was taken or rejected. The route continues to change after the point where greedy search had stalled.

Use Take one step to inspect the mechanism properly. On individual steps you will see the optimiser choose a move that makes the route worse, because every better move is currently tabu. That is the whole trick — the memory converts a dead end into forced exploration.

Tabu tenure is the parameter that matters. Too short and cycling returns, because moves become legal again before the search has left the neighbourhood. Too long and the search is over-constrained, prohibited from good moves for no reason and wandering aimlessly.

What to take away

For operational software, Tabu Search has a significant practical advantage over Simulated Annealing: it is deterministic. The same inputs produce the same plan every time, and the search diary explains each decision. When a planner asks why the system chose this route, “because the alternative was recently tried and rejected” is an answer a human can audit. “Because a random number was below a threshold” is not.

Russell Ackoff’s warning applies to optimisers as much as organisations — it is entirely possible to do the wrong thing very efficiently. Memory is how this algorithm notices.

Back to Simulations