Route Planning in Road Networks

We present various speedup techniques for route planning in road networks. After performing some preprocessing steps, we can compute accurate quickest-path lengths in a few microseconds on a 2.0 GHz machine, using real-world road networks with several million nodes. In addition to dealing with the static point-to-point problem, we also handle dynamic scenarios (like traffic jams) and many-to-many instances