🚚 Delivery Route Optimizer — Simulated Annealing Live

Simulated annealing is a probabilistic optimization technique inspired by the metallurgical process of heating a metal and slowly cooling it so its atoms settle into a low-energy crystalline structure. Applied to the traveling salesman / vehicle routing problem, the "energy" is the total tour distance. At high temperature the algorithm accepts many worsening moves, letting it explore widely and jump out of poor local arrangements; as temperature falls it becomes increasingly greedy, refining the tour until it converges near a short route. It is popular for routing because the search space of possible stop orderings is factorial in size, far too large to search exhaustively, yet 2-opt neighbourhoods combined with annealing reliably find tours within a few percent of optimal.

A 2-opt move removes two edges from the tour and reconnects the four endpoints the only other way that keeps a single closed loop, which is equivalent to reversing the order of the stops between the two cut points. It is the simplest local-search move that can uncross a tour: whenever two route segments cross on the map, exactly one 2-opt move straightens them out and shortens the total distance. Because only two edges change, the change in tour length (the delta) can be computed by comparing just those two old and two new edge lengths, without re-summing the entire route.

After a candidate move's cost delta is computed, the algorithm always accepts moves that shorten the tour (Δ < 0). For moves that lengthen it, it accepts with probability e^(−Δ/T), where T is the current temperature. This means a large worsening move is rarely accepted, but small worsening moves are still fairly likely early on when T is high. As T decays toward zero, e^(−Δ/T) collapses toward zero for any positive Δ, so the algorithm effectively becomes pure greedy descent — hill-climbing is disallowed and only improving moves survive.

This simulation uses geometric cooling: T is multiplied by a cooling rate α (close to but below 1) after every proposed move, so T decays exponentially with iteration count. A cooling rate very close to 1 (e.g. 0.9995) cools slowly, giving the search many iterations at higher temperatures to explore broadly before it commits to refining a solution — this typically finds shorter tours but takes longer to settle. A lower cooling rate (e.g. 0.985) cools fast and behaves almost like greedy 2-opt local search, converging quickly but more likely to get stuck in a mediocre local minimum.

That is the entire point of annealing: at high temperature the Metropolis criterion deliberately accepts some length-increasing moves. A tour can look locally optimal (no single 2-opt move improves it) while still being far from the shortest possible tour — this is a local minimum. By occasionally accepting a worse move, the search can climb out of that local minimum's basin and later fall into a different, shorter one. Watching the distance chart, you'll typically see it fall quickly at first, occasionally spike upward while T is still high, and then settle into a smooth monotonic decline as T approaches zero.

Real logistics companies solve vehicle routing problems (VRPs) with hundreds or thousands of stops, multiple vehicles, time windows and capacity limits — an NP-hard combinatorial problem where exact solutions are computationally infeasible past a few dozen stops. Metaheuristics like simulated annealing, along with genetic algorithms, ant colony optimization, and tabu search, are industry-standard tools for finding very good (though not provably optimal) routes in seconds to minutes. This simulation models the single-vehicle core of that problem — the classic traveling salesman problem — which is the same combinatorial engine at the heart of production routing software.