Finding k-Dissimilar Paths with Minimum Collective Length

Lade...
Vorschaubild
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2018
Autor:innen
Bouros, Panagiotis
Gamper, Johann
Leser, Ulf
Blumenthal, David B.
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
Internationale Patentnummer
EU-Projektnummer
DFG-Projektnummer
Projekt
Open Access-Veröffentlichung
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen in
Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York, NY: ACM Press, 2018, pp. 404-407. ISBN 978-1-4503-5889-7. Available under: doi: 10.1145/3274895.3274903
Zusammenfassung

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.

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Alternative Routing, Route Planning, Path Similarity
Konferenz
The 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems : SIGSPATIAL '18, 6. Nov. 2018 - 9. Nov. 2018, Seattle, Washington
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690CHONDROGIANNIS, Theodoros, Panagiotis BOUROS, Johann GAMPER, Ulf LESER, David B. BLUMENTHAL, 2018. Finding k-Dissimilar Paths with Minimum Collective Length. The 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems : SIGSPATIAL '18. Seattle, Washington, 6. Nov. 2018 - 9. Nov. 2018. In: Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York, NY: ACM Press, 2018, pp. 404-407. ISBN 978-1-4503-5889-7. Available under: doi: 10.1145/3274895.3274903
BibTex
@inproceedings{Chondrogiannis2018-09-18Findi-44861,
  year={2018},
  doi={10.1145/3274895.3274903},
  title={Finding k-Dissimilar Paths with Minimum Collective Length},
  isbn={978-1-4503-5889-7},
  publisher={ACM Press},
  address={New York, NY},
  booktitle={Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems},
  pages={404--407},
  author={Chondrogiannis, Theodoros and Bouros, Panagiotis and Gamper, Johann and Leser, Ulf and Blumenthal, David B.}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/44861">
    <dcterms:abstract xml:lang="eng">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.</dcterms:abstract>
    <dc:contributor>Gamper, Johann</dc:contributor>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-02-05T13:46:33Z</dc:date>
    <dc:creator>Bouros, Panagiotis</dc:creator>
    <dc:contributor>Bouros, Panagiotis</dc:contributor>
    <dc:language>eng</dc:language>
    <dcterms:title>Finding k-Dissimilar Paths with Minimum Collective Length</dcterms:title>
    <dc:creator>Blumenthal, David B.</dc:creator>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Leser, Ulf</dc:contributor>
    <dc:creator>Gamper, Johann</dc:creator>
    <dcterms:issued>2018-09-18</dcterms:issued>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44861"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:contributor>Blumenthal, David B.</dc:contributor>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:creator>Leser, Ulf</dc:creator>
    <dc:creator>Chondrogiannis, Theodoros</dc:creator>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-02-05T13:46:33Z</dcterms:available>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Chondrogiannis, Theodoros</dc:contributor>
  </rdf:Description>
</rdf:RDF>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet