Alternative routing : k-shortest paths with limited overlap

Abstract

Shortest path computation is a fundamental problem in road networks with application in various domains in research and industry. However, returning only the shortest path is often not satisfying; users are also interested in alternative paths which might be longer but have other advantages, e.g., less frequent traffic congestion. In this paper, we formally introduce the k-Shortest Paths with Limited Overlap (k-SPwLO) problem seeking to recommend k alternative paths which are (a) as short as possible and (b) sufficiently dissimilar based on a user-controlled similarity threshold. We propose two algorithms that examine the paths from a source s to a target t in increasing order of their length and progressively construct the result set. The baseline algorithm BSL builds upon a standard algorithm for computing k-Shortest Paths, followed by a filter step. The OnePass algorithm considers the overlap constraint in each expansion step while traversing the network. We evaluate the performance of both algorithms on real road networks and show that OnePass always outperforms BSL.