What online map software will choose the best multi-point route for me?

November 21, 2009 6:34 PM

Is there some online software/Web site that will take a list of addresses and generate the most efficient route to drive to all of them?

I want to drive around and look at houses in real-estate mode. I have a bunch of addresses, and I know generally where all of the places are, but I don't know the most efficient route to visit them all.

Is there some way to make GoogleMaps (or similar) put them in order for me and give me the best route to drive to all of them? I see how to use the "add another location" function to get a route that is made of A-->B-->C-->D, but in that case I would have to input them in the right order myself.

Does this question make sense? Am I the only one on the Internet who doesn't know how to do this? I feel like I might be ...

posted by mccxxiii to computers & internet (8 comments total)

That's the travelling salesman problem. In general, there's no way to get a computer to tell you the most efficient rout. There are obviously ways to get estimates, but I've never seen any online apps that do it.
posted by delmoi at 6:44 PM on November 21, 2009

Try this one out?
posted by GeekAnimator at 7:08 PM on November 21, 2009 [7 favorites]

The problem with the traveling salesman problem is that the only way to get God's solution is brute force. Which trying every possible route. For N stopping points, the brute force solution takes N-factorial time to fully search the solution space.

Genetic algorithms can find really good answers much more rapidly than that, but they aren't guaranteed to be the absolute best.
posted by Chocolate Pickle at 7:22 PM on November 21, 2009

Travelling salesman is hard, but not impossible. And you can find algorithms to get within say 50 percent of the best solution. This sounds bad, but the upper limit is not 100 percent; you can do way, way worse.

I should point out that TSP isn't quite the same as your problem. You don't want to visit every road intersection, but you do want the algorithm to consider them in routing you between points of interest.
posted by pwnguin at 10:20 PM on November 21, 2009

Wow, nice find, GeekAnimator!

FWIW, don't worry about the algorithmic complexity aspect. The TSP is one of those problems where there are approaches that do really well on real-world data even though the general case is quite difficult.
posted by hattifattener at 11:46 PM on November 21, 2009

GeekAnimator FTW! That's exactly what I needed, thanks!!
posted by mccxxiii at 8:52 AM on November 22, 2009

Not an online solution, but the GPS that I own is supposed* to do that.

* but I haven't read the manual enough, I haven't been able to get it to perform.
posted by Drasher at 11:56 AM on November 22, 2009

ZipperMaps

Full disclosure. Myself and a coworker of mine put that site together.
posted by miasma at 12:44 PM on November 22, 2009