+Chamma Posted January 27, 2009 Share Posted January 27, 2009 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 Quote Link to comment
eaparks Posted January 27, 2009 Share Posted January 27, 2009 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. Quote Link to comment
+trainlove Posted January 27, 2009 Share Posted January 27, 2009 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. Quote Link to comment
Motorcycle_Mama Posted January 28, 2009 Share Posted January 28, 2009 (edited) 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 Quote Link to comment
+JetSkier Posted January 28, 2009 Share Posted January 28, 2009 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 Quote Link to comment
+Chrysalides Posted January 28, 2009 Share Posted January 28, 2009 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. Quote Link to comment
+julianh Posted January 28, 2009 Share Posted January 28, 2009 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! Quote Link to comment
+PDOP's Posted January 28, 2009 Share Posted January 28, 2009 But Microsoft Streets and Trips has an optimize feature. More on this on the GPSBabel site (link) Quote Link to comment
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.