Optimize Order

[blahooma]

I will make a video!

[jfheath]

The basic solution to calculating the optimal route between a series of points is really very simple.

Take for example 4 towns ABCD. That would give 6 different routes from which you could choose the shortest route. You could use fastest time, but shortest is easier to imagine.

So give that a bit of explanation and put it in a box so that you can ignore it if you wish.

You have to start at A - because that is where you are. The other 3 can be chosen in 6 ways:
ABCD, ABDC, ACBD, ACDB, ADBC, ADCB

(You can work out the number of different ways for 3 towns - it is 3 x 2 x 1 = 6)

Then you need the shortest distance between each pair of towns. Lets make some up - making sure that the figures aren't impossible.
AB = 12m; AC = 15m; AD = 20m; BC = 18m; BD = 25m; CD = 30m

Then workout the distance for each of the possible calculations.

ABCD = AB BC CD = 12 + 18 + 30 = 60
ABDC = AB BD DC = 12 + 25 + 30 = 67
ACBD = AC CB BD = 15 + 18 + 25 = 58
ACDB = AC CB DB = 15 + 30 + 25 = 70
ADBC = AD DB BC = 20 + 25 + 18 = 63
ADCB = AD DC BC = 20 + 30 + 18 = 68

Find the smallest total mileage ....... 58 So ACBD is the shortest route

Ok, so that is the complexity of it. But it gets worse
The above is for a route with just 3 towns - 6 different routes.

4 towns + start point gives 24 different routes to calculate (4 x 3 x 2 x 1)
5 towns gives 120 different routes to calculate (5 x 4 x 3 x 2 x 1)
There is a mathematical term for this multiplication. It is called 5 Factorial (or Factorial 5). It is written 5 ! ... '5' with an exclamation mark.

10 towns to visit will give 10 ! different routes to calculate. 3,628,800. You don't work these things out unless the number is small. You enter "10 Factorial" into google. Let it do the work.

But let's say that an average delivery round is 20 drop-offs - that is 20 ! different routes to work out.
And that is a massive number (20 x 19 x 18 ..... x 3 x 2 x 1) = 2.432902E18 which is about 2 with 18 zeros after it. 2.4 million million million.

That is far too big to think about and that would take years and years to calculate.

More explanation in a box to make it easy to ignore if this stuff makes your brain hurt.

If you had a computer working at 1 GHz - 1 thousand million clock cycles every second. The 20! different 'clock ticks' in a computer running at 1000 million clock ticks per second ? It would take 77 years to complete that many clock cycles. And that is only clock cycles. Each separate route calculation would take hundreds / thousands of clock cycles.

Which is probably a tiny bit longer than most satnav users would want to wait for the optimal route to be calculated. So although this method gives the definitive answer no one who asked the question is going to be alive to see the result. So they don't do it this way. Instead , they have to come up with some clever algorithms that make the calculation shorter. Much shorter.

Example - you could put the location in order of latitude and visit them in order. But that may result in a zig-zag pattern - the points would be arranged north to south, but the locations could be one on the east coast, next on the west coast.

You could find the nearest main road that passes through the middle of all of the points. (Like a least squares regression analysis for the statistically minded). Find the best fit. And then just take detours off the fastest road.

You could cluster the points together and find the fastest way to the centre of each cluster. Then find the fastest way to do each cluster.

All these and many more. None of them will produce the definitive absolutley best route. The result will be faster than many other solutions, but it is unliekly to be the fastest. But it won't take 77 years to come up witht he answer.

So - do we wait for the XT to calculate all of the possibilities to come up with the absolute best route. Or do we accept some compromise. If so, which compromises do we accept ?

One thing is for sure - Garmin make lots of different types of satnavs, each of which use the same maps. But the programs that drive them are different. They take into account things like drivers with caravans, and they avoid routing them round narrow country roads with sharp right angled bends, or 1 in 3 hairpin mountain passes. Other programs will not take roads with certain width and height limits.

The priority for those vehicles is not necessarily the fastest time. Its getting there safely. Or just getting there. The compromises are different.

And if I was a courier, making drop offs to different places, I think I would be heading for a stanav that made a different set of compromises. Rather than an XT which is aimed at touring motorcyclists and off-roaders - the majority of whom do not go door to door.

Yes the XT has all sorts of little features. Hilly roads, twisty roads etc. And it includes an optimal option. They are all suggestions. It comes up with an answer that is reasonable, but it is not necessarily one that you would want to accept. The more you demand of it, the more it will compromise in order to cut down the processing time. And for the XT, this seems to be a big concern - which is possibly why when you choose faster routing, it rarely produces the fastest route. That is too much processing. It heads for the main roads instead. It doesn't have as much to think about.

And as long as we know that that is what it is doing, we can work with it. In the same way that we had to work with the earlier units to keep us away from using motorways.

The trick is - finding out what the satnav is doing. Garmin do not reveal much about that - except every now and then you get a snippet on their website help pages. But somehwere, someone may have found out, and most of us seem to have gathered together on this forum !

Ok - that is my little essay over. It's only for those that are interested. Those that aren't - well its OK, they won't have read this far !

[blahooma]

I don't see that Garmin is using an algorithm here.
Video:

[Peobody]

I think it is unreasonable to expect the XT to optimize a route with that many waypoints. If the video wasn't snipped, it is obvious that the XT gives up by how quickly the optimization calculation occurs.

[blahooma]

It doesn't matter whether there are 20-30 or 130 waypoints, Garmin simply can't handle it

[jfheath]

I'm curious to know how you got a trip with that many Via Points in it. Normally the XT will split such a trip into sections, each with a maximum of 31 Via Points. 31 is a stated maximum number of Vias by Garmin for a single trip. You've clearly found a way around that unless in a recent software update Garmin have changed that behaviour. Where did your route come from ? Sowhere that doesn't use Shaping Points I would guess.

But that aside. Of course it is using an algorithm. An algorithm is just a way of describing how to perform a particular task. It could be as simple as working out the direction between the first and last points, and then finding the next point heading in the direction of that line. That takes hardly any calculation at all.

But it isn't the absolute best order. It is a compromise.

[blahooma]

I only use the Garmin XT device - search and add. No limitations have occurred.

[jfheath]

I only use the Garmin XT device - search and add. No limitations have occurred.

That's interesting - I've just checked on of my saved test routes with 100 Via Points, and it loaded it in but split it into 4 different routes, the first 3 of which had 31 points. So I tried adding more to one with 31 points, and it accepted it - which is weird.

It is odd to use so many Via Points though. They are a bit unforgivng when navigating - ie - you must pass through them. But you have no option if you are using the XT screen and Favourites. You can change them to Shaping points, but it tends to relocate them !!
The Shaping tool is available, but it doesn't work very well with a small screen and big fingers. I end up deleting most of what I (accidentally) put in.

[danham]

It doesn't matter whether there are 20-30 or 130 waypoints, Garmin simply can't handle it

Actually, it does matter. A lot.

If you want the optimize function to work, why not try it with a route using fewer than 31 vias.

-dan

[blahooma]

XT performs poorly when calculating for three points as well

https://www.google.com/maps/d/edit?mid= ... sp=sharing

it calculates a 5km difference. Starts from the middle point and zigzags through. ETC