Earl is steel

By Richard Faint · 19 July 2026 · 15 min read

TL;DR:

Simulated Annealing sometimes accepts a worse route so that the search can escape a local minimum and reach a better region of the solution space. As the temperature cools, those disruptive moves become less likely and the search settles on a final solution.

“I’m just trying to be a better person.” — Earl Hickey

Earl Learns to Make Things Worse Before They Get Better: Simulated Annealing

The title is a pun about metal. The subject is Simulated Annealing, a route optimisation method that deliberately accepts a worse route for a while so the search can escape a local minimum and reach a genuinely better one.

In the previous article, Earl and Randy discovered how Two Opt and Three Opt can improve a route by removing poor connections and rebuilding the sequence in a more efficient order. These methods are effective because they repeatedly test changes and keep the ones that reduce the total route cost. However, they do not always find the best possible route. Problems arise when every available change appears to make the current route worse. A conventional improvement algorithm will then stop, even though a much better solution may exist elsewhere in the search space.

This creates an important question for any routing engine. Should it protect the best route it has found, or should it deliberately accept a worse route in the hope of reaching something better? That question sits at the heart of Simulated Annealing, a metaheuristic based on the idea that optimisation does not always progress through a continuous series of improvements. Sometimes the search must move away from a good solution before it can find a great one.

Earl understands this problem better than most people. His List gives him a clear direction, but it rarely gives him a direct route. Every attempt to repair the past reveals consequences, relationships and dependencies that were not obvious when the item was first written down. Simulated Annealing gives a routing engine similar freedom. It allows the search to continue when the obvious improvements have run out, while still controlling how much deterioration it will accept and how long that behaviour will continue.

The problem with a route that looks finished

Imagine that Earl and Randy have been given a delivery route around Camden County. The route begins at the motel, visits a collection of customers and returns after the final stop. Clarke Wright Savings has created the initial plan, Two Opt has removed the worst crossings, and Three Opt has tested several larger changes. The result looks sensible on the map and is much better than the first version.

The routing engine now tests another set of possible changes, but every one of them increases the total cost. A straightforward local search would stop at this point and declare that it has found the best answer available. However, the route may only be the best solution within its immediate neighbourhood. It may still be far from the best solution across the full search space.

A much cheaper route could exist, but reaching it may require several connected moves. The first move might increase the cost, while the second and third moves produce a much larger improvement. A greedy search will never reach those later moves because it refuses to accept the first deterioration. It becomes trapped in what optimisation theory calls a local minimum.

A local minimum is a solution that is better than every nearby alternative but still worse than solutions elsewhere. Kirkpatrick, Gelatt and Vecchi developed Simulated Annealing as a practical way to deal with this problem in difficult combinatorial optimisation tasks. Their method allows the search to escape from a local minimum without turning the process into uncontrolled random movement.

A useful way to picture the problem is to imagine Earl standing at the bottom of a shallow valley. Every step around him leads uphill, so he concludes that he has reached the lowest point in the whole of Camden County. However, a much deeper valley may exist beyond the next ridge. Earl will never reach it if he follows a rule that says every individual step must take him downhill.

Two Opt and Three Opt are very good at walking downhill because they repeatedly choose changes that reduce the route cost. Simulated Annealing becomes useful when progress requires the search to climb for a while before it can descend into a better valley.

Earl already understands temporary deterioration

Earl often begins an item on his List with a simple idea of what making amends will involve. He expects to return something, apologise to someone or undo a specific piece of damage. Once he starts, however, he usually discovers that the harm is wider than he first understood. The obvious solution may repair one part of the problem while making another part more complicated.

This happens when Earl returns the hot dog cart that he and Ralph stole. He expects the return of the cart to repair the harm, but Pops has already lost his customers and Ralph later burns the cart. Earl is forced to abandon the neat solution he originally imagined and follow a much less direct route towards making things right. The situation becomes worse before a satisfactory outcome becomes possible.

The same pattern appears in “Stole a Badge”. Earl initially believes that returning the stolen police badge will settle the item. He then discovers that the theft caused the officer to be demoted, which means the real damage is not simply the missing object. Earl has to continue beyond the first apparently correct action and accept further disruption while trying to restore the officer’s position.

Simulated Annealing does not possess Earl’s moral reasoning, but it follows a comparable search principle. It distinguishes between a move that is immediately worse and a move that is permanently useless. A temporary increase in route cost may still be valuable if it changes the structure of the plan, creates new connections between customers and opens a part of the search space that could not otherwise be reached.

Why it is called annealing

The name comes from the physical process of annealing. A material is heated so that its particles can move more freely, and it is then cooled gradually so that those particles settle into a stable structure. Simulated Annealing applies the same general idea to an optimisation problem.

