Can anyone help me find efficient routes between mutliple points?
July 13, 2010 1:10 PM   Subscribe

Can you point me to a tool that will plot the most efficient route between multiple addresses?

A few months ago a very helper person pointed me to BatchGeo. This has changed my life, as I have to generate maps regularly.

This was asked several years ago.

I also regularly need to travel between multiple addresses. Finding the most efficient route automatically would truly change my life again. Is this something anyone can point me to? A program that generates driving directions--or even just ranks locations according to proximity?

Thank you in advance
posted by jefficator to Travel & Transportation (20 answers total) 3 users marked this as a favorite
 
In general this is a very difficult problem to solve efficiently. It falls into a class of problems known as NP-complete in theoretical computer science.

http://en.wikipedia.org/wiki/Travelling_salesman_problem
posted by minicloud at 1:14 PM on July 13, 2010


I mean, GoogleMaps yes?

I'm not entirely clear about what you're trying to do, but you can enter a route with multiple destinations, and you can drag the routes around on the map to avoid doubling back. Is this not what you're looking for?
posted by valkyryn at 1:14 PM on July 13, 2010 [1 favorite]


Travelling Salesman Problem?

Fascinating. That's just it entirely. I need to visit 25 locations in a given city, and I would like to optimize the route between them.

How remarkable that there's a name for the problem.
posted by jefficator at 1:19 PM on July 13, 2010


Microsoft MapPoint does this (I don't know if they still make it). Noted correctly above, the TSP is NP-hard and can't be solved perfectly for a large set of addresses without taking *forever*. MapPoint uses some suboptimal algorithm (some variation on the greedy algorithm, I'm guessing), but it still produces pretty good results. I've used it on 50+ addresses and it doesn't take too long.
posted by zvs at 1:20 PM on July 13, 2010


More on this functionality in MapPoint.
posted by zvs at 1:22 PM on July 13, 2010


Map Quest Route Planner? Up to 25 addresses and you can sort by shortest time or shortest distance.
posted by BlooPen at 1:23 PM on July 13, 2010


jefficator: “How remarkable that there's a name for the problem.”

I think the really remarkable thing is that this is one of those few simple, seemingly straightforward computational problems for which the answer is: "this is impossible." Sort of unfortunate, but that's how it goes.

On the other hand, if you figure out a way to do this, you could probably be mildly famous.
posted by koeselitz at 2:22 PM on July 13, 2010


On the other hand, if you figure out a way to do this, you could probably be mildly famous.

Sometimes I know I am a moron when I think the solution to a problem is incredibly simple and then I need someone else to point out why I am wrong.

Seems like you put in your 25 locations. You pick your starting location. The computer then calculates which locations is closest to Location#1. This is Location#2. The computer then calculates which location is closet, exluding Location#1. And so on until all the locations are met?
posted by jefficator at 2:29 PM on July 13, 2010


That will get you a least-cost spanning tree. (You should now look up why that isn't a solution of TSP.)
posted by phliar at 2:35 PM on July 13, 2010


jefficator: That seems like a good way to start, but you could end up crisscrossing the city at the end.
posted by madcaptenor at 2:38 PM on July 13, 2010


The problem is that once you get above, say 10 addresses, there end up being a HUGE number of calculations. The NP-hard bit is a way of saying there is no other (known) way of solving it except testing each one. There are a lot of short cuts out there to get a reasonably efficient route but no way to guarantee the result without testing each possibility.

Georgia Tech has a great TSP page which includes a Google Maps TSP application.
posted by ChrisHartley at 2:39 PM on July 13, 2010 [1 favorite]


To follow up to my own answer, as I am want to do, and roughly quoting the TSP page I linked above: There are (n-1)!/2 routes for n number of stops, assuming the distance/cost from X to Y is equal to the distance from Y to X. With 7 stops there are 360 routes. With 8 stops there are 2,502. With 10 there are 181,440. It goes up quite quickly from there.
posted by ChrisHartley at 2:45 PM on July 13, 2010


jefficator: The computer then calculates which location is closet, exluding Location#1. And so on until all the locations are met?

This is called a greedy algorithm. They work for some problems (like minimum spanning tree) but not for TSP. The reason it won't work for TSP is essentially that early decisions to take a short edge can force you to take a very long edge later.

What you really want here is an approximation scheme (see the TSP wiki page). With 25 locations, the problem is too big to solve with brute force, but you can usually come pretty close with a polynomial-time approximation algorithm.

and in this case, you're not making a minimum spanning tree because you're always adding the edge to the most recently visited node
posted by qxntpqbbbqxl at 3:21 PM on July 13, 2010


Also note that your problem is non-Euclidean because distance from A to B is not necessarily the same as B to A.
posted by qxntpqbbbqxl at 3:23 PM on July 13, 2010


How remarkable that there's a name for the problem.

Not only a name, but as some of the responses here hint, it's a problem that any computer science major (and many self-taught programmers) knows. Very interesting and ultimately complex problem that lends itself to teaching about algorithm complexity, heuristics, and all sorts of other CS subjects.
posted by wildcrdj at 3:31 PM on July 13, 2010


there are many approaches, such as distributed genetic programming, for finding good solutions to this problem that scale into the many thousands of nodes. never seen one prettied up for consumer use but i would expect to see them deployed soon.
posted by paradroid at 3:36 PM on July 13, 2010


Just today I had to restrain myself from butting into a conversation between two of our sales guys who were trying to solve the TSP in Excel.
posted by odinsdream at 4:20 PM on July 13, 2010 [5 favorites]


I think Route4Me does exactly what you're asking, but maybe not with as many addresses as you need.
posted by dayintoday at 5:54 PM on July 13, 2010


I just tried Route4Me and it is useless. See my first example:
http://route4me.com/shareRoute.php?route_id=c5203f2488fb7c085768aa2a980bb71b
posted by bystander at 8:55 PM on July 13, 2010


Then there's this web tool that claims to do what you want.
posted by exphysicist345 at 9:09 PM on July 13, 2010


« Older I'm like two, three days from unspooling...   |   Help! My yard has fleas. Newer »
This thread is closed to new comments.