Eingang zum Volltext in OPUS
Hinweis zum Urheberrecht
Dissertation zugänglich unter
URN: urn:nbn:de:bsz:93-opus-11908
URL: http://elib.uni-stuttgart.de/opus/volltexte/2002/1190/
Berechnung kürzester Wege in Straßennetzen mit Wegeverboten
NN
Schmid, Wolfgang
Originalveröffentlichung:
(2000) Deutsche Geodätische Kommission bei der Bayerischen Akademie der Wissenschaften : Reihe C ; 538
pdf-Format:
Dokument 1.pdf (931 KB)
SWD-Schlagwörter:
Straßennetz , Straßenplanung , Reiseweg , Planung , Kurze Wege , Graphentheorie
Freie Schlagwörter (Englisch):
route planning , route inhibition , graph theory
Institut:
Institut für Photogrammetrie
Fakultät:
Fakultät Bau- und Umweltingenieurwissenschaften
DDC-Sachgruppe:
Geowissenschaften
Dokumentart:
Dissertation
Hauptberichter:
Fritsch, Dieter Prof. Dr.
Sprache:
Deutsch
Tag der mündlichen Prüfung:
25.07.2000
Erstellungsjahr:
2000
Publikationsdatum:
09.09.2002
Kurzfassung auf Deutsch:
Autonome Routenplanungssysteme gewinnen in den letzten Jahren zunehmend an Bedeutung im praktischen Einsatz. Ein Test der Zeitschrift ADAC Motorwelt vom April 1997 (Ausgabe 4 Seite 36) hat die sechs gängigsten Planungssysteme auf dem deutschen Markt untersucht. Zur allgemeinen Überraschung haben die sechs Systeme bei ein und derselben Route durch München sechs teilweise unterschiedliche Lösungen angeboten. Dieses Ergebnis erlaubt den Schluß, daß die Algorithmen, Kontroll- und Programmstrukturen, die den verwendeten Programmen zugrunde liegen, durchaus noch nicht den notwendigen Standard erreicht haben. Das grundlegende Konzept der Routenplanung besteht im Finden eines kürzesten Weges. Optionale Erweiterungen des Modells, die weitere Parameter wie 'Schnellster Weg', 'Umweltfreundlichkeit', 'Geringste Belastung' usw. in Kombination verwenden, werden hier bewußt außer acht gelassen. Eine Lösung für das dringendste Problem soll hier beschrieben werden - ein Algorithmus, der den Minimalstandard der Lösung des kürzesten Wege Problems soweit erweitert, daß ein zukünftiger Test nicht mehr sechs unterschiedliche und damit für den einzelnen Anwender suboptimale Lösungen hervorbringt, sondern wirklich den kürzesten Weg. Wie lassen sich diese suboptimalen Lösungen erklären? Es gibt in einer Großstadt an ca. 40 - 50 % der Kreuzungen ein Abbiege- oder ein Wegeverbot. Diese Abbiege- und insbesondere die Wegeverbote werden teilweise von den gängigen Routenplanungssystemen falsch oder gar nicht interpretiert. In der Praxis werden Straßennetze durch Graphen repräsentiert, da Graphen die in der Informatik am häufigsten verwendete Abstraktion darstellen. Daher untersucht diese Arbeit kürzeste Wege in Graphen mit Abbiege- und Wegeverboten.
Kurzfassung auf Englisch:
NN