How to use the shortest route calculator
- Choose stop coordinates or a distance table. With coordinates, write each stop on a line as name, x, y. With a table, write one row of distances per stop.
- The first stop is the start. For a distance table, you can add names for the stops in the same order.
- Choose a straight line or a street grid distance when you use coordinates, and tick whether to return to the first stop.
- Read the best order, the length of each leg and the total, and the total from the quick rule of always going to the nearest unvisited stop.
Formula
straight line distance = sqrt((x1 - x2)^2 + (y1 - y2)^2)
street grid distance = |x1 - x2| + |y1 - y2|
best(S, j) = the shortest path that starts at the first stop, visits every stop in set S and ends at j
best(S + k, k) = the smallest of best(S, j) + distance(j, k) over j in S
This is the Held-Karp method. It builds the best path to each set of stops from smaller sets, which is exact and fast for up to 13 stops, instead of trying every order.
Six stops on a map
Take stops at Depot (0, 0), Bakery (4, 3), School (8, 1), Library (6, 7), Park (1, 6) and Market (9, 5). The shortest round trip from the depot is 28.38: Depot, Park, Library, Market, School, Bakery and back to Depot. Going to the nearest unvisited stop each time gives 30.13, so the best order saves 1.75.
Without the trip back, the shortest path is 22.07. Using street grid distances instead of straight lines, the shortest round trip is 36. Trying all 120 possible orders confirms each answer.
Why the quick rule is not enough
Always driving to the nearest unvisited stop is easy, but it can leave a long trip at the end to reach a stop it skipped. The exact method weighs every order at once. With 13 stops there are over 479 million orders, which the method handles by reusing the best paths to smaller sets.
Real roads
The tool uses the distances you give it. Coordinates produce straight line or grid distances, which ignore one-way streets, traffic, bridges and opening hours. For a closer plan, build a distance table from real driving distances and paste it in. To split the cost of the trip, see the Trip Cost Split Calculator.
More planning and optimization tools
For related planning and optimization problems, try the Linear Programming Solver, NPK Blend Calculator and Knapsack Optimizer.
Assumptions and limits
- Between 3 and 13 stops can be entered, and each is visited exactly once.
- The first stop is the starting point.
- A distance table may be unsymmetric, but every distance is zero or more.
- Example stops are shown until you replace them.
Frequently asked questions
What is the traveling salesman problem?
It asks for the shortest route that visits each stop once and, usually, returns to the start. The number of possible orders grows very fast, so it is hard for many stops.
How many stops can the tool handle?
Up to 13, because the exact method needs time that roughly doubles with every extra stop. Within that limit the answer is the true shortest order.
Does the tool use real road distances?
Only if you give them. With coordinates it uses straight line or street grid distances. With a distance table you can enter real driving distances.
Why is the nearest stop rule shown?
It is a common quick method, and the difference between it and the best route shows how much a better order saves.