Finding k-dissimilar paths with minimum collective length
Chondrogiannis T, Bouros P, Gamper J, Leser U, Blumenthal DB (2018)
Publication Type: Conference contribution
Publication year: 2018
Publisher: Association for Computing Machinery
Pages Range: 404-407
Conference Proceedings Title: GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems
Event location: Seattle, WA
ISBN: 9781450358897
Abstract
Shortest path computation is a fundamental problem in road networks. However, in many real-world scenarios, determining solely the shortest path is not enough. In this paper, we study the problem of finding k-Dissimilar Paths with Minimum Collective Length (kDPwML), which aims at computing a set of paths from a source s to a target t such that all paths are pairwise dissimilar by at least and the sum of the path lengths is minimal. We introduce an exact algorithm for the kDPwML problem, which iterates over all possible s − t paths while employing two pruning techniques to reduce the prohibitively expensive computational cost. To achieve scalability, we also define the much smaller set of the simple single-via paths, and we adapt two algorithms for kDPwML queries to iterate over this set. Our experimental analysis on real road networks shows that iterating over all paths is impractical, while iterating over the set of simple single-via paths can lead to scalable solutions with only a small trade-off in the quality of the results.
Authors with CRIS profile
Involved external institutions
Johannes Gutenberg-Universität Mainz (JGU)
Germany (DE)
Humboldt-Universität zu Berlin
Germany (DE)
Universität Konstanz
Germany (DE)
Free University of Bozen - Bolzano
Italy (IT)
Germany (DE)
Humboldt-Universität zu Berlin
Germany (DE)
Universität Konstanz
Germany (DE)
Free University of Bozen - Bolzano
Italy (IT)
How to cite
APA:
Chondrogiannis, T., Bouros, P., Gamper, J., Leser, U., & Blumenthal, D.B. (2018). Finding k-dissimilar paths with minimum collective length. In Li Xiong, Roberto Tamassia, Kashani Farnoush Banaei, Ralf Hartmut Guting, Erik Hoel (Eds.), GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems (pp. 404-407). Seattle, WA, US: Association for Computing Machinery.
MLA:
Chondrogiannis, Theodoros, et al. "Finding k-dissimilar paths with minimum collective length." Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2018, Seattle, WA Ed. Li Xiong, Roberto Tamassia, Kashani Farnoush Banaei, Ralf Hartmut Guting, Erik Hoel, Association for Computing Machinery, 2018. 404-407.
BibTeX: Download