Mobilität und Wirtschaftlichkeit haben in unserer Gesellschaft einen hohen Stellenwert. Hierzu gehört unter anderem, möglichst zeit- oder kostengünstig ein geografisches Ziel zu erreichen. Dabei spielt der Einsatz von Systemen zur Routenplanung und –führung eine sehr große Rolle. Der technische Fortschritt der letzten Jahre hat dazu geführt, dass nicht nur in vielen Kraftfahrzeugen Navigationssysteme zur Standardausstattung gehören, sondern dass es auch leistungsstarke Lösungen zur Zielführung gibt, die in mobilen Geräten wie etwa in Personal Digital Assistant’s (PDA’s) integriert sind. Auch im Internet sind Routenplaner verfügbar, die für jeden Benutzer kostenfrei den optimalen Weg zu einem beliebigen Ziel in ganz Europa ermitteln.
Die Grundlage für derartige Systeme, die effizient einen optimalen Weg bestimmen, liegt in der möglichst präzisen Abbildung der Wirklichkeit in einem Datenmodell, ohne jedoch überflüssige Daten zu erheben. Anschließend muss auf diese Daten ein der Problemstellung angepasster Algorithmus angewendet werden, der in annehmbarer Zeit ein Ergebnis liefert.
Das Gebiet der Routenplanung umfasst aber noch mehr Fragestellungen, als nur Die nach dem kürzesten Weg zu einem gegebenen Ziel. Weitere Problemstellungen sind beispielsweise die Suche nach einer möglichst günstigen Verbindung mehrerer Orte, wie etwa für eine Geschäftsreise, oder auch die Suche nach einer effizienten Tour für die Müllabfuhr, also einer Route, auf der jede Straße eines Bezirks mindestens einmal, aber möglichst wenige Straßen doppelt befahren werden.
Im Fachbereich Vermessung und Geoinformatik der Hochschule Bochum, in dem diese Arbeit entstanden ist, sind bisher keine Forschungen zu dem Thema Routenplanung gelaufen. Aus diesem Grund ist dieses Werk in gewisser Weise als Pionierarbeit zu sehen. Ziel dieser Arbeit ist es somit, zunächst eine Einführung in diese vielfältige Problematik der Bestimmung optimaler Wege in den verschiedenen Anwendungsbereichen zu geben und die hierzu bestehenden Lösungsansätze vorzustellen. Des Weiteren soll auf der Grundlage einer selbst entworfenen Datenstruktur ein Programm implementiert werden, das das Kürzeste-Wege-Problem löst. Dieses Programm soll in der Lage sein, unter Berücksichtigung von speziellen Bedingungen, wie z.B. Abbiegeverboten, einen optimalen Weg von einem Start- zu einem Zielpunkt anzugeben.
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
3.1.1 Dijkstra-Algorithmus
Die Standardlösung bei der Suche nach einem kürzesten Weg führt zu dem Dijkstra-Algorithmus. Dieser verfolgt die Strategie, immer nur die in einem Knoten möglichen Alternativen zu untersuchen und nicht komplette Wege durch einen Graphen. Die Suche erfolgt auch nicht zielgerichtet in Richtung des Zielknotens, vielmehr werden kürzeste Wege von dem Startknoten aus zu allen Knoten des Graphen gesucht. Hierbei kann die Suche abgebrochen werden, wenn ein kürzester Weg zu dem Zielknoten gefunden wurde. Mit den folgenden Abbildungen soll der Algorithmus näher erläutert werden. Es werden die erreichten Knoten rot gefärbt, die benutzten Kanten schwarz und die als nächstes benutzbaren Kanten grün. Der restliche Teil des Beispielgraphen wird grau gefärbt.
Abbildung 8 zeigt oben den Graphen, in dem ein kürzester Weg von s nach z gesucht werden soll. Im ersten Schritt wird von allen Bögen der herausgesucht, der s am günstigsten verlässt. Dies ist der Bogen nach a mit dem Gewicht 3. Der erreichte Knoten wird rot gefärbt und in den Knoten wird die Länge des Weges vom Startknoten eingetragen. Außerdem wird der Knoten s als Vorgänger des Knoten a gespeichert, um am Ende der Suche nicht nur die Länge des Weges zum Zielknoten zu kennen, sondern auch den Weg dorthin konstruieren zu können. Alle Bögen, die in s und a beginnen, werden nun grün gezeichnet, da sie als nächstes verwendet werden können. Für die jetzt erreichbaren Knoten wird jeweils aus allen möglichen Wegen der Kürzeste bestimmt und in die Knoten eingetragen. Nun wird unter allen erreichbaren Knoten der mit dem kürzesten Weg ermittelt und ausgewählt.
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.
- Quote paper
- Dipl.-Ing. Michael Hülsmann (Author), 2008, Entwurf und Implementierung eines Routing-Algorithmus und eines zugrundeliegenden Datenmodells am Beispiel des Straßennetzes, Munich, GRIN Verlag, https://www.grin.com/document/90300
