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

[img]
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:
AbstractLanguage
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:
CreatorsEmailORCID
Hasselberg, Stephankeine AngabeUNSPECIFIED
URN: urn:nbn:de:hbz:38-6237
Subjects: Mathematics
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > no entry
Language: English
Date: 2000
Referee:
NameAcademic Title
keine Angabe, UNSPECIFIED
Full Text Status: Public
Date Deposited: 10 Jun 2003 10:35
URI: http://kups.ub.uni-koeln.de/id/eprint/623

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item