CR4® - The Engineer's Place for News and Discussion®

 Previous in Forum: Stop Calling it Autopilot Musk, You Peabrain Next in Forum: White City Streets
Power-User

Join Date: Jul 2008
Posts: 388

Destination Plotting Software

04/14/2018 10:22 AM

I have the task of visiting 130 destinations within a 12km radius and would like to plot the shortest route. I live in South Australia.

I've looked at google maps which can only cope with 10 destinations and relies on me to reorder the destinations to the best fit.

Thank you in anticipation, Tony

__________________
The nice thing about Standards is there are so many to choose from.
Interested in this topic? By joining CR4 you can "subscribe" to

Check out these comments that don't yet have enough votes to be "official" good answers and, if you agree with them, rate them!
Guru

Join Date: May 2006
Location: Reading, Berkshire, UK. Going under cover.
Posts: 9607
#1

Re: Destination plotting software

04/14/2018 10:31 AM

How much time have you got? AFAIK it would take more than the lifetime of the universe to compute an optimum solution.

__________________
"Love justice, you who rule the world" - Dante Alighieri
Guru

Join Date: Mar 2007
Location: at the beach in Florida
Posts: 20313
#2

Re: Destination plotting software

04/14/2018 11:08 AM

__________________
Life is like riding a bicycle. To keep your balance you must keep moving. A.E.
Guru

Join Date: Apr 2010
Posts: 6142
#3

Re: Destination plotting software

04/14/2018 11:15 AM

That's the famous "Travelling Salesman Problem", the archetypical "NP Hard" problem. NP Hard means there is no shortcut algorithm and the only known way of solving it is to list every solution, of which there are N factoral. (130 factoral = 6.47 x 10219.)

There is no algorithm to find the shortest route. However, there are techniques to find a "very good" solution.

https://en.wikipedia.org/wiki/Travelling_salesman_problem

Guru

Join Date: Oct 2008
Posts: 40705
#4

Re: Destination plotting software

04/14/2018 11:40 AM
5
Power-User

Join Date: Jul 2008
Posts: 388
#5

Re: Destination plotting software

04/14/2018 11:24 PM

Suddenly I found it, it's called Optimap go and have a play.

I loaded 131 addresses into it and within 2 minutes it had marked the map and given me a route. I can't visit 130 places in a day so I can make a number of smaller maps based on the master.

Also you can export to Google maps, Garmin or TomTom.

Tony

__________________
The nice thing about Standards is there are so many to choose from.
Power-User

Join Date: Jun 2011
Location: Thailand
Posts: 497
#7

Re: Destination plotting software

04/14/2018 11:34 PM

Looks handy, but it should also tell you to start at the furthest, end with the closest.

__________________
Floss or die!
Power-User

Join Date: Jul 2008
Posts: 388
#9

Re: Destination plotting software

04/14/2018 11:48 PM

Thanks Stuart21, a valid point.

Tony

__________________
The nice thing about Standards is there are so many to choose from.
Guru

Join Date: Feb 2008
Location: Australia
Posts: 1790
#10

Re: Destination plotting software

04/15/2018 5:45 AM

Tony, If you cannot visit all in one day, then unless you intend to sleep over to resume your trip, you should maybe include multiple sites at your home with some sort of constraint to visit say 30 places before it can go back there.

__________________
Just an Engineer from the land down under.
Power-User

Join Date: Jul 2008
Posts: 388
#11

Re: Destination plotting software

04/15/2018 6:44 AM

Yes I agree, the reason for putting so many in was to see how it coped, and it did very well.

It produces a round trip, part of which is shown, the first is the departure point [1] with [2], [3] close by and it then returns to this point, you can see [98], [99] and [100] on the return road.

Alternatively it will produce an A-Z where the last destination is the finish point.

I will have to manually select blocks for day1, day2 etc.

Tony

__________________
The nice thing about Standards is there are so many to choose from.
Guru

Join Date: Mar 2007
Location: at the beach in Florida
Posts: 20313
#12

Re: Destination plotting software

04/15/2018 11:26 AM

20 locations in one day?, sounds rather optimistic...Don't forget traffic, food breaks, and physical endurance....12 to 15 sounds more realistic....

__________________
Life is like riding a bicycle. To keep your balance you must keep moving. A.E.
Guru

