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).
PDF