Separator-Based Alternative Paths in Customizable Contraction Hierarchies

Let $P_{s,t}$ be the shortest $s$-$t$-path for $s,t\in V$. Following the definition by Abraham et al. [1], we say that an $s$-$t$-path $P$ is an admissible alternative if it has limited sharing, bounded stretch, and local optimality, which are defined as follows, depending on parameters $\gamma$, $\epsilon$, and $\alpha$, respectively.

1. 1.

   $P$ has limited sharing if $c(P\cap P_{s,t})\le \gamma \cdot d(s,t)$.

2. 2.

   $P$ has bounded stretch if for every $a$-$b$-subpath $P^{\prime }\subseteq P$ it holds that $c(P^{\prime })\le (1+\epsilon )\cdot d(a,b)$.

3. 3.

   $P$ is locally optimal if for every $a$-$b$-subpath $P^{\prime }\subseteq P$ with $c(P^{\prime })\le \alpha \cdot d(s,t)$, it holds that $P^{\prime }$ is the shortest $a$-$b$-path, i.e., $c(P^{\prime })=d(a,b)$.

In case we do not want just one but multiple alternatives, we require limited sharing (Property 1) to not only hold for the shortest path $P_{s,t}$ but for the union of $P_{s,t}$ and all other alternatives. Thus, we call a set $𝒫$ of alternative $s$-$t$-paths admissible if each $P\in 𝒫$ has bounded stretch (Property 2), is locally optimal (Property 3), and

We use the parameter values $\gamma =0.8$, $\epsilon =0.25$, and $\alpha =0.25$ typically used in the literature.

As already noted in the literature [1], it is unknown how to check bounded stretch (Property 2) and local optimality (Property 3) without requiring quadratic time in the length of the path. It is thus common to not check the properties exactly but instead use the approaches described in the following.

For bounded stretch (Property 2), instead of checking every subpath $P^{\prime }\subseteq P$, we only check the parts that deviate from the shortest path $P_{s,t}$. More precisely, we check the $a$-$b$-subpath $P^{\prime }$ if $P^{\prime }$ is maximal (with respect to inclusion) among the subpaths of $P$ that are edge-disjoint with the shortest path $P_{s,t}$. For paths based on one via vertex $v$, i.e., if $P$ is the concatenation of the shortest paths $P_{s,v}$ and $P_{v,t}$, one can see that there is just one such $a$-$b$-subpath; see Figure 1. More generally, for multiple via-vertices there is at most one such subpath for each via vertex.

For the local optimality (Property 3), we use the so-called T-test, which guarantees local optimality with respect to $\alpha$ but sometimes falsely rejects alternatives if they are not locally optimal with respect to $2\alpha$ [1]. For this, consider a via vertex $v$ and let $P_{s,v,t}$ be the concatenation of the shortest paths $P_{s,v}$ and $P_{v,t}$. Moreover, let $a^{\prime }$ and $b^{\prime }$ be the vertices on $P_{s,v,t}$ at distance $\alpha \cdot d(a,b)$ from $v$; see Figure 1. The alternative $P_{s,v,t}$ passes the T-test if $P_{a^{\prime },v,b^{\prime }}$ is the shortest $a^{\prime }$-$b^{\prime }$-path.

Here we introduce the concepts of CCH necessary to understand our alternative path algorithm. For a more general introduction and in-depth discussion, see the recent survey [5]. In general, CCH follows a three-phase approach: The first phase is a metric-independent preprocessing, i.e., a preprocessing of the graph $G$, ignoring the cost function $c$. This is the most costly phase, taking in the order of a few minutes for a continentally sized network, which is acceptable as the topology of $G$ rarely changes. The second step is the customization phase, where the cost function $c$ is preprocessed. Taking just a few seconds, this allows for frequent traffic updates. Finally, the third phase are the actual queries, which usually take less than a millisecond, exploiting the additionally information computed in the first two phases.

