Some results on heuristical algorithms for shortest path problems in large road networks

Hasselberg, Stephan (2000). Some results on heuristical algorithms for shortest path problems in large road networks. PhD thesis, Universität zu Köln. Open Access

Preview

PDF
11v3933.pdf
Download (85MB)

Abstract

This thesis studies the shortest path problem in large road networks. The classical algorithm for networks with non-negative edge weights is due to Dijkstra and has a worst-case performance of O ( |E |+ |V |log |V |) using a simple priority queue as data structure for temporarily labeled nodes. We present a new, so-called tree heuristic, which is based on the similarity of shortest path trees and which can be used to speed up the shortest path search especially in practical applications like microscopic simulation of traffic or route guidance systems. Instead of searching a path in the original network, the tree heuristic partitions the network into classes of about equal size and constructs a special searchgraph for each class. On a test road network of about one million nodes the tree heuristic outperforms Dijkstra\'s algorithm by a factor of more than three with respect to runtime and about seven with respect to permanently labeled nodes where the found paths can be expected to have a relative error below 1%, if the starting and end node are not too close to each other. We also analyze the A -algorithm with overdo-factor, originally devised for Euclidean networks and derive an interval [1.... 27......,5] from which an optimal overdo-factor should be chosen in practical applications. Finally we give an algorithm which calculates edge tolerances for a shortest path and which can be used to generate reasonable alternative routes to the exact shortest path.

Item Type:

Thesis (PhD thesis)

Translated abstract:

Abstract

Language

In dieser Arbeit wird das Problem, einen kürzesten Weg in einem großen Straßengraphen zu finden, untersucht. Der klassische Lösungsalgorithmus f ür Graphen mit nicht-negativer Kostenfunktion ist der Algorithmus von Dijkstra mit einem Laufzeitverhalten von O ( |E |+ |V |log |V |) unter Benutzung einer einfachen Priority Queue als Datenstruktur f ür temporär markierte Knoten. Wir stellen eine neue, sogenannte Baumheuristik vor, die auf der Ähnlichkeit von kürzesten-Wege-Bäumen basiert und besonders in praktischen Anwendungen wie beispielsweise in der mikroskopischen Verkehrssimulation oder bei Online-Routingsystemen eingesetzt werden kann. Anstatt einen Weg im Gesamtgraphen zu suchen, partitioniert die Baumheuristik den Graphen in Klassen von in etwa gleicher Größe und konstruiert einen speziellen Suchgraphen für jede Klasse. Auf einem Testgraphen mit ca. einer Million Knoten ist die Baumheurisitk um einen Faktor größer drei schneller als Dijkstra\'s Algorithmus bzgl. der Laufzeit. Die von der Baumheuristik gefundenen Wege haben dabei einen erwarteten Fehler von unter 1%, sofern Start- und Endknoten der Suche nicht zu nahe beieinander liegen. Ferner analysieren wir den A -Algorithmus mit Overdo-Faktor, der ursprünglich für Euklidische Netzwerke entworfen wurde, und leiten ein Intervall [1.... 27......,5] her, aus dem ein optimaler Overdo-Faktor in praktischen Anwendungen gewählt werden sollte. Abschließend stellen wir einen Algorithmus zur Bestimmung von Toleranzen für die Kantengewichte eines kürzesten Weges vor, der verwendet werden kann, um sinnvolle Alternativrouten zum kürzesten Weg zu finden.

German

Creators: