Mit MATSim [1] steht ein leistungsfähiges Werkzeug zur Simulation von Straßenverkehr zur Verfügung. Eingesetzt wird MATSim gegenwärtig hauptsächlich zur Verkehrsplanung, also der Gestaltung von ökonomischen und leistungsfähigen Verkehrsnetzen. Dabei ist MATSim dazu ausgelegt Simulationen in der Größenordnung von Fahrzeugen in Echtzeit durchzuführen. Entwickelt wird MATSim primär durch die Arbeitsgruppen des Herrn Prof. Nagel (TU Berlin) und des Herrn Prof. Axhausen (ETH Zürich). Ein angestrebtes Ziel der Entwickler für das Jahr 2009 ist es den gesamten Straßenverkehrs der Schweiz in Echtzeit zu simulieren.
Die Routenwahl der einzelnen Fahrzeuge ist dabei pro Simulationslauf statisch vorgegeben. Ziel dieser Diplomarbeit wird es sein, ein generisches Routingframework zu konzipieren und umzusetzen, welches es erlaubt verteilte, dynamische Routingalgorithmen zu implementieren und zu vergleichen. Verteilt bedeutet in diesem Zusammenhang, dass die Routingalgorithmen kein globales Weltbild besitzen, sondern nur Auslastungen des Straßennetzes in einem lokalen Bereich für ihre Routinganweisungen verwenden können. Dynamisch bedeutet, dass die Routen nicht a priori feststehen, sondern zur Laufzeit an die aktuelle (lokale) Auslastung angepasst wird. Ziel solcher Routingalgorithmen ist es, hinsichtlich festgelegter Kriterien (z.B. kürzere Fahrzeiten) Verbesserungen gegenüber autonomer Routenwahl durch den Fahrer zu erzielen.
Am Lehrstuhl 3 wurde dazu ein verteilter, dynamischer Routingalgorithmus für den Straßenverkehr (BeeJamA – Bee Jam Avoidance [2]) zur heuristischen Minimierung der Fahrtzeiten durch Stauvermeidung entwickelt. Der BeeJamA-Algorithmus basiert dabei auf der Schwarmintelligenz der Bienen, genauer gesagt auf dem Vorgehen bei der Futtersuche der Honigbienen. Im Zuge dieser Diplomarbeit soll eine Umsetzung des BeeJamA-Algorithmus auf der Grundlage des generischen Routingframeworks für die Nutzung mit MATSim durchgeführt werden, sowie Vergleichsalgorithmen (z.B. Shortest-Path, HotPotato, OSPF, AntNet [3], ReplEx [4], ...) umgesetzt werden. Ferner sollen Vergleiche der Algorithmen anhand gegebener Metriken auf realitätsnahen Szenarien durchgeführt werden, welche mit GIS-Werkzeuge erstellt werden können. Für die bei dieser Diplomarbeit erstellte Software soll die Maxime der Widerverwendbarkeit angestrebt werden, indem komponentenbasiert (z.B. mithilfe des Spring-Frameworks) entwickelt wird.
[1] http://www.matsim.org
[2] Horst F. Wedde, Sebastian Lehnhoff, Bernhard van Bonn, Z. Bay, S. Becker, S. Boettcher, C. Brunner, A. Buescher, T. Fuerst, A. M. Lazarescu, E. Rotaru, S. Senge, B. Steinbach, F. Yilmaz und T. Zimmermann, A Novel Class of Multi-Agent Algorithms for Highly Dynamic Transport Planning Inspired by Honey Bee Behavior. In: ETFA ’07 - Proceedings of the 12th conference on emerging technologies and factory automation, IEEE Press, Patras, 2007-09
[3] Di Caro G., Dorigo M., AntNet: Distributed Stigmergetic Control for Communications Networks, Journal of Artificial Intelligence Research (JAIR), Vol. 9, Pag. 317-365, 1998.
[4] Simon Fischer, Selfish Dynamic Routing, Dissertation RWTH Aachen, 2007