Given the graph $G$, the CCH preprocessing computes the following two additional structures. First, it computes a hierarchy of small balanced separators that splits the graph recursively into pieces; see Figure 2 (left) for an illustration. This hierarchy is represented by a rooted tree $T$ called elimination tree; see Figure 2 (right). Let $S\subseteq V$ be one of the separators. Then $S$ forms a path in $T$ and only the bottom-most vertex of $S$ has multiple children. The different subtrees below these children contain the vertices from the different connected components that were separated by $S$. From this, one can already make the following crucial observation: For two vertices $s$ and $t$, let $A\subseteq V$ be the set of common ancestors of $s$ and $t$ in $T$. Then, $A$ separates $s$ from $t$ (or contains one of the two) and thus any $s$-$t$-path goes through a vertex of $A$. Hence, to compute the distance $d(s,t)$, it suffices to compute the distances $d(s,v)$ and $d(v,t)$ for all $v\in A$ and then choose the vertex $v$ that minimizes $d(s,v)+d(v,t)$.

To achieve this, we need the second additional structure computed in the precomputation; the augmented graph $G^{+}$. The augmented graph is obtained from $G$ by inserting additional edges, which are called shortcuts and represent paths. Explaining why this works is beyond the scope of this paper (see e.g., [5]), but adding shortcuts in a clever way yields the following crucial property. Let $s\in V$ be any vertex and let $⟨v_1,\mathrm{\dots },v_k⟩$ be the path in the elimination tree $T$ from $s=v_1$ to the root $v_k$. Now run Dijkstra’s algorithm, but instead of using a priority queue to decide which vertices to relax, only relax the vertices $v_1,\mathrm{\dots },v_k$ in that order. Then this computes the correct distances $d(s,v_i)$ for all $i\in [k]$, i.e., for all ancestors of $s$ in the elimination tree $T$. Running this type of search from $s$ and (backwards) from $t$ thus yields the distances $d(s,v)$ and $d(v,t)$ for every common ancestor of $s$ and $t$, which yields the distance $d(s,t)$ as noted above.

To maximize the number of found alternatives, we would ideally check for each separator vertex $v\in S$ whether the via vertex $v$ yields an admissible alternative. From the resulting set of individually admissible alternatives, one would then have to extract a maximum set of alternatives that are also admissible together (recall that the limited sharing property for sets of alternatives also depends on the other selected alternatives). As this is computationally too expensive, we instead use the following greedy strategy, which is also commonly used in the literature regarding alternative paths.

We iteratively process the alternatives defined by vertices in $A$. When processing $v\in S$, we check whether the via path $P_{s,v,t}$ is admissible with respect to the already selected alternatives. If yes, we add it to the selection and discard it otherwise. We prioritize shorter alternatives, i.e., we process the candidates in the order of increasing length. We note that the CCH approach is very well suited for this. Recall that the CCH query computes $d(s,v)$ and $d(v,t)$ for every $v\in S$. Thus we already know the length of every via path $P_{s,v,t}$ without any overhead compared to the normal query.

It remains to check whether the next candidate path $P_{s,v,t}$ is admissible with respect to the already selected alternatives. To do this efficiently, we use four different checks that we apply in order of increasing computational cost. The reason for this is that, if an early cheap check already rules out a path, then we can save the later more expensive checks. The steps and how to implement them efficiently in the CCH approach are described in detail in the following. The first two steps check the bounded stretch requirement. The third step ensures limited sharing and the fourth and final step is the T-test checking for local optimality.

The biggest advantage of road networks for efficiently computing shortest paths – its small natural separators – can become a problem for our basic algorithm described above if the separators are too small. Figure 4 shows the example of London and Paris, which are separated by only a few vertices. The shortest path uses the Eurotunnel and the only possible way to avoid this is by using ferries which take too long to provide admissible alternatives. A similar issue can arise if the separator is too close to either $s$ or $t$. In such a case most separator vertices already violate the global stretch and get pruned.

