Real life traveling salesman problem

• I
• beamthegreat
In summary, the conversation discusses the shortest route for a person from New York to visit Paris, Rome, Munich, Bern, and Madrid in a single trip. It is suggested that this can be solved using brute force techniques and that Wolfram Alpha can also provide a solution. The importance of optimizing time or cost rather than distance is mentioned, and the potential difference if the return trip to New York is included is also considered. Finally, it is noted that the optimal route for a round trip is NY-Paris-Bern-Munich-Rome-Madrid-NY, but this can be made more interesting by replacing Bern with Lyon.
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?

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

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

pbuk and jbriggs444
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.

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

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.

1. What is the "Real life traveling salesman problem"?

The "Real life traveling salesman problem" is a mathematical problem that involves finding the shortest possible route that visits a given set of locations and returns to the starting point, while only visiting each location once. It is a real-life version of the classic traveling salesman problem, which is a well-known problem in the field of computer science and operations research.

2. How is the "Real life traveling salesman problem" relevant in real life?

The "Real life traveling salesman problem" has many real-life applications, such as route planning for delivery drivers, salespeople, and traveling salesmen. It is also used in logistics and supply chain management to optimize delivery routes and reduce costs. Additionally, it can be applied in the field of genetics to determine the most efficient order for sequencing DNA fragments.

3. What makes the "Real life traveling salesman problem" difficult to solve?

The main difficulty in solving the "Real life traveling salesman problem" is the sheer number of possible routes that need to be considered. As the number of locations increases, the number of possible routes increases exponentially, making it incredibly challenging to find the optimal solution. Additionally, the problem is classified as an NP-hard problem, meaning that there is no known efficient algorithm to solve it.

4. Are there any known solutions to the "Real life traveling salesman problem"?

While there is no known efficient algorithm to solve the "Real life traveling salesman problem", there are several approximation algorithms that can provide a near-optimal solution. These algorithms use heuristics and techniques such as genetic algorithms and simulated annealing to find a good solution in a reasonable amount of time. However, these solutions are not guaranteed to be the best possible solution.

5. How is the "Real life traveling salesman problem" relevant in the field of computer science?

The "Real life traveling salesman problem" is a well-known problem in the field of computer science and has been extensively studied due to its practical applications and its complexity. It is used as a benchmark problem for testing and evaluating optimization algorithms and is also relevant in the field of computational complexity theory. Additionally, the problem has inspired many other problems and algorithms in the field of computer science.

Replies
31
Views
4K
Replies
2
Views
9K
Replies
1
Views
425
Replies
2
Views
847
Replies
3
Views
2K
Replies
2
Views
1K
Replies
6
Views
2K
Replies
2
Views
1K
Replies
19
Views
2K
Replies
19
Views
3K