Automatic Routing Optimisation

Discussion about software such as GSAK, OziExplorer etc, as well as all things hardware, GPSrs, laptops, PDAs, paperless caching, cables etc
User avatar
Cached
2500 or more caches found
2500 or more caches found
Posts: 3087
Joined: 24 March 04 4:32 pm
Location: Launceston, Tasmania
Contact:

Automatic Routing Optimisation

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

User avatar
Geodes
Posts: 345
Joined: 22 April 05 5:52 pm
Location: Mitcham, Vic

Post by Geodes » 17 October 05 6:41 pm

Mapsource has auto-routing

User avatar
Cached
2500 or more caches found
2500 or more caches found
Posts: 3087
Joined: 24 March 04 4:32 pm
Location: Launceston, Tasmania
Contact:

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
400 or more spectacular views seen
400 or more spectacular views seen
Posts: 61
Joined: 15 September 03 11:19 pm
Location: Oakden South Australia

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.

User avatar
Cached
2500 or more caches found
2500 or more caches found
Posts: 3087
Joined: 24 March 04 4:32 pm
Location: Launceston, Tasmania
Contact:

Post by Cached » 17 October 05 11:01 pm

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

User avatar
Chwiliwr
10000 or more caches found
10000 or more caches found
Posts: 894
Joined: 10 April 05 10:39 pm
Location: Leeming Western Australia

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.

User avatar
Geodes
Posts: 345
Joined: 22 April 05 5:52 pm
Location: Mitcham, Vic

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
Posts: 1329
Joined: 29 March 03 6:04 pm
Location: Gladesville, Sydney
Contact:

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

User avatar
Postman Pat
100 or more tracks walked
100 or more tracks walked
Posts: 317
Joined: 01 March 05 9:23 pm
Location: Kootingal near Tamworth NSW

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

User avatar
Cached
2500 or more caches found
2500 or more caches found
Posts: 3087
Joined: 24 March 04 4:32 pm
Location: Launceston, Tasmania
Contact:

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
10000 or more caches found
10000 or more caches found
Posts: 1067
Joined: 13 October 03 11:45 am
Location: Travelling Australia using a Garmin Montana 650T

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
1100 or more caches found
1100 or more caches found
Posts: 953
Joined: 05 September 04 7:21 pm
Location: Brisbane

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

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

User avatar
langy
600 or more caches found
600 or more caches found
Posts: 159
Joined: 26 December 03 10:42 am
Location: Morayfield, QLD

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!

User avatar
Team Red Roo
5500 or more caches found
5500 or more caches found
Posts: 375
Joined: 02 May 03 9:30 pm
Location: Armadale WA
Contact:

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)

User avatar
Partic
500 or more caches logged
500 or more caches logged
Posts: 183
Joined: 29 November 04 4:09 pm
Twitter: https://www.twitter.com/partic
Facebook: https://www.facebook.com/Partic
Location: Wantirna South, VIC
Contact:

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...
:arrow: Destinator
:arrow: Destinator Console 3.1 (or any version of it that has "Favourites Importer")
:arrow: GSAK
:arrow: A filtered set of Geocaches

Steps:
:arrow: Filter the caches you want in GSAK (which I'm not going to explain here)
:arrow: Export a Custom CSV file (see Creating Custom CSV below)
:arrow: 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 8)

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

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

Post Reply