Daniel Delling, Andrew Goldberg, Thomas Pajor, Renato Werneck, (Delling et al. 2011)
Summary
See Customizable route planning
Thoughts
Notes
Abstract. We present an algorithm to compute shortest paths on continental road networks with arbitrary metrics (cost functions). The approach supports turn costs, enables real-time queries, and can incorporate a new metric in a few seconds—fast enough to support real-time traffic updates and personalized optimization functions. The amount of metric-specific data is a small fraction of the graph itself, which allows us to maintain several metrics in memory simultaneously.
Introduction
Most previous research focused on the most natural metric, driving times. Real-world systems, however, often support other natural metrics as well, such as shortest distance, walking, biking, avoid U-turns, avoid/prefer freeways, or avoid left turns.
The first [stage], metric-independent preprocessing, may be relatively slow, since it is run infrequently. It takes only the graph topology as input, and may produce a fair amount of auxiliary data (comparable to the input size). The second stage, metric customization, is run once for each metric, and must be much quicker (a few seconds) and produce little data—a small fraction of the original graph. Finally, the query stage uses the outputs of the first two stages and must be fast enough for real-time applications.
Previous techniques
Our approach
Basic algorithm
See Customizable route planning for write-up.
Sparsification
See Customizable route planning for write-up.