Jump label

Service navigation

Main navigation

You are here:

Main content

Diplomarbeit

Offline Güteberechnung und Bereichsclustering für BeeJamA

Michael Diel

BeeJamA (Bee Inspired Traffic Jam Avoidance) ist ein dezentraler Algorithmus zur Stauvermeidung in (Straßen-) Verkehrsszenarien. In BeeJamA existieren zwei Routingebenen: Die Bereichs- und die Netzebene. Auf der Bereichsebene wird ein Straßennetz in einen Graphen übersetzt (Kanten entsprechen Straßen und Knoten repräsentieren Routing-relevante Punkte). Dieser Graph ist in sog. Navigationsbereiche partitioniert. Jeder dieser Bereiche besitzt einen lokalen Navigator, der das Routing der Fahrzeuge innerhalb seines (Navigations-) Bereichs übernimmt. Auf der darüber liegenden logischen Netzebene entsprechen Bereiche wiederum Knoten. Kanten repräsentieren geographische Nachbarschaftsbeziehungen. Ein zonenübergreifendes Fernbereichsrouting findet so über die verschiedenen Ebenen hinweg statt [1,2,3,4]. BeeJamA ist ein adaptives Realzeitsystem, da jedes Fahrzeug, rechtzeitig vor Erreichen der nächsten Kreuzung, Auf- oder Abfahrt, neue Routinginformationen benötigt. Die damit durch die individuellen Fahrzeuggeschwindigkeiten vorgegebenen End-to-End Deadlines sind hart.

Problembeschreibung

Bei der Einteilung der Navigationsbereiche (Clustering) auf der Bereichsebene muss darauf geachtet werden, dass Bereiche einerseits groß genug gewählt werden, damit der Algorithmus genügend Auswahl- und Ausweichmöglichkeiten hat, Fahrzeuge innerhalb eines Bereichs zu routen. Andererseits ist die Bereichsgröße nach oben durch die Kapazitäten des Navigators begrenzt, der jedem Fahrzeug bis zum Erreichen der nächsten Kreuzung neue Routinginformationen zukommen lassen muss. Ein effizientes Clustering der Bereichsebene vor Betriebsbeginn ist damit von besonderer Bedeutung.

BeeJamA nutzt derzeit eine Heuristik um Verkehrsgraphen in Bereiche zu unterteilen. Durch die besondere Topologie (Autobahnen, Einbahnstraßen, Über-/Unterführungen, etc.) realistischer Straßennetze ergibt sich jedoch eine Vielzahl von Problemen die derzeit nur durch ein Postprocessing des Verkehrsgraphen „von Hand“ korrigiert werden können:

  • So können Bereiche entstehen, in die Fahrzeuge zwar hinein fahren, danach jedoch nicht alle Knoten innerhalb des Bereichs erreichen können.
  • In Extremfällen kann es passieren, dass Fahrzeuge nur in Bereiche hinein aber nicht wieder heraus kommen.
  • Das heuristische Clustering ergibt manchmal nur einen einzigen großen Bereich, oder aber alle Bereiche bestehen nur aus einem Knoten.

Für das Routing in BeeJamA über sämtliche Ebenen hinweg scheint es notwendig, das Navigationsbereiche starke Zusammenhangskomponenten innerhalb des Verkehrsgraphen bilden und Autobahnen seperat vom Rest des Netzes betrachtet werden.

Aufgabenstellung

Ziel dieser Arbeit ist die Identifizierung von Qualitätsmerkmalen, um die Güte eines gegebenen Teilnetzes zu bewerten und auf dieser Basis Vorhersagen für das Routingverhalten sowohl auf einfachen Basisnetzen (Wabenmodell, Gridmodell, etc.) als auch auf der realistischen Topologie des Ballungsraums Ruhrgebiet machen zu können. Auf Basis der Güte sollen Mechanismen erprobt werden, ein gegebenes Verkehrsnetz optimal zu strukturieren, also die Güte aller beteiligten Navigationsbereiche systemweit zu maximieren. Es sollen randomisierte, evolutionäre und hybride Algorithmen Ansätze untersucht werden.

Literatur

[1] Wedde, H.; Lehnhoff, S. ; van Bonn B.; Bay, Z.; Becker, S.; Boettcher, S.; Brunner, C.; Buescher, A.; Fuerst, T.; Lazarescu, A.M.; Rotaru, E.; Senge, S.; Steinbach, B.; Yilmaz, F.; Zimmermann, T.: A Novel Class of Multi-Agent Algorithms for Highly Dynamic Transport Planning Inspired by Honey Bee Behavior; in IEEE-ETFA ’07, Patras, IEEE CS Press, September, 2007.

[2] Wedde, H.; Lehnhoff, S. ; van Bonn B.; Bay, Z.; Becker, S.; Boettcher, S.; Brunner, C.; Buescher, A.; Fuerst, T.; Lazarescu, A.M.; Rotaru, E.; Senge, S.; Steinbach, B.; Yilmaz, F.; Zimmermann, T.: Highly Dynamic and Scalable VANET Routing for Avoiding Traffic Congestions; in ACM-VANET ’07, Montreal, ACM Press, September, 2007.

[3] Wedde, H.; Lehnhoff, S. ; van Bonn B.; Bay, Z.; Becker, S.; Boettcher, S.; Brunner, C.; Buescher, A.; Fuerst, T.; Lazarescu, A.M.; Rotaru, E.; Senge, S.; Steinbach, B.; Yilmaz, F.; Zimmermann, T.: Highly Dynamic and Adaptive Traffic Congestion Avoidance in Real-Time Inspired by Honey Bee Behavior; in Informatik Aktuell, Boppard, Springer, December, 2007.

[4] Wedde, H.; Lehnhoff, S. ; van Bonn B.; Bay, Z.; Becker, S.; Boettcher, S.; Brunner, C.; Buescher, A.; Fuerst, T.; Lazarescu, A.M.; Rotaru, E.; Senge, S.; Steinbach, B.; Yilmaz, F.; Zimmermann, T.: STOP – Stauvermeidung durch on-line Verkehrsplanung. Project group, University of Dortmund, Dept. of Computer Science, 2006-2007

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