Schnelle Algorithmen für ressourcenbeschränkte kürzeste Wege in Verkehrsnetzen (PDF)

Diplomarbeit aus dem Jahr 2002 im Fachbereich Mathematik - Angewandte Mathematik, Note: 1,3, Technische Universität Berlin (Fachbereich Mathematik), Sprache: Deutsch, Abstract: Die Anzahl registrierter Autos hat in vielen Industrienationen inzwischen einen
kritischen Stand erreicht. Da sie allem Anschein nach weiter wachsen wird, die
Infrastruktur jedoch nicht mehr beliebig ausbaubar ist, droht aufgrund der daraus
folgenden Verkehrsdichte schon bald ein rapides Zunehmen an Staus.
Um dies zu vermeiden, versuchen einige Automobilhersteller seit einiger Zeit, sogenannte
Navigationssysteme für ihre Wagen zu entwickeln, mit denen die Verkehrsteilnehmer
möglichst schnell durch den Verkehr geleitet werden sollen. Der
nächstliegende Ansatz bestand zuerst darin, für jeden Teilnehmer den schnellsten
Weg von seinem Start- zu seinem Zielort zu berechnen. Dies lässt sich mathematisch
durch das sogenannte Kürzeste-Wege-Problem mit nicht-negativen Kantengewichten
modellieren, welches in polynomialer Zeit lösbar ist. Wie sich jedoch
schon bald herausstellte, sind in der Praxis weitere Komponenten zu berücksichtigen,
die die Berechnung eines für jeden Fahrer akzeptablen Weges erschweren.
So wäre es zum Beispiel denkbar, bei der Berechnung des schnellsten Weges zu
fordern, dass der Fahrer keinen allzu grossen Umweg zu nehmen hat. Ein solcher
ressourcenbeschränkter kürzester Weg lässt sich leider nicht in polynomialer Zeit
ermitteln, da es sich dabei um ein sogenanntes schwach NP-vollständiges Problem
handelt.
Ziel der vorliegenden Arbeit ist es, Algorithmen zu entwickeln, die dieses Problem
möglichst schnell lösen, und zu untersuchen, welche am besten für den Einsatz in
einem solchen Route-Guidance-System geeignet sind. Zu diesem Zweck wird der
für das klassische Kürzeste-Wege-Problem häufig benutzte Di jkstra-Algorithmus
an die neue Problemstellung angepasst und in mehreren Varianten mit unterschiedlichen
Beschleunigungsmethoden implementiert. Diese werden dann auf verschiedenen
Beispielinstanzen sowohl untereinander als auch im Vergleich mit für andere
Projekte verwendeten Lösungsverfahren getestet. Anhand der daraus folgenden
Ergebnisse werden dann noch einmal zusammenfassend die Vorz¿uge und Nachteile
der jeweiligen Ansätze diskutiert, bevor wir abschließend vorschlagen, welches
Verfahren für den Gebrauch als Unterproblem in einem an der TU Berlin entwickeltes
Navigationssystem vorzuziehen ist. [...]