Alternative routing : k-shortest paths with limited overlap

Cite This

Files in this item

Checksum: MD5:706d6c75e0896ebf8f05a86b80a3aaa2

CHONDROGIANNIS, Theodoros, Panagiotis BOUROS, Johann GAMPER, Ulf LESER, 2015. Alternative routing : k-shortest paths with limited overlap. 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. Seattle, Washington, Nov 3, 2015 - Nov 6, 2015. In: Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York, NY:ACM Press, 68. ISBN 978-1-4503-3967-4. Available under: doi: 10.1145/2820783.2820858

@inproceedings{Chondrogiannis2015Alter-41130, title={Alternative routing : k-shortest paths with limited overlap}, year={2015}, doi={10.1145/2820783.2820858}, isbn={978-1-4503-3967-4}, address={New York, NY}, publisher={ACM Press}, booktitle={Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems}, author={Chondrogiannis, Theodoros and Bouros, Panagiotis and Gamper, Johann and Leser, Ulf}, note={Article Number: 68} }

<rdf:RDF xmlns:dcterms="" xmlns:dc="" xmlns:rdf="" xmlns:bibo="" xmlns:dspace="" xmlns:foaf="" xmlns:void="" xmlns:xsd="" > <rdf:Description rdf:about=""> <dspace:isPartOfCollection rdf:resource=""/> <dcterms:hasPart rdf:resource=""/> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:contributor>Chondrogiannis, Theodoros</dc:contributor> <dc:rights>terms-of-use</dc:rights> <dc:contributor>Gamper, Johann</dc:contributor> <dc:creator>Leser, Ulf</dc:creator> <dc:contributor>Bouros, Panagiotis</dc:contributor> <dcterms:abstract xml:lang="eng">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.</dcterms:abstract> <dspace:hasBitstream rdf:resource=""/> <dcterms:rights rdf:resource=""/> <dc:date rdf:datatype="">2018-01-24T12:32:20Z</dc:date> <dcterms:issued>2015</dcterms:issued> <dc:creator>Gamper, Johann</dc:creator> <dcterms:title>Alternative routing : k-shortest paths with limited overlap</dcterms:title> <dc:language>eng</dc:language> <dcterms:isPartOf rdf:resource=""/> <dc:creator>Chondrogiannis, Theodoros</dc:creator> <bibo:uri rdf:resource=""/> <dc:contributor>Leser, Ulf</dc:contributor> <dcterms:available rdf:datatype="">2018-01-24T12:32:20Z</dcterms:available> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:creator>Bouros, Panagiotis</dc:creator> </rdf:Description> </rdf:RDF>

Downloads since Jan 24, 2018 (Information about access statistics)

Chondrogiannis_2-1c1tkagu2twpj6.pdf 574

This item appears in the following Collection(s)

Search KOPS


My Account