Re: Routing algorithm question

From: Dale DePriest (Dale_at_gpsinformation.het)
Date: 07/07/04 

Date: Wed, 07 Jul 2004 06:47:02 -0700

JLB wrote:

> Just curious.
>
> Are there any web sites that explain the algorithm the various GPS auto
> routing programs use?

no, this is considered intellectual property for the GPS company.
>
> I assume it is some sort of least-cost routing algorithm, perhaps similar to
> the traveling salesman problem.
>
> My basic question is: How do they pick the quickest route

The entire USA roads are divided into classifications and each
classification is assigned a speed value. The number of classifications
varies with the database but it isn't a big number, more like 6.

  (or shortest)?

Shortest ignores speed classification.

> Do they include a factor for the number of traffic lights on a route?

Typically they don't know about traffic lights. There may be some
exceptions.

   How
> about the 'normal' amount of traffic?

Handled by road classifications.

   Of course they can not know about
> unusual traffic (unless you pay the extra $200 and get a wireless PDA).
> What I am talking about is some routes may be quicker in theory, but other
> routes (taking a side road around a city instead of going straight through,
> for example) may be quicker.
>

This is a new and very primitive routing application for most systems.
Navteq and perhaps others provide some same algorithms but the better
units have developed there own. They are not very sophisticated to date.
The better ones take too long to compute a solution and most people
don't mind recalculting.

One algorithm works similiar to: divide the route into 3 pieces.
Piece one - Route to a freeway
Piece two - follow the freeway to the closest point near the destination
Piece three - route to the destination.

There is lots of room for improvement in the algorithms but the
databases are pretty weak and the problem is complicated. Consider no
left turns, no left turs from 3 to 6 pm, one way roads, gates across
roads (not considered in most databases :-( ), barriers in road surfaces
blocking turns, right turn only, and many other things. Navteq claims
upto 150 attributes are assigned to an intersection but very few
programs can take advantage of this much data.

Dale 

-- 
     _      _     Dale DePriest
    /`) _  //     http://users.cwnet.com/dalede
  o/_/ (_(_X_(`   For GPS and GPS/PDAs

Relevant Pages

  • Re: How to efficiently determine if a string contains any one of many strings
    ... If you are looking to apply an algorithm similar to determining what is ... the algorithm that is used in most heuristic spam filters. ... kinds of classifications lend themselves to searches for string literals: ... Of course, assuming more input strings to match, you'd have a lot more ...
    (microsoft.public.dotnet.languages.csharp)
  • 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)
  • Re: Garmin GPSmap 76C Review
    ... >task to determine the best route under all conditions and get an answer ... When I write "correct algorithm", then that only means that the ... mathematics and that the algorithms do not pose any extreme ... calculation time increases far more than proportional. ...
    (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)