The goal in the following is to extend our approach to also provide admissible alternatives in these situations. For this, we use the following intuitive observation. The above scenario happens if the separator vertex $v$ used by the shortest path is too important to be avoided. Thus, we decide to keep $v$ and instead look for alternatives in the subpaths from $s$ to $v$ and from $v$ to $t$. The basic idea is to consider these two sides of the separator $v$ as independent subproblems of the alternative path problem.

To make this more precise, let $v$ be the vertex on the shortest path $P_{s,t}$ that is closest to the root in the elimination tree $T$. Moreover, let $v_s$ and $v_t$ be the two neighbors of $v$ in $P_{s,t}$. Then we recursively call the basic algorithm to compute alternatives for $s$ to $v_s$ and $v_t$ to $t$; see Figure 5. It remains to fill out the following details. First, we have to describe how to combine the subpaths that are returned by the recursive calls. Secondly, we want the resulting alternatives to be admissible for the original query of $s$ and $t$. While admissibility of the resulting paths can be checked when combining subpaths, we also have to adjust the requirements for admissibility in the recursive calls to not falsely prune promising subpaths or return subpaths that can never be completed to admissible alternatives.

A natural extension to the two step approach is to not compute the paths from $v$ to $v_s$ and $v_t$ to $t$ with the basic approach but with the two step approach itself. More precisely, we first use the base algorithm, if that does not yield sufficiently many alternatives we go one recursion step deeper and afterwards combine the paths in the same way as in Section 3.2 This approach ensures that even multiple small separators between $s$ and $t$ can be handled while only doing more work if necessary. As a stopping condition for the recursive descend, we propose to stop as soon as the distance between the current start $s^{\prime }$ and destination $t^{\prime }$ becomes too small. More precisely we introduce the new parameter $\mu$. The recursive call returns just the shortest path if $d(s^{\prime },t^{\prime })$ is less than $\mu \cdot d(s,t)$.

The input instance for all our experiments is the DIMACS Europe graph with travel-time as edge weights. The resulting graph has $18$ million vertices, $42$ million edges and represents the complete road network of west Europe around the year $2000$. We chose to use this graph even though larger networks are available since it is the main benchmark for various other route planning techniques and has also been used to evaluate all other alternative path techniques.

To make the comparison with the related work easier we copy the methodology introduced by Abraham et al. [1]. That is, we test our algorithm with the same parameters. More precisely, we require alternatives to be locally optimal for $\alpha =25\%$, have at most $\gamma =80\%$ sharing, and bounded stretch of $1+\epsilon =125\%$. Note that these are hard constraints and any alternative satisfying them is considered good. Thus, the quality of the algorithm can be measured by the success rate of finding alternatives. Additionally, we will consider the time required to find those alternatives. If not stated otherwise all numbers are averaged over ${10}^5$ random queries.

Our algorithms are implemented in C++17 and compiled with the GNU compiler $\mathrm{13.3.1}$ using optimization level $3$. Our test machine runs Fedora $39$ (kernel $\mathrm{6.8.11}$), and has $32$ GiB of DDR4-4266 RAM and a AMD Ryzen $7$ PRO $5850$U CPU with $16$ cores clocked at $4.40$ Ghz and $8\times 64$ KiB of L1, $8\times 4$ MiB of L2, and $16$ MiB of L3 cache.

Unfortunately, no implementations of the competitor algorithms are freely available and the queries used during their respective evaluations were not published. To nonetheless make a comparison possible, we report the success rates and computation times from the related work in Table 1. The success rate for $k\in \{1,2,3\}$ represents the fraction of queries, for which an admissible set of alternatives of size at least $k$ was found. Even though the numbers are based on different sets of sampled queries, the success rates should be comparable since they are averaged over at least ${10}^4$ queries. The timings on the other hand should not be compared directly; see the more detailed discussion of the running time below.

