Jump to content

Travelling Salesman Problem


derandere

Recommended Posts

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. :laughing:

 

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)

Link to comment

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

Link to comment

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.

Link to comment

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!

Link to comment

I load waypoints into MS Streets and Trips to get precise routing between caches.

Is that what your asking? :laughing:

 

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?)

Link to comment

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

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

Link to comment

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.

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

Link to comment

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

Link to comment

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.

Link to comment

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!

Link to comment

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

Link to comment

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.

Link to comment

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.

Link to comment

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 by GermanSailor
Link to comment

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?

Link to comment

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.

Link to comment
so, you can't just pick one, find it, and then hit "goto" next closest cache?

 

guess I'm too dense for this one. :D

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

Link to comment

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

Link to comment

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.

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