Real life traveling salesman problem

  • #1

Summary:

How to find optimal route for a trip to multiple cities

Main Question or Discussion Point

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?
 

Answers and Replies

  • #2
Math_QED
Science Advisor
Homework Helper
2019 Award
1,655
676
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.
 
  • #3
DavidSnider
Gold Member
487
131
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
 
  • #4
pasmith
Homework Helper
1,770
439
I think you'd want to optimise time or cost rather than distance here.
 
  • Like
Likes pbuk and jbriggs444
  • #5
osilmag
Gold Member
131
31
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.
 
  • #6
Tom.G
Science Advisor
3,293
2,045
Just wondering.
Does it make a difference if the return trip to New York is included?
 
  • #7
pbuk
Science Advisor
Gold Member
1,534
474
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.
 

Related Threads on Real life traveling salesman problem

  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
4
Views
4K
  • Last Post
Replies
11
Views
5K
  • Last Post
Replies
1
Views
8K
  • Last Post
Replies
17
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
Replies
7
Views
3K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
20
Views
6K
Top