Automatic Routing Optimisation

Cached · Post by **Cached** » 17 October 05 4:35 pm

Hi

Destinator (PDA) will let you put in a string of waypoints (addresses) and then calculate the best way round them - you don't have to specify the exact order.

Does anybody know of any PC software that can do this? Nroute can't?

TIA

Sam

Geodes · Post by **Geodes** » 17 October 05 6:41 pm

Mapsource has auto-routing

Cached · Post by **Cached** » 17 October 05 10:01 pm

I'm looking for an auto-routing solution that can optimize a route.

What I want to be able to do is say I want to visit point A, B, C, D & E and for the S/W to tell me that I need to go to A, D, C, E and then B because that is more efficient. And then autoroute me down that route.

Mapsource/nRoute will send me to A, B, C, D & E in that order, everytime, never suggesting that I should go in a different order.

Destinator has a demo, if you watch it far enough through to see the "Trip Planner" and "Trip Optimizer" then you can see what I mean first hand. http://www.destinator.com.au/index.html

Catchya

sam

gunnell&pandaabear · Post by **gunnell&pandaabear** » 17 October 05 10:47 pm

Get yourself a Garmin 2610. It has a function called travelling salesman that will do what you require.

No other garmin will do it.

Cached · Post by **Cached** » 17 October 05 11:01 pm

I'd like to do it on the PC...

Chwiliwr · Post by **Chwiliwr** » 18 October 05 12:35 pm

I think you might have trouble finding a PC version that will work the way you want it to from geocache coordinates.

The only PC versions that I have seen are based on street addresses and uses the road network to optomise the route. They all cost mega dollars and use proprietry databases.

Geodes · Post by **Geodes** » 18 October 05 12:55 pm

I remember one of the first computers I ever programmed (an ICL 1901A) had a "Travelling Salesman" function in its maths library. It certainly could be a useful tool - just select a group of caches and it would provide the shortest route to get them all

<P>I think I'll do some research into this problem - it sounds like fun.

Mind Socket · Post by **Mind Socket** » 18 October 05 2:46 pm

Interesting idea.

Cached, do you want to optimise the route as just a set of points, assuming no obstacles (which is easy), or should it take roads, rivers and other terrain into account (which is hard bordering on impossible, depending on the quality of terrain data)?

- R

Postman Pat · Post by **Postman Pat** » 19 October 05 1:36 pm

With map sourse you can change the order of your waypoints by going to propities of that particular saved route and moving the way points either up or down or even inserting a way point

Cached · Post by **Cached** » 19 October 05 2:51 pm

Ideally, I wanted something to work out the best way between a heap of points using roads.

But, if I was ordering 50 or so points, even a "as the crow flies" indication of the most efficient way round a heap of points would be a good place to start from and then using mapsource/nroute to manually reorder the points.

Actually, if I can get a 'route' file that nRoute/mapsource can read, with just a list of waypoints to be visited in order, nRoute will autoroute the actual roads between them for me - which is cool. I would then be able to manually edit the order for obvious improvements.

Make sense?

ian-and-penny · Post by **ian-and-penny** » 19 October 05 4:33 pm

Have a look at the "Cache Raid" macro in GSAK

You select a cache from the database and it can then then pick a set of caches by selecting the next closest cache etc etc - and copying all the caches into a new database - in route order.

By extension, is it possible to have GSAK output/export the list of caches as a route file?

Ian

The Garner Family · Post by **The Garner Family** » 19 October 05 6:12 pm

Speaking of Destinator... anyone know how to import cache co-ords into it?

langy · Post by **langy** » 20 October 05 8:19 am

Hate to be a nerdy downer here guys - but there is no guarantee that the route given is optimal as this problem cannot be optimised.

Damned unfinished PhD!

Langy!

Team Red Roo · Post by **Team Red Roo** » 20 October 05 9:08 am

Have a look at the UBD website (Cdrom section - City Streets). There is a section there on auto routing and it's pc based. I have not inquired about pricing though.

