My Name Is Earl and Large Neighbourhood Search: Sometimes You Have to Break the Plan

By Richard Faint · 7 August 2026 · 6 min read

TL;DR:

Large Neighbourhood Search escapes local traps by destroying part of a workable route and repairing it in a new way. Rebuilding several related decisions at once can reveal improvements that Two-Opt-style small moves cannot reach.

Earl Hickey had a problem. His list was working, but as anyone who has watched My Name Is Earl knows, working through the list rarely means following a neat sequence from one item to the next. Earl begins with what looks like a straightforward objective: identify the bad things he has done, put them right, and allow karma to take care of the rest. In practice, every attempt to repair one problem creates new constraints, exposes forgotten dependencies or drags another person into the situation. That is why the show makes such a good analogy for Large Neighbourhood Search, an optimisation method built around the idea that sometimes the best way to improve a reasonable solution is not to make another tiny adjustment, but to deliberately break part of it and rebuild it differently.

By the end of the first episode, Earl has already learned that distinction between having a plan and being in control of it. When he tries to avoid helping Kenny because the situation has become uncomfortable, events push him back towards the list and he concludes that, although he may have written it, “Karma makes the rules.” That is not a bad description of optimisation in the real world. We can define an objective function, construct a route plan and calculate what appears to be a good solution, but customers, geography, capacity, time windows and operational constraints ultimately determine what is possible.

Imagine a distribution operation based around Wakefield, serving Leeds, Bradford, Halifax, Huddersfield, York and Barnsley. An optimiser has already produced a respectable set of routes: one vehicle heads west towards Huddersfield and Halifax, another covers Leeds and Bradford, and a third works east towards York. The plan is not obviously poor, and conventional local search might improve it further by swapping two stops, reversing part of a route or transferring a customer between vehicles. The problem is that good solutions can become traps. Halifax might actually fit better with Bradford, but moving one Halifax delivery on its own increases mileage; shifting several related deliveries together, however, might allow two routes to reorganise into something substantially better. A local search method can struggle because it has to move through an apparently worse solution before it can reach the better one.

Large Neighbourhood Search takes a different approach. Rather than protecting the existing plan, it deliberately removes part of it and then repairs the damage. A set of deliveries is taken out of the current solution, leaving gaps in several routes, and those jobs are then inserted again according to some repair strategy. The process can be summarised as destroy, repair, evaluate and repeat, but the important point is what this does to the search space. Instead of asking whether Halifax and Huddersfield should swap places, the algorithm can temporarily forget where ten deliveries belonged at all and reconsider the structure of the routes from a much wider perspective.

Earl does something remarkably similar throughout the series, although usually without intending to. In “Faked My Own Death”, he is working on one list item when he unexpectedly encounters Natalie, the woman he once pretended to be dead to escape from. What was a reasonably ordered sequence of jobs suddenly has another unresolved item inserted into the middle of it. Earl’s current plan has effectively been disrupted and part of his life has to be reorganised around a problem he thought was safely in the past. The episode also contains the observation that “Sometimes Randy takes a long road to a simple thought,” which is unintentionally a decent description of heuristic optimisation. The path towards a good solution is not necessarily direct, and algorithms often need to explore arrangements that initially appear less sensible before they discover something better.

The same pattern appears in “Stole P’s HD Cart.” Earl returns a hot-dog cart that he and Ralph stole years earlier and, for a moment, the problem appears solved. Ralph then burns the cart, turning a completed repair into a new and more complicated problem involving Randy, Joy, Catalina and Darnell. From an optimisation perspective, the interesting part is not the absurdity of the plot but the dependency it reveals: changing one part of a system alters the conditions around everything else. Real transport planning behaves in exactly the same way. Moving a delivery from one vehicle may free capacity that allows another route to change, which may remove an overtime violation, which may then make an entirely different allocation attractive.

The cleverness of Large Neighbourhood Search lies in deciding which part of the solution to destroy. Removing ten deliveries at random is possible, but a better destroy operator might identify geographically related stops around Halifax and Bradford, jobs consuming unusually high vehicle capacity, deliveries with difficult time windows or customers responsible for expensive detours. Suppose the optimiser removes several jobs around Halifax, Sowerby Bridge, Brighouse and Huddersfield at the same time. When the repair phase begins, the algorithm may discover that one vehicle can approach Halifax from Bradford, another can take Brighouse while travelling along the M62, while the remaining Huddersfield deliveries form a much tighter local route. None of those changes may have looked attractive individually, yet collectively they produce a better plan because the algorithm was willing to dismantle part of the existing structure first.

Adaptive Large Neighbourhood Search, or ALNS, pushes the idea further by giving the optimiser several ways to destroy and repair a solution and then learning which ones appear to work best. It might alternate between random removal, worst-job removal, geographical clustering and route-sequence removal, while using cheapest insertion, regret-2 or regret-3 to rebuild the plan. Strategies that repeatedly produce better solutions are given a higher probability of being selected again, which means the algorithm is doing something more interesting than simply searching for a route: it is adapting the way it searches according to what it discovers about the problem.

That idea also fits “Randy’s Touchdown,” where Earl attempts to correct the fact that he prevented Randy from scoring a touchdown at school. Earl begins with a very specific view of what putting things right should look like, but the situation becomes entangled with his impounded car and lottery money, and Randy ultimately gives up his own opportunity to help Earl instead. When Earl worries that the whole attempt has gone wrong, Randy explains that helping his brother gave him the same feeling Earl had been trying to recreate for him. The solution Earl expected was not the solution that ultimately worked, because the problem itself was broader than he initially understood.

That is probably the most useful lesson from Large Neighbourhood Search. Optimisation is often presented as a process of gradually polishing a solution until no more improvement can be found, but some problems resist that kind of cautious progress. A transport plan can be locally excellent while still being globally mediocre because its underlying structure prevents the optimiser from reaching better alternatives. In those situations, the answer may be to stop protecting the plan, remove a meaningful part of it and allow the system to reorganise itself.

Earl spends four seasons doing much the same thing to his life. He tries to repair one item, discovers that it is connected to three others, and ends up rebuilding far more than he originally intended.

Large Neighbourhood Search simply gives the process a name.

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

Back to Articles