In Transit to Constant Time Shortest-Path Queries in Road Networks

Holger Bast, Stefan Funke, Domagoj Matijevic, Peter Sanders, Dominik Schultes

When you drive to somewhere `far away', you will leave your current location via one of only a few `important' traffic junctions. Starting from this informal observation, we develop an algorithmic approach---\emph{transit node routing}---that allows us to reduce quickest-path queries in road networks to a small number of table lookups. We present two implementations of this idea, one based on a simple grid data structure and one based on \emph{highway hierarchies}. For the road map of the United States, our best query times improve over the best previously published figures by two orders of magnitude. Our results exhibit various trade-offs between average query time ($6\,\usecs$ to $63\,\usecs$), preprocessing time ($62$\,min to $1200$\,min), and storage overhead ($27$ bytes/node to $247$ bytes/node).

Proc. of 9th Workshop on Algorithm Engineering and Experimentation (ALENEX) 2007, New Orleans