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. [...]
Inhaltsverzeichnis
1 Einleitung
1.1 Anwendungsgebiete
1.2 Das CMCF Route-Guidance-Projekt an der TU Berlin
1.3 Das CNOP-Paket
1.4 Anforderungen an die Problemlösungen
2 Beschleunigungsmethoden für das Kürzeste-Wege-Problem mit nicht-negativen Kantengewichten
2.1 Problemstellung
2.2 Der Dijkstra-Algorithmus
2.2.1 Formulierung
2.2.2 Korrektheit und Laufzeit
2.3 Beschleunigungsmethoden für den Dijkstra-Ansatz
2.3.1 Der zielgerichtete Ansatz
2.3.2 Der bidirektionale Ansatz
2.3.3 Verbindung des zielgerichteten und des bidirektionalen Ansatzes
3 Ressourcenbeschränkte Wege
3.1 Problemstellung
3.1.1 Das ressourcenbeschränkte Kürzeste-Wege-Problem
3.1.2 Pareto-optimale ressourcenbeschränkte Wege
3.1.3 Das doppelt beschränkte Problem
3.1.4 Beziehung zwischen den drei betrachteten Problemen
3.2 Grundlegende Eigenschaften des ressourcenbeschränkten Kürzeste-Wege-Problems
3.2.1 Komplexität
3.2.2 Bisherige Ansätze
3.3 Der erweiterte Dijkstra-Algorithmus
3.3.1 Die Grundversion
3.3.2 Die zielgerichtete Version
3.3.3 Die bidirektionale Version
3.3.4 Die bidirektional zielgerichtete Version
3.3.5 Versionen mit zusätzlichem Abbbruchkriterium
3.4 Weitere Lösungsmethoden
3.4.1 Der Labeling-Ansatz im CMCF-Projekt
3.4.2 Die 2-Phasen-Methode im CNOP-Paket
3.5 Überblick über die vorgestellten Algorithmen
4 Implementation und Geschwindigkeitsvergleiche
4.1 Angaben zur Implementation
4.1.1 Verwendete Datenstrukturen
4.1.2 Korrektur von Rechnerungenauigkeiten
4.1.3 Einlesen des Verkehrsnetzwerkes
4.1.4 Besonderheiten beim Aufruf des CMCF-Programms
4.2 Vergleiche
4.2.1 Tests auf LEDA-Graphen
4.2.2 Tests auf Raw-Graphen
5 Zusammenfassung
5.1 Interpretation der Ergebnisse
5.2 Empfehlung für das Route-Guidance-Projekt an der TU Berlin
Zielsetzung und thematische Schwerpunkte
Das Hauptziel dieser Arbeit besteht darin, effiziente Algorithmen für ressourcenbeschränkte Kürzeste-Wege-Probleme in Verkehrsnetzen zu entwickeln und deren Eignung für den Einsatz in Route-Guidance-Systemen zu evaluieren, um die Gesamtlaufzeit bei deren Berechnung spürbar zu reduzieren.
- Entwicklung und Optimierung von Algorithmen basierend auf dem Dijkstra-Verfahren.
- Untersuchung von Beschleunigungsmethoden wie bidirektionaler Suche und zielgerichteter Transformation.
- Vergleich verschiedener Lösungsansätze anhand von Zufallsgraphen und Verkehrsnetz-Daten.
- Implementierung von Lösungen für ressourcenbeschränkte, Pareto-optimale sowie doppelt beschränkte Probleme.
- Analyse der Performance im Kontext von realen Navigationsprojekten wie dem CMCF-Projekt.
Auszug aus dem Buch
Der zielgerichtete Ansatz
Der zielgerichtete Ansatz versucht, den kürzesten Weg schneller zu finden, indem er Teilwege, die offensichtlich zu einem langem s-t-Weg führen, nicht weiter betrachtet. Dies wird erreicht, indem die Kantengewichte transformiert werden, so dass genau die Kanten, welche in die Richtung des Zielknotens führen, vom Algorithmus bevorzugt werden, während solche, die in die entgegengesetzte Richtung laufen, mit einem ungünstigeren Kostenwert bestraft werden.
Zur korrekten Ausführung werden untere Schranken LB(v,t) für die kürzesten Wege von allen Knoten v E V zum Zielknoten t benötigt. Die folgenden modifizierten Kantenbewertungen werden dann benutzt:
c'(v,w) := c(v,w) - LB(v,t) + LB(w,t)
Wie wir in Abbildung (2.2) gut erkennen können, wird somit der gewünschte Effekt erreicht. Die Kante (v,w1) wird gegenüber (v,w2) bevorzugt behandelt, da die untere Schranke für den restlichen w1-t-Weg kleiner als LB(w2,t) ist.
Der Dijkstra-Algorithmus funktioniert wie bereits erwähnt nur für nicht-negative Kantengewichte. Möchte man deswegen das Verfahren mit den transformierten Kantenkosten benutzen, so muss für die unteren Schranken folgende Konsistenzbedingung gelten:
c(v,w) + LB(w,t) >= LB(v,t)
Zusammenfassung der Kapitel
1 Einleitung: Dieses Kapitel motiviert die Problemstellung ressourcenbeschränkter Wege in der Verkehrsplanung und definiert die Anforderungen an die Algorithmen für verschiedene Anwendungskontexte.
2 Beschleunigungsmethoden für das Kürzeste-Wege-Problem mit nicht-negativen Kantengewichten: Es werden Grundlagen des klassischen Dijkstra-Algorithmus sowie Techniken zur Beschleunigung wie zielgerichtete und bidirektionale Ansätze erläutert.
3 Ressourcenbeschränkte Wege: Dieser Hauptteil führt die mathematische Problemstellung für ressourcenbeschränkte, Pareto-optimale und doppelt beschränkte Probleme ein und präsentiert diverse erweiterte Algorithmen.
4 Implementation und Geschwindigkeitsvergleiche: Hier werden technische Details der Implementierung besprochen und die verschiedenen Algorithmen anhand von umfangreichen Testreihen verglichen.
5 Zusammenfassung: Die Ergebnisse werden interpretiert und es werden konkrete Empfehlungen für das Route-Guidance-Projekt an der TU Berlin ausgesprochen.
Schlüsselwörter
Kürzeste-Wege-Problem, Ressourcenbeschränkung, Dijkstra-Algorithmus, Verkehrsnetze, Routenplanung, Optimierung, Pareto-Optimalität, bidirektionale Suche, zielgerichtete Suche, Laufzeitoptimierung, Netzbelastung, Komplexität, Implementierung.
Häufig gestellte Fragen
Worum geht es in dieser Diplomarbeit grundsätzlich?
Die Arbeit befasst sich mit der Entwicklung und dem Vergleich schneller Algorithmen zur Lösung ressourcenbeschränkter Kürzeste-Wege-Probleme, die besonders bei komplexen Verkehrsnetzberechnungen auftreten.
Was sind die zentralen Themenfelder der Arbeit?
Zentral sind die Graphentheorie, Optimierungsmethoden für Netzwerke, die Anpassung klassischer Algorithmen sowie die praktische Implementierung und Performance-Analyse dieser Verfahren in Navigationssystemen.
Was ist das primäre Ziel der Forschungsarbeit?
Ziel ist es zu untersuchen, ob durch neuartige Beschleunigungsmethoden die Gesamtlaufzeit der Routenberechnung in komplexen Projekten wie dem CMCF-Route-Guidance-Projekt signifikant gesenkt werden kann.
Welche wissenschaftlichen Methoden werden verwendet?
Es kommen unter anderem der Dijkstra-Algorithmus, Transformationstechniken für Kantengewichte, dynamische Programmierung sowie Branch-and-Bound-Ansätze zum Einsatz.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil behandelt theoretische Grundlagen, definiert die mathematischen Problemstellungen (z.B. CSP, POCP, DB), beschreibt die erweiterten Algorithmen und präsentiert umfangreiche empirische Laufzeitvergleiche.
Welche Schlüsselwörter charakterisieren die Arbeit?
Wichtige Begriffe sind Kürzeste-Wege-Problem, Ressourcenbeschränkung, Dijkstra, Verkehrsnetze, Optimierung, Pareto-Optimalität und Laufzeitoptimierung.
Wie wirken sich Rechnerungenauigkeiten auf die Algorithmen aus?
Da Fließkommazahlen bei der Transformation von Kantengewichten zu Fehlern führen können, werden spezielle Skalierungsverfahren zur Sicherstellung der lexikographischen Ordnung eingesetzt, um Programmabstürze oder falsche Lösungen zu vermeiden.
Warum ist die Wahl des Algorithmus für das TU Berlin Projekt so wichtig?
Weil in diesem Projekt das ressourcenbeschränkte Wegproblem als Unterroutine extrem oft aufgerufen wird, führt jede Verbesserung der Effizienz dieses Unterproblems zu einer spürbaren Reduktion der gesamten Netzberechnungszeit.
- Quote paper
- Fabian Zenzinger (Author), 2002, Schnelle Algorithmen für ressourcenbeschränkte kürzeste Wege in Verkehrsnetzen, Munich, GRIN Verlag, https://www.grin.com/document/21008
