Finding k-shortest paths with limited overlap

Next, we elaborate on the complexity of the \(k\text {SPwLO}\).

A naïve approach for computing \(k\text {SPwLO}\) queries is to enumerate all paths from s to t and choose the subset that satisfies Definition 2. This is clearly impractical. A more efficient approach involves the examination of paths in increasing length order. After adding the shortest path \(p_{sp} (s{\rightarrow }t)\) to the result set \(P_{ LO }\), every next path p in length order is constructed using some algorithm for the K-shortest paths [16, 23, 37]. If p is an alternative to \(P_{ LO }\), then p is added to the result. This process continues until \(P_{ LO }\) contains k paths or all paths from s to t have been examined. Despite its simplicity, this approach is not practical even for small road networks. Chondrogiannis et al. [9] introduced the BSL algorithm that captures this approach and showed that the number of constructed paths is prohibitively high. In the worst case, all paths from s to t have to be constructed, which is a well-known \(\#P\)-complete problem [33].

To improve computation even further, Liu et al. [22] proposed the FindKSPD algorithm that employs two lower bounds. The first bound is determined using a reverse shortest path tree, while the second is derived from the similarity function of Eq. 1. These bounds prioritize the examination of paths that are more likely to lead to the next shortest alternative path. In practice though, the number of examined paths is still very high. Our experiments in Sect. 9 show that our exact algorithms clearly outperform FindKSPD.

Regardless of the approach, it is important to note that computing an exact solution to a \(k\text {SPwLO}\) query is not always possible. For instance, consider the query \(k\text {SPwLO} (G,s,t,5,0.3)\) on our running example in Fig. 2. By examining paths in length order aiming for constructing the \(P_{ LO }\) result, we obtain the set \(\{p_1,p_4,p_{11}\}\) that contains less than the requested five paths but still satisfies both conditions of Definition 2. We call such a set of paths an incomplete solution. Apparently, if an exact algorithm returns an incomplete result, then an exact solution for the given combination of k and \(\theta \) does not exist. Nevertheless, as an incomplete result may still be meaningful to the user, our algorithms in Sects. 5 and 6 return the incomplete result if a complete solution does not exist.

Throughout this paper, we consider a single optimization criterion (i.e., edge weight) and a single constraint (i.e., path overlap) for computing alternative routes. However, our problem definition and our solutions can be adapted to take into account more optimization criteria and/or constraints. A direct approach would be to have composite weights assigned to the edges of the road network edges using a linear combination of multiple criteria. Standard multicriteria optimization can also be supported, as the term ‘shortest’ can be interpreted as ‘the best path according to a set of optimization criteria’. This, however, would also increase the complexity of the problem. With regard to additional constraints, despite focusing on the path overlap, our problem definition and all the algorithms we present support any monotonic similarity measure. Nevertheless, our aim is to provide a general purpose solution. Investigating optimization criteria and/or constraints that might be interesting in specific application scenarios is out of the scope of this paper.

OnePass, our first exact algorithm, traverses the road network expanding paths from the source node s while pruning partially expanded paths that cannot lead to a result as early as possible. We call such paths infeasible. For this purpose, we first introduce the notion of one-way similarity, which enables the comparison of partially expanded paths \(p(s{\rightarrow }n)\) to paths \(p(s{\rightarrow }t)\) already in the tentative result set. Formally:Compared to Eq. 1, we observe that Eq. 2 is asymmetric, i.e., \(\overrightarrow{Sim} (p',p) \not \equiv \overrightarrow{Sim} (p,p')\). The following lemma follows naturally from the asymmetric nature of Eq. 2.

Lemma 1 unveils the monotonicity of the one-way similarity that enables the incremental computation of Eq. 1. Given two paths p and \(p'\), to compute \(\overrightarrow{Sim} (p,p')\) it suffices to accumulate the individual similarities of the edges of the longer path. Formally:Apart from enabling the incremental computation of the similarity measure, Lemma 3 also enables the early pruning of partially expanded paths that cannot lead to a solution. Let \(p_{sub}\) be a subpath of p. If \(p_{sub}\) shares some edges with some \(p_i \in P_{ LO } \), then p contains all those edges as well. From Eq. 2, we have \(\overrightarrow{Sim} (p_{sub},p_i) \le \overrightarrow{Sim} (p,p_i)\). Hence, given a similarity threshold \(\theta \), if there exists \(p_i \in P_{ LO } \) such that \(\overrightarrow{Sim} (p_{sub},p_i) \ge \theta \), then path p is infeasible and can be safely discarded. This pruning criterion is formally captured by the following lemma:

As a result of Lemma 2, we observe that, if the one-way similarity of a path \(p(s{\rightarrow }n)\) violates the threshold \(\theta \), then all of its extensions \(p(s{\rightarrow }n) \circ p(n{\rightarrow }t)\) to target node t are infeasible as they violate the similarity constraint.

