Grin logo
en de es fr
Shop
GRIN Website
Publish your texts - enjoy our full service for authors
Go to shop › Geography / Earth Science - Cartography, Geographic Information Science and Geodesy

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

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

Diploma Thesis , 2008 , 74 Pages , Grade: 1,0

Autor:in: Dipl.-Ing. Michael Hülsmann (Author)

Geography / Earth Science - Cartography, Geographic Information Science and Geodesy
Excerpt & Details   Look inside the ebook
Summary Excerpt Details

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.

Excerpt


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

Excerpt out of 74 pages  - scroll top

Details

Title
Entwurf und Implementierung eines Routing-Algorithmus und eines zugrundeliegenden Datenmodells am Beispiel des Straßennetzes
College
Bochum University of Applied Sciences
Grade
1,0
Author
Dipl.-Ing. Michael Hülsmann (Author)
Publication Year
2008
Pages
74
Catalog Number
V90300
ISBN (eBook)
9783638039253
ISBN (Book)
9783638937078
Language
German
Tags
Entwurf Implementierung Routing-Algorithmus Datenmodells Beispiel Straßennetzes
Product Safety
GRIN Publishing GmbH
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
Look inside the ebook
  • Depending on your browser, you might see this message in place of the failed image.
  • https://cdn.openpublishing.com/images/brand/1/preview_popup_advertising.jpg
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
  • Depending on your browser, you might see this message in place of the failed image.
Excerpt from  74  pages
Grin logo
  • Grin.com
  • Payment & Shipping
  • Contact
  • Privacy
  • Terms
  • Imprint