# Creating The Shortest Route to the 25 Nearest Geocache Waypoints

Followers 0

## Recommended Posts

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

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.

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

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

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.

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

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

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.

(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.

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.

(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.

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.

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.

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.

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.

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

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

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

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!

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

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

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

I would be interested in the Traveling Salesman Route Solver but I clicked on the posted link and could not find a program file to try.

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

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.

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.]

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.

Both of your briefcases are still empty, at least for me. Sorry for the nagging, it's just that I'd like to give your routing method a try

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

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

I've posted my route solver in the Files section of the Meridian Group at Yahoo

http://groups.yahoo.com/group/Magellan_Meridian/files

See if that works for you

I got it from the Files section of the Magellan Meridian group. Fired it up & it worked great on your sample set. Thanks so much for your perseverance!

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.]

## 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.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.