Slashdot Mirror

← Back to Stories (view on slashdot.org)

Where's the Traveling Salesman for Google Maps?

Posted by samzenpus on from the waffle-house-mod-soon-to-come dept.

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

5 of 125 comments (clear)

  1. Re:What's the point? by etymxris · · Score: 5, Insightful

    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.

  2. Scientific American Article on this by Precipitous · · Score: 3, Insightful
    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. "

    --
    My motto: "A cat is no trade for integrity."
  3. Right here... by jberryman · · Score: 5, Insightful

    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.

  4. Re:NOT a travelling salesman problem. by cnettel · · Score: 3, Insightful

    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.
  5. Re:What's the point? by TheLink · · Score: 3, Insightful

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

    --