Route Planning with Flexible Objective Functions
Robert Geisberger, Moritz Kobitzsch, Peter W. Sanders · Society for Industrial and Applied Mathematics eBooks · 2010
We present the first fast route planning algorithm that answers shortest paths queries for a customizable linear combination; of two different metrics, e. g. travel time and energy cost, on large scale road networks. The precomputation receives as input a directed graph, two edge weight functions t(e) and c(e), and a discrete interval [L, U]. The resulting flexible query algorithm finds for a parameter p ∊ [L, U] an exact shortest path for the edge weight t(e)+p·c(e). This allows for different tradeoffs between the two edge weight functions at query time. We apply precomputation based on node construction, which adds all necessary shortcuts for any parameter choice efficiently. To improve the node ordering, we developed the new concept of gradual parameter interval splitting. Additionally, we improve performance by combining node contraction and a goal-directed technique in our flexible scenario.