Customizable route planning is a shortestpath algorithm designed for use on road networks which is capable of handling:
 realworld 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 preprocessing 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
Metricindependent preprocessing
Our metricindependent 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 generalpurpose 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 wellbehaved metrics. At the cost of making its topology metricdependent, 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 partitionbased 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 level0 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 topdown 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\). Goaldirection can still be used on the top level.
Flashcards
Describe
position  ease  box  interval  due 

front  2.35  4  13.00  20230805T03:22:21Z 
back  2.50  1  1.00  20230718T13:53:54Z 
Stages of Customizable route planning
Back
 Metricindependent preprocessing
 Metric customization
 Query
Source
(Delling, Goldberg, Pajor, et al. 2011)
Describe (Customizable route planning)
position  ease  box  interval  due 

front  2.20  3  6.00  20230720T00:47:03Z 
back  2.5  1  0  20230626T14:31:53Z 
Metricindependent preprocessing
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)
position  ease  box  interval  due 

front  2.20  3  6.00  20230807T14:58:30Z 
back  2.5  1  0  20230626T14: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 Singlepair shortest path between each pair of \((\text{entry}, \text{exit})\) nodes
Source
(Delling, Goldberg, Pajor, et al. 2011)
Describe (Customizable route planning)
position  ease  box  interval  due 

front  2.50  3  6.00  20230807T01:19:46Z 
back  2.5  1  0  20230627T22:05:00Z 
Query
Back
 Perform a bidirectional 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
position  ease  box  interval  due 

front  2.35  3  6.00  20230805T23:50:37Z 
Why does Customizable route planning handle changing edge weights (due to traffic, etc) better than Contraction hierarchies?
Back
 Contraction hierarchies’s preprocessing depends on both Topology (Road networks) and Metric (Customizable route planning) data; the preprocessing is metricdependent
 Part of Customizable route planning’s preprocessing is metricindependend and need not be recomputed when metrics change
Source
(“Contraction Hierarchies” 2023)
Describe (Customizable route planning)
position  ease  box  interval  due 

front  2.50  4  13.57  20230813T13:16:52Z 
back  2.5  1  0  20230627T23: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.
Source
(Delling, Goldberg, Pajor, et al. 2011)
Compare and contrast
position  ease  box  interval  due 

front  2.50  3  6.00  20230729T03:40:27Z 
Contraction hierarchies and Customizable route planning for road network graphs
Back
 Contraction hierarchies
 Lower query latency
 Customizable route planning
 Greater preprocessing parallelization
 Supports dynamic weights (e.g. traffic jams) without rebuilding the whole graph
Source
Cloze (Customizable route planning)
position  ease  box  interval  due 

0  2.50  4  14.08  20230809T16:46:14Z 
1  2.5  1  0  20230710T01:06:24Z 
A query performs a {{bidirectional 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)
position  ease  box  interval  due 

front  2.50  1  1.00  20230802T15:05:34Z 
back  2.5  1  0  20230727T15:27:34Z 
\(C_s\) and \(C_t\)
Back
 Cells containing the starting and target vertices
Source
(Delling, Goldberg, Pajor, et al. 2011)
Denotes (Customizable route planning)
position  ease  box  interval  due 

front  2.50  1  1.00  20230727T02:55:06Z 
back  2.5  1  0  20230727T15:28:59Z 
\(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)