Why is route optimization so hard?

Short answer: because the number of possible orders grows faster than any computer can count. A route with 10 stops can be driven in 3.6 million different orders, with 15 stops in 1.3 trillion, and with 20 stops in more than 2 quintillion. No app checks them all. Route planners use shortcuts that find a very good order in seconds, without proving it is the best one possible.

How fast the number of orders grows

If you start from a fixed point and visit every stop once, the number of possible orders is 1 × 2 × 3 × … up to the number of stops (mathematicians write it as n!). The last column shows how long it would take a computer that checks a billion orders every second to try them all.

Each extra stop multiplies the count by the new number of stops. Going from 15 to 16 stops makes the search 16 times bigger, and from 19 to 20 stops, 20 times bigger. That is why a method that works for a short list breaks down completely for a normal delivery day.

The traveling salesman problem

Finding the shortest order through a list of places is a famous puzzle called the traveling salesman problem. Mathematicians have studied it for almost a century, and no known method finds the guaranteed best order quickly for every possible list. The best exact solvers can still prove the optimum for huge lists if you give them enough time. The record for the Concorde solver is a tour of 85,900 points, finished in 2006 after computing work equal to about 136 years of a single processor. A delivery driver needs an answer before the engine is warm.

Real roads make it harder

The puzzle in textbooks uses straight lines. A real route adds much more:

• Road distances and travel times. One-way streets, turn restrictions, bridges and highways make the drive from A to B different from the drive from B to A.
• Traffic. The same road takes longer at 8 am than at 11 am, so the best order depends on the time you set off.
• Time windows. A customer who is only home after 3 pm fixes part of the order.
• Time at each stop. Parking and handing over a parcel take minutes, which push later stops into busier hours.
• Pickups and deliveries. A parcel has to be collected before it can be delivered.
• More than one driver. Splitting stops between vehicles is a second puzzle on top of the first, called the vehicle routing problem.

How route planner apps solve it anyway

Apps don’t try every order. They build a good route quickly, for example by always driving to the nearest unvisited stop, and then improve it. A common improvement is to take two legs of the route that cross each other and uncross them. The app repeats such changes until no small change makes the route shorter, and returns the result within seconds. The answer isn’t proven to be the best possible order, but for everyday routes it is usually very close to it.

Different apps use different methods and different map data, which is why two apps can return slightly different routes for the same stops. MyWay compares results from several routing engines, including Google-based routing, GraphHopper and OSRM, and keeps the best one. We explain which maps it uses in which maps MyWay Route Planner uses.

What this means for your route

• Don’t trust your gut past ten stops. With millions of possible orders, a hand-made order is rarely the shortest.
• Re-optimize after changes. Adding one stop can change the best order for the whole route, not just one leg.
• Set your constraints. A time window or a fixed end point gives the app the information it needs to avoid a short but impossible route.

MyWay optimizes routes of up to 15 stops for free and up to 200 stops on Pro. For the difference between putting stops in order yourself and letting software do it, see route planning vs route optimization.

Sources

• Number of orders: our calculation (n! for n stops from a fixed start).
• Concorde TSP solver and the 85,900-point tour (pla85900): University of Waterloo, math.uwaterloo.ca/tsp.
• Routing engines used by MyWay: the FAQ on our comparison page.