Twenty Stops, One Terrible Order

Scotney Castle, stop six of twenty once the planner had its way. Photo by Sean Ferigan on Unsplash.

Here is a thing I do constantly and had never thought about properly.

I decide on a day out. I find the places I want to see, and I add them to the planner in the order I found them, because that is the order they were in on the website I was reading. Then I look at the total, decide it is too far, and start dragging rows around until it looks less silly.

That last part is the bit a computer should be doing.

The test

Twenty National Trust properties in Kent. I did not choose them to make a point: they are simply the ones with a postcode, taken in list order, from Chartwell at the top to One Tree Hill at the bottom. Chartwell is the start, One Tree Hill is the finish, and the eighteen in between are stops the planner is free to shuffle.

Typed in that order, the car route comes to 653.2 km and a little over ten hours of driving.

Look at stops five, six and seven. Ightham Mote to the White Cliffs of Dover is 91.8 km. Dover back to Emmetts Garden, which is four miles from where we started, is another 116 km. That is two and a quarter hours of motorway to visit one clifftop, and then we do most of it again later to reach Smallhythe.

On the map it is more obvious. The whole east of the county is one long spur, driven out and driven back.

What Auto order does with it

One button, eleven seconds.

327.0 km. The same twenty places, the same start and finish, half the driving.

Auto order solves three questions, not one, because "best" is not a single thing: shortest by distance, quickest by time, least metres of ascent. Here two of them landed on the same order, so they collapse into one chip that says so. Nothing moves until you pick something - your own order stays on offer as the first chip, and Compare puts them side by side with their elevation profiles.

Checking every leg

That eleven seconds hides a shortcut, and it is the part I find interesting.

Twenty stops have 190 possible legs between them. Measuring all of them means 190 routing requests before you can even begin to think, which is slow and is a lot to ask of the routing servers for a question you might not like the answer to.

So Auto order measures in two passes. It starts from straight-line distances, which are free, solves the order from those, then measures only the legs its candidate answers actually want to use. Solve again, measure what changed, repeat. Straight lines stand in for everything unmeasured, scaled so an unmeasured leg is never mistaken for a free one. On this route that came to 52 routing requests instead of 190.

The price is that the answer is very good rather than proven. So there is a button for the other choice.

Check every leg measures the whole matrix and solves the order exactly. It reuses every pair already measured, so it costs the difference rather than starting again: 144 further requests and 23 seconds here. It came back with a third option and a better shortest, 327.0 km down to 326.7 km.

Three hundred metres on a 327 km drive. That is the honest size of the prize, and it is why the thorough version is a button rather than the default.

Every name there is earned on the finished route rather than on the estimate that produced it, which was not true a week ago. The orders are worked out from a cost matrix that is partly straight lines, so the order that looks shortest on the matrix is not always the one that routes shortest. For a while the planner named each option after the matrix that produced it, and cheerfully showed a "Shortest" that was 13 km longer than the "Quickest" next to it. The figures were always measured; only the labels were guessing. Now an option is named after what it actually wins, and one that wins nothing is not offered at all.

Picking Shortest rewrites the list. Dover is now stop nine, reached on the way round rather than as an excursion, and the route reads as a loop instead of a scribble.

Eighteen stops, 6.4 quadrillion orders

The other half of the problem is the ordering itself, and it is worse than the measuring.

Eighteen stops can be arranged 18! ways. That is about 6.4 quadrillion, so trying them all is not on the table. Held-Karp gets the exact answer without trying them all, but it wants memory in proportion to 2^n, and until this week the planner gave up on it above twelve stops and fell back to nearest-neighbour with 2-opt and Or-opt improvement.

Twelve turned out to be far too cautious. The table Held-Karp needs is one big array of numbers, and it had been built as 262,144 small ones, where the bookkeeping cost more than the numbers. Flattened, eighteen stops solve exactly in 250 milliseconds and 38 MB. Nineteen would be 80 MB and twenty 168 MB, so eighteen is where it stops and the heuristic takes over again.

The useful thing I learned from measuring all this: the solving was never the expensive part. Seven seconds of an eleven second run is waiting for a routing server to answer questions about how far apart two castles are.

Keeping a stop where it is

Ordering by distance alone is fine for a list of hills. It is wrong the moment a stop has a time attached to it, and most good days out have at least one: the place that opens at eleven, the table booked for one, the ferry.

Every stop has a pin. Pin it and it stays at that position in the list while everything around it moves.

The pin is a position constraint handed to the solver, not a filter applied afterwards, so the order you get back is the best one that respects it. And because a pin changes no geometry, pinning something after the suggestions have arrived simply withdraws them: they were worked out under different rules, so they stop applying rather than quietly becoming wrong.

Where to find it

Open the Plan tab, drop your stops in any order at all, and press Auto order, next to Search and Reverse. It takes up to twenty stops between the start and the finish. If you change your mind while it is working, the button turns into Cancel and means it.

Once it has answered, Check every leg appears beside Compare if there were legs it did not measure. Expect it to take a while and to find very little; it is there for the days when you would rather know.

It will not reorder a plan with a straight-line or any-path section in it, because those belong to a position in the list rather than to a place: move the stops and your hand-drawn shortcut ends up on a leg you never chose.

The route planning guide walks through the rest of the planner, and Auto order has its own section there with the same feature shown step by step.

Two hundred miles saved on one day out, for one button. I will take that.