Simulated Annealing — An Interactive Route Optimisation Simulator

What this simulation shows

Local improvement algorithms such as Two-Opt stop when every available move makes the route worse. Often that is not the best route — it is merely the best route in the immediate neighbourhood. Reaching something genuinely better may require a sequence of moves where the first one increases cost and the later ones more than repay it. A greedy search never gets there, because it refuses the first step.

Simulated Annealing, published by Kirkpatrick, Gelatt and Vecchi, borrows its logic from metallurgy. Cool metal too quickly and it locks into a brittle, badly ordered structure. Cool it slowly and the atoms have time to settle into a stronger arrangement. Applied to routing: allow the search to accept worse solutions readily at the start, then steadily reduce that tolerance until it behaves like an ordinary local search and settles.

The crucial parameter is temperature. High temperature means “accept almost anything and explore widely”. Low temperature means “only accept improvements and converge”. The cooling schedule decides how you travel between the two.

How to use it

Run it once on Balanced cooling and watch the two panels that matter: Worse moves attempted and Current search state. Early on, the search will visibly accept routes that are worse than the best one it has already found. That is the mechanism working, not a bug.

Then compare the extremes deliberately.

Fast cooling converges quickly and usually lands on a mediocre answer. The temperature drops before the search has had a chance to explore, so it commits to whichever region it happened to start in. This is the most common misconfiguration in practice, because fast looks efficient right up until you compare the output with a slower run.

Slow cooling explores far more and generally finds better routes, at the cost of time. In a real TMS that time is a hard product constraint: planners will not wait four minutes for a plan they need in twenty seconds, so the schedule is tuned against the operational clock rather than against solution quality alone.

Earl’s chaotic cooling is the instructive failure. Tolerance never really falls, so the search wanders indefinitely and never settles. It explores beautifully and commits to nothing.

Adjust Starting temperature alongside the schedule, and use Surprise Me to sample configurations you would not have chosen — some of the better outcomes come from combinations that look wrong on paper.

What to take away

Simulated Annealing trades determinism for reach. The same inputs can produce slightly different plans on different runs, which is a genuine product problem in transport: planners reasonably expect a stable answer, and “the algorithm is stochastic” is a poor explanation at 6am. Systems usually manage this by fixing the random seed, capping runtime, and always retaining the best solution found rather than the last one visited.

Back to Simulations