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

## 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.

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$$.

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.

### 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$$.)

#### 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.

## Flashcards¶

### Describe¶

position ease box interval due
front 2.35 4 13.00 2023-08-05T03:22:21Z
back 2.50 1 1.00 2023-07-18T13:53:54Z

Stages of Customizable route planning

#### Back¶

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

### Describe (Customizable route planning)¶

position ease box interval due
front 2.20 3 6.00 2023-07-20T00:47:03Z
back 2.5 -1 0 2023-06-26T14:31:53Z

Metric-independent pre-processing

#### Back¶

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

### Describe (Customizable route planning)¶

position ease box interval due
front 2.20 3 6.00 2023-08-07T14:58:30Z
back 2.5 -1 0 2023-06-26T14:33:08Z

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

### Describe (Customizable route planning)¶

position ease box interval due
front 2.50 3 6.00 2023-08-07T01:19:46Z
back 2.5 -1 0 2023-06-27T22:05:00Z

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

### Describe¶

position ease box interval due
front 2.35 3 6.00 2023-08-05T23:50:37Z

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

### Describe (Customizable route planning)¶

position ease box interval due
front 2.50 4 13.57 2023-08-13T13:16:52Z
back 2.5 -1 0 2023-06-27T23:16:26Z

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.

### Compare and contrast¶

position ease box interval due
front 2.50 3 6.00 2023-07-29T03:40:27Z

Contraction hierarchies and Customizable route planning for road network graphs

### Cloze (Customizable route planning)¶

position ease box interval due
0 2.50 4 14.08 2023-08-09T16:46:14Z
1 2.5 -1 0 2023-07-10T01:06:24Z

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

### Denotes (Customizable route planning)¶

position ease box interval due
front 2.50 1 1.00 2023-08-02T15:05:34Z
back 2.5 -1 0 2023-07-27T15:27:34Z

$$C_s$$ and $$C_t$$

#### Back¶

• Cells containing the starting and target vertices

### Denotes (Customizable route planning)¶

position ease box interval due
front 2.50 1 1.00 2023-07-27T02:55:06Z
back 2.5 -1 0 2023-07-27T15:28:59Z

$$H$$

#### Back¶

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

## References¶

“Contraction Hierarchies.” 2023. Wikipedia, May. https://en.wikipedia.org/w/index.php?title=Contraction_hierarchies&oldid=1153438478.
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.
Delling, Daniel, Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck. 2011. “Graph Partitioning with Natural Cuts.” In 2011 IEEE International Parallel & Distributed Processing Symposium, 1135–46. Anchorage, AK, USA: IEEE. https://doi.org/10.1109/IPDPS.2011.108.
Jung, Sungwon, and S. Pramanik. 2002. “An Efficient Path Computation Model for Hierarchically Structured Topographical Road Maps.” Ieee Transactions on Knowledge and Data Engineering 14 (5): 1029–46. https://doi.org/10.1109/TKDE.2002.1033772.