Genetische Algorithmen zur Parameteroptimierung von Simulationsmodellen am Beispiel einer "Grünen Welle" entlang einer Hauptverkehrsstraße

Inhaltsverzeichnis

1 Einführung
1.1 Begriffe aus der Verkehrsplanung
1.2 Problemstellung
1.3 Überblick über bisherige Lösungsansätze

2 Simulation
2.1 Grundlagen
2.1.1 Begriffsdefinitionen
2.1.2 Das Simulations-Framework DESMO-J
2.2 Modell eines Straßenzuges mit Ampeln und Nebenstraßen
2.2.1 Beschreibung des Modells
2.2.2 Grenzen, Einschränkungen und Erweiterbarkeit
2.2.3 Klassendiagramm des Modells

3 Optimierung
3.1 Probleme und Lösungsverfahren
3.1.1 Optimierungsprobleme
3.1.2 Lösungsverfahren für diskrete Optimierungsprobleme
3.2 Genetische Algorithmen
3.2.1 Einführung
3.2.2 Vorbild Natur
3.2.3 Problemspezifische Kodierung
3.2.4 Ablauf eines einfachen GA
3.2.5 Kodierung
3.2.6 Das Gütemaß
3.2.7 Genetische Operatoren
3.2.8 Konvergenz
3.2.9 Variationen des einfachen GA
3.3 Theoretischer Hintergrund
3.3.1 Schemata
3.3.2 Hypercubes
3.3.3 Das Schema Theorem
3.3.4 Folgerungen

4 Simulationsbasierte Optimierung
4.1 Parameter
4.2 Verwendete Genetische Algorithmen
4.3 DISMO
4.4 Ergebnisse der Optimierungsläufe
4.5 Bewertung
4.6 Ausblick

Kapitel 1 Einführung

Wer hat noch nicht vor einer roten Ampel gestanden und sich gefragt, ob sich das ständige Warten nicht verkürzen ließe durch eine günstigere Ampelschaltung? Diese Fragestellung wird in der vorliegenden Arbeit am Beispiel eines Straßenzugmodells aufgegriffen. Mit Hilfe eines Systems zur verteilten simulationsbasierten Optimierung mittels Genetischer Algorithmen werden die Ampelphasen des Modells optimiert.

Ein Straßenzug sowie der Verkehr darauf läßt sich mit Hilfe eines Modells im Rechner darstellen. Mit Hilfe von Parametern kann die Schaltung der Ampeln im Modell gesteuert werden. Nach einem Simulationslauf ist bekannt, wie gut oder schlecht sich das Modell mit den gegebenen Parametern entwickelt hat. Dieses Ergebnis kann von einem Optimierungsverfahren verwendet werden, um bessere Parameter zu entwickeln. Die Simulation einer Vielzahl solcher Straßenzug-Modelle ist relativ zeitaufwendig, bei den verwendeten Optimie- rungsverfahren aber unumgänglich. Verteilt man die Berechnung auf mehrere Rechner, ergibt sich eine nahezu lineare Beschleunigung gegenüber der Be- rechnungszeit auf einem Rechner. Daher ist eine Verteilung der Berechnungen auf mehrere Rechner erstrebenswert. Zur verteilten Optimierung bieten sich Genetische Algorithmen besonders an. Sie sind robuste, problemunabhängige heuristische Optimierungsverfahren.

Bevor näher auf Genetische Algorithmen und ihre Anwendung zur Lösung der oben genannten Fragestellung eingegangen wird, soll zunächst im Folgenden die Problemstellung nächer beleuchtet werden.

1.1 Begriffe aus der Verkehrsplanung

Um Unklarheiten zu vermeiden, werden nachfolgend verschiedene Begriffe definiert. Sie entsprechen zum großen Teil den Festlegungen in [Ian94, S. 5ff].

Lichtzeichenanlage Eine Lichtzeichenanlage, im allgemeinen Sprachgebrauch auch Ampel genannt, ist eine technische Einrichtung, die durch Lichtsignale gemäß §37 StVO an Kreuzungen, Einmündungen oder anderen Straßenstellen den Verkehr regelt.

Lichtsignal Ein Lichtsignal ist ein farbiges Lichtzeichen einer Lichtzeichen- anlage, das in den Farben grün, gelb, rot sowie rot und gelb (zusammen) vor- kommt.

Signalzeit Als Signalzeit bezeichnet man die Zeit in Sekunden, während der die Lichtzeichenanlage ein bestimmtes Signal zeigt.

