Slashdot Mirror
Where's the Traveling Salesman for Google Maps?
Komi writes "Has anyone tackled the Traveling Salesman Problem with Google Maps or any other online mapping tool? I've searched, but can't find anything. To me this seems like such an obviously cool function. I'm not up to date on algorithms, so perhaps this isn't really tractable for large values of n. But for small numbers (maybe up to 5), this could at least be brute-forced. I would love to use this when I have errands to run, and I want an overall optimal route. So if this hasn't been done, someone please do it!"
The traveling salesman problem wasn't meant to be tested in real life.
;) )
Actually, travelling salesman solvers are used in all kinds of real world applications.
Some examples can be found here: http://www.tsp.gatech.edu/apps/index.html
A TSP solver on google maps would be useful to some people (such as travelling salesmen
I could imagine tourists using such a function to plan a route around all the sights they want to see
It could also be used by anyone who needs to make several deliveries
Well salesmen rarely do this. However, imagine a UPS driver delivering 40 different packages to various parts of a city. It would be quite useful to automatically determine the order of delivery ahead of time in such a way as to minimize time and distance. As indicated in other replies to this thread, good solutions are much easier to come by than perfect solutions. The difference between the two solutions is probably not great enough to justify the immense computation power required to churn out the perfect solution. The perfect solution would probably end up costing more since you have to figure in the cost of energy used to compute it.
The submitter just wanted to be able to use google maps to find the optimal route between points on an errand run. If you limit the number of nodes to 10, then perfect solutions remain tractable. And I doubt most people would have more than 10 errands to run at once.
On a related note, I just had a Mormon missionary knocking on my door last night. Perhaps we could rename this the traveling Mormon problem. I'm sure they would appreciate automated itineraries that minimize the burden on their poor soles.
However, in graphs upholding the triangle inequality (that is, if the distance A->C is d then the distance A->B plus B->C is at least d) there are algorithms that do give guaranteed good approximations. So in the real world you are correct.
As an example of how approximations tend to fail we can look at a case where the greedy inversions of pairs you suggest breaks down (the lameness filter screws up my fine ASCII art. The numbers now signify nodes and the initial path runs in number order):
Now, this is not a good path through all the points on this map, but flipping the order of any pair will only make the path worse. The correct solution would be much shorter, just going straight through the top and bottom rows. But that path cannot be reached by greedingly inverting the order of pairs.No, I won't link you to the site. It's the first hit when you google: travelling salesman google maps You fail at the internet.
1. Type this into Google: travelling salesman google maps
2. Click "Search"
3. Click the first result: "TSP Solver for Google Maps"
4. Practice searching for things more