Alternative routing : k-shortest paths with limited overlap


Dateien zu dieser Ressource

Prüfsumme: 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, 3. Nov 2015 - 6. Nov 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=""/> <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=""/> <dcterms:rights 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>

Dateiabrufe seit 24.01.2018 (Informationen über die Zugriffsstatistik)

Chondrogiannis_2-1c1tkagu2twpj6.pdf 105

Das Dokument erscheint in:

KOPS Suche


Mein Benutzerkonto