Shortest route for group of waypoints

[+Chamma]

Is there any maping software or program that will tell me the shortest road distance between a set of points. I have a program that will tell me point to point strait line distance, but where I want to go there is a river with few bridges, so it wont take that into account. My wife also wants to use it to run errands down is Nashville. I think it would be helpful for many uses.

 

Thanks

[eaparks]

Without knowing what type of GPS you have it is difficult to give very useful information. But, if you have a Garmin, you would need Garmin's City Navigator program. Then using Mapsource you could create a route from whatever stop/waypoint you want your first stop to be and create via waypoinsts for the other stops until you get to your final stop.

 

Some of the Nuvi models will do what you are wanting without additional software.

[+trainlove]

That's an NP-complete mathematics problem that many mathematicians have been working on since at least the Renaissance. There is no 'absolute' shortest solution, but some GPS makers have good algorithms that are somewhat good.

 

But I think that's only for point-to-point great circle routing among your set of caches, not street routing which really adds about a million dimensions to the problem. All street routing software I've seen that has more than 2 waypoints in a route only use the first and the last one.

[Motorcycle_Mama]

MapSource won't give you the optimized route. It will only give the the Shortest Distance or Fastest Time based on the order in which YOU input the Waypoints into the route.

 

But Microsoft Streets and Trips has an optimize feature.

Edited January 28, 2009 by Motorcycle_Mama

[+JetSkier]

My Magellan CrossoverGPS will optimize a set of waypoints for street routing. I just did a test with 20 waypoints all within 10 miles of each other. It took about 60 seconds to compute.

 

JetSkier

[+Chrysalides]

That's an NP-complete mathematics problem that many mathematicians have been working on since at least the Renaissance. There is no 'absolute' shortest solution, but some GPS makers have good algorithms that are somewhat good.

However, assuming you're starting at one point, and ending at another, and that the set of waypoints is limited, a brute force search is feasible.

[+julianh]

Is there any maping software or program that will tell me the shortest road distance between a set of points. I have a program that will tell me point to point strait line distance, but where I want to go there is a river with few bridges, so it wont take that into account. My wife also wants to use it to run errands down is Nashville. I think it would be helpful for many uses.

 

Thanks

This is the so-called "Travelling Salesman Problem" - visit all addresses on a list, using the shortest total journey distance.

 

Check out "Optimap" which runs using Google Maps on-line: http://gebweb.net/optimap/

 

Type in all of your addresses, and then find the shortest closed loop (i.e. takes you back to your start point at the end of the loop), or shortest one-way trip (starts at your first point, ends at your last point, and optimises all others in between).

 

There's no GPS interface, but at least it will give you the optimum sequence to visit the list of addresses, and then you can create a route on your GPS by entering the destinations in the optimum sequence. You can also get a list of (lat, long) coordinates in the optimum sequence, for those whose GPSRs don't have street map data.

 

Hope this helps!

[+PDOP's]

But Microsoft Streets and Trips has an optimize feature.

 

More on this on the GPSBabel site (link)