Next, we present the OnePass algorithm that traverses the road network, expanding every path from source node s that qualifies the pruning criterion of Lemma 2. Similar to all label-setting algorithms, OnePass maintains a set of labels \(\varLambda (n)\), where each label \(\langle n,p(s{\rightarrow }n) \rangle \) represents a path from s to n.² The paths are examined in increasing length order. By doing so, OnePass ensures that the shortest alternative path to each tentative \(k\text {SPwLO}\) result is computed. Let \(P_{ LO } = \{p_1,\ldots ,p_k\}\) be the result of a \(k\text {SPwLO}\) query. Every path \(p_{i+1}\) is the shortest alternative to each tentative result \(P_{ LO } ^{i} = \{p_1,\ldots ,p_{i}\}\). Since after the computation of each alternative path more paths are pruned but no new edges are added, every subsequent result path \(p_{i+1}\) will be longer than every \(p_i \in P_{ LO } ^{i}\). Hence, \(\overrightarrow{Sim} (p_{i+1},p_i) = Sim (p_{i+1},p_i)\) for all \(p_i \in P_{ LO } ^{i}\).

Algorithm 1 illustrates the pseudocode of OnePass. First, the shortest path \(p_{sp} (s{\rightarrow }t)\) is retrieved and the result set \(P_{ LO } \) is initialized with \(p_{sp} \) in Line 1. The algorithm uses a min priority queue \({\mathcal {Q}}\) (initialized with label \(\langle s,\emptyset \rangle \) in Line 2) to traverse the road network. Between Lines 5-16, OnePass examines the contents of \({\mathcal {Q}}\) until either \(P_{ LO } \) contains k paths or the queue is depleted. At each round, current label \(\langle n, p_n \rangle \) is popped from \({\mathcal {Q}}\) (Line 6). If n is the target node t, then \(p_n\) is recommended, i.e., added to \(P_{ LO } \) (Line 8). Next, between Lines 8–10, for each label \(\langle n_q, p_q \rangle \) in \({\mathcal {Q}}\), OnePass computes the similarity of \(p_q\) to the newly recommended path \(p_n\) and determines whether \(p_q\) qualifies the pruning criterion of Lemma 2; in particular, if \(\overrightarrow{Sim} (p_q,p_n) > \theta \) then \(p_q\) can be safely discarded. If node n is not the target t, the algorithm expands the current path \(p_n\) considering all outgoing edges \((n,n_c)\) (Lines 13-16), provided that the new path \(p_c \leftarrow p_n \circ (n,n_c)\) qualifies the pruning criterion of Lemma 2 (Line 15). Finally, OnePass returns the result set \(P_{ LO } \) in Line 17. Note that if \({\mathcal {Q}}\) is depleted before k paths are added to the result, then the result set \(P_{ LO }\) is incomplete and an exact solution does not exist.

Complexity analysis Since the pruning criterion of Lemma 2 does not give any guarantee as to how many paths are pruned, in the worst case OnePass has to enumerate all \((s{\rightarrow }t)\) paths. If K is the number of such paths, OnePass runs in \({\mathcal {O}}({{\,\mathrm{poly}\,}}(K))\) time. K is vastly superpolynomial, i.e., \({\mathbb {E}}(K)=\varOmega ((|N|-2)!d^{|N|})\) for random graphs with density d [28], which implies that OnePass is prohibitively expensive.

Despite employing the pruning criterion of Lemma 2, OnePass still has to expand and examine a large portion of all possible \(p(s{\rightarrow }t)\) paths. To address this shortcoming, we introduce MultiPass, our second exact algorithm. In addition to the pruning criterion of Lemma 2, MultiPass employs a second pruning criterion that aims at reducing the search space by avoiding the expansion of non-promising paths.

Let \(p_{sp} (s{\rightarrow }t)\) be the shortest path from a source node s to a target t as illustrated in Fig. 5. In addition, let \(p_{i}(s{\rightarrow }n)\) and \(p_{j}(s{\rightarrow }n)\) be two distinct paths from source s to a node n of the shortest path \(p_{sp} \) such that \(\ell (p_{i}){<}\ell (p_{j})\). Assuming that both \(p_i\), \(p_j\) are extended to reach t following the same path \(p(n{\rightarrow }t)\), any extension of \(p_{i}\) will be shorter than the respective extension of \(p_{j}\). Furthermore, let \(\overrightarrow{Sim} (p_i,p_{sp}) \le \overrightarrow{Sim} (p_j,p_{sp})\), i.e., the similarity of \(p_{i}\) with \(p_{sp} \) is equal or lower than the similarity of \(p_{j}\) with \(p_{sp} \). Due to the monotonicity of the one-way similarity, any extension of \(p_{i}\) to n will have the same or less similarity with \(p_{sp} \) compared to the respective extension of \(p_{j}\). As a result, for any extension of \(p_{j}\) there will always be a shorter extension of \(p_{i}\) with less or equal similarity with \(p_{sp} \); thus, \(p_{j}\) can be pruned. The same idea can be utilized to prune the search space when computing the shortest alternative path to a set of paths P. This pruning criterion is formally captured by the following lemma:

