Entwurf und Implementierung eines Routing-Algorithmus und eines zugrundeliegenden Datenmodells am Beispiel des Straßennetzes

Inhaltsverzeichnis

• AUFGABENSTELLUNG
• DANKSAGUNG
• 1 EINLEITUNG
• 1.1 ZIELSETZUNG DER ARBEIT
• 1.2 AUFBAU DER ARBEIT
• 2 ERLÄUTERUNG VON BEZEICHNUNGEN UND BEGRIFFEN
• 2.1 GRAPHENTHEORIE
• 2.1.1 Euler und Hamilton
• 2.1.2 Bäume
• 2.1.2.1 Minimaler Spannbaum
• 2.1.2.2 1-Baum
• 2.2 KOMPLEXITÄTSTHEORIE
• 2.2.1 Komplexität von Algorithmen
• 2.2.2 NP-Probleme
• 3 EINFÜHRUNG IN ROUTING-PROBLEME
• 3.1 KÜRZESTE-WEGE-PROBLEM
• 3.1.1 Dijkstra-Algorithmus
• 3.1.2 A*-Algorithmus
• 3.1.3 Floyd-Warshall-Algorithmus
• 3.1.4 Abbiegeverbote
• 3.1.4.1 Kantenaufnahme
• 3.1.4.2 Mehrfache Knotenaufnahme
• 3.1.4.3 Ziehen neuer Kanten
• 3.1.4.4 Verbotsorientiertes Knotensplitting
• 3.1.4.5 Knotenorientierte Netzwerke
• 3.1.5 Wegeverbote
• 3.1.6 Kürzeste Wege in modifizierten Graphen
• 3.2 CHINESISCHES-POSTBOTEN-PROBLEM
• 3.3 TRAVELING-SALESMAN-PROBLEM
• 3.3.1 Bestimmung einer oberen Schranke
• 3.3.2 Bestimmung einer unteren Schranke
• 3.3.3 Branch-and-Bound-Verfahren
• 4 IMPLEMENTIERUNG EINES SYSTEMS ZUR ROUTENPLANUNG
• 4.1 DATENMODELL
• 4.2 DEMONSTRATOR
• 5 ZUSAMMENFASSUNG UND AUSBLICK

Zielsetzung und Themenschwerpunkte

Die Diplomarbeit verfolgt das Ziel, Grundlagen für eine offene, eigenständige Lösung des Fachbereichs Vermessung und Geoinformatik für Routing-Probleme im Straßennetz zu schaffen. Dazu werden zunächst geeignete Algorithmen aus der Graphentheorie recherchiert. Anschließend erfolgt die Entwicklung eines Datenmodells zur Speicherung der Knoten und Kanten mit notwendigen Attributen und Beziehungen. Abschließend wird ein Demonstrator in Visual Basic .Net implementiert, der die Funktionalität des entwickelten Systems veranschaulicht.

• Graphentheorie und Routing-Algorithmen
• Datenmodellierung für Straßennetze
• Implementierung eines Demonstrators in Visual Basic .Net
• Entwicklung einer offenen und flexiblen Routing-Lösung
• Bewertung von Algorithmen und Datenstrukturen im Kontext von Routing-Anwendungen

Zusammenfassung der Kapitel

Das erste Kapitel führt in die Thematik der Diplomarbeit ein und erläutert die Zielsetzung sowie den Aufbau der Arbeit. Kapitel zwei behandelt grundlegende Begriffe aus der Graphentheorie und Komplexitätstheorie, die für das Verständnis der Routing-Algorithmen notwendig sind. Im dritten Kapitel werden verschiedene Routing-Probleme und Lösungsansätze vorgestellt, darunter das Kürzeste-Wege-Problem, das Chinesische-Postboten-Problem und das Traveling-Salesman-Problem. Kapitel vier widmet sich der Implementierung eines Systems zur Routenplanung, einschließlich des Datenmodells und des Demonstrators. Abschließend wird im fünften Kapitel die Arbeit zusammengefasst und ein Ausblick auf mögliche Weiterentwicklungen gegeben.

Schlüsselwörter

Routing, Straßennetz, Graphentheorie, Algorithmen, Datenmodell, Visual Basic .Net, Demonstrator, Navigation, Komplexitätstheorie, Kürzeste-Wege-Problem, Chinesisches-Postboten-Problem, Traveling-Salesman-Problem, Geodaten, GIS