Q-Logos
Simulated Annealing for Route Optimization: How a Stop Order Is Found, and Why Two Runs Can Differ
A plain-language walk through simulated annealing for ordering stops: segment reversals, accepting worse orders early, cooling down, and why the result is a heuristic rather than a proof. With the Q-Logos route planner as the worked example.
The problem simulated annealing is solving
You have a list of stops and you want an order to visit them in so the whole trip is short. For a handful of stops you can check every order. As the list grows, the number of possible orders multiplies with every stop you add, and checking them all stops being practical. Exact methods exist for this problem, but they slow down quickly, so most planners you can reach from a browser use a heuristic: a procedure that finds a good order fast without proving it is the shortest.
Simulated annealing is one of those heuristics. The name comes from metalwork, where a metal is heated and then cooled slowly so its structure can settle into a low-energy arrangement. The routing version borrows the picture: a hot, restless search early on, and a calm, settling search at the end.
If you want the broader context first, the page on how a multi-stop route planner works covers the problem, the common heuristics and the two questions to ask of any planner. This page goes deeper into one of those heuristics.
The move: reverse a stretch of the route
Every heuristic needs a way to turn one order into a slightly different one. The move simulated annealing uses here is a segment reversal. Pick two positions in the current order and reverse everything between them. On a map, this often untangles a place where the route crosses over itself, because the two legs that crossed get replaced by two legs that do not.
Reversing a segment changes only two legs of the route: the leg entering the segment and the leg leaving it. Everything inside the segment is driven in the opposite direction, but the distances inside it add up to the same total. That makes each proposed change cheap to evaluate: you only need to compare two old legs against two new ones.
This is the same move that the 2-opt method uses. The difference between the two methods is what happens when the proposed change makes the route longer.
Accepting a worse order, on purpose
Here is the rule in plain words:
- If the change shortens the route, accept it. Always.
- If the change lengthens the route, sometimes accept it anyway. The chance of accepting shrinks with two things: how much longer the route would get, and how far the search has cooled.
Why accept a worse order at all? Because a method that only ever accepts improvements can get stuck. Picture an order where no single segment reversal shortens the route, but a different order a few moves away is clearly shorter. To reach it, the search has to pass through orders that are temporarily worse. A strict improve-only rule refuses to take that step. Simulated annealing takes it sometimes, and more willingly at the start when it knows little about the landscape.
Cooling down
The willingness to accept worse moves is controlled by a number usually called the temperature. It starts high, so early on even a noticeably longer route has a fair chance of being accepted and the search roams widely. After every step the temperature is multiplied by a factor just under one, so it drifts down. As it falls, the search becomes pickier: small worsenings are still occasionally taken, large ones almost never, and eventually the procedure behaves like a plain improve-only search and settles.
Throughout, the procedure remembers the shortest order it has seen so far. When the step budget runs out, that remembered order is the answer, not necessarily the order the search happened to be sitting on at the end.
Three settings shape a run: the starting temperature, how quickly it cools, and how many steps to take. Hotter, slower, longer runs explore more and cost more computing; cooler, faster, shorter runs finish sooner and settle sooner. There is no setting that is right for every stop list.
Why it is a heuristic, and why runs differ
Two consequences follow from the description above, and both matter when you read a planner's output.
No proof of the shortest order. Simulated annealing never enumerates all orders and never produces a bound on how far its answer is from the shortest. The order it returns may be the shortest possible one, or close, or not; the method itself cannot tell you which. A planner that reports an "optimal" route from simulated annealing is overstating what the method delivers.
Different runs can return different orders. Two choices in every step are random: which segment to reverse, and whether to accept a worse order. Unless the random source is deliberately fixed, two runs on identical stops can take different paths through the search and finish on different orders. Neither is wrong. They are two samples from the same procedure. This is also why a planner that shows more than one ordering from one request is not contradicting itself.
Both points are reasons to prefer a planner that tells you what method it uses and what it compares against, over one that shows a single route with no explanation.
A worked example: how the Q-Logos planner uses it
The Q-Logos web route planner is a useful example because it discloses its own method on the results page. Here is what the current live version does, and nothing beyond it.
The engine is classical simulated annealing. When you press the optimize button, your stops are posted to the Q-Logos server, which orders them with simulated annealing of the kind described above: the search starts from the order you entered, your first stop stays first, the proposed moves are segment reversals among the later stops, shorter orders are always accepted, longer ones are accepted with a probability that falls as the run cools, and the shortest order seen is returned. The backend's own documentation labels the approach quantum-inspired; in plain terms it is a classical heuristic running on ordinary servers, with no quantum hardware and no quantum circuit involved. The pricing page describes the engine the same way. The server does not report how many steps it took, so the web page does not show a step count.
The distance being minimized is straight-line. The table of distances the search works on is the straight-line (haversine) distance between every pair of stops, and each route card labels its distance as straight-line rather than road distance. Durations are derived from that same model, so they are estimates, not measured drive times. In the current version you can also pick a traffic level, and the planner may apply the current weather at your first stop. These scale the estimated minutes by a fixed planning rule chosen for the product, not a model fitted to live traffic or weather measurements; there is no traffic feed behind it, the traffic value is your own choice. With a single route-wide setting the stop order itself does not change, only the times do.
Three independent runs, and the note that says so. Each request returns three orderings, drawn on the map and shown as three cards. The cards carry different labels, but the server also sends a note that the page prints under the results: the three routes are three independent simulated-annealing runs of the same distance objective, with small uniform scalings of that objective, and they differ by run rather than by a different goal. That is the behaviour this page has been describing, visible in the product: run the search three times and you may get three orders.
The baseline is nearest-neighbour improved by 2-opt. Any "saved" figure on a card is measured against a baseline, and the page prints the server's definition of it: a nearest-neighbour order starting from your first stop, improved by 2-opt until no reversal shortens it, on the same distance table. It is not the order you typed. This matters because comparing against the typed order would make almost any heuristic look impressive; comparing against an already-improved order is a fairer test. Even so, the saved figures are modelled differences on straight-line distance, not measured savings.
If you hold your stops in a spreadsheet, the page on the CSV import path explains what the planner reads and what it skips.
What this method does not do for you
Simulated annealing orders stops. It does not, on its own, know about road networks, one-way streets, delivery time windows, vehicle capacity, or how many vehicles you have. A planner built on it can add those things only by changing what the distance table contains or by adding constraints to the search; the plain method described here has neither. The Q-Logos route optimizer does not model road networks, turn-by-turn directions, time windows, vehicle capacity or more than one vehicle, and the traffic and weather settings described above adjust estimated times by a fixed rule rather than consulting live data.
How to read a simulated-annealing result
- Treat the order as a good candidate, not a proven shortest route.
- If you get more than one ordering, treat them as options to compare, not a ranking.
- Check what distance the search minimized. Straight-line ordering is a reasonable first pass in a dense grid and can mislead across water or limited-access roads.
- Check what the saved figure is compared against, and whether that baseline was itself a reasonable route.
- Expect a rerun to differ slightly. If it differs a lot, the stop list probably has several orders of similar length, which is useful to know.
Plans differ in how many routes you can run per day and how many stops a route can hold; the limits are on the pricing page. To see the method notes on your own stop list, create a free account and run the planner twice.
Create a free Q-Logos account, run the same stops twice, and compare the three orderings and the method notes printed under each result.
Get started