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!"
He is out, travelling? Or just too small to be seen in that resolution?
I have no idea.
Yahoo's map service has some sort of multiple destination feature... might be what your looking for.
The traveling salesman problem wasn't meant to be tested in real life. It is a theoretical problem designed to see if somebody could construct a reasonable NP-hard algorithm.
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.
-William Brendel
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.
The creatures outside looked from Alt-Right to Antifa; but already it was impossible to say which was which.
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.
I was about to say 13256278887989457651018865901401704640, but it appears this number is private property.
Oh, it's easy to solve the traveling salesman problem: you just need to prove that P=NP.
:-) )
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
I don't see the point at all.
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.
Just use a neural net in conjunction with Gmaps. Hook up the system to a GPS tracker and train it for a few weeks. Then link up GMaps and you get a pretty damn accurate system to suggest routes and points to the salesman.
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.
The approach discussed works on "... a simple premise: driving somewhere usually requires crossing major intersections that are sparsely interconnected. "
My motto: "A cat is no trade for integrity."
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!
My Aurora : http://www.youtube.com/watch?v=o91ZsGwJYyg
FB : https://www.facebook.com/TanveersPhotography
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.
You don't need to traverse every road connecting your errands, since you're not selling door to door along the way.
Boom tish
Donte Alistair Anderson Roberts - hi son!
Karma: Chameleon
You could even try and make the process fun making it visual and have swarms of ants running round your neighbourhood spreading virtual pheromones over your neighbours' garden all in the name of finding a good route to use!
The problem is that for real uses distance alone is not the sole/main factor, route quality, trafic conditions, horaries, etc are other factors to weight in if you really want to make or plan a real travel.
What's in a sig?
Assuming you want optimal route to visit N destinations on your vacation, all you have to do is map the directions from A to B, then click 'Add Destination' at the bottom for each stop over.
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.
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?
Support NYCountryLawyer RIAA vs People
"Sure I could just google it myself, but if I post to Slashdot I waste *everyone's* time!"
http://gebweb.net/optimap
Actually, this is a very real problem, with very real applications.
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 had time for a sneaky nap in the middle of the day, before finishing around 4:30 - 5pm or so.
The company he worked for kept rolling out hand-held computer systems aimed at tracking the parcels, but never really tried to get into route optimization - despite the fact that improving delivery runs could result in quicker delivery runs, thus (possibly) reducing the number of drivers needed to service a given supply of packages.
My solution (which was only designed mentally rather than written into a working system) was simpler than finding the ideal route by brute force.
You only really need one utility algorithim - a way of determining the distance/time between two points. Once you have that, it's a relatively easy task.
Create a linked list of points, initially consisting of only your starting point and the drop furthest away.
The traverse the list for each new drop, and insert it between the two adjoining points that it's closest to. The route you'll end up with, while possibly not perfect, will end up with a lot of short journeys between close locations.
Easy-ish.
... and today's pet project has
One CS student VS 893 DOS games: Let's play oldies
Problem statement from Wikipedia: "Given a number of cities and the costs of travelling from any city to any other city, what is the least-cost round-trip route that visits each city exactly once and then returns to the starting city?" He's not trying to reduce the number of places he gets to, he's trying to find the best route to go to all the places on his list. That's why you're a twit.
About 20 years ago, I had an IBM PC compatible computer, which ran at a whopping 10MHz, instead of the standard 4.77 MHz.
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 solution that my PC had.
The problem with scaling to 100 errands to run is that you need the full 100 x 100 distance table (cost matrix), and this would be "time in seconds between each of the stops", as issued by a route planner. Calculating 10 thousand routes is something that would still require quite some CPU time, whereas the resulting traveling salesman problem could then be solved on a modern computer in a matter of seconds. Still, with some smart pruning, the number of full-paths that need calculating can probably be significantly reduced.
Interesting problem! (TNT and FedEx probably have several PHDs working on this as we speak....)
I work for a small development company in the process of tackling this problem. We are building a social network (don't ask my why.. but the client pays..), and need to calculate the shortest path between any two members (IE, friend of a friend of a friend). This, essentially, is the traveling salesmen problem.
Although our solution may change, currently we are attempting to use the Dijkstra Algorithm as a stored SQL procedure. Of course, this approximates the shortest path, but the result is good enough for our needs, and based on the original post, probably good enough for a Google Maps app as well.
Holy fuck you Americans are lazy. "Um yeah we can't go hiking around a friggin' national park until we find the Provably Laziest Path." What's next, Yosemite sucks because there's no wifi? No gondola lift to Half Dome? No SUV access on El Cap? Want me to hold your 3oz digicam while you press the button to auto-focus to infinity?
Every time I use google for directions I'm left disappointed. I love the maps, hate the directions. I use google for virtually everything I can but if I'm trying to drive someplace I'm unfamiliar with I use mapquest. Google maps is reminiscent of the early directions we got on all of the map sites. Sometimes roads that cross do not intersect, sometimes there are other problems. I wish I could say googles directions were top notch but they're just not. I retry every 6 months only to be disappointed again.
...
Granted this may have no relevance on the mathmatical problem at hand
Most of our plots were US maps with state boundaries (which had long strings of continuous end-to-end line segments) plus a map of the user's network in one or more colors. The other main optimization that I did was a version of the background map that left out intermediate points on short line segments, so "A-B-C-D-E" would get compressed into "A-E" if the segments were short enough. It didn't change the map of Colorado much, but made a huge difference with the fractal Virginia/Carolina coastline and similar wiggly areas.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Here is a blog with source code.
http://gebweb.net/blogpost/2007/08/26/optimize-your-trips/
And the source code
http://gebweb.net/optimap/tsp.js
I had a job delivering auto parts and I looked at it as a kind of a traveling salesman problem.
Besides 'shortest route' I was trying for safest route, cheapest route, and smallest total miles in a workday.
The total dataset of customers was 20 and a full load was at most 5 customers.
As mentioned above, the loop always worked best if traveled it in a clockwise path due to the difficulty of making left hand turns where traffic drives on the right side of the street.
Eventually, I worked out the shortest loop path but then business needs kept messing up the ideal route.
When I get back to (my spare time project of) studying topology, I think I will revisit the traveling salesman problem, and see if there are ways in which a Jordan curve (a line connecting nodes with no crossing over) might yield some interesting theorms tied to the combinational puzzles of the TSP.
Great askslashdot question. Great bunch of posts eh?
TSP is most assuredly an NP-complete problem.
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 algorithms.)
As a very simple example of a real-world Traveling Salesman Problem, FedEx delivery trucks do this every single day.
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 each truck in a way to minimize the total cost.
Etc., etc. FedEx, UPS, DHL and the USPS are willing to throw lots of money at researchers in order to get a better handle on these problems.
Is here, strait from Steve lombardi, the Virtual Earth program manager. See also other pertinent answers here.
Animoog.org