Der Straßenverkehr in Deutschland nimmt jedes Jahr stetig zu. Die erhöhte Verkehrsdichte führt vermehrt zu Störungen im Verkehrsfluss. Methoden und Verfahren, die sich mit der Vermeidung von Stau und der Entlastung der Straßen befassen, werden zukünftig immer mehr an Bedeutung gewinnen. Dabei sind Verfahren, die die vorhandene Infrastruktur nutzen und auf die stetig wechselnden Verhältnisse auf Deutschlands Straßen reagieren können, Ansätzen vorzuziehen, die teure Hardware zur Messung des Verkehrsaufkommens benötigen. Routingalgorithmen, wie der am Lehrstuhl 3 der Fakultät Informatik entwickelte BeeJamA [1], können dezentral eingesetzt werden und dynamisch auf das Verkehrsaufkommen im Straßenverkehr reagieren. Solche Routingalgorithmen sind für den Einsatz in ComputerNetzwerken zum Paketrouting [2] erfolgreich getestet.
Eine Kernaufgabe dieser Diplomarbeit ist es, die neu entwickelten Routingalgorithmen zu testen. Mit einer Testumgebung für Routingalgorithmen soll die Funktionstüchtigkeit und Programmierfehlerfreiheit der Routingalgorithmen überprüft werden. Für einen Einsatz dieser Algorithmen im realen Straßenverkehr jedoch reicht ein Funktionstest alleine nicht aus. Um die Praxistauglichkeit der Routingalgorithmen darüber hinaus nachzuweisen, sind umfangreiche, möglichst praxisnahe Tests dieser Algorithmen notwendig, in denen z.B. die resultierende Verkehrsdichte, die Durchschnittsgeschwindigkeiten und das Fahrverhalten analysiert werden können. Ein solches Vorgehen ist in der Realität nicht möglich, da es sehr hohe Kosten verursachen würde. Daher bieten sich Simulatoren an, die ein Verkehrsaufkommen, wie es in der Realität vorkommt, simulieren können. Mit solchen Verkehrssimulatoren ist es möglich, Routingalgorithmen für den Straßenverkehr auf Graphen von realen Straßennetzen zu testen. Zum Beispiel bieten sich MATSim (Multi-Agent Transport Simulation) [3] und SUMO (Simulation of Urban Mobility) [4] als Simulatoren an, die für solche praxisnahen Tests geeignet sind.
Ein Generic Routing Framework, welches am Lehrstuhl 3 der Fakultät Informatik parallel zu dieser Diplomarbeit entwickelt wird, soll eine flexible Anbindung von Routingalgorithmen an verschiedene Simulatoren, ermöglichen. Teil dieser Diplomarbeit ist es, diese Anbindung zu konzipieren und umzusetzen, sowie den Entwurf neuer Routingalgorithmen zu unterstützen.
Insgesamt ergeben sich daraus die folgenden Arbeitsschritte:
Die Vorgehensweisen der einzelnen Arbeitsschritte werden mit den folgenden Punkten näher erläutert.
Die Konzeption und Implementation von Routingalgorithmen für das Generic Routing Framework erfordert eine ausreichende Testumgebung, um die Funktionstüchtigkeit der Algorithmen zu überprüfen. Eine solche Testumgebung für Routingalgorithmen benötigt für seine Arbeit als Eingabe einen oder mehrere Routingalgorithmen, einen Graphen und eine Testkonfiguration mit einer erwarteten Funktionsweise des Algorithmus. Darunter fällt z.B. die Wahrscheinlichkeit, mit der die Fahrzeuge die Knoten und Kanten des Graphen passieren, sowie deren vermutlich benutzen Pfade. Mit Hilfe dieser Eingaben wird eine Simulation durchgeführt und eine Ausgabe erstellt. Die Routingalgorithmen werden im Arbeitsschritt 2 dieser Diplomarbeit konzipiert und umgesetzt. Mit einer geeigneten Schnittstelle müssen sie an die Testumgebung angebunden werden.
Damit die Arbeit der Routingalgorithmen ausreichend getestet werden kann, werden mehrere Szenarien in Graphenform benötigt. Für die Simulationen werden einfache Graphen entwickelt, mit deren Hilfe die unterschiedlichen Routingalgorithmen auf Programmierfehlerfreiheit und Abweichungen von der Konzeption des Algorithmus zur Implementation überprüft werden können. Diese Graphen werden ebenfalls über eine geeignete Schnittstelle an die Testumgebung für Routingalgorithmen angebunden.
Für die verschiedenen Tests wird je eine Testkonfiguration erstellt. Hierbei muss es möglich sein, unterschiedliche Graphen, Routingalgorithmen, Kombinationen von Routingalgorithmen und eine Erwartung für die Funktionsweise der Algorithmen einzustellen.
Damit die Auswirkungen der Routingalgorithmen auf den Testgraphen sichtbar werden, ist eine Visualisierung zu entwickeln, die es ermöglicht die Funktionsweise der Routingalgorithmen bereits während des Tests nachzuvollziehen. Dabei ist es wichtig, dass mögliche Abweichungen und Fehler vom erwarteten Verhalten leicht erkennbar sind.
In diesem Arbeitsschritt muss die Implementierung des am Lehrstuhl 3 der Fakultät Informatik entwickelten BeeJamA-Algorithmus erweitert werden. Einen Schwerpunkt bildet dabei die Umsetzung des Algorithmus für große Netze, um ihn für praxisnahe Simulationen einzusetzen. Zusätzlich muss eine Schnittstelle für das Generic Routing Framework konzipiert werden, um den Routingalgorithmus in Schritt 3 für große Simulationen einsetzen zu können. Ziel ist es, die Arbeit in diesem Schritt mit einer Diplomarbeit zu koordinieren, die parallel am Lehrstuhl 3 der Fakultät Informatik bearbeitet werden wird. Sie wird sich mit der Anbindung des Generic Routing Frameworks an verschiedene Simulatoren, sowie der Erstellung von großen Szenarien und Graphen von Straßennetzen befassen, die über den Rahmen des in Schritt 3 dieser Diplomarbeit zu entwerfenden Szenarios der Stadt Dortmund hinaus gehen.
Um den BeeJamA-Algorithmus sinnvoll zu vergleichen, wird mindestens ein weiterer für den Straßenverkehr geeigneter Routingalgorithmus benötigt. Grundlage solch eines VergleichsRoutingalgorithmus können Verfahren zur Bestimmung von (approximativ) kürzesten Wegen in großen Netzen sein, wie sie z.B. von dem A*-Algorithmus bestimmt werden. Dieser Vergleichs-Algorithmus muss ebenfalls für große Netze konzipiert und an das Generic Routing Framework angebunden werden. Mit dem in Schritt 1 erstellten Testumgebung für Routingalgorithmen muss die Funktionsweise beider Routingalgorithmen ausreichend getestet werden.
In diesem Teilbereich sollen die in Arbeitsschritt 2 entwickelten Routingalgorithmen bewertet werden. Dafür sollen geeignete Testfälle entwickelt werden, die zum einen den Unterschied der einzelnen Routingalgorithmen zeigen und zum anderen den Einfluss auf das Gesamtverhalten messen. Dabei sollen wie bei den Tests im Arbeitsschritt 2 verschiedene Konfigurationen mit unterschiedlichen Algorithmenkombinationen untersucht werden. Bei den Simulationen soll das Verhalten der Algorithmen besonders in großen Straßennetzen analysiert werden. Hierfür wird ein großer Ausschnitt des Straßennetzes der Großstadt Dortmund verwendet. Weitere Netze wie das Straßennetz des Ruhrgebiets sind angestrebt. Während der Simulationen sollen Daten über Ort und Zeit der Fahrzeugagenten gesammelt werden, mit deren Auswertung sich Aussagen über die Auswirkungen der Routingalgorithmen auf den simulierten Verkehr treffen lassen.
Für die Simulation des Straßenverkehrs in Deutschland wird auf das Kartenmaterial des OpenStreetMap-Projekts [5] zurückgegriffen, welches sich auf Grund seiner frei verfügbaren Daten für diese Diplomarbeit anbietet. Mit Quantum Gis (QGIS) [6] lassen sich daraus Daten für ein Simulationsszenario erstellen. Für eine Implementation von Graphen wird das Java Universal Network/Graph Framework (JUNG) [7] eingesetzt. Der gesamte Quellcode wird ausreichend getestet. Dafür wird auf die Techniken des JUnitProjekts [8] zurückgegriffen.
In dieser Diplomarbeit wird erstens ein Framework geschaffen, mit dem die Funktionstüchtigkeit von Routingalgorithmen überprüft werden können (Schritt 1). Durch die in Schritt 2 durchgeführten Tätigkeiten lassen sich mit dem Generic Routing Framework Änderungen an dem BeeJamA-Algorithmus und zukünftig entwickelten Routingalgorithmen leicht umsetzen. Abschließend behandelt diese Diplomarbeit den Themenkomplex der Anwendung von Routingalgorithmen, insbesondere BeeJamA, in großen Verkehrsnetzen. Entscheidend sind hier die Auswirkungen der Routingalgorithmen auf den simulierten Straßenverkehr, wie die Reisezeitverkürzung und die Stauvermeidung. Es interessiert insbesondere die Fragestellung, ab welcher Kombination der Routingalgorithmen signifikante Veränderungen in den gesammelten Simulationsdaten auftreten.
[1] Horst F. Wedde, Sebastian Lehnhoff, Sebastian Senge und Anca Manuela Lazarescu, Bee Inspired Bottom-Up Self-Organization in Vehicular Traffic Management. In: Proceedings of the 3rd IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO'09), IEEE Press, San Francisco, California, USA , 2009-09-14
[2] Muddassar Farooq Bee-Inspired Protocol Engineering. Springer Verlag, 2009
[3] Multi-Agent Transport Simulation, http://www.matsim.org, 2010
[4] Simulation of Urban MObility, http://sumo.sourceforge.net, 2010
[5] OpenStreetMap, http://www.openstreetmap.org, 2010
[6] Quantum GIS, http://www.qgis.org, 2010
[7] Java Universal Network/Graph Framework, http://jung.sourceforge.net, 2010
[8] JUnit, http://www.junit.org, 2010