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