Logo des Repositoriums
 
Textdokument

Generierung und Abdeckung repräsentativer Pfadmengen in Straßennetzwerken

Vorschaubild nicht verfügbar

Volltext URI

Dokumententyp

Zusatzinformation

Datum

2022

Autor:innen

Zeitschriftentitel

ISSN der Zeitschrift

Bandtitel

Verlag

Gesellschaft für Informatik, Bonn

Zusammenfassung

Für die Suche nach kürzesten Pfaden in sehr großen Graphen wurden verschiedene Beschleunigungstechniken, wie z.B. Contraction Hierarchies, Hub-Labels oder Transit Node Routing, entwickelt. Um optimale Anfragezeiten und Speicherverbrauch zu erreichen, benötigen viele Beschleunigungstechniken eine Menge wichtiger Knoten. In dieser Arbeit wird eine Methode zur Berechnung wichtiger Knoten eines Graphen vorgestellt. Um diese Knoten zu finden, wird auf einer repräsentativen Pfadmenge ein Hitting Set Problem mit einem Greedy-Algorithmus gelöst. Die repräsentative Pfadmenge, die möglichst unterschiedliche kürzeste Pfade des Graphen enthalten soll, wird mit einer well-separated pair decomposition und einem Quadtree berechnet. Das Verfahren wurde mit dem deutschen Straßennetzwerk (25M Knoten) getestet und liefert hier einige tausend wichtige Knoten, mit denen bereits etwa 99.9% aller kürzesten Pfade im Graph abgedeckt sind.

Beschreibung

Berner, Lukas (2022): Generierung und Abdeckung repräsentativer Pfadmengen in Straßennetzwerken. SKILL 2022. Gesellschaft für Informatik, Bonn. PISSN: 1614-3213. ISBN: 978-3-88579-752-4. pp. 11-22. Routenberechnung. Hamburg. 29.-30. September 2022

Zitierform

DOI

Tags