Currently UBD maps are not suitable for Oziexplorer, though they have told me that version 3, due out in November, will 'interface with' Ozi (this is added in for Ozi users)

Partic · Post by **Partic** » 20 October 05 12:34 pm

Unfortunately, I don't have much to directly assist Cached. I usually sit down with OziExplorer, then filter the targeted caches in GSAK. Once I've finished planning, I print an overview map, then I run my exports, and start the route planning in Destinator.

Note Destinator's route optimising is limited to about 10 points to determine optimal route. More than that, and you're better off sorting them in your GSAK filter before doing the following...

The Garner Family wrote:Speaking of Destinator... anyone know how to import cache co-ords into it?

How I do it is outlined below. When I get more time soon I'm going to post it on the wiki, and will put a link back here.

Recipe:
You need...

Destinator

Destinator Console 3.1 (or any version of it that has "Favourites Importer")

GSAK

A filtered set of Geocaches

Steps:

Filter the caches you want in GSAK (which I'm not going to explain here)

Export a Custom CSV file (see Creating Custom CSV below)

Using Destinator Console's "Favourites Importer" load the CSV files into Destinator

You only need to do the setups below once, and then from there the steps above can be completed whenever you want to export to Destinator. I have it exporting several different queries in the macro (see below) and have several Custom export settings saved for the different groups of Favourties.

Creating Custom CSV:
To create the Custom CSV, you first need to create a GPSBabel translation document.

Code: Select all

# gpsbabel XCSV style file
#
# Format: Destinator 3.075 Favorites Importer

#
# Modified by Partic
#

DESCRIPTION Destinator Favourites

#
# FILE LAYOUT DEFINITIIONS:
#

FIELD_DELIMITER COMMA
RECORD_DELIMITER NEWLINE
BADCHARS ,"

# PROLOGUE Name, Description, Longitute, Latitude

#
# INDIVIDUAL DATA FIELDS, IN ORDER OF APPEARANCE:
#

IFIELD SHORTNAME, "", "%s" # Name
IFIELD DESCRIPTION, "", "%s" # Description
IFIELD LON_DECIMAL, "", "%f" # Longitude
IFIELD LAT_DECIMAL, "", "%f" # Latitude

Save this file as C:Program FilesGSAKDestinatorXCSV.txt

In the other Custom Export fields, you can set special tags to create the Cache name. I use "%name (%typ1)" which puts the Cache name, followed by the one character cache type code so you can see if you're driving past a Multi, Trad, Virtual etc when you spot the cache on the Destinator map.

Next you need to go to GSAK > File > Export > Custom Export and create your export. My command line is:

Code: Select all

"C:Program FilesGSAKGPSBabel.exe" -N -i gpx -f "C:Program FilesGSAKtempbabel.gpx" -o xcsv,style="C:Program FilesGSAKdestinatorXCSV.txt" -F "c:My DocumentsGeocachingDestinatorGeocaches.csv"

This creates a file called "C:My DocumentsGeocachingDestinatorGeocaches.csv". Change the various file names to where you would like the CSV file to be located.

Save the Custom Export Settings so you can use them in Macros. For the Macro below, I've called mine "Destinator Geocaches"

The GSAK Export Macro component (I use these lines as part of a 100 line macro that exports HTML, GPX, Destinator files for various cache, shutterspot and winery subgroups in Melbourne, and optionally Sydney and Wollongong if I'm travelling up there)

Code: Select all

# Create Destinator CSV Update file
EXPORT Type=CUS Settings="Destinator Geocaches"

Finally, in Destinator Console, connect your PDA, then click on map, then "Favourites Importer". Browse for your CSV file location, pick the file, then Convert then Download the file.

Destinator Console then converts the CSV into the Favourites file, then downloads it onto the PDA - and then you can Destinate to Geocaches! Makes life so much more fun

For a garnish, you can actually create your own 16x16 Favourites .bmp icons. But that's for the wiki

Any questions, post them here. In theory, most of this is correct, but I may have glanced over something by accident.