Signalzeitenplan Ein Signalzeitenplan ist ein Plan, der angibt, zu welchem Zeitpunkt an einer Lichtzeichenanlage und in welcher zeitlichen Reihenfolge ein bestimmtes Signal angezeigt wird.

Phase Unter einer Phase versteht man denjenigen Teil einer Signalprogrammes, während dessen ein bestimmter Zustand der Signalisierung einer Lichtsignalanlage unverändert bleibt.

Freigabezeit oder Grünzeit Mit Freigabezeit bezeichnet man die Zeit, während der eine Lichtzeichenanlage „GRÜN“ zeigt.

Sperrzeit Unter Sperrzeit versteht man die Zeit in Sekunden, während der eine Lichtzeichenanlage „ROT“ zeigt.

Umlaufzeit oder Zykluslänge Die Umlaufzeit ist die Periodendauer für eine Lichtzeichenanlage.

Zyklus Mit Zyklus bezeichnet man die Abfolge der verschiedenen Phasen des Signalprogrammes einer Lichtzeichenanlage.

Signalprogramm Als Signalprogramm bezeichnet man die zeitliche Verteilung der Signalzeiten für eine Lichtzeichenanlage. Das Signalprogramm ist eine zeitlich wiederkehrende Folge von Signalen, die an den einzelnen Sichtzeichenanlagen einer Kreuzung angezeigt wird. Es besteht in der Regel aus der Umlaufzeit, der Anzahl und Art der Phasen, der Phaseneinteilung und deren zeitlicher Abfolge sowie der Dauer der Freigabezeiten.

Phasenverschiebung oder Versatzzeit Hiermit wird die zeitliche Verschiebung zwischen den Startzeitpunkten der Signalprogramme zweier Lichtzeichenanlagen bezeichnet.

Grüne Welle Als Grüne Welle bezeichnet man eine Schaltung von Lichtzeichenanlagen entlang einer bestimmten Strecke oder eines Straßenzuges so, daß die Verkehrsteilnehmer diese Strecke ohne anzuhalten mit konstanter Geschwindigkeit durchfahren können.

Haltelinie Die Haltelinie gibt an einer durch Lichtzeichenanlagen geregelten Kreuzung die Stelle an, an der das erste wartende Fahrzeug zu halten hat, wenn diese Lichtzeichenanlage “ROT"´ signalisiert.

Stauraum Als Stauraum bezeichnet man den Raum vor einer Kreuzung, in dem Fahrzeuge während der Sperrzeit vor einer Lichtzeichenanlage auf das Freigabesignal warten. Er erstreckt sich von der Haltelinie bis zur davorlie- genden Kreuzung.

Straße Mit Straße bezeichnet man einen Verkehrsweg, auf dem sich Fahrzeuge in eine bestimte Richtung bewegen.

Fahrstreifen oder Spur Der zum ungehinderten Fahren eines Fahrzeuges benötigte Teil der Straße ist der Fahrstreifen.

Kreuzung Eine Kreuzung ist ein Ort, an dem mindestens zwei Straßen zusammengeführt werden.

Verkehrsstrom Als Verkehrsstrom bezeichnet man eine Anzahl von Fahrzeugen, die sich auf einer Straße bewegen.

1.2 Problemstellung

Der Verkehrsplaner eines innerstädtischen Straßennetzes hat dafür zu Sorgen, daß der gesamte Verkehr möglichst reibungslos fließt. Besonders zu den soge- nannten Stoßzeiten, dem morgendlichen und abendlichem Berufsverkehr, ist dies keine einfache Aufgabe. Ein ihm zur Verfügung stehendesInstrument zur kurzfristigen Steuerung des Verkehrsstroms sind die Lichtzeichenanlagen. An Stellen mit besonders hohem Verkehrsaufkommen ist es sicher sinnvoll, durch die Koordination der Lichtzeichenanlagen, eine Grüne Welle einzurichten. Ty- pischerweise sind die Zentren besonders hohen Verkehrsaufkommens zu den Stoßzeiten die Straßen, welche das Stadtzentrum mit den Randbezirken ver- binden. Nachdem der Verkehrsplaner auf diesen Hauptverkehrsstraßen eine Güne Welle eingerichtet hat, stellt sich natürlich die Frage, wie störungsfrei der Verkehrsfluß in der Gegenrichtung verläuft. Bei einer eingerichteten Grü- nen Welle auf einer Hauptverkehrsstraße muß die Gegenrichtung keinen op- timalen Verkehrsfluß mehr aufweisen. Wie stark ist die Benachteiligung die- ser Minderheit an Verkehrsteilnehmern? Falls die Benachteiligung dieser Ver- kehrsteilnehmer zu stark ausfällt, muß der Verkehrsplaner zur Erreichung ei- nes optimalen Verkehrsflusses diese mit ins Kalkül aufnehmen. Schließlich müssen noch die Verkehrsteilnehmer der in die Hauptverkehrsstraße einmün- denden Straßen bedacht werden.

