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

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

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