Route creation using an unsorted set of destination postcodes

[robert french]

OK, I want to create a route that minimises distances between a set of unordered postcodes (or eastings/northings).

This is for a set of educational establishments, I can get either the postcodes or eastings/northings for these.

For a test run I am just conducting this in my local area, but ideally I'd like to include a much larger set of postcodes.

example data  https://docs.google.com/spreadsheet/ccc?key=0AhH383N3HlFrdEpnWUhjc1hhTnJ4RlktbzV4ZWp0aGc&usp=sharing (note this data is not senstitive)

[tom_e]

It's a well studied problem called travelling salesman (Wikipedia).  There is no easy full solution.

[robert french]

How can this be so hard? Surely the brute force method should be relatively straightforward for someone to implement using google maps.

Can I instead use something to bring up these postcodes as a set of points in google maps and join the dots manually?

Or even a way of searching for multiple directions at once (in google you can search for CH44 7LK to CH44 7NN - BUT you cannot do this for multiple directions AFAIK) which I can then edit to make as short as possible afterwards.

[Ian H]

Didn't/doesn't Autoroute rearrange destinations to produce a shorter route?

[bikenrrd]

Brute force method takes way too much computing time.
There are lots of algorithms for traversing a graph - look at the A* algorithm, often used in computer games for path finding for AIs / baddies.

[Ningishzidda]

Microsoft Autoroute 2011 does 'Optimising'.

Just done my Christmas card delivery using exactly this.

[robert french]

Are there any free websites / software that do this optimisation or do I need to buy a copy of autoroute 13 (£34.06  on amazon)?

[Ningishzidda]

The alternative is to Place all the points on Googlemaps and then move them around until the total distance is as low is you can get it.

It usually ends up being a big circular ring.

[robert french]

Is there a quick way of putting 100+ postcodes into google maps for the manual approach?

(Even if I had autoroute 13, is it possible to put that many postcodes in quickly for their optimisation?)

[Ningishzidda]

Its what's known in the IT trade as "Manual input".

It's long and tedious.

[robert french]

Ningishzidda - so whether I have autoroute or use google maps I have to manually input the postcodes?

[Ningishzidda]

Ningishzidda - so whether I have autoroute or use google maps I have to manually input the postcodes?

You have the postcodes on an Excel spreadsheet, so you can copy and paste them one-by-one into Googlemaps.
Don't forget to click 'Add destination' between each.

[robert french]

But can this adding of postcodes be done more easily with autoroute or is it the same kind of manual entry?

[mcshroom]

You could map them out on a road atlas with oat flakes and get a slime mould to figure it out

[darkpoint]

As mentioned this is the traveling salesman problem, and is thought to be hard.

Some promicing research is currently modeling ants, is proving intresting however.  The good solution is still going to be a long way off.

[robert french]

Had a go with google engines - printout map and navigate on the fly: https://mapsengine.google.com/map/edit?mid=z3833Sltlxt8.kUvajJaE2Ho4

not ideal - maximum 100 points per spreadsheet

[Ningishzidda]

Been on MS Autoroute 2011.

I created one tab in a workbook which had the list of my postcodes in column A

I used Autoroute's 'Import Data Wizard' to import the list of postcodes to create one .AXE file with all the postcodes as a Pushpin Set.

I right-click on the Pushpin Set and choose 'Add Pushpins as stops' and hey presto, they are all Waypoints.

Then I go 'Optimise stops' and the software sorts them into the shortest journey.

Done. No trouble.

[robert french]

Have started Optimap thread https://yacf.co.uk/forum/index.php?topic=78809.new#new