Jump to content

Creating The Shortest Route to the 25 Nearest Geocache Waypoints


Guest paul_stratton

Recommended Posts

Guest paul_stratton

I've created a spreadsheet and procedure on explaining how to create the shortest route to the nearest 25 Geocache waypoints. I use the waypoints downloaded using EasyGPS then use the GPS and a spreadsheet to do the computations.

 

Enjoy! The files, in a compressed zipped file, are located in the "Friends" folder at

http://briefcase.yahoo.com/bc/strattonpaul

 

let me know what you think!

 

paul_stratton@sbcglobal.net

Link to comment
Guest ClayJar

I'm just waiting for someone to solve the travelling salesman problem so that I can schedule the rest of the caches optimally... Unfortunately, it *is* an example of an NP-complete problem, and solving it would be almost the equivalent of finding alien life. icon_smile.gif

 

(Mind you, I'm not saying anything against this. I think it's cool, but I just wish it would scale to N caches. icon_biggrin.gif)

 

[This message has been edited by ClayJar (edited 27 January 2002).]

Link to comment
Guest ClayJar

I'm just waiting for someone to solve the travelling salesman problem so that I can schedule the rest of the caches optimally... Unfortunately, it *is* an example of an NP-complete problem, and solving it would be almost the equivalent of finding alien life. icon_smile.gif

 

(Mind you, I'm not saying anything against this. I think it's cool, but I just wish it would scale to N caches. icon_biggrin.gif)

 

[This message has been edited by ClayJar (edited 27 January 2002).]

Link to comment
Guest infosponge

It's not all that bad if you use a mix of genetic algorithms and lots of CPU's. Well, of course you can get good solutions quickly, but proving that their the best is of course the NP-complete beast. icon_smile.gif

 

(I used to work for a company that specialized in operations research software)

 

quote:
Originally posted by ClayJar:

I'm just waiting for someone to solve the travelling salesman problem so that I can schedule the rest of the caches optimally... Unfortunately, it *is* an example of an NP-complete problem, and solving it would be almost the equivalent of finding alien life. icon_smile.gif


Link to comment
Guest infosponge

It's not all that bad if you use a mix of genetic algorithms and lots of CPU's. Well, of course you can get good solutions quickly, but proving that their the best is of course the NP-complete beast. icon_smile.gif

 

(I used to work for a company that specialized in operations research software)

 

quote:
Originally posted by ClayJar:

I'm just waiting for someone to solve the travelling salesman problem so that I can schedule the rest of the caches optimally... Unfortunately, it *is* an example of an NP-complete problem, and solving it would be almost the equivalent of finding alien life. icon_smile.gif


Link to comment
Guest ClayJar

quote:
Originally posted by infosponge:

Well, of course you can get good solutions quickly, but proving that they're the best is of course the NP-complete beast. icon_smile.gif


If we can have such interesting discussions about antenna characteristics, tracklogs, reception, and all, I figure we'd have to do the NP-complete solution to satisfy us all. Of course, for the more impulsive among us, myself included, having a "good enough" solution is fine, and having a zeroth order approximation (i.e. "Um, let's go... that way.") is even fine. icon_wink.gif

Link to comment
Guest ClayJar

quote:
Originally posted by infosponge:

Well, of course you can get good solutions quickly, but proving that they're the best is of course the NP-complete beast. icon_smile.gif


If we can have such interesting discussions about antenna characteristics, tracklogs, reception, and all, I figure we'd have to do the NP-complete solution to satisfy us all. Of course, for the more impulsive among us, myself included, having a "good enough" solution is fine, and having a zeroth order approximation (i.e. "Um, let's go... that way.") is even fine. icon_wink.gif

Link to comment
Guest paul_stratton

ClayJar,

 

I've created *ANOTHER* MS-Excel workbook to compute the shortest route to the

nearest *250* random Lat/Lon waypoints, worldwide. This workbook took

approximately ten minutes to complete the computations on my 400MHz Pentium

II. Your times will vary.

 

The macro to do the computations can be invoked using Ctrl+Shift+L.

 

Enjoy! The Excel workbook, in a compressed zipped file, are located in the

same "Friends" folder at:

http://briefcase.yahoo.com/bc/strattonpaul

 

There's the theoretical side of this type of TSP analysis. The Excel

workbook provides a brute force method. There are other methods that can

save time. But on today's PCs, the horsepower is there.

 

The shortest route idea started out as a simple question. If I went

somewhere for vacation and wanted to see as many sights as I could in one

day, how would I do it?

 

The idea about geocache points was just another application of the same

question and possible solution. The same TSP solution principals can be

applied to delivery companies, service personnel, telephone/cable

installers, and GEOCACHE hunting.

 

I just wish I could use real-world mapping software (e.g., Garmin's

Mapsource) to determine the shortest distances or shortest times. If I could

work out the interfaces between a waypoint database and the mapping

software, it could be done. However, it would be really slow, even on some

of the fastest machines of today...

 

paul_stratton@sbcglobal.net

Link to comment

I use MS Streets and Trips to visualize and plan for my GC adventures.

 

Throught Geobuddy or Panterra you can export the .LOC file as a CSV and then import it into S & T. From there you select the caches you want to go to, add them to your route and the select "optimize route".

 

Not only will this optimize by distance but also by the actual roads too!

 

I showed a friend of mine how to do this and now he maintains a site for Canada... http://ian.kenetic.com/

 

Cheers!

 

Rob

Link to comment
Guest paul_stratton

