Re: Garmin GPSmap 76C Review

From: Hans-Georg Michna (hans-georgNoEmailPlease_at_michna.com)
Date: 07/28/04 

Date: Wed, 28 Jul 2004 18:47:21 +0200

On Wed, 28 Jul 2004 08:37:23 -0700, Dale DePriest
<Dale@gpsinformation.net> wrote:

>For routing there is no correct algorithm for anybody!. Even the human
>mind which is much more complex than a GPS cannot always produce the
>best results. There are many refinements and if you have a main frame
>processor you could probably determine an optimum route under most
>conditions but with current mapping data even this would be flawed by
>the incorrect or misleading data. To even think that there is a
>"correct" algorithm that Garmin should have produced is flawed thinking
>in the current state of the art. I am sure that 20 years form now we
>will all look back at the primitive stuff of today. It is not an easy
>task to determine the best route under all conditions and get an answer
>in a reasonable waiting period.

Dale,

I'm not saying that there is exactly one optimal route, even
with several parameters.

When I write "correct algorithm", then that only means that the
calculated route is not obviously very bad, makes no unnecessary
detours, and is repeatable.

In this case there are obvious defects. For example, I had one
case in which I entered some parameters like Avoid Highways and
calculated a route that, indeed, avoided highways. When I then
remove the Avoid Highways parameter and there is one obvious,
straight highway route available, the algorithm has to deliver
that route, particularly if it did so under the same conditions
yesterday.

I'm not complaining about the program choosing this or that
choice, as long as the choice is not entirely unreasonable. For
example, when I calculate a long bicycle route (on MapSource),
and in spite of lots of big and little roads available, the
route contains a huge detour almost back to my starting point,
then the algorithm is defective.

I would also say that, once you have clearly defined maps with
clearly defined roads, the routing problem is a purely
mathematical, and if you can define exactly what you want, there
is at least one correct mathematical algorithm to fulfill the
definition. I believe that there is nothing miraculous in these
mathematics and that the algorithms do not pose any extreme
difficulties, particularly since there is no demand to find the
absolute optimum, only to find a route that is reasonably close
to the optimum. I'll ask a mathematician if I can get hold of
one.

As I understand it, routing over short distances, i.e. few
nodes, is easy, but as the number of nodes increases, the
calculation time increases far more than proportional. So the
algorithm has to make do with the limited processor time it can
get and find a reasonable route with that, and the 76C, having
only a very weak processor, apparently skimps a little bit too
much on long routes, even though I set it to Best Route.

By the way, I wonder why they don't have a setting like, "Keep
Looking For A Better Route" or "Improve Route In The
Background". For long routes that could be quite interesting,
because then the device would have much more time for the
background calculation.

One more remark. I don't intend to complain loudly. As I already
wrote, there is the reasonable hope that these devices work
fairly well in most practical circumstances. I found the errors
only when I posed somewhat unlikely problems, like a 400 mile
bicycle ride or repeating a route calculation several times with
alternating parameters, both situations that are rare in
reality. My tests only showed that the algorithms aren't
correct, not that they are entirely unusable. But of course I
wish for devices that show no such defects, not even under
stress test conditions, and I'm sure you wouldn't mind those
either. Actually there is a good chance that Garmin will improve
the firmware.

Hans-Georg 

-- 
No mail, please.

Relevant Pages

  • Re: Routing algorithm question
    ... > I assume it is some sort of least-cost routing algorithm, ... The entire USA roads are divided into classifications and each ... divide the route into 3 pieces. ...
    (sci.geo.satellite-nav)
  • Re: Bus/train timetable search algorithm
    ... one could route from New Orleans to Minneapolis ... Something like Dijkstra's algorithm isn't obviously applicable because ... the quickest route does not necessarily comprise of the quickest ... I'm left with a depth first exhaustive search, ...
    (comp.programming)
  • Re: Garmin GPSmap 76C Review
    ... > routing algorithm. ... >>106 km route). ... > residential streets, while Bicycle does not. ...
    (sci.geo.satellite-nav)
  • Routing algorithm question
    ... routing programs use? ... I assume it is some sort of least-cost routing algorithm, ... How do they pick the quickest route? ... What I am talking about is some routes may be quicker in theory, ...
    (sci.geo.satellite-nav)
  • Re: 60C spontaneous shutdown problems
    ... >>You mentioned five different routing calculation speed settings. ... > get a route that takes me 10 minutes longer to drive. ... >>I was hoping to influence this behaviour by changing the driving speeds. ... In some cases the cut-through route may be faster but I can't believe that's ...
    (sci.geo.satellite-nav)