Real life traveling salesman problem

[beamthegreat]

TL;DR Summary

How to find optimal route for a trip to multiple cities

If a person is from New York, and he/she wants to visit Paris, Rome, Munich, Bern, and Madrid in a single trip, what's the shortest route to take? Are there any practical online tools you can use to solve this problem that doesn't require you to have knowledge of programming or mathematics?

 

[member 587159]

Here we have 6 cities to visit. This is solvable by brute force techniques.

You start in NY, thus you have 5 options for the first city, 4 for the next one etc. So eventually, you have $5! =120$ possible routes. Now, pick the one with minimal distance.

 

[DavidSnider]

Wolfram alpha can do this with simple location data (as the bird flies), but not with roads \ railway \ airports I don't think. Shortest Path

 

[pasmith]

I think you'd want to optimise time or cost rather than distance here.

 

[osilmag]

When I look at the map, Madrid seems to be the outlier of those. The other 4 seem to have some proximity to each other. However that might just be my opinion.

 

[Tom.G]

Just wondering.
Does it make a difference if the return trip to New York is included?

 

[pbuk]

If you assume straight line distances then simply by looking at the map the optimum route for a round trip is NY-Paris-Bern-München-Roma-Madrid-NY. This is trivial because the path is almost convex with only a slight deviation to Bern.

Replace Bern with Lyon and the problem becomes more interesting (and at the risk of offending anyone from Switzerland, so does the trip ).

The one-way solution is again trivial by inspection (if you count checking that Madrid is closer to Paris than it is to Roma with dividers on my globe): NY-Madrid-Paris-Bern-München-Roma.