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
Close
Close
Close
19 comments
Power-User

Join Date: Jul 2008
Location: Adelaide, Australia
Posts: 388
Good Answers: 13

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.
Register to Reply
Pathfinder Tags: Google Maps
Interested in this topic? By joining CR4 you can "subscribe" to
this discussion and receive notification when new comments are added.

Comments rated to be Good Answers:

These comments received enough positive ratings to make them "good answers".

Comments rated to be "almost" Good Answers:

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
United Kingdom - Member - Not a New Member Hobbies - Musician - New Member Hobbies - Fishing - New Member

Join Date: May 2006
Location: Reading, Berkshire, UK. Going under cover.
Posts: 9607
Good Answers: 457
#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
Register to Reply
Guru

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

Re: Destination plotting software

04/14/2018 11:08 AM

Ask Watson, he knows everything...

__________________
Life is like riding a bicycle. To keep your balance you must keep moving. A.E.
Register to Reply Score 1 for Good Answer
Guru

Join Date: Apr 2010
Posts: 6142
Good Answers: 636
#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

Register to Reply
Guru

Join Date: Oct 2008
Posts: 40705
Good Answers: 1606
#4

Re: Destination plotting software

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

Join Date: Jul 2008
Location: Adelaide, Australia
Posts: 388
Good Answers: 13
#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.

Each map has a reference so you can return to it.

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

Tony

__________________
The nice thing about Standards is there are so many to choose from.
Register to Reply Good Answer (Score 5)
Power-User

Join Date: Jun 2011
Location: Thailand
Posts: 497
Good Answers: 3
#7
In reply to #5

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!
Register to Reply
Power-User

Join Date: Jul 2008
Location: Adelaide, Australia
Posts: 388
Good Answers: 13
#9
In reply to #7

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.
Register to Reply
Guru
Australia - Member - New Member

Join Date: Feb 2008
Location: Australia
Posts: 1790
Good Answers: 210
#10
In reply to #9

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.
Register to Reply
Power-User

Join Date: Jul 2008
Location: Adelaide, Australia
Posts: 388
Good Answers: 13
#11
In reply to #10

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.
Register to Reply
Guru

Join Date: Mar 2007
Location: at the beach in Florida
Posts: 20313
Good Answers: 1187
#12
In reply to #11

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.
Register to Reply
Guru
Popular Science - Weaponology - New Member

Join Date: Jan 2013
Posts: 625
Good Answers: 16
#16
In reply to #12

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
Register to Reply
Guru
United Kingdom - Member - Indeterminate Engineering Fields - Control Engineering - New Member

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
Good Answers: 724
#18
In reply to #7

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
Register to Reply
Power-User

Join Date: Jul 2008
Location: Adelaide, Australia
Posts: 388
Good Answers: 13
#8
In reply to #5

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.
Register to Reply
Guru

Join Date: May 2006
Location: Placerville, CA (38° 45N, 120° 47'W)
Posts: 4812
Good Answers: 184
#13
In reply to #5

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.
Register to Reply
Guru
Hobbies - CNC - New Member

Join Date: Jul 2013
Location: Lost Wages Nevada
Posts: 1551
Good Answers: 54
#19
In reply to #5

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.
Register to Reply
Power-User

Join Date: Jun 2011
Location: Thailand
Posts: 497
Good Answers: 3
#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!
Register to Reply
Guru

Join Date: Aug 2014
Location: 31°26'S 152°54'E Port Macquarie N.S.W. Australia
Posts: 936
Good Answers: 194
#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.

Register to Reply Score 1 for Good Answer
Power-User

Join Date: Jul 2008
Location: Adelaide, Australia
Posts: 388
Good Answers: 13
#15
In reply to #14

Re: Destination Plotting Software

04/15/2018 10:58 PM

Thanks Spades

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.
Register to Reply
Guru

Join Date: Aug 2014
Location: 31°26'S 152°54'E Port Macquarie N.S.W. Australia
Posts: 936
Good Answers: 194
#17
In reply to #15

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.

Register to Reply
Register to Reply 19 comments
Interested in this topic? By joining CR4 you can "subscribe" to
this discussion and receive notification when new comments are added.

Comments rated to be Good Answers:

These comments received enough positive ratings to make them "good answers".

Comments rated to be "almost" Good Answers:

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

Users who posted comments:

dkwarner (1); Don from Oz (1); JohnDG (1); Just an Engineer (1); lyn (1); Original_Macgyver (1); PWSlack (1); Rixter (1); SolarEagle (2); spades (2); Stuart21 (2); Tonymech (5)

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

Advertisement