Ianigro führt in [Ian94] eine Untersuchung verschiedener Optimierungskrite- rien zur Steigerung der Qualität des Verkehrsflußes an. Darin werden als be- sonders maßgeblich die Kriterien Reisezeit, Summe der Wartezeiten und die Anzahl der verkehrsbedingten Halte angesehen. Er kam zu dem Schluß, daß man sich auf die Minimierung der Reisezeit beschränken kann, da die anderen Kriterien sich mit der gleichen Tendenz ändern.

Als Ziele des Verkehrsplaners können daher die folgende Kriterien in der folgenden Reihenfolge festgehalten weden:

Minimierung der durchschnittlichen Fahrzeit der Fahrzeuge

- auf der Hauptverkehrsstraße in Richtung der Grünen Welle
- auf der Hauptverkehrsstraße in beiden Richtungen
- in den Nebenstraßen und der Hauptverkehrsstraße

Zum Erreichen dieser Ziele wird das Problem der Optimierung der Signalprogramme der Lichtzeichenanlagen in mehrere Teilprobleme unterteilt:

Zunächst muß ein geeignetes Modell eines Straßenzuges gefunden werden. Das verwendete Modell eines Straßenzuges mit vier Lichtzeichenanlagen wird nach einer kurzen Einführung in die Grundlagen der Simulation in Kapitel 2.2 auf Seite 10 beschrieben.

Ein geeignetes Optimierungsverfahren muss gefunden werden. Aufgrund der breiten Anwendbarkeit könnte sich ein Genetischer Algorithmus für die gegebene Fragestellung gut eignen. In Kapitel 3 auf Seite 19 wird auf verschiedene Optimierungsmethoden hingewiesen und auf die Technik der Genetischen Algorithmen näher eingegangen.

Es müssen verschiedene Optimierungsläufe am Modell des Straßenzu- ges in verschiedenen Szenarien durchgeführt werden. Unter einem Opti- mierungslauf sind viele Optimierungsiterationen mit jeweils vielen Expe- rimenten zu verstehen. Dies wird in Kapitel 4 auf Seite 43 beschrieben.

Schließlich wird in Kapitel 4.5 auf Seite 56 bewertet, inwieweit die Gene- tischen Algorithmen in der Lage sind, die gegebenen Probleme zu lösen.

1.3 Überblick über bisherige Lösungsansätze

Staubekämpfung an Lichtsignalgesteuerten Knotenpunkten Nach [Ian94, S. 30f] gibt [Bie87] einige Hinweise zur Staubekämpfung an lichtsignalgesteuerten Knotenpunkten. Dabei werden maximal zwei hintereinander liegende Kreuzungen betrachtet. Die untersuchten Maßnahmen sind:

Versatzzeitreduzierung Die Reduzierung der Versatzzeit zur nachfolgen- den Lichtzeichenanlage wird dahingehend untersucht, ob sie das Pro- blem lösen kann, wenn an einer Kreuzung ein Rückstau entsteht, der so lang ist, daß er den Verkehrsablauf an einer davorliegenden Kreuzung behindert. Nach Ansicht des Autors muß in jedem Einzelfall geprüft werden, ob durch diese Maßnahme der Gegenverkehr zu stark behin- dert wird.

ausgleichende Versatzzeit Mit dem Ansatz der ausgleicheneden Versatzzeit bezeichnet der Autor die Umkehrung der Versatzreduzierung. Hierdurch soll verhindert werden, daß der Querverkehr an einer Kreuzung zu stark behindert wird.

Pulkstauchung Diese Methode erfordert einen mindestens 200 Meter langen Stauraum in dem die Fahrzeuge zu einem Pulk zusammen gefaßt werden. Während der Freigabezeit sollen dann die Fahrzeuge im Pulk die Kreuzung überqueren.

Umlaufzeitveränderung Diese Maßnahme kann bei einer eingerichteten Grünen Welle nicht ohne weiteres vorgenommen werden, da sie sich stark auf die übrigen beteiligten Lichtsignalanlagen auswirkt.

