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!"

Comments

You can do much better than what you assume

[Darth_Ramirez]

We can do much better than that solving TSP nowadays. While NP--complete it doesn't mean that you're reduced to 5 cities problems:

1) You can use Heuristic Search to look for solutions of quite big TSPs. One very simple heuristic is the Maximum Spanning Tree heuristic. Not so simple is the AP heuristic. Do a search on scholar.google.com with the terms "TSP" "Heuristic" "Search" for the state-of-the-art. Note that this approach allows you to find the optimal tour.

2) For a practical application I doubt you'll be needing *always* an optimal solution - you can settle for something satisfactory, either by relaxing further the problem or by using non-optimal search algorithms. In this case, the NP--completitude issue becomes non-relevant at all.

Re:What's the point?

[etymxris]

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.

Scientific American Article on this

[Precipitous]

The Fastest Way to Get There.

The approach discussed works on "... a simple premise: driving somewhere usually requires crossing major intersections that are sparsely interconnected. "

Right here...

[jberryman]

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.

NOT a travelling salesman problem.

[3-State Bit]

You don't need to traverse every road connecting your errands, since you're not selling door to door along the way.

Re:NOT a travelling salesman problem.

[cnettel]

You don't need to traverse every road connecting your errands, since you're not selling door to door along the way. TSP is not a filling problem. You only need to traverse every road when doing a brute-force TSP search for an arbitrary graph, since you cannot assume any specific distance constraints (like the triangle inequality or a close-to-planar structure). The problem itself is just about getting a(n optimal) permutation of the nodes. I can't imagine why you were modded insightful.

Re:NOT a travelling salesman problem.

[david_thornley]

No, that would be the Chinese Postman Problem, which is solved (provided you have a good linear programming engine available). There are variants that at least weren't solved when I was working on it ten years ago, such as the Windy Postman Problem (where the cost to go from A to B isn't necessarily the same as that to go from B to A), which I was attacking with simulated annealing. Awful slow to run, though. I haven't heard of problems in that family being classified as NP, but as I said I've been out of them for a while.

Re:Do it the old way

[voss]

The problem with simple math solutions like this one is that they make assumptions such as all else being equal.
In the real world it doesnt function like that. A mathematically optimal route may not work because of real world
conditions(traffic, construction, everybody else trying that same route) or it may work somedays but not others
or some times of the day but not others.

Re:Do it the old way

[Anonymous Coward]

dude, you just need to include those circumstances into the distance function! Route planners routinely do this, where the actual distance function is really more like a function of the actual distance travelled and the time it takes to travel down that road (according to a typically simple model of the possible travelling speed).

Re:What's the point?

[TheLink]

I believe in the USA, UPS picks routes which reduce left hand turns.

Delivery people would rather have the fastest time rather than the shortest distance.

Or at least one that makes them more money in the long run (which is slightly different from "saves them more money" ).

Re:Acceptable solutions

[TheRequiem13]

Not that I'm saying his method is foolproof, but your example does not show its failure. You say any pair will make the path worse (true) but gp is saying portion, which can be as little as a single pair or as much as the entire path less an endpoint.

In your example, if you reversed the visitation order of the sub-path 0-1-2 you would remove one vertical jump, thereby improving the path.

| 2 3 4 7 8
|
|
| 1 0 5 6 9

is obviously better than

| 0 3 4 7 8
|
|
| 1 2 5 6 9

Genetic algorithms improve this type of sub-path fine-tuning, by "mating" good paths with each other randomly (splicing portions across) combined with the randomized mutations described by the GP and ranking a large "population" of solutions according to some fitness/distance measure.