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
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
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]
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]
Response by poster: 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
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
posted by zvs at 1:20 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
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
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
Response by poster: 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
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
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
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]
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
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
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
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
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
posted by paradroid at 3:36 PM on July 13, 2010
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
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
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
posted by exphysicist345 at 9:09 PM on July 13, 2010
This thread is closed to new comments.
http://en.wikipedia.org/wiki/Travelling_salesman_problem
posted by minicloud at 1:14 PM on July 13, 2010