Primäres Ziel dieser Arbeit ist es ein Framework zu schaffen, so dass mittels statistischer Verfahren die Wirksamkeit einzelner Routingalgorithmen bzgl. festzulegender Kriterien (z.B. Stauaufkommen, Reisezeit) im Vergleich zu anderen Verfahren zu beurteilen. Insbesondere soll, falls möglich, gezeigt werden, dass der BeeJamA-Algorithmus [10, 11, 12] überlegen ist. Um zu ermöglichen, dass realitätsnahe Verkehrsströme erzeugt und die simulativen Ergebnisse aus Sicht der verwendeten statistischen Verfahren bewertet werden, müssen die drei weiter unten aufgeführten Schwerpunktgebiete bearbeitet werden. Die notwendigen Implementierungsarbeiten werden in Einklang mit aktueller Literatur zum Thema Softwarearchitekur durchgeführt, damit Wart- und Wiederverwendbarkeit erleichtert werden [9, 5].
Einschränkungen ergeben sich insbesondere aus den Grundlagen auf denen diese Diplomarbeit aufbaut. So ist für den verteilten Simulator [13] zur Zeit weder ein taugliches Verkehrsmodell, noch der BeeJamA-Algorithmus implementiert. Weiterhin ist die Visualisierung gegenwärtig nicht geeignet größere Graphen anzuzeigen, womit es schwierig ist größere Testszenarien zu entwickeln. Die Architektur und Dokumentation des Simulators ist aus Entwicklersicht leider nicht belastbar und somit eine Entwicklung von Zusatzkomponenten zeitraubend. Weiterhin sind die verfügbaren Datensätze zur Straßenauslastung nicht sehr granular.
Unmittelbar notwendig zur Beurteilung der Algorithmen sind realitätsnahe Verkehrsströme, da sonst die ermittelten simulativen Ergebnisse nur schwerlich als Prädiktor für zukünftige Ergebnisse im realen Einsatz verwendet werden könnten. Optimalerweise basieren die generierten Verkehrsströme auf real beobachteten Verkehrsströmen. Allerdings ist die Beschaffung dieser Daten in notwendigen Auflösung jedoch kaum möglich; die verfügbaren Daten geben nur Aufschluß über die Auslastung der wichtigsten Straßen Nordrheinwestfalens auf das ganze Jahr gesehen. Aufgabe für diesen Bearbeitungsschritt ist die Entwicklung und Umsetzung eines Modells, welches sowohl die Nutzung real beobachteter Verkehrsströme als auch heuristische Ansätze ermöglicht.
Zur Umsetzung dieser Anforderungen wurde bis jetzt folgendes sogenanntes Zonen-Modell angedacht und testweise rudimentär implementiert. Eine Zone entspricht dabei einer Menge von Knoten des Graphen mit gleicher "Nutzung". Eine Zone könnte bspw. ein Wohn-, ein Industrie- oder ein Innenstadtgebiet repräsentieren. Zonen werden nun Mengen von Regeln der folgenden Form zugeordnet:"Im Zeitraum A werden mit einer W'keit von B pro Zeiteinheit C Fahrzeuge gemäß Profil D erzeugt" Hierbei kapselt das Profil nun Informationen wie den Fahrzeug- und Fahrertyp, das Ziel und ähnliches. Damit lassen sich Szenarien der folgenden Form modellieren, hier z.B. die morgenliche Fahrt zur Arbeit: "Morgens zwischen 6.30-7.00 Uhr verlassen im Schnitt 100 Fahrzeuge die Wohnsiedlung mit dem Ziel Industriegebiet. Die Fahrzeuge sind eher klein und die Fahrer halten normalen Abstand." Über dieses Zonen-Modell lassen sich auf der einen Seite vollständig zufällige Verkehrsströme realisieren, auf der anderen Seite allerdings auch Verkehrsströme die sich bestmöglich an real beobachtbare Daten, sofern vorhanden, orientieren. Weder das eine noch das andere Extrem ist sinnvoll oder realisierbar. Stattdessen können einerseits einige Testszenarien, d.h. die Identifikation von Zonen und deren Generierungswahrscheinlichkeiten, manuell erstellt werden, andererseits können die Auslastungsangaben der einzelnen Straßen dazu genutzt werden, um heuristisch die Zonengenerierungswahrscheinlichkeiten zu initialisieren. Folgende Heuristik könnte dabei zum Einsatz kommen: Zonen werden zufällig über die Karte verteilt, und die Generierungswahrscheinlichkeiten (abhängig von der Uhrzeit) sind proportional zur Auslastung und Entfernung umgebender Straßen. So generieren Zonen, welche gemäß (offiziellen) Auslastungsangaben von vielen stark ausgelasteten Straßen umgeben sind, mehr Verkehr als beispielsweise Zonen in ländlichen Gegenden. Nachteilig ist dabei allerdings die äußerst geringe Auflösung der vorhandenen Daten, bei denen nur Auslastungen für das komplette Jahr angegeben sind und das auch nur für die wichtigsten Straßen Nordrheinwestfalens.
Die Menge aller möglichen Zonenbeschreibungen (bei konstantem Verkehrsnetz, hier: Ruhrgebiet) stellt somit die Population dar und die tatsächlich als Eingabeinstanzen verwendeten, bilden die Menge der Stichproben.
Im Verlauf der PG502 [8] wurde die Verkehrsdomäne nur informell dargestellt. Aber erst die Umwandlung in formale Modelle ermöglicht es Aussagen zur Konvergenz oder zur Komplexität zu tätigen. Durch statistische Methoden kann man lokale Vergleiche zwischen Algortihmen ziehen, aber erst eine mathematische Analyse ermöglicht es die Leistung eines Algortihmus global einzuordnen. Diese Analyse kann im Rahmen dieser Diplomarbeit allerdings nicht vorgenommen werden, vielmehr dient die formale Darstellung dem Zweck die verschiedenen Straßenverkehrsroutingalgorithmen kompakt beschreiben und grundlegende systematische Strukturierungen vornehmen zu können. Nur so ist es dann möglich mathematisch präzise Bewertungsfunktionen zu formulieren, was nötig erscheint, da mittels der weiter unten beschriebenen statistischen Verfahren die Algoorithmen genau bzgl. solcher präzisen Unterscheidungsmerkmale verglichen werden sollen. Dabei stellen sich zwei zentrale Fragen:
Im betrachteten Kontext liefern selbst deterministische Algorithmen keine deterministischen Ergebnisse, sobald die verwendeten Verkehrsmodelle randomisiert sind. Daraus folgt die Notwendigkeit zur Verwendung von statistischen Verfahren zur Leistungsbewertung. Dabei sind dem Versuchsaufbau und der Auswertung jeweils besondere Beachtung zu schenken. Beim Versuchsaufbau stellen sich folgende Fragen:
Auf der anderen Seite stellen sich natürlich auch Fragen zur Auswertung, insbesondere welche statistischen Tests sinnvoll einsetzbar sind (Wilcoxon-Vorzeichen-Rangtest, Mann-WhitneyU-Test, Friedman-Test, ...) [7, 4].
Bisher konnten zwei Fragestellungen identifiziert werden, die unterschiedliche Behandlung bzgl. Versuchsaufbau und Analyse nahelegen. Zum einem der Fall in dem einfach mehrere Algorithmen (bspw. BeeJamA und Kürzester-Weg) miteinander verglichen werden. Dabei werden die Algorithmen (bzgl. unterschiedlicher Durchdringungen) alle auf den selben Eingabeinstanzen ausgeführt und statistisch verglichen (der nicht-parametrische Wilcoxon-Vorzeichen-Rangtest zum Vergleich der zentralen Tendenz bei verbundenen Stichproben böte sich hierbei an). Ergebnis solch eines Vergleichs wäre bspw. die Aussage, dass der (randomisierte) Algorithmus A mit Sicherheitswahrscheinlichkeit x besser ist als die anderen. Wie erwähnt, wird hierbei jeder Algorithmus auf jeder Instanz ausgeführt. Dies ist unter Umständen sehr rechen- und insbesondere zeitintensiv. Soll nur herausgefunden werden, welcher der Algorithmen am besten abschneidet, kann mit F-Race [3], ein, auf dem Friedman-Test basierendes, statistisches Verfahren verwendet werden das weniger rechen- und damit zeitintensiv ist. Allerdings wird hierbei nur ermittelt, dass ein Algorithmus besser abschneidet als die anderen, sich aber nur schwerlich exakt bestimmen läßt, wie groß dieser qualitative Unterschied ist. Dies erscheint auf den ersten Blick wie ein Nachteil, ist aber in (automatisierten) Situationen in denen nur geprüft werden soll, welche Parametrisierung von einer großen Anzahl von möglichen Parametrisierungen eines Algorithmus sinnvoll ist, vermutlich ausreichend. Die statistischen Testverfahren sind vollständig unabhängig von den eingesetzten Algorithmen, so dass leicht neue Algorithmen getestet werden können.
Es sei ein prototypischer Ablauf eines Experimentes dargestellt, dass nach Bearbeitung der Diplomarbeit möglich wäre:
Da die Simulation aus Sicht der statistischen Tests als Black-Box auftritt, ist dieses Framework vollständig unabhängig von der Art, der Anzahl oder den Implementierungsdetails der diversen Routingalgorithmen.
[1] Angela Dean, Daniel V.: Design and analysis of experiments. Springer, 2000
[2] Bartz-Beielstein, Thomas: Experimental Research in Evolutionary Computation - The New Experimentalism. Springer, 2006
[3] Birattari, Mauro: The Problem of Tuning Metaheuristics, Universite Librede Bruxelles, Dissertation, 2005
[4] Conover, W.: Practical Nonparametric Statistics. John Wiley & Sons, 1999
[5] Gregor Engels, et a.: Quasar Enterprsie. 2008 [6] Kleijnen, J.P.C.: Design and Analysis of Simulation Experiments. Springer, 2008
[7] Larson, H.: Introduction to Probability Theory and Statistical Inference. John Wiley & Sons, 1982
[8] PG502, Sven Becker, Sven Böttcher, Christian Brunner, Armin Büscher, Thomas Fürst, Anca Manuela Lazarescu, Elisei Rotaru, Sebastian Senge, Bastian Steinbach, Funda Yilmaz, Thomas Z.: Stauvermeidung durch on-line Verkehrsplanung. 2007
[9] Siedersleben, Johannes: Moderne Softwarearchitekturen. dpunkt Verlag, 2004
[10] Wedde, Horst F.; Lehnhoff, Sebastian; Bonn, Bernhard v.; 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: PEARL 2007: Informatik Aktuell - Mobilität und Echtzeit. Boppard, Germany : Springer, Dec 2007
[11] Wedde, Horst F.; Lehnhoff, Sebastian; Bonn, Bernhard v.; 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: VANET 2007: Proceedings of the 4th ACM International Workshop on Vehicular Ad Hoc Networks. Montreal, Canada : ACM Press, Sep 2007
[12] Wedde, Horst F.; Lehnhoff, Sebastian; Bonn, Bernhard v.; 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: ETFA ’07: Proceedings of the 12th conference on emerging technologies and factory automation. Patras : IEEE Press, Sep 2007
[13] Wündsch, Mario: Entwicklung einer verteilten Simulationsumgebung zur Analyse dezentraler Routingalgorithmen in dynamischen Verkehrsszenarien, Dortmund, Technical University, Diplomarbeit, 2008