Join Date: Jan 2013
Posts: 625
#16

Re: Destination plotting software

04/15/2018 11:30 PM

Did he say that his lovely wife was in the second car ... and his oldest son might be drafted in to help ... wearing a helmet of course on his bike? Aiming for 30 contacts in a day ... and then there is buying a commercial spot on a prime radio station to reach them all (and more) in an instant!

__________________
DY
Guru

Join Date: Jan 2007
Location: In the bothy, 7 chains down the line from Dodman's Lane level crossing, in the nation formerly known as Great Britain, and now disconnecting ["brexit" - ugh] as Little England and Wales (not too sure about Wales bit, either). Kettle's on.
Posts: 27251
#18

Re: Destination plotting software

04/16/2018 6:02 AM

That would rather depend upon whether the mission were to collect or to deliver, though. A collection would work best by going to the farthest location first and work back towards the origin, so that the stuff has the least [weight x distance] to travel with the correspondingly lowest carbon footprint. If it were a delivery mission, then the opposite is true.

As Los Angeles has admitted that global warming is no longer a myth, these things are no longer trivial considerations.

__________________
"Did you get my e-mail?" - "The biggest problem in communication is the illusion that it has taken place" - George Bernard Shaw, 1856
Power-User

Join Date: Jul 2008
Posts: 388
#8

Re: Destination plotting software

04/14/2018 11:46 PM

On further examination I realise it has only taken the first 100, that's OK I can't visit 130 in a day and I sorted them by postcode first.

Still think it's a brilliant bit of software.

Tony

__________________
The nice thing about Standards is there are so many to choose from.
Guru

Join Date: May 2006
Location: Placerville, CA (38° 45N, 120° 47'W)
Posts: 4812
#13

Re: Destination plotting software

04/15/2018 12:58 PM

Excellent Find! I was very pleasantly surprised to find that A) It's web-based, so works fine on a Mac, B) It apparently works world-wide, C) It came up with my location visible on the map without having to specify, and D) It's apparently free!

__________________
Teaching is a great experience, but there is no better teacher than experience.
Guru

Join Date: Jul 2013
Posts: 1551
#19

Re: Destination plotting software

04/16/2018 1:29 PM

Tony,

Great find.

Thank you for updating us on your search. I don't need this type of mapping ability but if I do in the future, I will definitely use Optimap.

__________________
Though it does seem he frequently has a Swiss Army knife or Leatherman and a roll of duct tape with him.
Power-User

Join Date: Jun 2011
Location: Thailand
Posts: 497
#6

Re: Destination plotting software

04/14/2018 11:30 PM

Is there any kind of geographical grouping? If so you might be able to come up with 10 groups or less.

As a general rule, with 'milk runs' it is best to start with the furthest, and end with the closest, especially if times / traffic etc are unpredictable. Can be disappointing to 'almost' get finished, but to have to go out to to the furthest the next day -

__________________
Floss or die!
Guru

Join Date: Aug 2014
Location: 31°26'S 152°54'E Port Macquarie N.S.W. Australia
Posts: 936
#14

Re: Destination Plotting Software

04/15/2018 9:28 PM

Most decent GPS/street pilot units have a facility that enables you to enter all waypoints and you can then instruct it to automatically order them in shortest route format.

You can even designate your start and finish points as desired (they can be the same point if need be), you will get turn by turn directions as you go, and can even get it to find fuel and overnight accommodation if you don't get to them all in one day.

Power-User

Join Date: Jul 2008
Posts: 388
#15

Re: Destination Plotting Software

04/15/2018 10:58 PM

I use Google maps and am not aware that facility exists in it.

Tony

__________________
The nice thing about Standards is there are so many to choose from.
Guru

Join Date: Aug 2014
Location: 31°26'S 152°54'E Port Macquarie N.S.W. Australia
Posts: 936
#17

Re: Destination Plotting Software

04/15/2018 11:48 PM

It probably doesn't, I'm referring to the in car type units. - Garmin, Tomtom, Navman, VMS, etc.

My 15 year old Garmin 2610 street pilot stores only 48 via points and will auto arrange them into the most efficient route, later units go to around 1000 waypoints but, depending on the route length, you may not be able to use all of them as via points.

Interested in this topic? By joining CR4 you can "subscribe" to