Mehrfachanwurf Durch die Methode der mehrfachen Zuteilung ei- ner Freigabezeit für eine Kreuzungszufahrt während einer Umlaufzeit kommt es mit hoher Wahrscheinlichkeit zu stop-and-go Verkehr. Die Au- torin schlägt diese Methode jedoch vor, da mit ihr die Ausnutzung des Stauraumes verbessert und der Verkehr in kleine Pulks zusammengefaßt werden kann.

Eine Theorie für die Signalsteuerung in Stadtnetzen In einem analytischen Modell mittels Funktionen untersucht [SS73] nach [Ian94, S. 32f] die Verkehrs- ströme in einem Straßenzug mit maximal drei Kreuzungen. Der Autor kommt zu dem Schluß, daß die beste Lösung für eine einfache Realisierung der Grü- nen Welle die Simultan-Schaltung der beteiligten Lichtzeichenanlagen ist. Ver- kehrsabhängige Steuerungen „...versprechen insgesamt nicht den großen Vor- teil, den man von ihnen erwartet“.

Ein Modell zur Berechnung optimal koordinierter Lichtsignalsteuerungen Nach [Ian94, S. 35f] untersucht [Sch81] den Verkehrsstrom zweier hintereinander liegender Kreuzungen mittels schematisierter Dichtefunktionen. Zur Optimierung der Signalzeiten wird ein Gradienten-Rundungs-Verfahren verwendet. Angewandt auf einen realen Straßenzug konnten hiermit positive Veränderungen in Form einer Versatzzeitänderung erreicht werden.

Folgerung Die obigen Ansätze liefern interessante Hinweise zum Auffinden von Signalprogrammen für Lichtsignalsteuerungen. Dennoch ist es sinnvoll weitere Verfahren zu testen, um eventuell bessere Lösungen bzw. allgemeinere Lösungsverfahren zu finden.

Kapitel 2 Simulation

2.1 Grundlagen

Dieses Kapitel gibt eine kurze Einführung in die Grundbegriffe der Simulation. Kapitel 2.2 auf Seite 10 geht daran anschließend auf die Umsetzung eines konkreten Modells mit Hilfe von DESMO-J in Java ein.

Eine detaillierte Einführung zu den Grundlagen der diskreten Simulation ist etwa in [Pag91] zu finden.

2.1.1 Begriffsdefinitionen

Was ist ein System?

„Die Umwelt des Menschen besteht nicht nur aus einer Anhäufung von Einzelobjekten, sondern auch aus einem Netz von Beziehungen, das die Objekte untereinander verbindet. Ausschnitte aus dieser Gesamtmenge der Objekte und Beziehungen werden vom Menschen abgegrenzt und als Systeme bezeichnet.“ [Pag91, S. 1]

Nach dieser Definition ist das größtmögliche System das Universum. Wann immer man einen Teil des Universums betrachtet und genau sagt, was zu diesem Teil gehört, was nicht und wie es mit seiner Umgebung interagiert, so hat man ein neues System definiert. Dieser Betrachtung liegt eine Hierar- chie der Systeme zugrunde: Aus einem System kann man einen kleineren Teil betrachten, wodurch dieser als neues System definiert ist. Als Element eines Systems bezeichnet man ein als nicht weiter teilbar angesehenes Objekt eines Systems. Systeme stehen gewöhnlich mit ihrer Umgebung über ihren Syste- meingang bzw. -ausgang in interaktiver Beziehung. Ein Beobachter kann von außen auf ein System einwirken und Änderungen der Ausgabe des Systems beobachten. Derartige Systeme bezeichnet man als offene Systeme. Geschlossene Systeme haben keine interaktive Beziehung mit der Umgebung. Sie sind meist gedankliche Vereinfachungen realer offener Systeme (vgl. [Pag91, S. 2-3]).

Was ist ein Modell? Ein Modell ist ein System, welches ein anderes System abstrahiert und idealisiert darstellt. Durch Modelle wird die Untersuchung komplexer Systeme häufig überhaupt erst machbar. Ob ein Modell eine geeignete Abstraktion eines Systems ist, hängt von der gegebenen Fragestellung ab (vgl. [Pag91, S. 4]).

Mathematische Modelle Nach der Art der Zustandsübergänge lassen sich Modelle in Kategorien einteilen. Neben den statischen Modellen ohne Zu- standsübergänge unterscheidet man dynamische Modelle, in denen die Zeit kontinuierlich vergeht, und solche, die mit einer diskreten Zeiteinteilung ar- beiten(vgl. [Pag91, S. 6]).

