Building a Real-World Routing Engine

Computing driving directions in road networks is a fundamental
problem with numerous applications. Although graph-search algorithms
can solve it in almost linear time, this is not fast enough to enable
interactive queries on continental road networks. Modern algorithms
thus work in two stages: an offline preprocessing routine first computes
some auxiliary data, which is then used to answer exact queries interactively.
In a true success story, the Algorithm Engineering community has developed in
the past decade a diverse set of techniques providing various trade-offs
between preprocessing effort, query time, space usage, extensibility, and
simplicity. This talk explains the requirements for real-world journey planning,
and how they are addressed by the system currently in use by Microsoft's
Bing Maps.

back to the Program