• We invite you to join UKWorkshop.
    Members can turn off viewing Ads!

Route Planner software.

UKworkshop.co.uk

Help Support UKworkshop.co.uk:

Shaggy

Established Member
Joined
4 Feb 2018
Messages
107
Reaction score
5
Location
Durham
I've been given a job a work to collect the Used Christmas trees to go for shredding and recycling. The problem is the sheets of over seven hundred addresses for these trees are all mixed up and some of the areas I haven't got a clue where the streets are. Does anyone know of any free software that I could just type out the addresses and post codes in and it will work out a route that I can print out, so I am not going back wards and forwards around county Durham.
I'm looking for a free one because after this job I probably won't need it again so I don't really want to spend anything on something that'll not be used again.

Glen.
 

thick_mike

Wood Shortener
Joined
21 Aug 2011
Messages
826
Reaction score
65
Location
Wing, Bucks
Bloody hell that sounds like a rubbish job. There was a programme about quantum entanglement on bbc 4 last night where they said planning an optimised route around 30 addresses was beyond normal computers and would require a quantum computer to check all of the permutations. So I’m guessing you won’t find anything to give you a perfect route around 700!

Maybe group them based on postcode and do them in batches?
 

Brandlin

Established Member
Joined
5 Aug 2015
Messages
536
Reaction score
2
Location
Flint
thick_mike":3o8chz3x said:
Bloody hell that sounds like a rubbish job. There was a programme about quantum entanglement on bbc 4 last night where they said planning an optimised route around 30 addresses was beyond normal computers and would require a quantum computer to check all of the permutations. So I’m guessing you won’t find anything to give you a perfect route around 700!
True.

This is one of those problems that is intuitively easy to state but surprisingly complex to calculate.

If you use basic algorithms then you have a choice of 30 addresses to start at then 29 next then 28 etc... so you have 30 x 29 x 28 x ... x 3 x 2 x 1 different possible routes to compare. That's 30 factorial ... expressed as 30!

Roughly 2.6 x 10^32 or 26 with 31 zeros afterwards.

But there are cleverer ways of doing it without brute force number crunching. Even so 700 is A LOT.
(for example 700! is 2.4x10^1689 or 24 with 1688 zeros afterwards.)

You want software that is able to do "A-Star serach algorithm". That starts at address 1 and then seeks the next nearest address, and then the next nearest to that. It wont find the overall shortest though and in many circumstances can through up nonsense routes when you look at the whole thing.

You really aren't going to find a piece of free software to do this.I certainly don't know of any. People like Royal mail spend millions on research annually into this kind of problem.
 

Shaggy

Established Member
Joined
4 Feb 2018
Messages
107
Reaction score
5
Location
Durham
Looks like I'll be continuing with the looking at google maps to find the houses and making my own routes :cry: .
I started with 1325 addresses and have done about 680 in four days but it's taking me ages to find each house and work a route to take me round.
 

pulleyt

Established Member
Joined
24 May 2014
Messages
124
Reaction score
108
Location
Nottingham
This is all theoretical so someone else that has looked into this kind of problem practically may recommend that you ignore this suggestion :)

If i were to look at a problem like this I would aim for a visual solution using My Maps from Google. I couldn't tell you how to create a map of all the locations but I'm sure there are tutorials out there on how to import post codes and addresses (I've used My Maps for different purposes and found it fairly straight forward to work with). With all the addresses plotted you could view an area and work out your own 'best fit' route and mark them off as you collect the trees.

Good luck,
Trevor
 

Shaggy

Established Member
Joined
4 Feb 2018
Messages
107
Reaction score
5
Location
Durham
Nearly finished them but entering post code into google maps to see where they are and writing them down in separate areas, then going back through the areas on google maps and work out the route and print it off. It takes a long time but by the time you've finished you can more or less drive around the route only looking at the printed sheet to check house numbers :oops: .
 
Top