Where's the Traveling Salesman for Google Maps? 125
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!"
He is out, travelling? (Score:4, Funny)
I have no idea.
Re: (Score:2)
Re:He is out, travelling? (Score:5, Informative)
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
Re: (Score:2)
And the solution using MS Virtual Earth... (Score:2)
Yahoo has multiple stops (Score:1)
"tackel the problem" == "make it not NP-hard"? (Score:2, Informative)
Re:"tackel the problem" == "make it not NP-hard"? (Score:4, Informative)
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: (Score:1, Interesting)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
And I would bet that they visit 5 or fewer.
Re: (Score:3, Interesting)
Re: (Score:2)
For a very large portion of the problem space, TSP is really quite tractable once you use a proper heuristic. I've seen damn near perfect approximations to a 100-city TSP problem computed in under ten seconds.
Good heuristics are just frighteningly good.
If you want to see an example of this, take a look at Djinni [uiowa.edu], which imp
Re: (Score:2)
Re: (Score:2)
Actually, we did exactly that in the AI class I took last semester. My GA implementation was still able to find optimal solutions for 49 cities (a 7x7 grid) in about 3 minutes fairly regularly.
Re: (Score:2)
Re: (Score:2)
For convenience, we used a special case of the TSP, where all cities are considered to be in an NxN grid with uniform spacing (of 1 unit) and the cost to move from one city to another is the Euclidean distance between the two. This makes the optimal cost quite easy to calculate by hand, especially since it follows an obvious pattern (9.414, 16, 25,414, 36, ...).
Re: (Score:2)
Re: (Score:2)
ahh, but I'm guessing you feed it waypoints in the order you want them, the GPS doesn't tell you the best order for the waypoints?
the travelling salesman problem here would be where you could enter in say 5 desintations and your starting point, and the appl
Re: (Score:2)
Routing through point A to point B in a directed graph is a solved problem - Dijkstra's algorithm isn't that bad computationally, and there are others that have the same worst-case performance as Dijkstra but better average performance (such as I believe A*).
What your GPS supports is just applying the same problem sequentially. Given points A,B,C,D,..., visit them in the user-specified order. A to B, B to C,
What the article poster wants is:
Given starting point A, what is the best way
Re: (Score:2)
Re: (Score:2)
Do it the old way (Score:4, Funny)
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: (Score:3, Insightful)
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: (Score:1, Insightful)
Re: (Score:1)
According to the Google Maps API Terms of use, you're limited to 15,000 queries per day.
So if you're doing even 5 nodes, then that's you down to 600 users per day (15000/(5^2)).
10 nodes, and you're only going to be able to process 150 users per day!
Re: (Score:2)
Although this would be a nifty feature for the few times that the order doesn't matter.
Re: (Score:2)
Traveling salesman is (n - 1)! / 2, so you could do 1,250 users with 5 nodes. Of course, with 10, it would take you a little over 12 days to complete a query.
Acceptable solutions (Score:3, Interesting)
Re:Acceptable solutions (Score:5, Informative)
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.Re: (Score:2, Insightful)
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.
is obviously better than
Genetic algorithms improve this type
Re: (Score:2)
where we say that A is a cluster containing points 0 and 1 close together, B is the cluster of point 2 and 3 close together and so on. This is still the same problem as before, but now we can generalize the key point in it.
I
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Just prove that P=NP (Score:1)
Until that, since TSP is NP-Complete, there's no way to do deterministically on large data sets: it's computationally intractable (and, i guess, Google Maps data set it's *definitely* huge
Re: (Score:3, Informative)
Re: (Score:3, Informative)
TSP is NP-complete. (Score:2)
The definition of NP-completeness--or at least one of them, you can define it in several different (but all equivalent) ways--is a problem which exists in NP, but is also NP-HARD.
You appear to not understand complexity theory. I would suggest brushing up on it.
(ObDisclosure: I am a graduate student in CompSci. One of my research areas involves the TSP. I have spoken at CodeCon 2006 and OSCON 2006 on new approaches in heuristic approximators for NP-complete alg
What's the point? (Score:2)
Maybe I misunderstand the question.
If you want to select some number of real cities, just go ahead and select them and figure out the distances from each city to each other city. Google Maps might help figuring out the distance, but that's about it.
It seems rather pointless, though. How many salesmen do you know who travel in the manner in the problem? The problem is important, but not for real life traveling salesmen.
Re:What's the point? (Score:5, Insightful)
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.
s/poor soles/poor souls/g (Score:1)
Re: (Score:2)
Re:What's the point? (Score:4, Insightful)
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: (Score:2)
Re: (Score:2)
Re: (Score:2)
The point? A case study (Score:2)
Consider:
My flatmate (translation: person I share a flat with) was at one time a courier. When he arrived at work (at 5 am) he'd be given a number of packages to be dropped off. Usually around 40, all within his "patch", a postcode based area. He'd usually then spend the next hour in the back of his van grouping them together into groups. Given that he was expected to come back for a second load in the early afternoon, this meant he usually
Re: (Score:2)
Re: (Score:2)
On reflection, I may have missed a few points out.
The starting linked lists consists of the depot as both the origin and the final destination. It may be worth preparing a few core stops, say 2 or 3 stops that are furthest from the average / centre.
Bear in mind that this was a courier, operating in a postcode / suburb based area, and returning to base, the local airport.
While not being a perfect solution, it's much better than the one in place, which is very random - possi
Re: (Score:2)
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.
I'd suggest a variant, the "real-time travelling salesman problem": You have a computer in your car, and you enter all the destinations into your computer. Then it starts calculating, and as soon as it spits out the first destination, you go there. Once it gives you the second destination and you have reached the first one, you go to the second destination. The goal is to minimise the total time.
Here the software would have to take into account not only the driving time, but also the calculation time. It
Re: (Score:2)
http://slashdot.org/article.pl?sid=07/12/12/1355219&from=rss [slashdot.org]
Re: (Score:2)
The problem with the salesmen problem is that even if you did have the time, real-time events would eventually fuck with teh solution anyway, at some point there is such a thing as "good enough" until we get a computer that is equal to a god in intelligence and computational power.
Re: (Score:2)
yet there are humans that do this processing every day. How?
The human mind is still one of the best computers available.....especially for pattern recognition and learning.
Those guys have had time to refine their routes based on previous instances (John Customer is a neighbor to Sally Secretary who used the service just last week). They can also look at things at the microscopic and macroscopic levels and include multiple inputs (time of day, traffic patterns, importance, time, distance, etc.) quite easily where a computer only knows what it knows. And in your sp
Re: (Score:2)
Suppose you wanted to provide power to n-1 locations (i.e. n points on the map including the power plant) and you want to minimize the distance for the lines. Assume, of course, that right of way is related linearly to distance.
It may not be intuitive, but there will be times when you can introduce another point and result in less distance than the traveling salesman distance.
For
Re: (Score:2)
I don't see the point at all.
Maybe I misunderstand the question.
Here's a good example. Let's say you're hired by a company to market to beer breweries and brewpubs, and you were arranging personal visits in order to demonstrate your new beer widget to them. Take a look at this map:
... * 3 * 2 * 1) where n is the number of locations. Basica
http://beermapping.com/maps/maps.php?m=northcentral [beermapping.com]
Now quickly find the most optimal route to visit all those locations in the least amount of time. The number of permutations are basically n! (that's n factorial: n * n-1 * n-2 *
Re: (Score:2)
You might also have preferred places to spend the night. How about if you have a favorite restaurant along the way and you want to order your visits so that you can go there for supper one night of the trip? How about if an old friend lives near one brewery and
Re: (Score:2)
Re: (Score:2)
I like that. It made me laugh pretty good.
However, his best path might still be suboptimal.
Use a neural net (Score:1)
Re: (Score:2)
But since you suggested it, I'm willing to give you the benefit of the doubt.
Please fill in a few details such as the number of inputs and their form, the number of levels, how the output will be interpreted,
Re:Use a neural net (Score:4, Interesting)
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: (Score:2)
Bob
Re: (Score:2)
Well, I suppose an experienced salesman can plan pretty good routes, but I thought that the question was about using a computer for this ;).
You can do much better than what you assume (Score:2, Insightful)
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
Scientific American Article on this (Score:3, Insightful)
The approach discussed works on "... a simple premise: driving somewhere usually requires crossing major intersections that are sparsely interconnected. "
Re: (Score:2)
Interesting question.. But sorry no answer from me (Score:3, Interesting)
Re: (Score:2)
Right here... (Score:5, Insightful)
Re: (Score:2)
Crazy like a fox!
Re: (Score:2)
NOT a travelling salesman problem. (Score:1, Insightful)
Re:NOT a travelling salesman problem. (Score:4, Insightful)
Re: (Score:1, Informative)
real travelling salesman have a solved problem [wolfram.com]: walking along each road once, selling to each house along the way.
Re: (Score:2)
As a SALESMAN, you TRAVEL across the region making sales calls. Thus, this is a TRAVELLING SALESMAN problem. I had an uncle who used to make sales calls to restaurants in the Daytona Beach area.....a little more local, but the same principle.....he travelled the
Re: (Score:3, Insightful)
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
Ant Colony Optimization? (Score:2)
Huh??? I don't get it (Score:3, Informative)
J.F.G.I. (Score:4, Informative)
http://gebweb.net/optimap [gebweb.net]
Travelling salesman.. (Score:2)
Innocent as I was, I thought the traveling salesman problem could easily be solved by a computer. I wrote the code, and gave it a "standard" traveling salesman problem from a book. 60 CPU-seconds later, I got the optimal answer. It was a 100 city (or was it 133?) problem.
The book said that a pruning brute force algorithm had been run on a CRAY supercomputer. It had come to the same solut
Re: (Score:2)
In real-life problems, you can make some
Re: (Score:2)
I really don't remember.
Thinking about it some more, some heuristics that I used depend on the problem being planar. This is an assumption that goes out the door once you have the route planner give the "cost" of each of the n^2 combinations of places.
Some people "give up" the moment a problem has been proven NP-complete/intractible.
In practise, someone running a couple of errands or delivering 10 or 20 club-newsletters, the n^2 part as well as the 2^n TSP problem is so
Re: (Score:2)
First, in your path, remove one city, and try plugging it in the route at another spot. This is n^2.
Second, in the path, take two edges, AB and CD. See if the path with AC and BD is shorte
Re:Google Maps is not required nor desired (Score:5, Informative)
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 [gatech.edu]
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: (Score:2, Informative)
http://gebweb.net/optimap/ [gebweb.net]
Re: (Score:2)
Layne
You can already do that sort of (Score:2)
It won't automatically find the shortest drive to visit each, however, you can drag them around on the left to change the overall route ordering. Assuming your vacation route is only 4 or 5 items it should be fairly simple to plan the optimal route for your family using the map on the right while you drag.
Re: (Score:2, Interesting)
This seems to be caused by Google's use of the crappy Teleatlas map data.
Re: (Score:2)
Once you have your addresses entered, minimuze the individual directions leading from stop to stop and google lets you drag and drop the locations on the pane i
FedEx (Score:2)
They actually do a variant of the problem called the TSPTW, the TSP with Time Windows, where the salesman has to visit each point within a certain time window. In FedEx's case, this corresponds to the time the recipient is expecting delivery.
There's another variation, the Vehicle Routing Problem, which is basically giving a set of vehicles a set of clients to visit and apportioning stops to e
Re:Google Maps is not required nor desired (Score:4, Interesting)
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)
Pen Plotters in the 1980s (Score:2)
Re: (Score:2)
TSP is the linking of several shortest paths, which would get really strange in the social graph, something like: "I want a path of friends where A, B, C, D, E, F are included, but also allo
Re: (Score:2)