+derandere Posted January 10, 2007 Share Posted January 10, 2007 Hi, I have tried long to solve this problem. But I don't have the Geocaching solution yet. Problem: How to find the shortest way between several waypoints (Caches)? This problem is based on a wikipedia article. Which you can read here. I would like to have a computer program which would calculate the shortest tour visiting different waypoints. But for right now I can't solve the problem. I would really like to have a tool which would be able to do that. Might even be a nice addition to gc.com. Even if you need to download it in order to save calculating power of GC servers. What do you think? Possible? Needed? Solved? DerAndere (Germany) Quote Link to comment
+9Key Posted January 10, 2007 Share Posted January 10, 2007 I load waypoints into MS Streets and Trips to get precise routing between caches. Is that what your asking? Quote Link to comment
+derandere Posted January 10, 2007 Author Share Posted January 10, 2007 It's not about geting derections from cache to cache. I am looking for a program which optimates distances on a route from cache to cache. There is an island in Germany which has a close to 100 caches on a quite small area. I would like to calculate the shortest way visiting all of them. DerAndere Quote Link to comment
+Wayfinders Posted January 10, 2007 Share Posted January 10, 2007 Being a Premium Member, you can view the caches using Google Earth. You would probably need a high speed connection. Quote Link to comment
+derandere Posted January 10, 2007 Author Share Posted January 10, 2007 Hm, alright. I just don't know how to explain. Have you followed the link in my first post? DerAndere Quote Link to comment
+VeryLost Posted January 10, 2007 Share Posted January 10, 2007 Hm, alright. I just don't know how to explain. Have you followed the link in my first post? As a programmer who tinkers in AI related applications sometimes, I'm familiar with the Traveling Salesman problem, and I understand what you're looking for. What I can't do, unfortunately, is give you any useful information about how to solve the problem. Surely there must be mapping software somewhere that lets you plot a whole bunch of points (caches), then calculates the optimum route to hit them all. However, I suspect that a commercial application that could do it might be priced a bit high for the average hobbyist. Quote Link to comment
+derandere Posted January 10, 2007 Author Share Posted January 10, 2007 Hi, right, that was the thing I was looking for. Thank you so much. Okay, seems to be a tough nut to crack. I guess that's why we did not have a clue to figure it out. All others, feel free to post your comment. DerAndere Quote Link to comment
+Wayfinders Posted January 10, 2007 Share Posted January 10, 2007 Hm, alright. I just don't know how to explain. Have you followed the link in my first post? No, I didn't. Interesting. The German in me wants to gather all the cache locatons in coordinates (not lat / long) and build one heck of a spreadsheet. The English in me wants to look a Google Earth for a few minutes and say "yep.....that should work okay". Good luck! Quote Link to comment
+derandere Posted January 10, 2007 Author Share Posted January 10, 2007 Well, alright. No problem. Might be a "typical" German approach. I am sorry for any missunderstandings ragarding how I try to explain my thoughts. Don't want to be mean to anybody. ;-) DerAndere Quote Link to comment
+DavidMac Posted January 10, 2007 Share Posted January 10, 2007 I load waypoints into MS Streets and Trips to get precise routing between caches. Is that what your asking? S&T has an "optimize stops" option on the route planning tab. Just individually add all caches to a route in any order (this may be time consuming unless there's an easy way that I don't know of), then click the button and wait. This should do what you need, unless there aren't any roads on the map for your area (my version of the program doesn't show any of the roads in Germany, but I wonder if there are separate versions for Europe and North America?) Quote Link to comment
+derandere Posted January 10, 2007 Author Share Posted January 10, 2007 There should be an European version. Thank you for that information. I will take a look at that. DerAndere Quote Link to comment
+J10fly Posted January 10, 2007 Share Posted January 10, 2007 Streets and Trips and add each waypoint as a stop and mark where you want to start from and end. Then use the optimize routes button. I do a lot of traveling sales visiting customers in the US and I use that all the time. Works great for me. Saves me tons of time!! Jayman11 Quote Link to comment
+Stunod Posted January 10, 2007 Share Posted January 10, 2007 S&T has an "optimize stops" option on the route planning tab. Just individually add all caches to a route in any order (this may be time consuming unless there's an easy way that I don't know of)... Draw a selection box on the map encompassing all the waypoints, right click in the box and select ADD PUSHPINS AS STOPS Quote Link to comment
+Markwell Posted January 10, 2007 Share Posted January 10, 2007 You can get the points in GSAK and convert them to Streets and Trips for importing. Streets and Trips does a optimize stops, but by NO means is it as complicated as the Traveling Salesman problem (TSP). I've optimised up to 40 or 50 stops on in Streets and Trips, and I know the TSP would barf at something that complicated. It must be a truncated version, but it actually works well. Quote Link to comment
+fizzymagic Posted January 10, 2007 Share Posted January 10, 2007 Have you followed the link in my first post? I think maybe part of the problem is that you didn't read the article carefully enough! I am half joking about that. The Traveling Salesman problem is an extremely well-known one, and it is one of a class of problems that are known as "NP-hard." Basically, that means that there is no way to determine which route through the points is optimal without trying them all. The algorithms that give "solutions" to the problem are generally able to give you a non-optimal route that is reasonably close to the optimal one, where the definition of "reasonably close" is very complicated. Implementing such an algorithm yourself might be a very good learning exercise, even though it is already done by many mapping programs. There is a group at Heidelberg that is working on these algorithms. You can read about it here. In particular, I followed links to an application known as Concorde that is supposedly quite good at solving these problems. It looks like it is free for research purposes. Quote Link to comment
+derandere Posted January 10, 2007 Author Share Posted January 10, 2007 The Program for Europe should be MS AutoRoute Euro 2007. Kind of weird changing names for the same programm just becaus it's for europe, but alright. That should be it. Which format to convert waypoints to using GSAK to open them in MS S&T (MS AR E2007 which should be the same)? DerAndere Quote Link to comment
+derandere Posted January 10, 2007 Author Share Posted January 10, 2007 I am half joking about that. That's alright, no problem with that! I read the German text on wiki, might have missed that. Sorry for wasting your time. Derandere Quote Link to comment
+sbell111 Posted January 10, 2007 Share Posted January 10, 2007 The Program for Europe should be MS AutoRoute Euro 2007. Kind of weird changing names for the same programm just becaus it's for europe, but alright. That should be it. Which format to convert waypoints to using GSAK to open them in MS S&T (MS AR E2007 which should be the same)? DerAndere Export them as Streets and Trips CSV. Quote Link to comment
+TetrAmigos Posted January 10, 2007 Share Posted January 10, 2007 derandere, I know exactly what you are looking for -- I would love to use that sort of utility myself. As it stands, I usually only travel in the United States and as such I use Mapopolis on my PDA and GPXtoMaplet to pick the "seemingly" most effective routing but it's always hand-to-mouth, point-to-point. I'd love to be able to print out (or display) a route like the one you are talking about, even if it took my PC an hour to compute! Quote Link to comment
+derandere Posted January 10, 2007 Author Share Posted January 10, 2007 Thanks for all the discussion guys. I appreciate all your ideas. I am quite happy with all the posted solutions. Got all the information I wanted to have. Keep on posting as you like. International time diffrence is forcing me to leave the computer in a couple of minutes. DerAndere Quote Link to comment
+derandere Posted January 10, 2007 Author Share Posted January 10, 2007 just seems like codebraking, and brute force method... no way to solve it perfectly... DerAndere Quote Link to comment
robertlipe Posted January 10, 2007 Share Posted January 10, 2007 Autoroute is the same as S&T in this regard. The two questions asked are answered somewhat graphically at http://www.gpsbabel.org/formats/s_and_t/Im...Trips_2003.html and http://www.gpsbabel.org/formats/s_and_t/TripPlanning.html NP nature of TSP aside, any "one heck of a spreadsheet" approach that doesn't have access to road and routing data (exits, rivers, etc.) for any but the most trivial cases (e.g. all the points are in one part) is essentially doomed. Quote Link to comment
+DavidMac Posted January 10, 2007 Share Posted January 10, 2007 Draw a selection box on the map encompassing all the waypoints, right click in the box and select ADD PUSHPINS AS STOPS And I always assumed that feature was used only to zoom the map. Thanks for the tip. Quote Link to comment
+BigFurryMonster Posted January 10, 2007 Share Posted January 10, 2007 If you find any useful tool for a limited number of point, please let me know. I'm looking to base a cache on such a problem. Quote Link to comment
+derandere Posted January 10, 2007 Author Share Posted January 10, 2007 I thing there is no such tool combining geocaching and the TSP...right now... just keep on searching for what you are looking for... all of this seems to be requiring some excellent AI, coding and math skills. I hope I didn't get you wrong. DerAndere Quote Link to comment
+BBWolf+3Pigs Posted January 10, 2007 Share Posted January 10, 2007 I thing there is no such tool combining geocaching and the TSP...right now... just keep on searching for what you are looking for... all of this seems to be requiring some excellent AI, coding and math skills. I hope I didn't get you wrong. DerAndere This is not a trivial problem. United Parcel Service (UPS) doesn't just look at distance between stops, but also the number of left hand turns! Since a left hand turn means crossing traffic, minimizing the lefts will reduce wait time, gas used, and chances for accidents. Quote Link to comment
+ClydeE Posted January 10, 2007 Share Posted January 10, 2007 Not terribly sophisticated, but GSAK does have a macro called Cache Raid that does go some way to achieving this goal. Quote Link to comment
+derandere Posted January 10, 2007 Author Share Posted January 10, 2007 Didn't mean to say that it is trivial. It's all about optimizing. Optimizing means that the outcome is not likely to be perfect, right? For my part of the problem, I will just take "English" (see above) aproach, get there and do it the way I feel like. DerAndere Quote Link to comment
GermanSailor Posted January 10, 2007 Share Posted January 10, 2007 (edited) Hi, what you could do is write a program which gets the data from every cache to every cache and puts this information in a matrix. (Like the ones found on paper charts to figure out distances between towns). For example __A B C D A _ 5 2 7 B 5 _ 3 6 C 2 3 _ 4 D 7 6 4 _ And then let the program always find the a route to the nearest new cache unless all are found. Lets say starting at A, one would go next to C(2), then to B(3) then to D(6). You would have travelled 11 units, compared to the 12 you would have done by following in the alphabetical order. This system ist far from perfect and is only likely to produce a good solution, but it's fairly easy. It's has been quite a while since I had to deal with the travelling salesman problem. But I remember that the method described above is one of the solutions and by far not the best. If you have time or a fast enough computer, a kind of brute-force approach might be the solution. Let the computer, again using the precalculated matrix, calculate all possible solutions and pick the shortest one. You could considerably reduce the required amount of calculations by defining a threshold (the number which you already have by using the first method) after which calculations on this combination stop. I hope what I wrote is not too confusing, not easy to write about such stuff in a foreign language. GermanSailor Edited January 10, 2007 by GermanSailor Quote Link to comment
+derandere Posted January 10, 2007 Author Share Posted January 10, 2007 Thanks for all replies. Stayed up long to get to read all of this. Many thanks from Germany Take care. DerAndere Quote Link to comment
+ePeterso2 Posted January 12, 2007 Share Posted January 12, 2007 I'm guessing that those caches are NOT evenly distributed across the map and that they are NOT connected to their nearest neighbors in a roughly equal manner. That would imply that there are probably clusters of caches out there ... you can probably see them visually on Google Earth (as other posters have suggested). Instead of trying to use every cache as a stop, why not just pick one cache within each cluster, then have S&T plot the route for that simplified problem? Quote Link to comment
+sbell111 Posted January 12, 2007 Share Posted January 12, 2007 What's the downside of just having S&T (or mappoint) chug out a solution on the entire group? Quote Link to comment
+TetrAmigos Posted January 12, 2007 Share Posted January 12, 2007 sbell, could you elaborate a bit? Quote Link to comment
+sbell111 Posted January 12, 2007 Share Posted January 12, 2007 (edited) Doesn't optimizing the stops in S&T do what is being asked? Wouldn't the weights all be the same, for our purposes? Edited January 12, 2007 by sbell111 Quote Link to comment
+TetrAmigos Posted January 12, 2007 Share Posted January 12, 2007 I couldn't say, but you've got my ear. So MS Streets and Trips can spit out an optimized route based on GPX imports of waypoints? Quote Link to comment
+nekom Posted January 12, 2007 Share Posted January 12, 2007 The problem is one of mathematics, not programming. It's easy to write a program to do it, it will just never end, not in any reasonable amount of time at least. Same thing with cracking public key encrpytion. The code is easy, there just isn't enough processing power on earth to run it in a reasonable amount of time. So the answer is that it can't be done I guess. Quote Link to comment
+sbell111 Posted January 12, 2007 Share Posted January 12, 2007 I couldn't say, but you've got my ear. So MS Streets and Trips can spit out an optimized route based on GPX imports of waypoints? Yes. Easy peasy. Of course, nekom is correct in that the route may not be 'perfectly' optimized. It will be quite good, however. Quote Link to comment
+Jhwk Posted January 12, 2007 Share Posted January 12, 2007 so, you can't just pick one, find it, and then hit "goto" next closest cache? guess I'm too dense for this one. Quote Link to comment
+sbell111 Posted January 12, 2007 Share Posted January 12, 2007 so, you can't just pick one, find it, and then hit "goto" next closest cache? guess I'm too dense for this one. To tell you the truth, that's how I usually do it. The problem is, you might end up getting all the 'closest' ones in the center of the target area and then waste a bunch of time cleaning out the edges. Quote Link to comment
+Markwell Posted January 12, 2007 Share Posted January 12, 2007 ...there just isn't enough processing power on earth to run it in a reasonable amount of time. So the answer is that it can't be done I guess. To get it PRECISE - true. But the close approximation or "good enough" is feasible, and not too bad of a result. On my personal map of unfound caches within a 60 minute trip of my house - only caches of a type and style that I choose - and including some other GPS related spots for other games that I play, there's about 85 locations. That's within a 30 minute drive of my house (according to Streets and Trips). I had S&T select all of those points and them "optimize" them for the route. I figured that 87 locations (my house as first and last point) would take a long time for the processor to crank and answer. End result is that within about 60-90 seconds, Streets and Trips had a reasonable route selected that had minimal backtracking and found quick routes to and from areas, so that (if I wanted to), I could hit these 85 locations (without taking into account walking speed and time at the caches) in about 10 hours and 13 minutes. So - the absolute mathematical problem of the Traveling Salesman may not have a complete answer, but if the computer can come up with a close approximation, isn't that good enough for what the OP is looking for? Quote Link to comment
+StarBrand Posted January 12, 2007 Share Posted January 12, 2007 Like Markwell - I ran a test on 2004 S&T with 225 geocaches within 50 miles of here. On a 1.4GHz P4 system it took just over 3 minutes to come up with a quite reasonable route to hit all of them. Quote Link to comment
+sbell111 Posted January 12, 2007 Share Posted January 12, 2007 For anyone that is going to really use this method, remember to put your home location as the first and last stop. Otherwise, it will crank out the best solution, but you might end up thirty miles away from where you want to be. Quote Link to comment
+Papa & Mama Dabob Posted January 20, 2007 Share Posted January 20, 2007 Great discussion! Now all I need is a simple way to enter a whole lots of waypoints into S&T----- Papa Dabob Quote Link to comment
+sbell111 Posted January 20, 2007 Share Posted January 20, 2007 Great discussion!Now all I need is a simple way to enter a whole lots of waypoints into S&T----- Papa Dabob Pocket queries and GSAK will get it done for you. Open your PQ in GSAK and export it to a 'Microsoft Streets & Trips text file'. Import this file into S&T. Easy Peasy. Quote Link to comment
+The Leprechauns Posted January 20, 2007 Share Posted January 20, 2007 Remember that optimizing a route can suffer from the same drawbacks as autorouting. If there is a cache way, way back in the far corner of a park that's bordered on three sides by private property, Streets and Trips or your GPS' autorouting software will tell you to drive to the closest neighbor's driveway and cut through their yard to the cache. The software is proud of itself for delivering you to a point 350 feet away from the cache, when in reality you are facing a .7 mile walk that starts on the next road over. Assume further that there's a park and grab just a little ways down the road from the entrance to the park with the nice hike (P&G#1) and a park and grab at the street corner near the park neighbor's house (P&G#2). Streets and Trips will route you to Park Cache, then P&G#2, then P&G#1. The correct route is Park Cache, P&G#1 then P&G#2. This requires a combination of human intelligence, map study and parking coordinates (if included as an Additional Waypoint). Quote Link to comment
+sarhound Posted January 21, 2007 Share Posted January 21, 2007 I've been using S&T for over a year now, loading in anywhere from 75 to 100 caches in a specific region, then letting S&T figure out the best way to navigate them. It does reasonably well, but I do scan the maps and do a little rearranging of some of the stops, since I like to work from farthest to nearest when some caches string themselves out along the periphery. Admittedly, I'll never make my way through the entire list at one time, but I can start at any point that I want and work in a relatively systematic fashion back along the route. It might take a few weeks to knock out a hunk of the list, but at least it's in the cachemobile for a spontaneous caching trip. 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.