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

He is out, travelling?

[G3ckoG33k]

He is out, travelling? Or just too small to be seen in that resolution?

I have no idea.

Re:He is out, travelling?

[KillerCow]

Has anyone tackled the Traveling Salesman Problem with Google Maps or any other online mapping tool? I've searched, but can't find anything.

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

"tackel the problem" == "make it not NP-hard"?

[wbren]

By "tackle the problem", do you mean "make it not NP-hard anymore"? If so then, no, it has not been "tackled". However, algorithms exist that approximate a solution to the problem, as is the case with many NP-hard/NP-complete problems.

Re:"tackel the problem" == "make it not NP-hard"?

[dintech]

He's clearly aware of the intractability. From the summary, "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."

And he's right. If you remember your computability and intractability lessons at Uni then you'll rember that TSP is quickly solvable for small values of n. Just like the summary states. Approximations are only required for larger values of n where the solution takes much longer to arrive at.

Re:"tackel the problem" == "make it not NP-hard"?

[CastrTroy]

I remember that they had heuristics to give very close to the best path with a lot less computation for figuring out the actual correct solution. They used it for figuring out paths for things such as machines assembling circuit boards. Following the shortest path means they can produce them faster.

Do it the old way

[KiloByte]

Well, I haven't heard about any Nobel prizes or Fields medals awarded to Google's employees recently.

So, because of network latency, the best you can do is:
1. run Google queries for n^2 routes for all node pairs
2. solve the Travelling Salesman problem yourself

Because there is no way to go A->B->C faster than A->B + B->C if you want to visit B on the way, asking Google/Yahoo/etc for A->B->C routes is pointless.

Of course, step 2. is left as an exercise to the reader.

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.

Acceptable solutions

[Wiseman1024]

Given a reasonable number of points, say, 300, You can't easily find the best solution, but you can find a "good enough" solution that'll be little worse than the best possible solution. One way to do so is to keep a list of the points in any order, calculate the length of visiting them in that order, and choose random portions of the list to try in inverse order and see if you're saving distance. After many iterations of trying that without getting an improvement, you consider the solution good enough.

Re:Acceptable solutions

[jiushao]

Interestingly this is not really the case in the general problem. Notably the travelling salesman problem is not in APX unless the hamiltonian path problem is in P. That is, unless P=NP, there exists no algorithm which can give an approximation of the solution to the travelling salesman problem which is guaranteed to be within a constant factor c of the correct answer.

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):

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

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.

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.

Re:Just prove that P=NP

[sigmoid_balance]

First of all TSP is not NP-Complete it is NP-hard. This means we couldn't find a polynomial algorithm that reduces TSP to a NP-Complete problem: it either exists, but it wasn't found, or it doesn't exist and then it's even harder than NP-Complete. Second, intractable means "unsolvable by a Turing Machine in a finite time", which is not true, since you can find a naive algorithm that takes a lot of time, but finishes. The algorithm is like this: generate all possible paths in the graph and test if it's a minimal solution. The number of paths is less than |E|!, where E is the set of edges. The solution space is finite so the problem is solvable in finite time.

Re:Google Maps is not required nor desired

[actiondan]

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

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

Interesting question.. But sorry no answer from me

[tanveer1979]

When I went to see Yosemite, and had just a day(half actually), I could not figure out in what sequence to follow so that I see most of the spots. such a application for google maps will be just great!

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.

Re:Use a neural net

[arivanov]

As the saying goes artificial intelligence is no replacement for natural stupidity.

My old Advanced CS professor in high school gave an even better explanation to one geek who was trying to use a similar approach to minimise his search field in a classic travelling salesman problem: "Dear, you cannot have your dick in both hands or your soul in paradise, you have to chose: it is either a full enumeration or you can express it as a sorting problem".

If you deal with the original travelling salesman problem, neural net will not help you by any means. If you modify the problem so it can be solved by means different from brute force you might as well solve it properly. In that case it is no longer the classic "travelling salesman" though.

Re:Google Maps is not required nor desired

[jberryman]

Okay, fine:

http://gebweb.net/optimap/

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:Just prove that P=NP

[psmears]

Second, intractable means "unsolvable by a Turing Machine in a finite time" No, intractable usually means not solvable with the resources that are available in practice. Your definition corresponds more closely to undecidable.

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:Google Maps is not required nor desired

[SharpFang]

Maybe it wasn't but it definitely happens.

My previous job, working with a CNC engraving machine. If you want for example engrave letters (outlines), the tool runs over enclosed paths so the start and end of each path is at the same point. Each line is a single path associated with a single point. The tool needs to be moved between these points above the surface of the material. The ordering which path goes first is of little significance, but travel above the material takes time - so picking paths that are near results in a shorter time of the production. So you order the paths so that the total distance between start/end points is shortest. This is about 99% of the salesman problem - only exception is that you don't return to the first point after you finish your work. (also, "cities" are non-zero size and you may enter any at any given "city limit" point, but exit in the same place - any point of the path is good for the start/end point)

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.

Huh??? I don't get it

[zappepcs]

The submitter obviously understands Google... first link if you search Google for "map 'traveling salesman'" gives you http://gebweb.net/optimap/ ... is that what you mean?

J.F.G.I.

[portnoy]

"Sure I could just google it myself, but if I post to Slashdot I waste *everyone's* time!"

http://gebweb.net/optimap

Re:Google Maps is not required nor desired

[SpinyManiac]

I think they should fix the map data first. If I plan any route from home using Google Maps it starts by telling my to drive east through a neighbour's house and garden to get to a minor road instead of driving west to get to the main road. The lane which links my house and several others to the main road is clearly visible on the satellite image.
This seems to be caused by Google's use of the crappy Teleatlas map data.