Der Schwerpunkt unserer Arbeit im Rahmen des FVU liegt im Bereich der Verkehrssimulation. Bereits in der Vergangenheit existierte hierzu eine große Anzahl von Modellen und Programmen, die z.B. im Rahmen des Projektes PROMETHEUS verwendet wurden. Eine vergleichende und bewertende Untersuchung dieser verschiedenen Ansätze liegt bislang noch nicht vor, soll aber innerhalb des FVU erarbeitet werden.
Am ZPR wird gegenwärtig ein Modell verwendet, das sich in einem wichtigen Punkt von den meisten gängigen Modellen unterscheidet: es ist ein minimales mikroskopisches Modell. Mikroskopisch heißt, daß einzelne Fahrzeuge simuliert werden, mit minimal ist der Versuch bezeichnet, die Fahrzeugdynamik auf einen minimalen Satz von Regeln zu reduzieren, mit denen makroskopische Größen wie die Verkehrsdichte und der Fahrzeugfluß korrekt abgebildet werden können.
Dieses Modell hat den großen Vorteil, daß es viele Eigenschaften komplizierterer Modelle im Kern enthält. Bevor diese Behauptung an einem Beispiel belegt werden kann, soll das hier verwendete Modell kurz vorgestellt werden. Es handelt sich dabei um eine Erweiterung der aus der Physik bekannten zellularen Automaten, bei denen Raum, Zeit und Zustand nur diskrete Werte annehmen können. Die am ZPR verwendete Erweiterung besteht darin, daß nur die Zeit diskret bleibt, während Raum und Zustand (hier: Geschwindigkeit) eines Fahrzeuges kontinuierliche Werte annehmen. Zu dieser Beschreibung gehört eine Dynamik, d.h. ein Satz von Regeln, die bestimmen, wie die Modellfahrzeuge weiterbewegt werden:
Hier sind x(t) und v(t) der Ort bzw. die Geschwindigkeit eines Fahrzeuges zur Zeit
t, gap(t) der Abstand zum Fahrzeug davor, 
die Größe des
Rauschterms (das Modell ist stochastisch), 
die maximale
Beschleunigung und rand() eine Zufallszahl im Intervall [0,1]. Die Regeln
sind Karikaturen dreier Einflußgrößen, die das menschliche Fahrverhalten bestimmen:
Alle drei Faktoren gibt es auch in aufwendigeren Modellen, nur sind
sie dort hinter einer komplizierten Beschreibung mit vielen Parametern
verborgen, was die Kalibrierung mitunter sehr erschwert.
Das am ZPR verwendete Modell ( 
) hingegen ist relativ
leicht zu kalibrieren und ergibt trotz seiner einfachen Regeln eine erstaunlich
realistische makroskopische Beschreibung, wie an Abbildung
zu sehen ist. Für den Spezialfall diskreter Orte und
Geschwindigkeiten kann man den Ansatz noch weiter vereinfachen und erhält
damit einen reinen Zellularautomaten, der numerisch etwas
effizienter, aber schwieriger zu kalibrieren und unflexibler
ist.
Abbildung: Ein Fundamentaldiagramm. Dargestellt ist die Verkehrsstärke q
als Funktion der Verkehrsdichte . Die dunklen Punkte stammen aus einer
Simulation, die helleren sind Meßwerte.
Der Ansatz mit einem minimalen mikroskopischen Modell hat eine Reihe
von Vorteilen, deren wichtigster seine hohe numerische Effizienz ist.
Dennoch zeigt sich, daß zur Simulation des Autobahnnetzes der BRD
(11.000 km, 2-3 Spuren, ca. 
Fahrzeuge) in Echtzeit ein hoher
Rechenaufwand notwendig ist, der nur mit Hilfe von Parallelrechnern
erbracht werden kann. Es sind daher von uns die zwei verschiedenen
Implementationen LEGO und MICROSIM der Simulation erarbeitet
worden, die unterschiedliche Aspekte in den Vordergrund stellen:
Zum einen ist dies die Integration realer
Verkehrsdaten mit hoher Netzauflösung, zum anderen die verschiedenen
Fragestellungen einer effizienten Parallelisierung.
Damit kann das Autobahnnetz der Bundesrepublik in Echtzeit
simuliert werden. Möglicherweise ist hier aber noch nicht das gesamte
Optimierungspotential ausgeschöpft. So ist es denkbar, für
bestimmte Fragestellungen gröbere Modelle zu benutzen, bei
denen jeder Straßenabschnitt (Kante) als Warteschlange realisiert
wird, wobei die Anzahl der Fahrzeuge in der Schlange bestimmt, wie
groß die Reisezeit eines neu in die Kante einfahrenden Fahrzeuges
ist. Erste Ergebnisse zeigen, daß ein solches Modell mehr als
zwei Größenordnungen schneller ist als der zellulare Automat und
damit ein hervorragendes Werkzeug zur Untersuchung des im Abschnitt
beschriebenen Problems des dynamischen
Verkehrsgleichgewichtes darstellt.
Abbildung: Simulation des Sonnborner Dreiecks mit LEGO
Um aus dem oben beschriebenen Modell ein Werkzeug zu machen, das zur
mikroskopischen Simulation von Straßennetzwerken verwendet werden
kann, muß ein Programm aufgebaut werden, das die teilweise sehr
komplizierte Topologie des Straßennetzes abbilden kann. Grundlage
eines solchen Netzwerksimulators ist eine einzelne Kante (ein
Straßenabschnitt), die im Unterschied zum ursprünglichen Modell
mehr als nur eine Spur besitzen kann. Das bedeutet vor allem, daß
zusätzlich zu dem oben beschriebenen Regelsatz ()
ein weiterer dazukommt, der das Wechseln zwischen verschiedenen Spuren
beschreibt. Entsprechende Spurwechselregeln sind in der Literatur zu
finden und sollen hier nicht beschrieben werden.
Ein Netz entsteht aus diesen Kanten durch Zusammenstecken, wozu ein Verbindungsstück namens ,,Connection`` verwendet wird. Dieses Zusammenstecken erinnert an das Spielen mit Bausteinen und erklärt den Namen. LEGO wurde erstellt, um verschiedene Verkehrsmodelle integrieren und untersuchen zu können. So sind zur Zeit drei verschiedene Modelle implementiert, die reibungsfrei zusammenarbeiten. Beispielsweise ist es möglich, Fahrzeuge zwischen den Modellen zu transferieren. Diese Eigenschaft ist wichtig, um das Zusammenspiel von LEGO mit anderen Mikrosimulationsprogrammen, wie z.B. dem vom Institut für Kraftfahrwesen ika an der RWTH Aachen entwickelten PELOPS, zu ermöglichen. Auch eventuelle makroskopische Ansätze sollten sich ohne größere Probleme in LEGO integrieren lassen.
Connections sind relativ einfache Gebilde, solange man im
Autobahnnetz bleibt und nicht zwischen verschiedenen Modellen wechseln
muß. Das Autobahnnetz läßt sich aus Ab- und Auffahrten,
Fahrzeugquellen und -senken zusammensetzen. Meist sind reale Netze
recht kompliziert, wie das Beispiel des Sonnborner Dreiecks in
Abb. illustriert. Bereits dieser kleine Ausschnitt
enthält etwa einhundert Kanten und wurde mit Hilfe der
Straßendatenbank des Landschaftsverbandes Rheinland aufgebaut.
Die Fahrzeuge innerhalb der Simulation müssen mit Routenplänen
ausgestattet werden. Gerade diese Routenpläne machen den
wesentlichen Vorteil einer mikroskopischen Simulation aus.
Fahrzeuge werden bei der Abfahrt vom Ausgangsort mit einer genauen
Wegbeschreibung (Routenplan) ausgestattet, der von außen beliebig
vorgegeben werden kann. Gegenwärtig wird in LEGO die Möglichkeit
geschaffen, daß der Simulator selbst aus der Angabe des Zielortes und
der augenblicklichen Position seine Routenpläne generiert. Diese
Arbeiten werden in enger Zusammenarbeit mit dem Echtzeit-Optimierungsprojekt
(siehe Abschnitt ) durchgeführt und verknüpfen das hier
beschriebene Projekt mit der kombinatorischen Optimierung.
Noch komplizierter wird es, wenn der Stadtverkehr hinzukommt. Man muß Vorfahrtregelungen und Ampeln berücksichtigen, was den momentanen Stand von LEGO darstellt. Darüber hinaus werden z.Zt. Arbeiten mit dem Lehrstuhl für Verkehrswesen an der Universität Bochum durchgeführt, bei denen das Modell an realen Daten kalibriert wird.
In der Testphase befindet sich gegenwärtig ein Modul zur Schadstoffberechnung, außerdem sind zwei Schnittstellen zu anderen Modellen geplant. Zum einen ist das die Schnittstelle mit den Verfahren zur Berechnung der Verkehrsnachfrage, zum anderen die Möglichkeit, die generierten Emissionsdaten an die meteorologischen Simulatoren innerhalb des FVU weiterzureichen. Für die Berechnung dieser Daten ist ein sogenanntes Emissionsmodul notwendig, das gegenwärtig in Zusammenarbeit mit dem ika in Form eines ,,look-up table`` erstellt wird. Darin wird einem gegebenen makroskopischen Verkehrszustand (definiert durch Verkehrsdichte, Verkehrsstärke, Durchschnittsgeschwindigkeit und Lkw-Anteil) ein Satz von Emissionen zugeordnet, der die Bestimmung der vom Straßenverkehr generierten Emissionen für das gesamte simulierte Straßennetzwerk ermöglicht.
Abbildung: Das Autobahnnetz der BRD verteilt auf 16 Prozessoren
Wie im vorangehenden Abschnitt beschrieben, werden für die Simulation realistischer Straßennetze (z.B. des Autobahnnetzes der Bundesrepublik) hohe Rechenleistungen benötigt. Die Beschleunigung der Arbeitsgeschwindigkeit von Prozessoren (CPUs) verläuft jedoch zunehmend schleppend, da die Miniaturisierung von Halbleiterelementen an physikalische Grenzen stößt. Deshalb bestehen moderne Höchstleistungsrechner aus teilweise Hunderten von Prozessoren, die gleichzeitig an einer Problemstellung arbeiten und damit im Idealfall die Bearbeitungszeit auf einen entsprechenden Bruchteil reduzieren. Leider ist das Zusammenspiel der Prozessoren alles andere als trivial, sondern bedarf besonderer Programmiertechniken, die die strukturellen Gegebenheiten einer Problemstellung ausnutzen, um eine optimale Leistung zu erreichen.
In Zusammenarbeit mit der Verkehrsforschungsgruppe TRANSIMS am Los Alamos National Lab wurde in den vergangenen beiden Jahren eine Programmbibliothek (Parallele Toolbox) entwickelt, die die vereinfachte Parallelisierung von Verkehrssimulationen erlaubt. Sie basiert auf dem Prinzip des Message Passing, das die Kommunikation zwischen den Prozessoren eines parallelen Rechners regelt. Die Grundidee der Parallelisierung der Verkehrssimulation besteht in der Zerteilung des gesamten Straßennetzes in genau so viele Teilnetze, wie Prozessoren vorhanden sind. An den Schnittkanten tauschen die Prozessoren Zustandsinformationen in Form von Fahrzeugpositionen aus. Die Eigenschaften der Simulation MicroSim und der Toolbox werden in den folgenden Abschnitten näher erläutert.
Das verwendete Verkehrsmodell entspricht dem Modell von
Nagel/Schreckenberg (Glgn. ), erweitert um
Spurwechselregeln. Als Datengrundlage dient ein Straßennetz der
Firma PTV, das eine hierarchische Selektion der Straßentypen
zuläßt. Für die meisten Simulationen wird das komplette
Autobahnnetz der Bundesrepublik (siehe Abbildung )
verwendet, das stellenweise durch Bundesstraßen ergänzt ist, um
einen guten Netzzusammenhang zu garantieren. Da die in dem Modell
LEGO verwendeten Daten über die Mikrostruktur der
Autobahnknotenpunkte nicht flächendeckend für die gesamte
Bundesrepublik vorliegen, wurden modellhafte Prototypen für
Autobahndreiecke und -kreuze verwendet, die über wenige
Parameter den Leistungsmerkmalen angepaßt werden können.
Der eigentliche Ablauf der Simulation ist - wie bei LEGO - über einen Satz von Routenplänen festgelegt, der für jedes Fahrzeug Startpunkt, Route und Zielpunkt bestimmt. Während der Simulation ist ein Fortschreiben der Durchschnittsgeschwindigkeiten auf allen Straßenabschnitten möglich, die als Basis für Routing-Algorithmen dienen können.
Bei der Implementation einer parallelen Anwendung muß die gleichmäßige Verteilung der Teilprobleme auf die einzelnen Prozessoren besonders beachtet werden, denn nur bei vollkommen gleicher Belastung ist eine optimale Nutzung des Rechners möglich. Dieser Prozeß wird Lastausgleich genannt. Falls sich die benötigte Rechenleistung der Teilprobleme während der Simulation ändert, ist sogar ein dynamischer Lastausgleich vonnöten.
Im konkreten Beispiel der Verkehrssimulation, bei der die Teilprobleme Teilnetzen (z.B. Großräumen) entsprechen, entstehen die Lastunterschiede hauptsächlich durch folgende zwei Faktoren:
Die oben beschriebene Toolbox verwendet einen lokalen Ansatz zur Lastumverteilung, bei dem jeder Prozessor seine Last mit den Lasten seiner Nachbarn vergleicht, und bei Bedarf einen Teil abgibt. Die Größe der abgegebenen Last ist proportional zur Differenz der Lasten, was gewisse Analogien zu Diffusionsprozessen aufweist.
Zusätzlich zur Lastverteilung, bei der die Anzahl der Prozessoren konstant bleibt, ist es durch die Toolbox möglich, dynamisch Prozessoren dem Rechnerverband hinzuzufügen oder aus ihm zu entfernen. Dies ist besonders bei Workstation-Clustern vorteilhaft, da diese Maschinen von Zeit zu Zeit zu Wartungszwecken gestoppt werden müssen.
Mit Hilfe der beschriebenen Toolbox und mit dem zellularen Automaten als Simulationsmodell war es uns möglich, erstmals das gesamte deutsche Autobahnnetz mit Routenplänen in Echtzeit zu simulieren. Wir verwendeten dafür zwei unterschiedliche Rechnerarchitekturen. Im ersten Fall handelte es sich um eine SGI Power Challenger mit 16 Prozessoren. Zwar hat dieser Rechner eine Shared-Memory-Architektur, die der Toolbox zugrundeliegende Kommunikationsbibliothek PVM ermöglicht jedoch deren Benutzung mit Message Passing. Im zweiten Fall verwendeten wir ein aus 12 Sun Workstations des Typs SPARC 5 oder Rechnern vergleichbarer Leistung bestehendes Cluster, die über konventionelles Ethernet verbunden waren. Besonders diese Konfiguration zeigt die hohe Leistungsfähigkeit unseres Ansatzes, da solche Hardware heutzutage fast in jedem Institut verhanden ist.
Abbildung: Erzielbare Echtzeitfaktoren
(Real-Time Ratio) für das gesamte Autobahnnetz (BRD) und das Teilnetz von
Nordrhein-Westfalen (NRW) auf der SGI Power Challenge und einem
Workstationcluster. Die maximale Geschwindigkeit wird nach
anfänglichem Lastausgleich ca. bei Zeitschritt 200 erreicht.
Wir bemühen uns derzeit, die Simulation auf Rechner mit einer anderen Kommunikationstopologie zu portieren. Dazu gehören zum Beispiel Parallelrechner, deren Prozessoren über ein zweidimensionales Gitter verknüpft sind. Im Gegensatz zu den bisher verwendeten Bus-Architekturen ist nach unseren Überlegungen zu erwarten, daß die Simulation dort noch mit bis zu 500 Prozessoren effizient abläuft, was einen Echtzeitfaktor von 30 für das Autobahnnetz von Deutschland ermöglichen würde. Diese extrem hohe Geschwindigkeit könnte zum Beispiel Verkehrsprognosen dienen, bei denen die Entwicklung des Verkehrsaufkommens der nächsten Stunde innerhalb von zwei Minuten hochgerechnet werden könnte.