Die zeitkontinuierlichen Modelle sind dadurch charakterisiert, daß sie Ihren internen Zustand innerhalb einer endlichen Zeitspanne unendlich häufig än- dern können. Ein solches Modell ist repräsentierbar durch einen Satz von Dif- ferentialgleichungen. Wird ein kontinuierliches Modell auf einem gängigen Digitalrechner umgesetzt, so ist eine Abbildung des kontinuierlichen Modells auf diskrete Zustände des Digitalrechners unumgänglich. Man bezeichnet sol- che Modelle als quasikontinuierlich. Tieferen Einblick in die Modelierung kon- tinuierlicher Systeme bietet etwa [Cel91].

Ein zeitdiskretes Modell zeichnet sich dadurch aus, daß sich die Zustände des Modells zu diskreten Zeitpunkten sprunghaft verändern. Zeitdiskrete Model- le lassen sich weiter in stochastische und deterministische Modelle unterschei- den. In deterministischen Modelle kann immer aus einem Modellzustand der Folgezustand des Modells ermittelt werden. Dies ist bei stochastischen Model- len nur bedingt möglich. Mit Hilfe von Zufallsvariablen in stochastischen Mo- dellen können sehr komplexe deterministische Vorgänge einfach dargestellt werden. Speziell die Modellierung von externen Einflüssen auf das Modell kann durch Zufallsvariablen leicht dargestellt werden.

Der vorliegende Text beschäftigt sich ausschließlich mit der Simulation diskreter Modelle.

Modellierungsstile Ein Modell eines dynamischen Systems beinhaltet akti- ve und passive Elemente. Daher unterscheidet Page in [Pag91] für die diskrete Simulation zwischen zwei Sichtweisen unter denen ein Modell betrachtet wer- den kann. Stehen die passiven Elemente im Fokus des Betrachters, so verwen- det er einen materialorientierten Ansatz zur Modellbeschreibung. Erachtet der Modellierer die aktiven Elemente als zentraler, so wird er einen maschinenori- entierten Modellierungsstil wählen.

Die wichtigsten heute gebräuchlichen Konzepte sind zum einen die ereigni- sorientierte Simulation für den materialorientierten Ansatz, zum anderen die prozeßorientierte Simulation für den maschinenorientierten Ansatz (vgl. [Pag91, S. 71ff]).

Ereignisorientierter Ansatz Der ereignisorientierte Ansatz beruht auf der Beschreibung von Ereignissen in Form von Ereignisroutinen. In den Ereignis- routinen werden die Zustandänderungen des Modells durchgeführt, die zu den Ereigniszeitpunkten stattfinden. Zeitlich ausgedehnte Vorgänge werden auf eine Folge von Ereignissen reduziert, von denen jedes einzelne einem Ereigniszeitpunkt zugeordnet ist. Während der Ausführung der Ereignisroutine vergeht keine Simulationszeit. Nach der Ausführung „springt“ die Simulationsuhr zum nächsten Ereigniszeitpunkt vor.

Prozeßorientierter Ansatz Der prozeßorientierte Ansatz faßt die auf ein Ob- jekt bezogenen Aktivitäten mit seinen Attributen zu einem Prozeß zusammen. Während der aktiven Phase eines Prozesses steht die Simulationsuhr und der Prozeß führt Zustandsänderungen durch. Im Gegensatz zur Ereignisroutine hat der Prozeß die Möglichkeit sich zu passivieren. Bis der Prozess wieder re- aktiviert wird, läuft die Simulationsuhr weiter. So ist es möglich, passive und zeitkonsumierende Phasen einer Systemkomponente darzustellen.

Ein konkretes Beispiel der Umsetzung des prozessorientierten Ansatzes wird in Kapitel 2.2 auf der nächsten Seite vorgestellt. Mit Hilfe des in Kapi- tel 2.1.2 auf der nächsten Seite vorgestellten Simulationsframeworks DESMO- J, wird dort ein Straßenzug mit mehreren Ampeln und Seitenstraßen model- liert.

Was ist ein Experiment? Ein Experiment ist der Prozess der Datenentnahme von einem System während es durch seine Eingabe beeinflußt wird. Ein großer Nachteil von Experimenten mit real existierenden Systemen ist, daß diese Systeme normalerweise unter dem Einfluß von vielen nicht steuerbaren Eingaben sind. Auch kann sich eine Menge der interessanten Ausgaben des System häufig einer Messung entziehen. Dies sind wichtige Gründe, warum die Simulation mit Hilfe eines Modells einem Experiment an einem realen Sy- stem häufig vorzuziehen ist. In der Simulation sind alle Ein- und Ausgaben zugänglich. Das erlaubt es, Experimente durchzuführen, die in der realen Welt nicht möglich wären (vgl. [Cel91, S. 4f]).

