Jump to content

Shortest route for group of waypoints


Chamma
Followers 3

Recommended Posts

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

Link to comment

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.

Link to comment

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.

Link to comment
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.

Link to comment

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!

Link to comment

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.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
Followers 3
×
×
  • Create New...