
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.
info:eu-repo/classification/ddc/004
info:eu-repo/classification/ddc/004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 35 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