Was ist eine Simulation? Eine Simulation ist ein Experiment, das auf an ei- nem Modell durchgeführt wird. Sofern das Modell bezogen auf die Fragestel- lung eine hinreichend exakte Abstraktion des modellierten Systems ist, lassen sich durch die Simulation Kenntnisse über das Originalsystem gewinnen (vgl. [Pag91, S. 7f]).

Obwohl diese Definition allgemein gehalten ist, wird es im weiteren nur um solche Simulationen gehen, die sich auf einen Rechner übertragen lassen. Diese Art der Simulation wird auch Computer-Simulation genannt. Sie ist eine kodierte Beschreibung eines Experimentes unter Bezugnahme auf das Modell, an welchem dieses Experiment durchgeführt wird.

Warum Simulation? Es ist häufig keine leichte Aufgabe, ein Modell eines realen Systems zu erstellen. Noch schwieriger kann es sein, zu beweisen, daß sich die aus der Simulation gewonnenen Erkenntnisse auf das reale System übertragen lassen. Aufgrund der zusätzlichen Einflußfaktoren im realen Sy- stem kann sich dieses leicht völlig anders verhalten, als von der Simulation vorhergesagt. Aus dieser Überlegung heraus ist es sicher ratsam, wo es geht, auf Simulation und die dadurch entstehenden zusätzlichen Schwierigkeiten zu verzichten. Stattdessen sollte man zunächst versuchen, analytische Techni- ken einzusetzen. Ihre Anwendungsgebiete sind wesentlich begrenzter. Aber dort, wo sie möglich sind, sollte man sie der Simulation vorziehen. In vielen Fällen ist jedoch Simulation das Mittel der Wahl - eventuell gemein- sam mit analytischen Ansätzen. Ohne Anspruch auf Vollständigkeit können gerade für die Verwendung von Simulation einige Gründe sprechen:

Das zu untersuchende System steht nicht zur Verfügung. Eventuell soll es nach erfolgreicher Simulation überhaupt erst gebaut werden.

Das Experimentieren mit dem zu untersuchenden System ist zu gefähr- lich.

Die Kosten für ein Experiment am zu untersuchenden System sind zu hoch.

Das Experiment am zu untersuchenden System dauert eine zu kurze oder zu lange Zeitspanne.

Parameter des zu untersuchenden Systems sind nicht einstellbar oder können nicht gut ermittelt werden.

In der Simulation können einzelne Effekte bewußt ausgeklammert oder separat betrachtet werden, die im zu untersuchenden System nur gemeinsam auftreten.

2.1.2 Das Simulations-Framework DESMO-J

DESMO-J ist die Abkürzung von "Discrete Event Simulation and MOdeling in Java". Es ist ein Framework, daß aus einer Reihe von Java-Klassen besteht, welche die Entwicklung von Modellen zur Simulation unterstützen. Die für je- de diskrete Simulation notwendigen Funktionalitäten wie Erzeugung von Zu- fallszahlen, Statistikfunktionen, Berichterstattung sowie Ablaufplanung der Simulation werden von DESMO-J bereitgestellt. Es sind verschiedene Model- lierungskomponenten enthalten, die zur Erstellung des eigenen Modells ver- wendet werden können. Detaillierte Dokumentation sowie die DESMO-J Klas- sen können im Internetunter [PLCN00] eingesehenund herunter geladen wer- den.

Es wird sowohl der ereignis- als auch der prozeßorientierte Ansatz durch die DESMO-J Klassen unterstützt. Bei der Modellierung macht DESMO-J keinerlei Einschränkungen. Der volle Funktionsumfang von Java kann genutzt werden.

2.2 Modell eines Straßenzuges mit Ampeln und Neben- straßen

Das nachfolgend beschriebene Modell eines Straßenzuges mit mehreren Am- peln und Nebenstrßen hat einen idealisierten Straßenzug zum Vorbild. Ziel

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Das Modell des Straßenzuges mit vier Kreuzungen

des Modells ist es, für eine gegebene Belastung der verschiedenen Zufahrtswege durch Fahrzeuge die durchschnittliche Verweildauer der Fahrzeuge auf einigen Routen im Modell zu ermitteln. Durch geeignete Wahl der Modellparameter könnte das Modell an einen real existierenden Straßenzug angepaßt werden. Hierbei ist natürlich zu prüfen, ob die im Modell vorgenommenen Vereinfachungen die Realität ausreichend genau abbilden.

