Real life traveling salesman problem

  • Context: Undergrad 
  • Thread starter Thread starter beamthegreat
  • Start date Start date
  • Tags Tags
    Life
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
Sign up Log in
6 replies · 2K views
beamthegreat
Messages
116
Reaction score
7
TL;DR
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?
 

Discussion

Mathematics news on Phys.org
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.
 
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
 
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.
 
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 :biggrin:).

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.