Lemma 3 can be utilized to compute the shortest alternative to a set of paths as follows. Let P be the set of paths for which we want to compute the shortest alternative path, and \(P_n\) the set of paths from s to some node n created during the expansion of all paths from s. If \(P_n\) contains a path \(p'(s{\rightarrow }n)\) such that (a) \(p'\) is longer than any path \(p_n \in P_n \setminus \{p'\}\), and (b) for every path \(p \in P\) the similarity \(\overrightarrow{Sim} (p',p)\) is higher than \(\overrightarrow{Sim} (p_n,p)\) for all paths \(p_n \in P_n \setminus \{p'\}\), then \(p'\) can be pruned. Note that the addition of a path in \(P_n\) may render Condition (B) of Definition 2 not applicable for another path already in \(P_n\). To ensure that set \(P_n\) always contains only paths that satisfy Conditions (A) and (B), we have to check whether both conditions still hold every time a new path is added to \(P_n\).

We now present MultiPass, an algorithm that employs the pruning criteria of both Lemma 2 and Lemma 3. For each node n of the road network, MultiPass maintains a set of labels \(\varLambda (n)\). Each label represents a path from s to n and is of the form \(\langle n,p(s{\rightarrow }n) \rangle \)³. The algorithm examines paths from s in increasing order of their length and expands every path \(p(s{\rightarrow }n)\) from s to a node n that satisfy the conditions set by Lemma 2 and Lemma 3. Similar to OnePass, by examining paths from s in length order, MultiPass ensures that the shortest alternative path to each tentative \(k\text {SPwLO}\) result is computed.

Algorithm 2 illustrates the pseudocode of MultiPass. First, the \(P_{ LO } \) result set is initialized to the shortest path in Line 1. Before each round, a min priority queue \({\mathcal {Q}}\) is initialized to \(\langle s,\emptyset \rangle \) (Line 3) and each node n is associated with a (initially empty) set of labels \(\varLambda (n)\) (Lines 4–5). At each round in Lines 5-20, MultiPass pops label \(\langle n,p_n \rangle \) for current path \(p_n\) in Line 7. If n is the target t, then \(p_n\) is added to \(P_{ LO } \) and the round terminates (Lines 8–10). Otherwise, MultiPass expands \(p_n\) considering all outgoing edges \((n,n_c)\) (Lines 11–17). Each new path \(p_c \leftarrow p_n\circ (n, n_c)\) (Line 13) is evaluated against the pruning criteria of Lemma 2 (Lines 14–15) and Lemma 3 (Lines 16–17). If \(p_c\) qualifies both pruning criteria, MultiPass removes from \({\mathcal {Q}}\) and \(\varLambda (n_c)\) every label representing a path \(p'_n\) such that \(p_c\prec _{P_{ LO }} p'_n\) (Line 19). The new label is added to \({\mathcal {Q}}\) (Line 20) and \(\varLambda (n_c)\) (Line 21), and the next label is popped from \({\mathcal {Q}}\). The loop terminates when either k paths are added to \(P_{ LO } \) or \({\mathcal {Q}}\) is empty. Finally, MultiPass returns the result set \(P_{ LO }\) in Line 22. Note that, similar to OnePass if the loop terminates before k paths are found, then the result set \(P_{ LO }\) is incomplete; an exact solution does not exist.

Complexity analysis With regard to the complexity of MultiPass we state the following theorem:

Note that, in contrast to OnePass, MultiPass traverses the road network multiple times, i.e., \(k-1\) times in total. As the pruning criterion of Lemma 3 can be utilized to compute only a single alternative path to a set of paths, there is no guarantee that a path pruned at a given round of MultiPass using the pruning criterion of Lemma 3, will not lead to a result during a subsequent round. Consider again the example in Fig. 5. Let \(p_{sp} \) be the only path in the tentative set \(P_{ LO } \) of alternative paths. If during the search for the alternative path \(p_1\) to \(P_{ LO } \), \(p_j\) is pruned because \(p_i{\prec _{P}}p_j\) holds, \(p_j\) cannot be part of the shortest alternative to \(P_{ LO } \). However, there is no guarantee that \(p_j\) will not be part of the shortest alternative to both \(p_{sp} \) and \(p_1\). If \(p_i\) is a subpath of \(p_1\), then during the search for the alternative path to \(P_{ LO } = \{p_{sp},p_1\}\), \(p_i\) may be pruned much earlier by Lemma 2. Consequently, MultiPass needs to restart the traversal to ensure the correctness of the result and may potentially re-examine paths already examined in previous rounds. However, in contrast to the runtime complexity of OnePass, the runtime complexity of MultiPass does not depend on the exponentially large number K of \((s{\rightarrow }t)\) paths. Hence, despite traversing the network \(k-1\) times instead of one, MultiPass is expected to be much faster than OnePass.

Our first heuristic algorithm, denoted by OnePass \(^+\), provides a first cut solution for computing \(k\text {SPwLO}\) queries. Given a source node s and a target node t, OnePass \(^+\) traverses the road network expanding every path \(p(s{\rightarrow }n)\) from the source to a node n that qualifies both Lemma 2 and Lemma 3. This procedure is the same as one round of MultiPass. In contrast to MultiPass though, each time a new path is added to the result set \(P_{ LO } \), OnePass \(^+\) does not restart the traversal like MultiPass, but continues in a similar fashion to OnePass, thus traversing the network only once. Recall our discussion for MultiPass though, that a path which is pruned as non-promising during the current round may be promising during the next round. As such, OnePass \(^+\) cannot guarantee that the exact solution is found. However, as this case applies to only a small subset of the examined paths, the result of OnePass \(^+\) is expected to be close to the optimal solution in terms of length, a fact which is supported by our experiments in Sect. 9.

Algorithm 3 illustrates the pseudocode of OnePass \(^+\). The \(P_{ LO } \) result set is initialized to the shortest path \(p_{sp} (s{\rightarrow }t)\) (Line 1). The algorithm employs a min-priority queue \({\mathcal {Q}}\) (initialized with s in Line 2) to traverse the road network. Between Lines 5 and 22, OnePass \(^+\) examines the contents of \({\mathcal {Q}}\) until either k paths are added to \(P_{ LO } \) or \({\mathcal {Q}}\) is depleted. At each iteration, a label \(\langle n,p_n \rangle \) is popped from \({\mathcal {Q}}\) (Line 6). If node n is target t (Line 7), then \(p_n\) is added to \(P_{ LO } \) (Line 8) and the same update procedure as in OnePass takes place (Lines 9–11), i.e., all paths \(p_h\) with \(\overrightarrow{Sim} (p_h,p_c) > \theta \) are discarded. Otherwise, the algorithm expands the current path \(p_n\) considering all outgoing edges \((n,n_c)\)(Lines 13–22). OnePass \(^+\) checks whether the new path \(p_c \leftarrow p_n \circ (n,n_c)\) qualifies the pruning criteria of both Lemma 2 (Lines 15–16) and Lemma 3 (Lines 17–18) and updates \({\mathcal {Q}}\) and \(\varLambda (n_c)\) accordingly. Then, OnePass \(^+\) adds a new label for \(p_c\) to \({\mathcal {Q}}\) (Line 21) and \(\varLambda (n_c)\) (Line 22) and proceeds with popping the next label from \({\mathcal {Q}}\). Finally, the result set \(P_{ LO } \) is returned in Line 23.

Complexity analysis OnePass \(^+\) and MultiPass use the same pruning criteria. Hence, following the complexity analysis of MultiPass in Sect. 5.2, we obtain that OnePass \(^+\) enters the main while-loop at most \(O(|N|\cdot (\theta {\cdot }L)^k)\) times and that each of its iterations runs in \(O(|N|\cdot (\theta {\cdot }L)^k)\) time. Therefore, the runtime complexity of OnePass \(^+\) is \(O(|N^2|\cdot (\theta {\cdot }L)^{2k})\) time. As OnePass \(^+\) traverses the network only once, the overall runtime complexity of OnePass \(^+\) corresponds to the complexity of one traversal carried out by MultiPass.

Our second heuristic algorithm, denoted by SVP \(^+\), recommends alternative paths by employing the concept of single-via paths [2]. Given a road network \(G = (N,E)\), a source node s and a target node t, the single-via path of every node \(n \in N\) is the concatenation of the shortest paths \(p_{sp} (s{\rightarrow }n)\) and \(p_{sp} (n{\rightarrow }t)\). SVP \(^+\) aims at finding a set of k single-via paths such that: (a) the shortest single-via path, i.e., the shortest path \(p_{sp} (s{\rightarrow }t)\), is always recommended, (b) every single-via path is dissimilar to its predecessors with respect to a similarity threshold \(\theta \), and (c) all k single-via paths are as short as possible. The main idea behind SVP \(^+\) is similar to the baseline method for computing \(k\text {SPwLO}\) queries discussed in Sect. 4.2. However, instead of iterating over all possible \((s{\rightarrow }t)\) paths, SVP \(^+\) iterates over the much smaller set of single-via paths.

Algorithm 4 illustrates the pseudocode of SVP \(^+\). In Line 1, the result set \(P_{ LO } \) is initialized to the shortest path \(p_{sp} (s{\rightarrow }t)\). Then, two shortest path trees are computed, one from s to every node n of G (Line 2) and a reverse one from every node n of G to t (Line 3). During this step, all distances d(s, n) and d(n, t) are computed. The algorithm organizes the nodes of the road network according to the length of their single-via path, i.e., \(\ell (p_{svp}(n)) = d(s,n){+}d(n,t)\), inside min-priority queue \({\mathcal {Q}}\) (Lines 4–6). At each iteration between Lines 7 and 11, SVP \(^+\) pops from the queue the top element representing a node n (Line 8) and retrieves the single-via path \(p_n\) for node n (Line 9). The single-via paths are examined in increasing order of their length. In Line 10, SVP \(^+\) checks whether \(p_n\) is simple (contains no cycles) and sufficiently dissimilar to all paths currently in \(P_{ LO } \); if so, \(p_n\) is added to \(P_{ LO } \) (Line 11). The algorithm terminates when either k paths have been added to \(P_{ LO } \) or there exist no more single-via paths to examine, i.e., queue \({\mathcal {Q}}\) is depleted, in which case the \(P_{ LO }\) result set contains less than k paths. Finally, the result set \(P_{ LO } \) is returned in Line 12.

Notice that in Example 5, SVP \(^+\) fails to find the exact result for the given \(k\text {SPwLO}\) query. In particular, path \(p = \langle (s,n_3),(n_3,n_4),(n_4,t) \rangle \), which is in the exact \(k\text {SPwLO}\) result, is not a single-via path; hence, p is not examined by SVP \(^+\). At a more general level, this example shows that SVP \(^+\) is unable to compute the exact solution to a \(k\text {SPwLO}\) query if a path p is part of the exact result, but is not a single-via path.

Complexity analysis To build the set of single-via paths, SVP \(^+\) needs to run Dijkstra’s algorithm twice, which requires \(O(|E|+|N| \cdot log{|N|})\) time. Since, by definition, there is one single-via path for each node \(n\in N\setminus \{s,t\}\), the number of paths that have to be examined by SVP \(^+\) is in the worst case O(|N|). Examining whether a given single-via path should be added to the \(P_{ LO } \) set or not requires O(k) time. Therefore, the overall runtime complexity of SVP \(^+\) is \(O(|N| \cdot k + |E| + |N| \cdot log{|N|})\).

Our third heuristic algorithm, denoted by ESX, computes \(k\text {SPwLO}\) by executing shortest path searches while progressively excluding edges from the road network⁴. We identify two important factors that affect the processing of a \(k\text {SPwLO}\) query with ESX: (1) the order in which edges are removed from the road network and (2) the maintenance of the connectivity of the network. We investigate the former in detail in Sect. 6.4. Regarding the latter, removing an edge from the road network may cause the network to become disconnected. This prevents any subsequent iteration from finding a valid path. To avoid such cases, if the shortest path search fails to find a path from s and t after the removal of an edge e from the road network, ESX re-inserts e in the network and marks it as non-removable. Non-removable edges are never removed from the road network regardless of their priority.

Algorithm 5 illustrates the pseudocode of ESX. The algorithm maintains a heap \({\mathcal {H}}_i\) for each path \(p_i(s{\rightarrow }t)\) added to the \(P_{ LO }\) result set. The heap organizes every edge \(e_j\) contained in \(p_i\) according to their priority \(\mathtt {prio}(e_j)\); \({\mathcal {H}}_i\) can be either a min-heap or a max-heap depending on the strategy in which the edges are prioritized (see Sect. 6.4). Initially, the \(p_{sp} (s{\rightarrow }t)\) shortest path is added to the result and the associated heap \({\mathcal {H}}_{sp}\) is initialized with the edges of \(p_{sp} (s{\rightarrow }t)\) (Lines 1–2). The algorithm keeps track of the non-removable edges inside set \(E_{ DNR }\) (initialized to an empty set in Line 3).

In Lines 4–19, ESX iterates over the already computed paths and their heaps to determine the next alternative path, until either the \(P_{ LO }\) result set contains exactly k paths or there are no more edges to be removed from the road network. Specifically, ESX first accesses the most recently recommended path, denoted by \(p_c\) in Line 5 and then executes the loop in Lines 6–16. At each iteration of this loop, the already computed path \(p_i \in P_{ LO } \) with the highest similarity to \(p_c\) is chosen as long as \(p_i\) contains edges that can be removed from the road network. ESX then considers edge e of path \(p_i\), i.e., the top of the \({\mathcal {H}}_i\) max-heap (Line 7). If e is not marked as non-removable, then the algorithm removes the edge from road network in Line 10 and computes the new shortest path \(p_c\) in Line 11. If \(p_c\) is null, then the removal of e has rendered the network disconnected. Consequently, e is re-inserted to the road network (Line 13) and is inserted to \(E_{DNR}\) (Line 14), and ESX proceeds to the next round. Otherwise, \(p_c\) is checked whether it is an alternative to \(P_{ LO } \) (Line 16), the result set is updated accordingly in Line 17 and a new heap \({\mathcal {H}}_c\) associated with \(p_c\) is initialized with the edges of \(p_c\) in Line 18. This process is repeated until either k paths have been added to \(P_{ LO } \) or there are no more edges that can be removed, in which case the \(P_{ LO } \) result set contains less than k paths. Finally, the result set \(P_{ LO } \) is returned in Line 19.

Complexity analysis The total amount of time ESX spends in the if-block that starts in Line 16 is \(O(k\cdot |N|)\): ESX enters it \((k{-}1)\) times and then has to initialize the \({\mathcal {H}}_c\) heap. This initialization is linear in the length of \(p_c\), which is upper bounded by \(|N{-}1|\). In each iteration of the inner while-loop starting in Line 6, one edge is popped from the head associated to one of the first \((k{-}1)\) paths. Since all paths have length at most \(|N|{-}1\), ESX enters the inner while-loop as most \(O(k\cdot |N|)\) times. The most expensive operation that has to be carried out in one iteration of the inner while-loop is the shortest path computation, which requires \(O(|N|\cdot \log {|N|} + |E|)\) time. Therefore, ESX runs in \(O(k{\cdot }|N|{\cdot }(|N|{\cdot }\log {|N|} + |E|))\) time.

The order in which edges are removed from the road network affects both the result quality and the performance of ESX. Since determining the optimal order is prohibitively expensive, in what follows we describe three strategies to determine which edge to remove at each iteration. Depending on the strategy and the nature of the heap (min or max) that is used to organize the edges of a path, we discuss six variants of ESX.

Smallest/largest edge weight The first strategy uses the edge weight to select which edge to remove at each iteration. We prioritize either edges with small weight (MinW variant) or edges with large weight (MaxW variant). Removing first edges with a large weight causes the next path to be less similar to the already computed paths, thereby enabling the algorithm to terminate sooner. However, there is a higher chance that ESX will miss alternative paths that have small differences in length with the paths already found. Hence, on average the result set is expected to contain longer paths. On the contrary, prioritizing edges with a small weight decreases the chances of missing such paths, but leads to more iterations of the algorithm, thereby increasing the overall runtime of ESX.

Minimum/maximum stretch Our second strategy is to remove edges based on their stretch. Given an edge \(e = (n_i,n_j)\), let p be the shortest path from \(n_i\) to \(n_j\) computed by excluding e from the network. The stretch of an edge e is the difference between the length of p and the length of e, i.e., \(stretch(e) = \vert \ell (p) - \ell (e) \vert \). Similar to MinW/MaxW, the removal of edges with a high stretch (MaxS variant) is more likely to cause a detour, leading to paths that are less similar to the paths already in the result set and, hence, allowing ESX to find a result sooner. In contrast, prioritizing edges with a small stretch (MinS variant) leads to the examination of more paths. This increases the overall runtime, but at the same time, it also increases the chances that on average the result set will contain shorter paths.

Least/most local shortest paths Our third strategy is inspired by the edge betweenness. Given an edge e(a, b) on some path \(p \in P_{ LO } \), let \(E_{inc}(a)\) and \(E_{out}(b)\) be the set of all incoming edges \(e(n_i,a)\) to a from some nodes \(n_i \in N{\setminus }\{b\}\) and the set of all outgoing edges \(e(b,n_j)\) from b to some nodes \(n_j \in N{\setminus }\{a\}\), respectively. First, ESX computes the set \(P_s\) which contains the shortest paths \(p_{sp} (n_i,n_j)\) such that \(n_i \in E_{inc}(a)\) and \(n_j \in E_{out}(b)\). Then, ESX defines the set \(P'_s\) of all paths \(p_{sp} (n_i,n_j)\) that cross e. Finally, ESX assigns a priority to e, denoted by \(prio(e)\), which is set to \(|P'_s|\). Similar to the previous variants, the intuition behind MaxP is that the more (shortest) paths cross an edge, the more the chances that removing this edge causes a detour; thus, ESX will find an alternative path sooner. By employing MinP, ESX examines more paths and increases the chance of computing alternative paths that are shorter on average, at the cost of an increased overall runtime.

A naive solution to deal with an incomplete result set \(P_{ LO }\) is to execute multiple \(k\text {SPwLO}\) queries, each time increasing the original similarity threshold \(\theta \) manually. Such a trial-and-error approach is impractical unless there is a hint on how much to increase \(\theta \). Furthermore, executing multiple queries means that all previously computed intermediate results, e.g., rejected paths, are disregarded. To this end, we aim for a solution that determines the smallest increase of \(\theta \) that yields a complete result automatically and computes the complete result without running another query from scratch.

Let \(k\text {SPwLO} (G,s,t,k,\theta )\) be a query whose \(P_{ LO }\) result set is incomplete, i.e, \(|P_{ LO } | < k\). In addition, let \(P_{cand}\) be a set of paths from s to t with \(P_{ LO } \subseteq P_{cand}\). We will elaborate on the nature of \(P_{cand}\) and how it is computed in Sect. 7.2. Without loss of generality, assume for now that \(P_{cand}\) contains all possible \(p(s{\rightarrow }t)\) paths in road network G. By the definition of the \(k\text {SPwLO}\) problem, for every path \(p \in P_{cand}{\setminus }P_{ LO } \), there exists a shorter path \(p^{\prime } \in P_{ LO } \) such that \(Sim (p,p^{\prime }) > \theta \). Based on this, we define the maximum similarity of a path \(p \in P_{cand}\) to result set \(P_{ LO }\) as:Consequently, path \(p \in P_{cand}\) cannot be part of the result set \(P_{ LO }\), as long as either \(p^{\prime }\) is part of the result, or the similarity threshold is greater than \(\theta \) and lower than \(Sim _{max}(p,P_{ LO })\). In fact, even if we use a new similarity threshold equal or higher than \(Sim _{max}(p,P_{ LO })\), we cannot guarantee that p will be included in the new result set \(P_{ LO } \). That is because the new threshold may cause a shorter path \(p^{\prime \prime }\) with \(\ell (p^{\prime \prime }) \le \ell (p)\) to join \(P_{ LO } \) that keeps p out. In other words, with this new threshold, we can only guarantee that the result set \(P_{ LO } \) will indeed change. In this context, we next define \(\theta _{min}\) as the minimum value for the new similarity threshold such that query \(k\text {SPwLO} (G,s,t,k,\theta )\) will return an updated result as:Essentially, if the new threshold is set inside \([\theta ,\theta _{min})\), the \(P_{ LO }\) result remains unchanged, while a value equal or higher than \(\theta _{min}\) will cause \(P_{ LO }\) to change.

To ensure a complete result, we need to progressively increase \(\theta _{min}\) until \(P_{ LO }\) contains exactly k paths. This iterative procedure is captured by Complete_kSPwLO illustrated in Function 1. The function receives as input a set of candidate paths \(P_{cand}\) out of which the result will be extracted, the number k of requested paths, and an initial similarity threshold \(\theta \). The first step is to sort the paths in \(P_{cand}\) in increasing length order. Note that if \(P_{cand}\) contains less than k paths, it is impossible to return a complete result; hence, the function terminates and \(P_{ LO } \leftarrow P_{cand}\).

Next, between Lines 4 and 15 the function progressively relaxes the similarity threshold \(\theta \) until the \(P_{ LO }\) result is complete. At each round, \(\theta _{min}\) and \(P_{ LO }\) are re-initialized to 1 and the shortest path \(p_{sp}\), respectively (Lines 5-6); note that \(p_{sp}\) is the first path in \(P_{cand}\). Then, in between Lines 7 and 14, Complete_kSPwLO examines the paths in \(P_{cand}\) in increasing length order. Fix such a path p. If p is alternative to the current result set \(P_{ LO }\), p is added to \(P_{ LO }\). At this point, the function will terminate if \(P_{ LO }\) already contains k paths as the result set is now complete. In contrast, if the current path p is not alternative to \(P_{ LO }\), the current \(\theta _{min}\) is checked against \(Sim _{max}\) of p to \(P_{ LO }\) in Line 13 and is updated in Line 14 accordingly using Eqs. 4 and 5. Finally, the value of \(\theta \) is relaxed, i.e., increased to \(\theta _{min}\) to prepare for the next round. Note that the while loop eventually terminates due to the condition in Line 10, i.e., after k paths are added to \(P_{ LO }\).

Complexity analysis The runtime of function Complete_kSPwLO depends on the size of \(|P_{cand}|\). At each round, the number of paths examined by Complete_kSPwLO is \(O(|P_{cand}|)\). To determine whether a path should be added to \(P_{ LO } \) or not requires O(k) time. Furthermore, as for each path we keep at most \(k{-}1\) similarities with paths in the result set, to add a single path to \(P_{ LO } \) we need, in the worst case, to run an iteration for all the similarities of all paths, i.e., \(O(|P_{cand}|{\cdot }k)\) iterations. Since, we need to fill the result set with k paths, the total number of iterations is \(O(|P_{cand}|{\cdot }k^2)\). Therefore, the overall runtime complexity of Complete_kSPwLO is \(O(|P_{cand}|^2{\cdot }k^3)\).

As discussed in the previous subsection, the Complete_kSPwLO function can operate with any arbitrary set of \((s{\rightarrow }t)\) paths as input. The only requirement dictated by Definition 2 for \(P_{cand}\) is to include the shortest path from s to t.

Paradigm 1 outlines the completeness-oriented computation of \(k\text {SPwLO} (G,s,t,k,\theta )\) queries. Initially, the query is processed by a \(k\text {SPwLO}\) algorithm. Besides \(P_{ LO }\), the algorithm also returns the candidate set \(P_{cand}\) of paths from s to t. If \(P_{ LO }\) contains k paths, the result is already complete and the computation terminates. Otherwise, the completeness process takes over in between Lines 4 and 6. To deliver a complete result set, \(P_{cand}\) must contain k or more paths. To this end, if \(P_{cand}\) contains less than k paths, we add to it the k-shortest paths from s to t (Lines 4-5). Finally, \(P_{cand}\) is fed to the Complete_kSPwLO to produce a complete \(P_{ LO }\) result in Line 6.

In practice, using all possible paths from s to t as \(P_{cand}\) is prohibitively expensive. Therefore, we rely on the \(k\text {SPwLO}\) algorithms to provide a set of candidate paths. Not all of our \(k\text {SPwLO}\) algorithms are compatible with Paradigm 1 though. Algorithms that traverse the original network, i.e., exact OnePass, MultiPass and heuristic OnePass \(^+\), do not qualify for this purpose, as the only \((s{\rightarrow }t)\) paths these algorithms construct are the ones that constitute the result set. On the contrary, this is possible with SVP \(^+\) and ESX; recall that SVP \(^+\) considers concatenations of single-via paths as candidate results (cf. Algorithm 4, Line 9) while ESX constructs candidate paths by removing edges (cf. Algorithm 5, Line 11). We denote by SVP-C and ESX-C the algorithms that follow Paradigm 1 and employ SVP \(^+\) and ESX respectively to compute an initial \(P_{ LO }\) result and a set of candidate paths \(P_{cand}\).

Figure 11 reports the runtime of our exact algorithms for processing \(k\text {SPwLO}\) queries while varying parameter k. As expected, the runtime of all algorithm goes up for increasing values of k since more paths need to be examined. MultiPass clearly outperforms both OnePass and FindKSPD [22] and, in most cases, by a large margin. By utilizing the pruning criterion of Lemma 3, MultiPass is able to significantly reduce the total number of examined paths, even though it scans the network multiple times. Furthermore, while OnePass is always faster than FindKSPD, none of these two algorithms scale. Even for the road networks of Rome and Oldenburg, the smallest networks used in our experiment, both algorithms require in most cases several seconds on average to process \(k\text {SPwLO}\) queries.

Figure 12 reports the runtime of our exact algorithms for processing \(k\text {SPwLO}\) queries while varying parameter \(\theta \). Similar to varying k, MultiPass is clearly the fastest exact algorithm. We also observe that the runtime of OnePass and FindKSPD increases for decreasing values of \(\theta \) while the runtime of MultiPass peaks for \(\theta =0.3\). This result reveals an important trade-off: as \(\theta \) increases, the pruning power of Lemma 2 deteriorates, and, MultiPass constructs more (partial) paths. At the same time, the next path added to the result set is shorter due to the higher similarity threshold, and hence, the algorithm terminates earlier. With a decreasing \(\theta \), the pruning power of Lemma 3 also increases and more partial paths are pruned.

Next, we report the performance, result quality, and completeness of our heuristic algorithms.

To sum up, our experimental analysis concludes into three key findings. First, our tests for the exact computation of \(k\text {SPwLO}\) are in line with the theoretical analysis on the optimality of MultiPass (cf. Sect. 5.2). MultiPass is the fastest exact algorithm outperforming both OnePass and FindKSPD [22] by a significant margin. However, MultiPass is practical only for \(k=2\). For \(k > 2\), MultiPass is practical only on small road networks, as its response time even for mid-sized road networks is prohibitively high.

Two out of our three performance-oriented heuristic algorithms manage to address this scalability issue. More specifically, despite being an improvement over MultiPass in terms of runtime and computing a result set that is close to the exact solution, OnePass \(^+\) does not scale on large road networks. On the contrary, SVP \(^+\) and ESX are both significantly faster than OnePass \(^+\) and able to scale, but on average they compute slightly longer alternative paths. Overall, ESX is the best choice as it is the fastest performance-oriented heuristic algorithm while recommending more and shorter alternative paths than SVP \(^+\).

Finally, in applications where a complete result is required, i.e., exactly k alternative paths must be retrieved, we distinguish between two cases. If the response time matters more than the quality of the complete result set, ESX-C is the algorithm of choice as it inherits the performance advantage of ESX. However, if result quality is more important, SVP-C is preferred as its candidate set enables the Complete_kSPwLO to find a result set of more dissimilar paths than ESX-C.

To provide additional insights on how our approach could be used in practice, in Fig. 24 we visualize different sets of 3 alternative paths between two locations in the city of Oldenburg, setting the similarity threshold \(\theta =50\%\). Figure 24a shows the K-shortest paths, which clearly have little practical value since they are too similar to each other. On the contrary, both the \(k\text {SPwLO}\) shown in Fig. 24b and the results of our heuristic algorithms shown in Fig. 24d–f offer much more attractive alternative paths. As the heuristic algorithms compute fairly similar results to the \(k\text {SPwLO}\), in applications where response time is important, we expect these results to be satisfactory. We also visualize the result of a randomized search to examine how better or worse the alternative paths would be if they were to be selected at random. We first add the shortest path into the result set, and then, we execute \(k{-}1\) random walks in order to obtain k paths in total. We repeat this process multiple times and keep the best result in terms of shortness. Figure 24c shows that the alternative paths obtained using this randomization are too long and contain too many needless detours, even after 1000 iterations to improve the result quality.