Sprungmarken

Servicenavigation

Hauptnavigation

Sie sind hier:

Hauptinhalt

Diplomarbeit

Konzeption und Entwicklung eines "Generischen Routing Frameworks" für die Simulation von Straßenverkehr in großen Netzen

Fabian Knobloch

Motivation

Verkehrsstaus wirken sich in vielerlei Hinsicht negativ auf die Umwelt und Wirtschaft aus. Staus verursachen einen erhöhten Schadstoffausstoß und einen erhöhten Kraftstoffverbrauch. Der Transport von Waren und Gütern wird zeitlich verzögert, wodurch im Jahr 2000 ein ökonomischer Schaden in Höhe von ca. 270 Milliarden Euro entstand [9]. Die Vermeidung bzw. Verminderung von Stau liegt also im allgemeinen Interesse. Es gibt mehrere Lösungsansätze, um Verkehrsstau zu vermeiden. Die Infrastruktur weiter auszubauen ist einer davon. Dieser ist allerdings mit hohen Kosten verbunden und hat in vielen Fällen ebenfalls negative Auswirkungen auf die Ökologie [4]. Ziel ist es also, auch ohne strukturelle Veränderungen am vorhandenen Straßennetz, den Verkehrsfluss zu optimieren [5]. Dies soll mit Hilfe von Straßenverkehrsroutingalgorithmen geschehen. Diese Algorithmen sollen bei der Entscheidung der Verkehrsteilnehmer über einen günstigen Pfad vom Start- zum Zielpunkt hinsichtlich Stauvermeidung behilflich sein. Aus diesem Grund wird in dieser Arbeit ein Generisches Routing Framework (GRF) konzipiert und entwickelt. Das Framework soll es ermöglichen, verschiedene Routingalgorithmen (RA) in eine MobWorld (MW) zu integrieren (z.B. Simulatoren, Navigationssysteme...). Bereits vorhandene Simulatoren, wie z.B. MATSim [8] (Multi-Agent Transport Simulation) oder SUMO [6] (Simulation of Urban Mobility), sollen über eine Schnittstelle an das GRF angebunden werden können. Diese Simulatoren sind in der Lage mit großen Datenmengen umzugehen, welche durch das Verkehrsaufkommen auf großen Straßennetzen resultieren. Des Weiteren sollen vorhandene Routingalgorithmen, wie der am LS III entwickelte BeeJamA [11] Algorithmus oder Dijkstra ShortestPath Algorithmus zur Auffindung eines kürzesten Weges, durch Erweiterungen an das GRF angebunden werden können. Ein Ziel der Diplomarbeit ist es, Aussagen über die Güte, z.B. Gesamt- und Durchschnittsfahrtzeiten der Verkehrsteilnehmer, von Routingalgorithmen zu ermöglichen. Das GRF soll hierzu Möglichkeiten zur Auswertung bieten. Um realistische Aussagen über die Güte der Algorithmen treffen zu können, müssen auch die Szenarien, die simuliert werden, realitätsnah sein. Es soll z.B. das Dortmunder Straßennetz und umliegende Bereiche (Autobahnanbindung in Richtung Bochum und Essen, Teile des Ruhrgebiets) über das Landkartenportal OpenStreetMap [2] bezogen werden. Das Verkehrsaufkommen in realitätsnaher Größenordnung kann in OD-Matrizen [7] (origin destination matrix) kodiert werden. Dazu wird jedem Fahrzeug eine Startzeit und Start- und Zielort zugeteilt. In dieser Diplomarbeit werden randomisiert erzeugte oder mit Hilfe von Quantum GIS [10] (ein Open Source Geographical Information System) generierte OD-Matrizen verwendet.

Ziel dieser Arbeit ist es mittels des GRF unterschiedliche RA und MW miteinander koppeln zu können und die Entwicklung neuer RA zu vereinfachen. So soll insbesondere MATSim so verbereitet werden, dass externe online RA verwendet werden können und auf großen Netzen evaluiert werden können.

Generisches Routing Framework

Das Generische Routing Framework (GRF) bündelt alle Datenstrukturen, Methoden und Informationen, die für eine Verkehrssimulation und -auswertung benötigt werden. Das Straßennetz wird durch einen gerichteten Graphen samt Knoten und gewichteten Kanten modelliert. Von den Verkehrsteilnehmern wird abstrahiert und durch Agenten repräsentiert, die über den Graphen geroutet werden. Die Anbindung an eine Simulationsumgebung, die hier MobWorld genannt wird, muss für jeden vorhandenen Simulator spezialisiert werden. Konkret soll hier MATSim als Simulator dienen. Später können SUMO und andere Umgebungen folgen, indem neue Adapter erstellt werden.

MobWorld MATSim

Die MobWorld ist die Umgebung, in der die Verkehrsteilnehmer ihre Aktionen ausführen. Prinzipiell kommt jede Umgebung in Frage, in der Verkehr vorkommt. Die Verkehrsteilnehmer könnten also Autos, LKW, Schiffe oder Roboter sein. Diese Diplomarbeit beschränkt sich auf den Straßenverkehr. Die typischen Aktionen sind hier das Losfahren, geradeaus Fahren, Abbiegen, Bremsen, Beschleunigen, Parken usw. Der Simulator MATSim wird hier als Umgebung dienen und ersetzt somit den realen Straßenverkehr. Der agenten-basierte Simulator ist geeignet, weil es mit ihm möglich ist, auch große Szenarien mit mehreren tausend Verkehrsteilnehmer und mehreren tausend Straßen zu simulieren. Bisher arbeitet MATSim mit statischen offline-Routingalgorithmen. Es werden nur Veränderungen an den Routen der Agenten vorgenommen, nachdem ein kompletter Simulationslauf beendet wurde. Um den Simulator mit dynamischen Routingalgorithmen zu versehen, werden die Routinganfragen der Fahrzeuge in MATSim an die Agenten im GRF weitergeleitet und dort von den angebundenen dynamischen Routingalgorithmen beantwortet.