The temperature inside the algorithm is not a physical temperature. It is a parameter that controls how willing the search is to accept a worse solution. When the temperature is high, the algorithm behaves more adventurously and may accept a noticeable increase in cost. As the temperature falls, the algorithm becomes more conservative and is increasingly likely to reject moves that do not improve the current plan.

The cooling schedule therefore changes the character of the search over time. Early in the process, the algorithm explores widely and tests alternative route structures. Later, it becomes more selective and concentrates on refining the strongest regions it has discovered.

This changing behaviour matters because a routing engine needs different capabilities at different stages of its run. Early in the process, it should be willing to break connections that currently look reasonable, move customers into different combinations and test plans that may initially appear inefficient. The purpose is not to perfect the first route but to discover whether better regions exist elsewhere.

Once the algorithm has explored widely and the temperature has fallen, it should become more demanding. At that stage, it behaves more like a conventional improvement process and focuses on smaller changes around the best solutions it has found. High temperature supports exploration, while low temperature supports refinement.

How the routing search works

A Simulated Annealing search begins with a feasible route. The engine then creates a neighbouring solution by changing the current plan. It might reverse part of a route, relocate a customer, exchange two stops, transfer a group of deliveries between vehicles or change the order in which a cluster is served.

The new route is evaluated using the objective function. When the candidate produces a better score, the engine accepts it immediately. This part of the process is similar to an ordinary local search because an improvement should normally be kept.

The important difference appears when the candidate is worse. Simulated Annealing does not reject it automatically. Instead, the algorithm calculates an acceptance probability based on two factors: the size of the deterioration and the current temperature.

A small deterioration is more likely to be accepted than a large one. Timing also matters because the same deterioration is more likely to be accepted early in the search, when the temperature is high, than later, when the temperature has fallen. This produces controlled uncertainty rather than random movement. The objective function still guides the search, but the algorithm retains enough flexibility to escape from a local minimum.

Suppose the current delivery route covers 300 miles and a proposed customer relocation increases the distance to 320 miles. A greedy algorithm rejects the move because the route is now worse. Simulated Annealing may accept it while the temperature is high because the relocation changes which customers sit beside one another.

The next move could then reduce the route from 320 miles to 280 miles. In that case, the increase to 320 miles was not the destination. It was a bridge that allowed the search to reach a better region. The algorithm accepted a temporary deterioration because it created new opportunities for improvement.

The engine must also keep a separate record of the best solution found during the entire run. The current solution may become worse by design, so it cannot be treated as the final answer. By storing the best route separately, the engine can take controlled risks without losing the strongest plan it has already discovered. Earl may wander into a worse situation while repairing an item, but the routing engine keeps a copy of its best plan in its pocket.

Cooling without freezing too early

The most important design question is not whether Simulated Annealing should accept worse moves. That is the defining feature of the method. The real question is how often those moves should be accepted and how quickly that willingness should disappear.

When the initial temperature is too low, the algorithm behaves almost like an ordinary local search. It rejects most deteriorations and becomes trapped in the same local minimum that Simulated Annealing was meant to escape. When the temperature is too high, the algorithm may accept too many poor solutions and wander through the search space without learning enough from the objective function.

The cooling rate creates a similar balance. Cooling too quickly makes the search cautious before it has explored enough alternatives. Cooling too slowly can waste a large amount of computation on routes that are unlikely to provide useful information.

A common implementation reduces the temperature by multiplying it by a cooling factor after a defined number of moves. However, there is no universal setting that works for every routing problem. The schedule must reflect the scale of the objective values, the number of customers, the available neighbourhood moves and the amount of runtime the business is willing to provide.

The temperature therefore controls how much uncertainty the engine will tolerate, how long it remains exploratory and when it begins to behave like a conventional improvement process. This is partly an algorithmic decision, but it is also a product decision. The business must decide how much computing time it is prepared to spend in exchange for the possibility of a better plan.

A transport operator producing thousands of routes overnight may accept a longer search if a one per cent improvement creates a significant reduction in annual mileage. A planner who needs an answer within seconds may prefer a faster cooling schedule and accept that some opportunities will remain unexplored. The correct configuration depends on the operational context rather than the algorithm alone.

The moves still determine where the search can go

Simulated Annealing cannot discover useful routes if the available moves are poorly chosen. The algorithm can only travel through the search space using the neighbourhood operators it has been given. If every move changes one small part of one route, the search may struggle to reach plans with a completely different structure.

A strong routing implementation therefore combines several types of move. The engine might reverse a sequence, relocate a customer, exchange two stops, move a route segment or transfer work between vehicles. Some operators make small adjustments, while others create much larger structural changes.