2.2.1 Beschreibung des Modells

Das Modell „Crossings“ ist unter Verwendung von DESMO-J in Java geschrie- ben. Wie in Abbildung 2.1 zu sehen ist, bildet das Modell vier einfache Straßen- kreuzungen, die durch drei Straßen in gerader Linie verbunden sind, ab. Die so entstandene Achse liegt in West-Ost Richtung. Zu den übrigen Zufahrts- möglichkeiten der Kreuzungen führt jeweils eine Straße. Der Eingang des Mo- dells ist durch sogenannte „Auto-Erzeuger“ (bzw. „CarGenerator“) realisiert. Durch sie wird das Eintreten der Fahrzeuge in das System modelliert. Je einer steht am Anfang einer jeden Straße. Die Ausrichtung der Straßen an den Him- melsrichtungen ist gewählt worden, um eine eingängige Bezeichnungsweise der Straßen und Fahrtrichtungen zu ermöglichen.

Modellparameter Die Modellparameter ermöglichen es dem Benutzer des Modells verschiedene Szenarien und Umgebungen zu charakterisieren. Folgende Parameter stehen in diesem Modell zur Verfügung:

Für alle Fahrzeuge

- Durchschnittsgeschwindigkeit
- Fahrzeuglänge

Für jeden einzelnen Straßenabschnitt

- Straßenlänge

Für jede einzelne Kreuzung

- Dauer der Rot- und Grünphasen
- Phasenverschiebung des Rot-Grün-Zyklus relativ zum Startzeitpunkt der Simulation

Für jeden Auto-Erzeuger

- Obere und Untere Schranke der gleichverteilten Ankunftszeit eines Fahrzeugs

Für alle Fahrzeuge, die an eine Kreuzung kommen

- Wahrscheinlichkeiten, mit denen ein Fahrzeug von der Hauptverkehrsstraße nach links oder rechts abbiegt oder geradeaus fährt

- Wahrscheinlichkeiten, mit denen ein Fahrzeug von einer Nebenstraße nach links oder rechts abbiegt oder geradeaus fährt

Für alle Kreuzungen

- Länge der Linksabbiegerspur auf der Kreuzung
- Dauer der Sperrzeit für beide Richtungen vor dem Umschalten der Freigabezeit auf die neue Fahrtrichtung (vgl. unter Lichtzeichenanlage in Kapitel 2.2.1 auf Seite 15)
- Dauer zu Beginn der Grünphase in der nur verlangsamt Fahrzeuge über die Kreuzung fahren; hierdurch wird die Beschleunigung der Fahrzeuge modelliert.
- Dauer bis das nächste Fahrzeug über die Kreuzung fährt während der verlangsamten Grünphase
- Dauer der Überfahrten während der restlichen Grünphase

Modellresultate

Durchschnittliche Fahrzeit

- der Fahrzeuge, die vom westlichen zum östlichen Ende des Modells fahren
- der Fahrzeuge, die vom östlichen zum westlichen Ende des Modells fahren
- aller Fahrzeuge im Modell vom Eintritt in das Modell bis zum Aus- tritt

Längste und kürzeste durchschnittliche Verweilzeit eines Fahrzeugs im Modell

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2: Lebenszyklus-Diagramm eines Auto-Erzeugers

Auto-Erzeuger Der Systemeingang des Modells wird von den AutoErzeugern dargestellt. Durch sie wird abgebildet, daß es weiteren Verkehr außerhalb des in der Simulation betrachteten Modells gibt und Fahrzeuge aus diesem Verkehr in das Modell eintreten. Um dies zu erreichen, erzeugt jeder Auto-Erzeuger in zufälligen zeitlichen Intervallen ein Fahrzeug auf der ihm zugewiesenen Straße. Vgl. unter „Modellparameter“.

Ist die Straße bereits voll mit wartenden Fahrzeugen, kann das Fahrzeug die Straße nicht befahren und tritt nicht in die Simulation ein. Es bildet sich ein Stau bei diesem Auto-Erzeuger. Sobald ein Platz auf der Straße frei wird, fährt ein Fahrzeug aus diesem Stau auf den freien Platz.

Für Fahrzeuge, die auf unmittelbar aus dem Modell hinausführenden Straßen fahren, wird angenommen, daß keine Probleme beim Verlassen des Modells auftreten. Hier bildet die Ausfahrtstraße die Systemgrenze. Das Diagram des Lebenszyklus eines Auto-Erzeugers ist in Abbildung 2.2 dargestellt. Implementiert ist der Auto-Erzeuger in der Klasse „CarGenerator“ als Erweiterung der DESMO-J Klasse „ExternalEvent“.

