Customizable route planning is a shortest-path algorithm designed for use on road networks which is capable of handling:

  • real-world dynamic costs (e.g. increased edge cost due to traffic jam)
  • varied, custom, cost functions (i.e. more than just distance or time) which we don’t need to prescribe at pre-processing time

Terms

Algorithm

Metric-independent pre-processing

Our metric-independent preprocessing stage partitions the graph into connected cells [Connected components] with at most \(U\) (an input parameter) vertices each, with as few boundary arcs (arcs with endpoints in different cells) as possible.

[…]

Our first improvement over HiTi (NO_ITEM_DATA:jungEfficientPathComputationModelHierarchicallyStructuredTopographicalRoadMaps2002) and similar algorithms is to use [Partitioning Using Natural Cut Heuristics] PUNCH (NO_ITEM_DATA:dellingGraphPartitioningNaturalCuts2011) to partition the graph. Recently developed to deal with road networks, it routinely finds solutions with half as many boundary edges (or fewer), compared to the general-purpose partitioners (such as METIS [20]) commonly used by previous algorithms.

(Delling et al. 2011)

An example, with \(U=3\):

Metric customization

The metric customization stage builds a graph \(H\) containing all boundary vertices (those with at least one neighbor in another cell) and boundary arcs of \(G\). It also contains a clique for each cell \(C\): for every pair \((v, w)\) of boundary vertices in \(C\), we create an arc \((v, w)\) whose cost is the same as the shortest path (restricted to \(C\)) between \(v\) and \(w\) (or infinite if \(w\) is not reachable from \(v\)). We do so by running Dijkstra [Dijkstra’s algorithm] from each boundary vertex. Note that \(H\) is an overlay [24]: the distance between any two vertices in \(H\) is the same as in \(G\).

(Delling et al. 2011)

Nodes in \(H\) are bold and clique edges are red.

Sparsification

Using full cliques in the overlay graph may seem wasteful, particularly for well-behaved metrics. At the cost of making its topology metric-dependent, we consider various techniques to reduce the overlay graph.

The first approach is edge reduction [24], which eliminates clique arcs that are not shortest paths. After computing all cliques, we run Dijkstra from each vertex \(v\) in \(H\), stopping as soon as all neighbors of \(v\) (in \(H\)) are scanned. Note that these searches are usually quick, since they only visit the overlay.

(Delling et al. 2011)

Query

[…] to perform a query between \(s\) and \(t\), we run a bidirectional version of Dijkstra’s algorithm [Dijkstra’s algorithm] on the graph consisting of the union of \(H\), \(C_s\) , and \(C_t\) . (Here \(C_v\) denotes the subgraph of \(G\) induced by the vertices in the cell containing \(v\).)

(Delling et al. 2011)

Reduce query latency

  • Nested partitions

    To accelerate queries, we can use multiple levels of overlay graphs, a common technique for partition-based approaches, including HiTi (NO_ITEM_DATA:jungEfficientPathComputationModelHierarchicallyStructuredTopographicalRoadMaps2002). We need nested partitions of \(G\), in which every boundary edge at level \(i\) is also a boundary edge at level \(i − 1\), for \(i > 1\). The level-0 partition is the original graph, with each vertex as a cell. For the \(i\text{-th}\) level partition, we create a graph \(H_i\) as before: it includes all boundary arcs, plus an overlay linking the boundary vertices within a cell. Note that \(H_i\) can be computed using only \(H_{i−1}\). We use PUNCH [ (NO_ITEM_DATA:dellingGraphPartitioningNaturalCuts2011) ] to create multilevel partitions, in top-down fashion. An \(s \arrow t\) query runs bidirectional Dijkstra on a restricted graph \(G_{st}\). An arc \((v, w)\) from \(H_i\) will be in \(G_{st}\) if both \(v\) and \(w\) are in the same cell as \(s\) or \(t\) at level \(i + 1\). Goal-direction can still be used on the top level.

    (Delling et al. 2011)

Bibliography

References

Delling, Daniel, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. 2011. “Customizable Route Planning.” In Experimental Algorithms, edited by Panos M. Pardalos and Steffen Rebennack, 6630:376–87. Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-20662-7_32.
NO_ITEM_DATA:jungEfficientPathComputationModelHierarchicallyStructuredTopographicalRoadMaps2002
NO_ITEM_DATA:dellingGraphPartitioningNaturalCuts2011