Ziele

In der Diplomarbeit sollen folgende Bereiche bearbeitet werden:

Generisches Routing Framework und MATSim:

Es soll ein Framework in Java entwickelt werden, welches Graphen, Agenten und Routingalgorithmen verwaltet. Die Agenten sollen Routinganfragen von einer angeschlossenen Simulationsumgebung dynamisch zur Laufzeit beantworten können. Anschließend sollen die Fahrtzeiten und -strecken der einzelnen Agenten ausgewertet werden können, um verschiedene Algorithmen vergleichbar zu machen. Es sollen Durchdringungsraten simuliert werden können, d.h. die Agenten aus einem Szenario werden mit unterschiedlichen Routern ausgestattet werden, sodass ein Teil der Agenten seine Routen z.B. von Dijkstra-Routern und ein weiterer Teil von BeeJamA-Routern erhält.

MATSim muss bei der Simulation seiner Fahrzeuge seine Routinganfragen an das GRF stellen. Dazu müssen nur wenige Veränderungen an MATSim vorgenommen werden.

Routingalgorithmen:

Wenn das GRF konzipiert und entwickelt wurde, können die Routingalgorithmen, die im Rahmen einer weiteren Diplomarbeit am LS III implementiert werden, in das GRF aufgenommen werden. Dazu müssen anfangs Schnittstellen definiert werden und setzt die Kommunikation zwischen den Diplomanden voraus.

Verkehrszenario erstellen:

Es müssen Verkehrszenarien erstellt werden. Dazu gehören Straßennetze und Fahrzeuge. OpenStreetMap liefert hierzu das Kartenmaterial, welches transformiert werden muss. OD-Matrizen speichern hierfür die Start- und Zielpositionen der Verkehrsteilnehmer und eine genaue Startzeit für die Fahrzeuge. Mit geeigneten Programmen, wie z.B. Osmosis [3], können die OpenStreetMap Dateien manipuliert werden und mit Programmen wie JOSM [1] können diese anschließend visualisiert werden. Das Verkehrsaufkommen auf den resultierenden Straßennetzen soll entweder zonenbasierend mit einem Geographical Information System, wie z.B. QGIS, generiert werden oder mit einem randomisierte Verfahren, um diese OD-Matrizen zu generieren. Es können auch beide Verfahren kombiniert benutzt werden.

Simulation und Auswertung:

Bei der Simulation soll schrittweise herausgefunden werden, in welcher Größenordnung ein Szenario noch in einem angemessenen Zeitraum simuliert werden kann. Die Parameter, die die Laufzeit der Berechnung stark beeinflussen, sind die Anzahl der Fahrzeuge, also die Größe der OD-Matrix, die Größe des verwendeten Straßennetzes und die Art der RA (online vs. offline). Des Weiteren beeinflusst die verwendete Hardware die Simulationslaufzeit. Im Rahmen der Diplomarbeit stehen Desktoprechner (Intel P4, 3GHZ, 2GB Ram, Windows XP 32 Bit) und größere Rechner (8 CPUs, 16GB Ram, Linux 64 Bit) zur Verfügung, auf denen das GRF evaluiert werden kann. Insbesondere sollen die verschiedenen Dikjkstra Routingalgorithmen, also statische und adaptive Varianten, verglichen werden und deren Auswirkungen auf den Straßenverkehr hinsichtlich Stauvermeidung beobachtet werden. Der Abgleich zwischen den erwarteten und tatsächlichen Ergebnissen gibt so Aufschluss über die Qualität des GRF.

Literatur

[1] http://josm.openstreetmap.de/, 06.06.2010.

[2] http://www.openstreetmap.org, 06.06.2010.

[3] http://wiki.openstreetmap.org/wiki/osmosis, 06.06.2010.

[4] Richard T. T. Forman and Lauren E. Alexander. Roads and their major ecological effects. Annual Review of Ecology and Systematics, 29:207-C2, 1998.

[5] G. Wolfgang Heinze. Kurskorrektur - eine Ortsbestimmunt der Raumordnung aus Verkehrssicht. Inst. for Land and Sea Transport Systems, TU Berlin, Germany, Working Paper 06-6, 2006.

[6] Daniel Krajzewicz, Georg Hertkorn, Christian Rössel, and Peter Wagner. Sumo (simulation of urban mobility); an open-source traffic simulation. Proceedings of the 4th Middle East Symposium on Simulation and Modelling (MESM2002), pages 183-187, 2002.

[7] KULCSÁR, BÉCSI, and VARGA. Estimation of dynamic origin destination matrix of traffic systems. PERIODICA POLYTECHNICA SER. TRANSP, 33(1):3-14, 2005.

[8] Prof. Dr. Kai Nagel and Prof. Dr. Kay W. Axhausen. http://www.matsim.org, 2009.

[9] W. Rothengatter. External costs of transport. 2004. Online verfügbar unter http://www.uic.asso.fr/html/environnement/cd_external/docs/externalcosts_en.pdf; aufgerufen am 09.02.2009.

[10] Gary Sherman. http://www.qgis.org, 06.06.2010.

[11] Horst F. Wedde and Sebastian Lenhoff. Highly Dynamic and Adaptive Traffic Congestion Avoidance in Real-Time Inspired by Honey Bee Behavior. 2007.