Sprungmarken

Servicenavigation

Hauptnavigation

Sie sind hier:

Hauptinhalt

Diplomarbeit

Entwicklung einer alternativen Darstellung der Netzebene für das verteilte Verkehrsrouting in BeeJamA

Anca Manuela Lazarescu

Motivation

Innerhalb der Projektgruppe 502 wurde ein dezentraler, skalierbarer Algorithmus (BeeJamA) zur Lösung des Stauproblems in realistischen Straßennetzen entwickelt.

Der BeeJamA Algorithmus basiert auf den am Lehrstuhl III entwickelten naturinspirierten Multipfadalgorithmen BeeHive und BeeAdHoc, die für das Routing von Datenpaketen in Computernetzwerken entworfen wurden. Die Idee des effizienten, dezentralen Routings von Datenpaketen wurde auf das Routing von Fahrzeugen in realistischen Verkehrsnetzen übertragen. Das Ziel ist, die Fahrtzeiten zu minimieren und dass global möglichst wenig Verkehrsstau entsteht.

Modelliert wurde ein Straßensystem, welches Verkehrswege unterschiedlicher Kapazitäten berücksichtigt und in einem geeigneten Graph darstellt. Das Systemmodell besteht aus zwei unterschiedlichen Ebenen. Die tatsächlich vorhandene Straßentopologie wird in Bereiche eingeteilt und auf der ersten Ebene (Bereichsebene) auf einen Graphen abgebildet, wobei die Kanten Straßen und die Knoten mögliche Verzweigungen darstellen. Jeder Bereich wird von einem Navigator verwaltet, der Informationen über Fahrzeuge sammelt und bewertet, und anschließend weitere Routingvorschläge an das Fahrzeug zurücksendet. Das Routing zwischen Bereichen erfolgt auf der zweiten Ebene (Netzebene). Hier werden die Bereiche als Knoten dargestellt. Kanten verlaufen zwischen benachbarten Bereichen und stellen logische Verbindungen zwischen Bereichen dar. Folglich werden auf der Netzebene alle Verbingdungen zwischen zwei benachbarten Bereichen durch eine einzige Kante dargestellt und entsprechend nur einmal bewertet.

Innerhalb der Projektgruppe hat man einerseits ein stark vereinfachtes, wenig realistisches Wabenmodell, andererseits einen Teil des Ruhrgebietsstraßennetzes zum Testen des BeeJamA Algorithmus benutzt. So ist man zur Schlussfolgerung gekommen, dass der in der PG entwickelte Ansatz der Repräsentation der Netzebene ungeeignet ist. Folgende Probleme sind dabei aufgetreten:

  • Sollten zwischen zwei Bereiche mehrere Verbindungen vorhanden sein, werden diese mit dem ersten Ansatz auf der Netzebene als eine einzige Kante dargestellt und entsprechend nur einmal bewertet, was die einzelnen Werte stark verzerren kann. So ist es möglich, dass eine sehr gut bewertete Straße gar nicht betrachtet wird, weil die Bewertungsfunktion von sehr schlecht bewerteten Straßen beeinflusst wird.
  • Das zweite Problem bezieht sich nicht auf den Übergang zwischen den Bereichen, sondern auf die Kosten, die entstehen, wenn man einen Bereich überquert. Bisher sind gar keine Informationen über Überquerungskosten vorhanden. Es ist wichtig betrachten zu können, zu welchem der Grenzknoten geroutet wird, da die Zeit, in der von diesem Grenzknoten der aktuelle Bereich überquert werden kann von Bedeutung ist. Betrachtet man ausschließlich die beste Verbindung zum Nachbarbereich, besteht die Gefahr, dass eine gut bewertete Route zu einem Grenzknoten im Nachbarbereich führt, von dem man nur kostenintensive weitere Fahrmöglichkeiten hat.

Lösungsansatz

Zur Vereinfachung der Erklärung einer alternativen Repräsentation der Netzebene wird zuerst das in der PG502 vorgestellte Wabenmodell verwendet, in dem jede Wabe einen Bereich darstellt. Das Wabenmodell wird so verändert, dass jetzt die Grenzknoten nicht nur einem einzigen Bereich gehören, sondern allen Bereichen, die dieser Knoten verbindet. In diesem Ansatz haben die Bereiche also gemeinsame Knoten und überlappen sich an den Grenzknoten mit ihren Nachbarbereichen.

Entsprechend müssen einige Veränderungen auch in den Area-Tabellen gemacht werden. Der Knoten 3 gehört jetzt wie in Abbildung 1 beschrieben zu drei Bereichen, und muss für jeden dieser Bereiche eine eigene Tabelle besitzen. Geeignete Modifikationen müssen auch für die restlichen Tabellen gemacht werden.

Wie erwähnt lag das Hauptproblem der in der PG entwickelten Netzebenendarstellung in der Tatsache, dass einzelne Verbindungen zwischen Bereichen nicht betrachtet werden konnten, da die Bewertung des Übergangs von einem Quellbereich zu einem Zielbereich alle möglichen Routen zusammenfasste, bzw. nur die kostengünstigste Verbindung berücksichtigte. Werden alle Verbindungen in der Bewertung berücksichtigt, besteht die Gefahr, dass eine gute Verbindung durch die gemeinsame Bewertung mit schlechten Verbindungen übersehen wird. Wird immer die beste Verbindung zum Nachbarbereich genommen, so entsteht das Problem, dass diese Verbindung potentiell zu einem Grenzknoten im Nachbarbereich führt, von dem man nur ungünstig weiterfahren kann.

Um effizient Fahrzeiten zu minimieren besteht also die Notwendigkeit, die Verbindungen (Straßen) zwischen Bereichen individuell zu betrachten, sowie die Fahrtzeiten zur Überquerung von Bereichen zu berücksichtigen. Entsprechend wird eine neue graphische Darstellung der Netzebene entwickelt, wobei jetzt nicht mehr Bereiche als Knoten dargestellt werden, sondern die Grenzknoten der Bereichsebene auch als Knoten auf der Netzebene modelliert werden. Dabei ist es wünschenswert, wenig oder nicht relevante Übergangsknoten (z.B. Übergänge durch Siedlungen oder Gegenden, in denen das Durchfahren nicht erwünscht ist) nicht zu betrachten. Es ist eine entsprechende Klassifizierung der Grenzknoten erforderlich, so dass die Auswahl ungünstiger Übergangsknoten verhindert wird.

Die Kanten stellen auf der Netzebene die schnellsten Verbindungen zwischen zwei Grenzknoten, die für die Modellierung auf der Netzebene relevant sind, dar. Diese Verbindungen verlaufen nur zwischen Grenzknoten des selben Bereichs. Die Bewertung für die Kanten kann man dann aus den Tabellen (auf Bereichsebene) des aktuellen Bereichs entnehmen. Auch wenn jetzt die Tabellen für jeden Knoten auf die Netzebene größer werden, besteht der Vorteil, dass die Bewertungsinformationen auf der Netzebene nicht neu berechnet werden müssen.

Zur Publikation...
Weitere Publikationen zu BeeJamA...