[GIS] How do services like Google Maps compute the set of instructions for a route

algorithmgoogle maps

The problem of computing the driving directions from A to B can be divided into two equally important parts:

  • Finding the best path from A to B.
  • Identifying all the relevant maneuvers along that route.

While there is loads of information and research papers on the first topic, no one seems to be talking about the second one. And from my experience, computing instructions is a non-trivial problem for at least the following reasons:

  • Maps are very complex, diverse and sometimes full of geometry inconsistencies.
  • It is very hard to define what a "relevant maneuver" is. Some users might want to hear a "Go straight" instruction at each crossing, just for reassurance. Others would find this totally annoying.
  • It is hard to compare two sets of instructions and decide which one is better (because of the previous point). This makes automatic regression testing impossible.

So, are there any resources on this topic? Some literature, best practices, or actually any kind of advice would be very welcome.

Best Answer

You are unlikely to find the actual algorithms (would be classified as intellectual property)

Google use TeleAtlas data, since 2008 this has been owned by TomTom (know for Sat Nav products).

http://en.wikipedia.org/wiki/Tele_Atlas#Google_and_other_Internet_mapping_agreements

likewise Mapquest and Microsoft (Bing) use NavTeq owned by Nokia.

TeleAtlas capture this from multiple sources

enter image description here

After it is captured is then goes through a verification process

enter image description here

The product is available to purchase under the 'multinet' brand which is the most comprehensive of TomTom (TeleAtlas) Products with contains Navigation attributes (speed, restrictions, traffic lights, impedance factors)

multinet http://www.tomtom.com/en_gb/licensing/products/maps/multinet/ http://www.tomtom.com/en_gb/licensing/products/maps/multinet/

Sample Data is available from (Shape, File Geodatabase or DWG formats)

TomTom MultiNet With Driving Attributes Chicago, IL http://www.adci.com/html/samples/tomtom.php

Related Question