Errand Route Optimizer, Explained
Read this and you will know how to order a list of stops so your total travel is as short as possible, why the tool can prove the answer for small lists but only estimate it for large ones, and how to trust the result before you drive.
What the tool does
Give the tool a start point and a handful of stops. It returns the order that makes your total trip shortest. That is the travelling salesman problem (TSP): visit every point once and keep the distance down.
Here is the hook. Suppose you leave Home and must reach a bakery, a pharmacy, a library, a market and a post office. There are 120 possible orders for five stops. Most of them backtrack across town. One or two are tight. The tool searches through them and hands you the tight one, so you do not drive the same street twice by accident.
You supply coordinates as plain x, y numbers. The units are yours: kilometres, city blocks, grid squares off graph paper. The tool never needs to know what they mean, only that you use them consistently.
When to use it, and when not
Use it when the stops are roughly on an open plain and straight-line distance tracks driving distance well: a suburb with a regular grid, a campus, a warehouse floor, a set of villages joined by direct roads. In those cases the crow-flies order is almost always the real-road order too.
Be careful when geography breaks the straight line. A river with one bridge, a motorway you can only join at junctions, a one-way system downtown: there the shortest straight-line order can send you the long way round. The footnote on the tool says this plainly, and it matters. Two stops 3 units apart on the map can be 8 units apart by road if a rail line sits between them.
The tool measures distance, not time. A route that is 2 km shorter but crosses three traffic lights and a school zone can take longer than a slightly longer clear run. Treat the output as an ordering suggestion, then sanity-check the legs against what you know about the roads.
The distance and the objective
Every leg uses straight-line (Euclidean) distance. For two stops at (x_1, y_1) and (x_2, y_2):
Here d is the distance of one leg, and the two coordinate pairs are its endpoints. The total trip cost is the sum of all legs in the order you visit them.
In this sum L is total length, n is the number of legs, and s_i is the i-th stop in your chosen order, starting from the fixed start s_0. For a round trip the last leg returns to s_0. For an open path it stops at the final stop and the return leg is dropped.
Why small is easy and large is hard
The number of possible orders explodes. With a fixed start and k other stops, a loop has (k-1)!/2 distinct routes. Five other stops give 12 routes. Ten give 181{,}440. Fifteen give about 4.4 \times 10^{10}. You cannot list them all by hand past about seven.
The tool uses Held-Karp for up to 12 stops. That is dynamic programming: it builds the best path to reach each subset of stops, reusing work instead of re-checking whole orders. Its cost grows like 2^{n} \cdot n^{2}, which is far smaller than n!. At 12 stops that is roughly 590{,}000 operations, done in a blink, and the answer is provably the shortest.
Beyond 12 the exact method becomes slow, so the tool builds a route with nearest neighbour (always drive to the closest unvisited stop) and then polishes it with 2-opt (repeatedly uncross any two legs that cross). That is fast and usually within a few percent of optimal, but it carries no guarantee.
Worked example: the demo data
Six stops as a round trip
Load the demo. The stops are Home (0,0), Bakery (2,1), Pharmacy (3,4), Library (-1,3), Market (-2,-1), Post office (1,-2), in loop mode.
- Compute the leg distances you will need. Home to Bakery is \sqrt{2^2 + 1^2} = \sqrt{5} \approx 2.236. Bakery to Pharmacy is \sqrt{1^2 + 3^2} = \sqrt{10} \approx 3.162.
- Continue around: Pharmacy to Library is \sqrt{4^2 + 1^2} = \sqrt{17} \approx 4.123; Library to Market is \sqrt{1^2 + 4^2} = \sqrt{17} \approx 4.123; Market to Post office is \sqrt{3^2 + 1^2} = \sqrt{10} \approx 3.162; Post office back to Home is \sqrt{1^2 + 2^2} = \sqrt{5} \approx 2.236.
- Add them:
2.236 + 3.162 + 4.123 + 4.123 + 3.162 + 2.236 = 19.04. This loop, Home, Bakery, Pharmacy, Library, Market, Post office, Home, is the shortest of all 60 possible round trips.
Notice the shape. The route sweeps the stops in a ring around Home rather than darting out and back. That is the signature of a good tour: it does not cross itself.
Now compare a naive order, visiting in the order typed but as a loop that happens to backtrack. Take Home, Pharmacy, Bakery, Post office, Market, Library, Home. Its legs sum to about 24.9, roughly 31% longer, because it jumps from Pharmacy at the top down to Bakery and later climbs back up to Library. The optimizer removes exactly that kind of waste.
Reading and interpreting the result
The tool gives you an ordered list and a total distance. Three habits make the number useful.
- Check for crossings
- Sketch the route. In a good tour no two legs cross. A crossing is a signal that swapping the order of two stops would shorten the trip, which is exactly what 2-opt fixes.
- Compare loop against open
- An open path drops the final return leg, so it is always shorter or equal. In the demo, an open path ending at Post office saves the
2.236return to Home, giving about16.80. Choose open when someone else picks you up or you finish near your next task. - Treat the distance as a floor
- Real roads only add distance, never subtract it. If the crow-flies total is
19.04, your driving distance will be that or more. A common rule of thumb in gridded towns is to expect 20 to 40 percent above the straight-line total.
Common mistakes
Four errors account for most confusing results.
Mixing units. If some coordinates are in blocks and others in kilometres, the distances are meaningless. Read every stop off the same map at the same scale.
Putting the start in the wrong place. The first line is always the start. Swap it in by accident and the whole loop pivots around the wrong point.
Reading x and y from a screen. Screen coordinates often run y downward, while graph paper runs y upward. The optimizer does not care about the direction, but you will misread the sketch. Pick one convention and keep it.
Expecting road distance. The number is straight-line. Where a river or motorway forces a detour, add the extra leg by hand or split the day into two loops on each side of the barrier.
If two stops share almost the same coordinates, the tool will happily order them next to each other, which is correct. But check that they really are one trip and not, say, a shop that is closed until noon. The optimizer knows geometry, not opening hours.
How much a few extra stops cost you
Adding a stop rarely adds its full round-trip distance, because a good route weaves it into the existing path. The chart below shows the optimal loop length as you build up the demo one stop at a time, in the typed order.
The two-stop loop (Home and Bakery) is just 2 \times \sqrt{5} \approx 4.47. By six stops the optimal loop is 19.04. The marginal cost shrinks because a well-placed stop sits near the path you were driving anyway.
Related tools
Routing is one member of a family of ordering-and-matching problems. If you are pairing two sides by ranked preference rather than sequencing one traveller, the Stable Matching Calculator finds a pairing where no two people would both rather swap. If your problem is when people work rather than where you drive, the Shift Rota Builder lays out a weekly rota around everyone's unavailable days.
Frequently asked questions
Why does the tool say "optimal" only up to 12 stops?
Held-Karp is exact and returns the provably shortest route, but its work grows like 2^{n} \cdot n^{2}. At 12 stops that is manageable. At 20 it is billions of operations. Past 12 the tool switches to a fast heuristic that is usually within a few percent of optimal but carries no proof.
How far off can the heuristic be?
Nearest neighbour alone can run 25 percent or more above optimal on awkward layouts. The 2-opt polish that follows typically pulls it back to within 2 to 5 percent. On most everyday errand lists the heuristic route matches the exact one.
Should I pick loop or open?
Pick loop if you must return to the start, for example home to home. Pick open if you can end anywhere. Open is always shorter or equal, since it drops the final return leg. In the demo that leg is worth about 2.24 units.
Can I force a stop to come first or last?
The start is always first. To pin a last stop, run in open mode and then check that the tool ends there; if it does not, that stop is not naturally last and forcing it would lengthen the trip. There is no fixed-end control, so the honest workaround is to compare the open route against your preferred ending by hand.
Do straight-line distances ever match road distances exactly?
Only on a perfectly open plain with direct roads. In a square grid, driving distance is the sum of the x and y gaps (the "taxicab" distance), which is always at least the straight line and up to about 41 percent longer for a diagonal trip. Treat the tool's total as a lower bound and add a margin for your street layout.
Related tools
Shift Rota Builder
A fair weekly rota around everyone’s unavailable days.
Stable Matching Calculator
Gale–Shapley pairing from two sides of ranked preferences.
Round-Robin Schedule Generator
Everyone plays everyone: fixtures by the circle method, byes included.
Seating Chart Optimizer
Assign guests to tables around keep-together and keep-apart rules.
Secret Santa Generator
Draw gift-exchange pairs with exclusions, no self-draws guaranteed.
Voting Methods Lab
Drag candidates on an opinion map and watch plurality, runoff, Borda and Condorcet crown different winners.