Customizable route planning

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

• Topology (Road networks)
• Metric (Customizable route planning)
• Cell: A group of Vertices
• Boundary vertices: Vertices with at least one incident edge to a different cell (e.g. \(B\) and \(C\), bold, below)
• Boundary arcs: Arcs (Edges) between boundary vertices in different cells (e.g. \((B, C)\) and \((C, B)\), bold, below)

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 (Jung and Pramanik 2002) and similar algorithms is to use [Partitioning Using Natural Cut Heuristics] PUNCH (Delling, Goldberg, Razenshteyn, et al. 2011) 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, Goldberg, Pajor, 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, Goldberg, Pajor, 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, Goldberg, Pajor, 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, Goldberg, Pajor, 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 (Jung and Pramanik 2002). 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 [ (Delling, Goldberg, Razenshteyn, et al. 2011) ] 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, Goldberg, Pajor, et al. 2011)

Flashcards

Describe

Stages of Customizable route planning

Back

1. Metric-independent pre-processing
2. Metric customization
3. Query

Source

(Delling, Goldberg, Pajor, et al. 2011)

Describe (Customizable route planning)

Metric-independent pre-processing

Back

Partitions the graph into Connected components (cells) with at most \(U\) vertices, minimizing boundary edges.

Source

(Delling, Goldberg, Pajor, et al. 2011)

Describe (Customizable route planning)

Metric customization

Back

• Build an “overlay” graph, \(H\), containing (1) all boundary vertices and (2) edges between boundary vertices (i.e. shortcuts)
• Compute length of shortcuts as Single-pair shortest path between each pair of \((\text{entry}, \text{exit})\) nodes

Source

(Delling, Goldberg, Pajor, et al. 2011)

Describe (Customizable route planning)

Query

Back

• Perform a bi-directional Dijkstra’s algorithm on the union of \(H\), \(C_s\), and \(C_t\).
  • Optionally over the hierarchy of \(H\) instances if you’re using nested partitions

Source

(Delling, Goldberg, Pajor, et al. 2011)

Describe

Why does Customizable route planning handle changing edge weights (due to traffic, etc) better than Contraction hierarchies?

Back

• Contraction hierarchies’s pre-processing depends on both Topology (Road networks) and Metric (Customizable route planning) data; the pre-processing is metric-dependent
• Part of Customizable route planning’s pre-processing is metric-independend and need not be re-computed when metrics change

Source

(“Contraction Hierarchies” 2023)

Describe (Customizable route planning)

Nested partitions

Back

A technique for reducing query latency by building a hierarchical view of the graph. The shortest path algorithm can take shortcuts upward and downward through the hierarchy to skip large swaths of intermediate vertices and edges.

Source

(Delling, Goldberg, Pajor, et al. 2011)

Compare and contrast

Contraction hierarchies and Customizable route planning for road network graphs

Back

• Contraction hierarchies
  • Lower query latency
• Customizable route planning
  • Greater pre-processing parallelization
  • Supports dynamic weights (e.g. traffic jams) without re-building the whole graph

Source

• (“Contraction Hierarchies” 2023)
• (Delling, Goldberg, Pajor, et al. 2011)

Cloze (Customizable route planning)

A query performs a {{bi-directional Dijkstra’s algorithm}@0} on {{the union of \(H\), \(C_s\), and \(C_t\)}@1}.

Source

(Delling, Goldberg, Pajor, et al. 2011)

Denotes (Customizable route planning)

\(C_s\) and \(C_t\)

Back

• Cells containing the starting and target vertices

Source

(Delling, Goldberg, Pajor, et al. 2011)

Denotes (Customizable route planning)

\(H\)

Back

An “overlay” graph which contains (1) all boundary vertices and (2) edges between boundary vertices (i.e. shortcuts)

Source

(Delling, Goldberg, Pajor, et al. 2011)

References

Backlinks

• Daniel Delling, Andrew V. Goldberg, Thomas Pajor, Renato F. Werneck | Customizable Route Planning
• Metric (Customizable route planning)