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

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.

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

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.

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

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