This is where the relationship with Two Opt and Three Opt becomes important. Simulated Annealing does not necessarily replace those methods. Instead, it changes the rules under which their moves are accepted.

A Two Opt move that would be rejected by a greedy improvement process may be accepted by Simulated Annealing when the temperature is high enough. The route is changed in the same way, but the acceptance policy is different. Two Opt defines how the route can be changed, while Simulated Annealing decides whether a worse version may be kept.

A practical routing engine will often vary how frequently it selects each operator. Customer relocation may be cheap to evaluate and useful for small improvements, so the engine can test it regularly. A large exchange between routes may require more computation, but it could provide a better chance of escaping from a stubborn local minimum.

The quality of the final result depends on the interaction between the neighbourhood operators, the acceptance rule and the cooling schedule. A powerful acceptance policy cannot compensate for moves that never reach useful parts of the search space. In the same way, excellent neighbourhood moves will achieve little if the algorithm refuses every temporary deterioration.

Worse does not mean impossible

Allowing a worse solution does not mean abandoning operational constraints. A candidate route may add mileage, increase driver time or produce a less balanced workload while still remaining feasible. Those are examples of deterioration that the algorithm may be allowed to accept.

A plan that exceeds vehicle capacity, breaks a mandatory time window, assigns a customer to an incompatible depot or sends a vehicle along an inaccessible road is different. Those plans may be operationally impossible rather than merely expensive.

The simplest approach is to generate only feasible neighbours. Every candidate must satisfy the hard constraints before the objective function is evaluated. This keeps the search inside the set of plans that could actually be operated.

Another approach allows temporary infeasibility but adds substantial penalties to the score. This can help the search move between separate feasible regions when the problem is highly constrained. However, it requires careful design because the algorithm must not become comfortable inside plans that could never be executed.

The distinction between hard and soft constraints therefore remains essential. A high temperature may justify accepting more mileage or a less balanced workload, but it should not automatically grant permission to ignore physical, contractual or legal rules.

The objective function must also represent the real business problem rather than simply the shortest distance. A route that adds three miles but removes a serious lateness risk may be better overall. A shorter route that overloads a vehicle or creates an unacceptable service failure is not a genuine improvement.

Simulated Annealing can only explore the landscape created by the costs and constraints it receives. When the model is poorly designed, the algorithm may search very efficiently for the wrong answer. The intelligence of the search cannot repair an objective function that does not reflect the operation.

Where it sits in a modern routing engine

Modern routing engines rarely rely on one method from beginning to end. Creating an initial solution, checking feasibility, improving local sequences and escaping from local minima are different problems. Each stage may require a different technique.

A typical process begins by creating an initial solution with Clarke Wright Savings, an insertion method or another construction heuristic. It then applies local improvements such as Two Opt, Three Opt and customer relocation. When those methods stop producing progress, the engine introduces a metaheuristic such as Simulated Annealing to explore beyond the current neighbourhood.

Once a promising region has been found, the engine can return to more conservative improvement methods and refine the strongest solution. Simulated Annealing therefore sits between construction and final refinement. Its role is to prevent the search from treating the first good solution as though it must also be the best one.

Other metaheuristics can perform a similar role, including Tabu Search, Genetic Algorithms and Large Neighbourhood Search. Each uses a different mechanism to explore the solution space. Simulated Annealing is distinctive because it allows worse moves according to a probability that falls as the temperature cools.

Making things worse with a reason

Two Opt and Three Opt teach a routing engine how to improve a plan through direct local changes. Simulated Annealing teaches it how to continue when those direct improvements are no longer available. The central insight is that optimisation does not always follow a smooth path towards a better answer.

Some solution spaces contain ridges that must be crossed before a deeper valley can be reached. An algorithm that refuses every uphill step may stop too early, not because it has found the best route, but because it has found a route that cannot be improved through one immediate move.

Earl succeeds when he stops treating every setback as proof that the List is failing. Repairing a complicated situation may expose more damage, consume more resources and create more disruption before the real problem becomes clear. The temporary deterioration is not always evidence of failure. Sometimes it is part of the route towards a better outcome.

Simulated Annealing formalises the same uncomfortable principle. It permits the search to deteriorate in a controlled and gradually diminishing way, while preserving the best route already discovered. Early in the process, the algorithm is willing to take risks. Later, it becomes increasingly cautious and focuses on refinement.

The result is neither random chaos nor blind optimism. Worse moves are accepted according to a defined probability, the appetite for risk falls as the temperature cools, and the engine ultimately returns the best plan it found during the search.

Earl might describe the process as trusting karma, while an optimisation engineer would describe it as escaping a local minimum. Both are expressing the same underlying idea: sometimes the route to a better place begins with a step that appears to take you further away.

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

Back to Articles