Home Publications Research Grants Inventions & Patents Awards Additional Research Activities Faculties & Institutions Research Areas

Finding k-shortest paths with limited overlap

Chondrogiannis T, Bouros P, Gamper J, Leser U, Blumenthal DB (2020)

---

Publication Type: Journal article

Publication year: 2020

Journal

DOI: 10.1007/s00778-020-00604-x

Abstract

In this paper, we investigate the computation of alternative paths between two locations in a road network. More specifically, we study the k-shortest paths with limited overlap (kSPwLO) problem that aims at finding a set of k paths such that all paths are sufficiently dissimilar to each other and as short as possible. To compute kSPwLO queries, we propose two exact algorithms, termed OnePass and MultiPass, and we formally prove that MultiPass is optimal in terms of complexity. We also study two classes of heuristic algorithms: (a) performance-oriented heuristic algorithms that trade shortness for performance, i.e., they reduce query processing time, but do not guarantee that the length of each subsequent result is minimum; and (b) completeness-oriented heuristic algorithms that trade dissimilarity for completeness, i.e., they relax the similarity constraint to return a result that contains exactly k paths. An extensive experimental analysis on real road networks demonstrates the efficiency of our proposed solutions in terms of runtime and quality of the result.

Authors with CRIS profile

Involved external institutions

How to cite

APA:

Chondrogiannis, T., Bouros, P., Gamper, J., Leser, U., & Blumenthal, D.B. (2020). Finding k-shortest paths with limited overlap. Vldb Journal. https://dx.doi.org/10.1007/s00778-020-00604-x

MLA:

Chondrogiannis, Theodoros, et al. "Finding k-shortest paths with limited overlap." Vldb Journal (2020).

BibTeX: Download