Abstract
Shortest path computation is a fundamental problem in road net- works with various applications in research and industry. However, returning only the shortest path is often not satisfying. Users might also be interested in alternative paths that are slightly longer but have other desired properties, e.g., less frequent traffic congestion.
In this paper, we study alternative routing and, in particular, the k-Shortest Paths with Limited Overlap (k-SPwLO) query, which aims at computing paths that are (a) sufficiently dissimilar to each other, and (b) as short as possible. First, we propose MultiPass, an exact algorithm which traverses the network k−1 times and em- ploys two pruning criteria to reduce the number of paths that have to be examined. To achieve better performance and scalability, we also propose two approximate algorithms that trade accuracy for efficiency. OnePass+ employs the same pruning criteria as Multi- Pass, but traverses the network only once. Therefore, some paths might be lost that otherwise would be part of the solution. ESX computes alternative paths by incrementally removing edges from the road network and running shortest path queries on the updated network. An extensive experimental analysis on real road networks shows that: (a) MultiPass outperforms state-of-the-art exact algo- rithms for computing k-SPwLO queries, (b) OnePass+ runs sig- nificantly faster than MultiPass and its result is close to the exact solution, and (c) ESX is faster than OnePass+ (though slightly less accurate) and scales for large road networks and large values of k.