Straßen Die Straßen des Modells liegen entweder in West-Ost- oder Nord- Süd-Richtung und bestehen je aus zwei Spuren; eine für jede Fahrtrichtung. Je- de Spur besteht aus zwei Warteschlangen, die „DrivingQueue“ und die „Wait- Queue“. Das Fahren eines Fahrzeugs entlang einer Spur wird abgebildet auf das Verweilen in der „DrivingQueue“ für den entsprechenden Zeitraum. Ist die Ampel grün und kein Fahrzeug in der Warteschlange, so fährt es über die Kreuzung. Sonst reiht es sich hinten in die „WaitQueue“ ein. Da es lediglich von Interesse ist, wie lange sich das Fahrzeug insgesamt auf der Straße befin- det, ist es belanglos, daß es einen Teil der Strecke bei teilweise belegter „WaitQueue“ doppelt fährt.

Die Straße hat im Gegensatz zu den übrigen Modellkomponenten keinen ei- genen Lebenszyklus sondern dient als passiver Teil des Modells als Rahmen für Warteschlangen der Fahrzeuge. Um die Namen der Warteschlangen der beiden Spuren innerhalb der Klasse unterscheiden zu können, haben die War- teschlangennamen nach Norden bzw. Westen „first“ vorangestellt, die nach Süden bzw. Osten „second“. Die Straßen sind in der Klasse „Street“ imple- mentiert, die sich von der DESMO-J Klasse „ModelComponent“ ableitet.

Fahrzeuge Ein Fahrzeug befährt nach seiner Erzeugung bzw. nach dem Überqueren einer Kreuzung eine Straße, indem es sich in die Warteschlan- ge „DrivingQueue“ der Straße in der entsprechenden Fahrtrichtung einreiht und dort je nach Länge der Straße wartet. Hierdurch wird die Zeit simuliert, die das Fahrzeug benötigt, um zum Ende der Straße zu gelangen. Findet es hier keine Kreuzung vor, verläßt es das Modell. Falls eine Kreuzung existiert, die Ampel der Kreuzung „Grün“ signalisiert und keine weiteren Fahrzeuge in der „WaitQueue“ vor der Kreuzung stehen, überquert das Fahrzeug die Kreu- zung sofort. Es reiht sich in der DrivingQueue einer angrenzenden Straße ein, die für die Weiterfahrt vorgesehen ist. Falls das Fahrzeug nicht sofort über die Kreuzung fahren kann, reiht es sich in der „WaitQueue“ vor der Kreuzung ein und passiviert sich. Wird das Fahrzeug durch die Kreuzung schließlich wie- der aktiviert, versucht es die Kreuzung zu überqueren und sich in der zufällig ausgewählten Straße einzureihen. Gelingt dies nicht, da diese Straße voll ist, bleibt es vor der Kreuzung stehen und passiviert sich wieder. Linksabbiegende Fahrzeuge reihen sich bei Grün zunächst in eine Warteschlange auf der Kreu- zung, die „TurnLeftQueue“, ein. Bevor sie weiterfahren können, überprüfen sie, ob Gegenverkehr herrscht oder die Straße, die sie befahren wollen, voll ist. Ist dies der Fall, bleiben sie auf der Kreuzung stehen. Ist die Schlange auf der Kreuzung voll, so können nicht nur folgende Linksabbieger nicht mehr in die Warteschlange nachrücken, auch geradeaus fahrende oder rechtsabbie- gende Fahrzeuge können die Kreuzung nicht mehr überqueren. Sobald die Ampel auf rot schaltet, werden die Fahrzeuge in der „TurnLeftQueue“ auf der Kreuzung noch einmal aktiv und versuchen, bevor in der entgegengesetz- ten Richtung grün wird, abzubiegen. Ist die Straße, in die sie abbiegen wollen immer noch voll, bleiben sie weiterhin auf der Kreuzung stehen. Keines der Fahrzeuge, welches nun grün bekommt, kann die Kreuzung passieren, bis die Abbieger die Kreuzung geräumt haben.

In Abbildung 2.3 auf der nächsten Seite ist der Lebenszyklus eines Fahrzeugs grafisch dargestellt. In den Quellen ist ein Fahrzeug in der Klasse „Car“ zu finden. Es leitet sich von der DESMO-J Klasse „Simprocess“ ab.

[...]