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

Inhaltsverzeichnis

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 & Themen

Die vorliegende Diplomarbeit befasst sich mit der Entwicklung und Implementierung eines Routenplanungssystems und des zugrundeliegenden Datenmodells am Beispiel des Straßennetzes, um eine offene und eigenständige Lösung für Forschungszwecke an der Hochschule Bochum bereitzustellen.

• Grundlagen der Graphen- und Komplexitätstheorie
• Algorithmen zur Lösung von Routing-Problemen (kürzeste Wege, Postboten-Problem, Traveling-Salesman)
• Methoden zur Berücksichtigung von Abbiege- und Wegeverboten
• Konzeption und Implementierung eines relationalen Datenmodells
• Realisierung eines Demonstrators in Visual Basic zur Routenplanung

Auszug aus dem Buch

Zusammenfassung der Kapitel

1 EINLEITUNG: Einführung in die Relevanz der Routenplanung und Zielsetzung der Diplomarbeit als Pionierarbeit im Fachbereich.

2 ERLÄUTERUNG VON BEZEICHNUNGEN UND BEGRIFFEN: Erläuterung der graphentheoretischen Grundlagen sowie der Komplexitätstheorie zur Bewertung von Algorithmen.

3 EINFÜHRUNG IN ROUTING-PROBLEME: Detaillierte Darstellung verschiedener Problemstellungen wie das Kürzeste-Wege-Problem, das Chinesische-Postboten-Problem und das Traveling-Salesman-Problem.

4 IMPLEMENTIERUNG EINES SYSTEMS ZUR ROUTENPLANUNG: Beschreibung des Datenmodells und der Programmierung eines Demonstrators zur Routenberechnung unter Berücksichtigung von Verkehrsregeln.

5 ZUSAMMENFASSUNG UND AUSBLICK: Zusammenfassende Rückschau auf die Ergebnisse sowie Vorschläge zur Weiterentwicklung des Systems.

Schlüsselwörter

Routenplanung, Graphentheorie, Dijkstra-Algorithmus, A*-Algorithmus, Straßennetz, Datenmodell, Abbiegeverbot, Wegeverbot, Chinesisches-Postboten-Problem, Traveling-Salesman-Problem, Komplexitätstheorie, Visual Basic, Datenbank, Routing, Navigationssystem

Häufig gestellte Fragen

Worum geht es in dieser Diplomarbeit im Kern?

Die Arbeit behandelt den Entwurf und die Implementierung eines Routenplanungssystems auf Basis eines mathematischen Datenmodells, das für das Straßennetz optimiert ist.

Welche zentralen Probleme der Routenplanung werden thematisiert?

Im Zentrum stehen das Kürzeste-Wege-Problem, das Chinesische-Postboten-Problem sowie das Traveling-Salesman-Problem.

Was ist das primäre Ziel der Arbeit?

Ziel ist es, ein offenes und eigenständiges System zur Routenplanung am Fachbereich Vermessung und Geoinformatik der Hochschule Bochum zu etablieren.

Welche wissenschaftlichen Methoden kommen zum Einsatz?

Es werden Methoden aus der Graphentheorie (wie Dijkstra- und A*-Algorithmen) sowie Verfahren zur Komplexitätsbewertung und Optimierung (Branch-and-Bound) genutzt.

Was wird im praktischen Hauptteil der Arbeit behandelt?

Der Hauptteil konzentriert sich auf die Modellierung eines Straßennetzes in einer Datenbank und die Implementierung eines Demonstrators mittels Visual Basic 2005.

Welche Schlüsselwörter beschreiben die Arbeit am besten?

Routenplanung, Graphentheorie, Dijkstra, A*-Algorithmus, Abbiegeverbote, Datenmodell, Traveling-Salesman-Problem und Datenbankimplementierung.

Wie werden Abbiegeverbote in diesem System berücksichtigt?

Dies geschieht primär durch die Methode der Kantenaufnahme, bei der die Baumstruktur des Kürzeste-Wege-Algorithmus durch leichte Modifikationen beibehalten wird.

Warum ist das "Chinesische-Postboten-Problem" für die Arbeit relevant?

Es dient als Beispiel für eine Routing-Aufgabe, bei der – im Gegensatz zum kürzesten Weg – alle Kanten eines Graphen mindestens einmal befahren werden sollen.

Warum wird der Floyd-Warshall-Algorithmus im Kontext der Arbeit erwähnt?

Er wird als Methode zur Bestimmung kürzester Wege zwischen allen Knotenpaaren angeführt, insbesondere im Rahmen der Vorbereitung für das Chinesische-Postboten-Problem.

Welche Rolle spielt die Zeitkomplexität für den Autor?

Sie ist entscheidend, um die Effizienz der gewählten Algorithmen zu bewerten und zu entscheiden, ob diese für den Einsatz in einem Navigationssystem praktikabel sind.