I've looked at MS Streets & Trips before and found it lacking. However, I didn't know that it could take what is essentially 26 random waypoints and put them in a route and then sort the waypoints to create the most efficient route by computing the shortest distances between each one. Cool! I'll have to look at the latest MS Streets & Trips again!

Link to comment
Guest philipTB

I've just thrown together a Travelling Salesman solver designed specifically for Geocaching and based upon genetic algorithms.

 

It's still very buggy - especially the data entry part - but it solves a 30 cache route in about 15 seconds. The route is displayed graphically as it converges and can be printed out in its optimised order.

 

If it's of interest I might be persuaded to polish it up a bit.

 

Find it on

 

http://briefcase.yahoo.com/bc/niknelb

 

in the Software folder under CR.EXE

Link to comment

I like it. Have you worked on the CR.EXE since the initial release? I'd like to try it with more waypoints... ...say, 250 or so.

 

quote:
Originally posted by philipTB:

I've just thrown together a Travelling Salesman solver designed specifically for Geocaching and based upon genetic algorithms.

 

It's still very buggy - especially the data entry part - but it solves a 30 cache route in about 15 seconds. The route is displayed graphically as it converges and can be printed out in its optimised order.

 

If it's of interest I might be persuaded to polish it up a bit.

 

Find it on

 

http://briefcase.yahoo.com/bc/niknelb

 

in the Software folder under CR.EXE


Link to comment

quote:
Originally posted by paul_stratton:

I like it. Have you worked on the CR.EXE since the initial release? I'd like to try it with more waypoints... ...say, 250 or so.

 

quote:
Originally posted by philipTB:

I've just thrown together a Travelling Salesman solver designed specifically for Geocaching and based upon genetic algorithms.

 

It's still very buggy - especially the data entry part - but it solves a 30 cache route in about 15 seconds. The route is displayed graphically as it converges and can be printed out in its optimised order.

 

If it's of interest I might be persuaded to polish it up a bit.

 

Find it on

 

http://briefcase.yahoo.com/bc/niknelb

 

in the Software folder under CR.EXE



Link to comment

quote:
Originally posted by paul_stratton:

I've created a spreadsheet and procedure on explaining how to create the shortest route to the nearest 25 Geocache waypoints. I use the waypoints downloaded using EasyGPS then use the GPS and a spreadsheet to do the computations.

 

Enjoy! The files, in a compressed zipped file, are located in the "Friends" folder at

http://briefcase.yahoo.com/bc/strattonpaul

 

let me know what you think!

 

paul_stratton@sbcglobal.net


Link to comment

It looks like the CR.EXE file was removed from the http://briefcase.yahoo.com/bc/niknelb URL.

 

Maybe the original author might put it, or an update to it there again?

 

OOPS! The "Friends" folder was inadvertently made "private". It's now open to the public. My Mistake! Enjoy! My files, all are compressed zipped files, are located at:

http://briefcase.yahoo.com/bc/strattonpaul

 

let me know what you think!

 

paul_stratton@sbcglobal.net

 

quote:
Originally posted by zapped:

quote:
Originally posted by Mtn_Bkng_Dave:

IN THE FRIENDS FOLDER?


 

Um, no, that's an empty folder when I go into it. Weird thing is at the top level it shows "4 items" in "Friends" folder.


 

[This message was edited by paul_stratton on March 27, 2002 at 06:34 PM.]

Link to comment

I haven't taken this TSP solver using Genetic Algorithms because until recently I'd had no feedback!

 

I'm not sure why the folder on Yahoo turned private - it seems to be ok now. If anyone has problems with downloading it e-mail me and I'll try and help.

 

I'll do a few timing tests on bigger routes and report back.

Link to comment

OK, where's a free website to put these files? Yahoo's briefcase "feature" doesn't seem to be working.

 

I just don't understand. I set the Yahoo briefcase directories and folders to all be "Public" access and "I" can see it. I even sign out of Yahoo and login as a different user and I can still see it. Weird.

 

Tell ya what, I'll put them in a special directory on my PC and allow everyone FTP access. Do you have an FTP program on your PC? If so, connect to the IP address of 66.137.227.192. Use the temporary login account of "gps" and the password is also "gps". Use lower-case.

 

If this doesn't work, I'll just email them to all that ask. The total size of everything is less than 2MB. The IP address is valid until I reboot... (Windows, Don't Lock Up On Me Now!)

 

Paul

icon_frown.gif

Link to comment

OK, where's a free website to put these files? Yahoo's briefcase "feature" doesn't seem to be working.

 

I just don't understand. I set the Yahoo briefcase directories and folders to all be "Public" access and "I" can see it. I even sign out of Yahoo and login as a different user and I can still see it. Weird.

 

Tell ya what, I'll put them in a special directory on my PC and allow everyone FTP access. Do you have an FTP program on your PC? If so, connect to the IP address of 66.137.227.192. Use the temporary login account of "gps" and the password is also "gps". Use lower-case.

 

If this doesn't work, I'll just email them to all that ask. The total size of everything is less than 2MB. The IP address is valid until I reboot... (Windows, Don't Lock Up On Me Now!)

 

Paul

icon_frown.gif

Link to comment

http://groups.yahoo.com/group/gps-v/files/Geocache_Routing_Tools_V1.0.2.zip

 

Taking the great hint from PhilipTB, I've placed the Garmin GPS-V version of my spreadsheet (version 1.0.2) that computes and graphically plots the shortest route to 25 waypoints (Geocache or otherwise) at the above URL.

 

Hopefully this one is readable by all.

 

paul_stratton@sbcglobal.net

 

[This message was edited by paul_stratton on March 30, 2002 at 10:58 AM.]

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...
×
×
  • Create New...