Another question about traveling salesman problem

Joe · science forum beginner Joined: 25 Jun 2005 Posts: 22

I have been working on optimizing a route that I drive 7 days a week (42
stops altogether). All that I have been reading says that an optimum route
can not be guaranteed unless one uses the 'brute force' method, ie trying
all routes (which would be 42!, prohibitive, I think, for my computer
anyway)

Now yesterday, I visited a local computer store looking for street map
software for use with gps ( I have been using gps to keep track of the stops
along my route, but the mapping software I have is outdated, so I was
looking to upgrade). I found something called DeLorme Street Atlas 2006.
According to the salesperson, this will solve the traveling salesman problem
for me. All I have to do is enter (insert) the coordinates of my stops and
it will automatically generate the best route either by distance, or by
amount of time. They (as most places) have a no return policy on software,
so I am hesitant to buy it because I doubt that it will really do what I
need it to do automatically. Also, checking the DeLorme site, and with other
newsgroups having to do with gps, there is some confusion over whether it
will really do what the salesperson said. So I am wondering first if this
claim is credible. Also, it is made to be used in the vehicle, connected to
a laptop, which I don't own. .

Is there anything out there, available commercially that will simply take
the coordinates of your stops, and generate the optimum (or close, within,
say 5% of the optimum) solution that anyone knows of?

I have been making progress on my own using the 'nearest neighbor' method,
but I have to keep adding additional coordinates in for roads,
intersections, etc. so it does not go too far off track and start giving me
too many crossovers.

When I tackled this problem, I did it mostly for enjoyment and to learn a
little about combinatorial optimization. I know it's not something that has
a quick and dirty solution. If anyone has any ideas or opinions, I would
welcome them.

TIA,
Joe

richo@mcn.org · science forum beginner Joined: 04 Oct 2005 Posts: 2

Maybe you should post this at alt.satellite.gps

Rich Owings
http://www.MakeYourOwnMaps.com/
http://www.GPStracklog.com/

"We were desert mystics, my friends and I, poring over our maps as
others do their holy books." - Edward Abbey

Joe · science forum beginner Joined: 25 Jun 2005 Posts: 22

Hi Rich,

I did. Actually, I think it was at sci.geo.satellite-nav. A couple of the
guys over there said the same thing. It solves for an optimum route while
you insert the new stops between the beginning and the end of the route. I
bought the package today. So far, it looks like it is using the 'nearest
neighbor' algorithm, but I haven't looked at it that extensively yet. Still
reading the manuals and learning how to use it.

Thanks for the suggestion

Joe
<richo@mcn.org> wrote in message
news:1128470540.154708.199720@g44g2000cwa.googlegroups.com...

richo@mcn.org · science forum beginner Joined: 04 Oct 2005 Posts: 2

I had never played with that feature in any of my many mapping
programs, but I checked it out yesterday on Garmin's City Select
software, which is what I use for turn-by-turn directions on my GPS.
Sure enough, there is a feature that allows you to select a list of
waypoints, and the program will automatically calculate the route.
Pretty cool!

Rich Owings
http://www.MakeYourOwnMaps.com/
http://www.GPStracklog.com/

"We were desert mystics, my friends and I, poring over our maps as
others do their holy books." - Edward Abbey

Joe · science forum beginner Joined: 25 Jun 2005 Posts: 22

Hi Rich,

Yes, as I use it more and more, I am really liking it. Up to now, I have
only used my gps for bush wacking and plotting trails. We have a town forest
that no one knew where the trails were or where they led to, so one winter I
took my dogs up there regularly for their walks and just attached my gps12
to my belt. Using topo gps usa, I was able to plot all the trails and
donated them to the local conservation commission. They then posted them in
the local town library.

Anyway, this may be getting a little OT. I checked out your web sites,
pretty cool. I'll have to look at them a little closer. Thanks again for the
tips.

Joe

Google