Earl is Tabu

By Richard Faint · 22 July 2026 · 6 min read

TL;DR:

Tabu Search uses short-term memory to mark recent moves as forbidden, preventing the optimiser from cycling back to the same solutions. That memory pushes the search into unexplored territory without relying entirely on random moves.

“You know what? I’ve already tried that.” — Earl Hickey

The title is a pun. The subject is Tabu Search, a route optimisation method that gives the optimiser a short-term memory of forbidden moves so it stops cycling through solutions it has already tried.

One of the reasons My Name Is Earl works so well is that Earl rarely solves a problem on his first attempt. His famous list gives him a direction, but every episode reminds us that simply trying harder is not the same as trying differently. Earl frequently discovers that an approach which seemed sensible at first has already failed, either because he overlooked something important or because he is repeating a mistake he made before. The breakthrough usually comes when he abandons the familiar path and forces himself to look somewhere new. Transport optimisation faces exactly this same challenge.

The Limits of Local Search

By the time a routing engine reaches the local improvement stage, it already has a feasible solution where vehicles are assigned, customers are allocated, and the routes satisfy operational constraints. Algorithms such as Two-Opt and Three-Opt then refine that solution by making thousands of small adjustments to reduce total distance or travel time. Eventually, however, those improvements stall: every move appears worse, even though a much better overall solution probably exists somewhere else.

In a previous article, we looked at Simulated Annealing, which escapes this trap by occasionally accepting worse solutions through controlled randomness. Tabu Search takes a fundamentally different approach as instead of relying on chance, it relies on memory, an idea that changes everything.

Why Local Search Gets Stuck

Imagine Earl trying to complete a list item by apologising to someone. They reject him, so he changes his wording slightly and tries again. When that fails, he returns the next day with almost exactly the same approach, expecting a different result until Randy points out the obvious: “You’ve already tried that.”

Local search algorithms often suffer from this exact behavior. A Two-Opt algorithm may swap two road segments to reduce distance, only to swap them right back on the next iteration because that reversal looks attractive from its current position. A few steps later, it reverses course again, cycling through variations of the same solution rather than discovering genuinely different ones. It ends up working hard without actually learning. Humans do this too with organisations routinely reviving old ideas while veterans quietly recognise history repeating itself. As Russell Ackoff famously observed, organisations are often very good at doing the wrong things efficiently. Tabu Search attempts to avoid precisely that trap by remembering where it has recently been.

Giving the Optimiser a Memory

The key innovation behind Tabu Search is simple, every time the algorithm performs a move, it records that move in a short-term memory called the Tabu List, making that specific move temporarily forbidden. If swapping customers A and B improved the solution in one iteration, the optimiser is blocked from immediately undoing that swap. Likewise, if Customer 17 was just moved from Vehicle 2 to Vehicle 3, they cannot be moved straight back. By enforcing these temporary restrictions, the optimiser is forced to investigate parts of the search space it would otherwise ignore.

In Earl’s world, this looks like writing notes underneath his list items: “Already tried apologising with flowers,” “Borrowing Randy’s idea didn’t work,” or “Don’t ask Joy for help.” Those ideas may eventually become worth trying again under different circumstances, but right now they simply waste time because Earl already knows where they lead. That list of notes is essentially a Tabu List. It is not a permanent ban, but rather a temporary reminder to stop repeating yesterday’s decisions long enough to discover something better.

Why This Works

At first glance, deliberately ignoring good moves sounds irrational. If reversing yesterday’s decision would slightly improve today’s route, a greedy optimiser would take it immediately. Tabu Search refuses, which sounds inefficient but by preventing immediate reversal, the search continues exploring different possibilities, often discovering an entirely new region of the search space where far greater improvements become possible.

This is a practical example of sacrificing short-term gains in pursuit of a better long-term outcome. Tabu Search embodies that philosophy mathematically by resisting attractive short-term reversals in favour of longer-term exploration.

Managing Memory: Tenure and Aspiration

However, what if a forbidden move genuinely becomes the best option later? Entries on the Tabu List are not permanent; they expire after a set duration known as the tabu tenure. Once that period ends, the move becomes available again. Choosing the right tenure is critical as if the list is too short, the algorithm quickly falls back into old habits, but if it is too long, the optimiser unnecessarily restricts itself and misses opportunities. Like many optimisation techniques, success depends on balancing exploration with exploitation.

One of the cleverest features of Tabu Search is that it knows when to ignore its own rules. Suppose a forbidden move would produce the best solution the algorithm has ever found; in that case, an aspiration criterion allows the optimiser to override the Tabu List and perform the move anyway. The memory guides the search without turning into rigid bureaucracy.

Tabu Search in Modern Routing Engines Although the underlying idea is straightforward, Tabu Search has became one of the most influential metaheuristics in operations research after Fred Glover introduced it in the 1980s. It has been successfully applied to vehicle routing, production scheduling, airline crew planning, telecommunications, warehouse optimisation, manufacturing sequencing, facility location, and timetabling. Its greatest strength is its deterministic ability to learn from recent history and push into new territory. However, that intelligence comes with configuration complexity: selecting the right tabu tenure, defining what constitutes a move, and deciding when aspiration should override memory all require careful engineering.

Modern transport engines rarely rely on any single technique. Instead, commercial routing engines combine several algorithms into a coordinated team:

• Constraint checking removes impossible solutions.

• Grouping creates sensible territories.

• Clarke-Wright rapidly constructs initial routes.

• Two-Opt and Three-Opt refine local details.

• Simulated Annealing occasionally accepts worse solutions to escape local traps.

• Tabu Search remembers recent moves to prevent repeating mistakes.

Each technique solves a specific weakness in the one before it, ensuring the engine explores efficiently without falling into repetitive traps.

Final Thoughts

Earl’s list was never simply about crossing items off a page; it was about becoming someone who learned from experience. Every completed task changed the way he approached the next one, and every failure made future success slightly more likely. Tabu Search operates on that exact same principle. Instead of pretending every iteration starts with a blank slate, it remembers the recent past, avoids revisiting unproductive decisions, encourages exploration of unfamiliar possibilities, and breaks its own rules when an exceptional opportunity appears.

Try it interactively. Open the Tabu Search simulator on its own page → — full-width, with a walkthrough of what each control does.

Back to Articles