We want to note that CRP and our approach are arguably the most practically relevant approaches due to their support for efficient metric updates. We thus focus our discussion on the comparison to CRP. The other approaches listed in Table 1 are included for completeness.

Recall that our algorithm starts with a set of candidates for alternative paths, which are then filtered by different checks ensuring the resulting set of alternatives is admissible. Figure 6 shows for our basic (non-recursive) approach, how many candidates pass which check before we find the first, second, or third alternative (after finding the previous alternative). The first bar indicates the number of considered candidate paths that have overall length at most $(1+\epsilon )\cdot d(s,t)$. The second bar shows how many of those have bounded stretch (property 2). The third bar shows the number of checked candidates additionally having limited sharing with the shortest path $P_{s,t}$ and the fourth bar is obtained by additionally requiring limited sharing with all previously selected alternatives (property 1). Finally, the fifth bar indicates the average number of paths also passing the T-test (property 3), which coincides with the fraction of queries finding at least one, two, or three alternatives.

One can clearly see that most considered candidates are rejected due to the stretch. For the second and third alternative, the T-test additionally rules out a big fraction of candidates. Note that only very few checked candidates are rejected due to too much sharing with previously selected alternatives.

We believe that the last observation is particularly interesting for the following reason. While the alternative path problem ensures high-quality alternatives by requiring admissibility (hard constraints), the optimization goal is to maximize the number of found alternatives. However, our approach follows the literature by greedily adding alternative paths to the set of alternatives, prioritizing shorter paths. A better approach to maximize the number of alternatives might be to somehow select the alternatives based on how much they share with candidates that are considered later. However, the fact that there is almost no difference between the third and fourth bars in Figure 6 shows that earlier selected alternatives very rarely make later candidates non-admissible due to a large overlap. This justifies the decision to select alternatives greedily by length instead of trying to explicitly maximize their number.

An important degree of freedom in CCH is the used separator hierarchy. Except when explicitly stated otherwise, we use the state-of-the-art algorithm InertialFlowCutter²²2https://github.com/kit-algo/InertialFlowCutter engineered by Gottesbüren, Hamann, Uhl and Wagner in the default configuration [13]. This can be seen as the the default choice for high-performance CCHs. However, as already mentioned in Section 1, larger separators (which are worse for performance) provide more candidates for via vertices. For comparison, we thus additionally ran our alternative path algorithm using separators provided by the simpler InertialFlow algorithm proposed by Schild and Sommer [18], using the implementation in RoutingKIT³³3https://github.com/RoutingKit/RoutingKit in the default configuration.

Figure 7 shows the number of alternatives found by the basic (non-recursive) variant of our algorithm for the different separator hierarchies. We can see that, indeed, the number of found alternatives slightly increases with the larger separators. Thus, in principle, choosing different separators provides a trade-off between quality and runtime. However, since the effect is quite small, we suggest using the InertialFlowCutter separators together with our recursive algorithm, which also provides a trade-off between quality and runtime, as discussed in the next section.

Figure 8 shows the trade-off between success rate and runtime of our recursive algorithm depending on the parameter $\mu$. In the right plot, we can clearly see that less recursive calls (i.e., larger $\mu$) yields lower runtimes. The plot on the left shows that the success rate already starts on a high level for large $\mu$, which agrees with our previous observation that the two-step variant⁴⁴4We note that the two-step variant is incomparable with the recursive variant. The two-step variant always makes two recursive calls, one for each subpath on the top level. The recursive variant might, e.g., make multiple nested recursive calls but always only for one of the two subpaths. already yields good results. From this high level, the success rate further increases for smaller $\mu$. A success rate of at least $90\%$ for the first alternative is obtained for $\mu \ge 0.3$ and with $\mu =0.3$, we obtain a runtime of just below $6\mathrm{ms}$. As $90\%$ is comparable with the state-of-the-art, we suggest and use $\mu =0.3$ as the default value.