next up previous contents
Next: On-line-Routing von Fahrzeugen unter Up: Forschungsschwerpunkt Verkehr Previous: Forschungsverbund Verkehrssimulation und Umweltwirkungen

 

Mikrosimulation von Verkehr

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:


 equation489

Hier sind x(t) und v(t) der Ort bzw. die Geschwindigkeit eines Fahrzeuges zur Zeit t, gap(t) der Abstand zum Fahrzeug davor, tex2html_wrap_inline3962 die Größe des Rauschterms (das Modell ist stochastisch), tex2html_wrap_inline3962 die maximale Beschleunigung und rand() eine Zufallszahl im Intervall [0,1]. Die Regeln sind Karikaturen dreier Einflußgrößen, die das menschliche Fahrverhalten bestimmen:

(1)
So schnell wie möglich zum Ziel zu gelangen,
(2)
nicht mit anderen Fahrzeugen zusammenzustoßen,
(3)
Ungenauigkeit beim Fahren (Menschen können Geschwindigkeiten und Abstände schlecht einschätzen).

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 ( gif) hingegen ist relativ leicht zu kalibrieren und ergibt trotz seiner einfachen Regeln eine erstaunlich realistische makroskopische Beschreibung, wie an Abbildung gif 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.

  figure504
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. figure504  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 gif beschriebenen Problems des dynamischen Verkehrsgleichgewichtes darstellt.

LEGO

  figure514
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 (gif) 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. gif 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 gif) 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.

Der parallele Mikrosimulator MicroSim

  figure540
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.

Mikrosimulation

Das verwendete Verkehrsmodell entspricht dem Modell von Nagel/Schreckenberg (Glgn. gif), 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 gif) 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.

Dynamischer Lastausgleich

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.

Derzeitige Leistungsfähigkeit

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.

  figure561
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.


next up previous contents
Next: On-line-Routing von Fahrzeugen unter Up: Forschungsschwerpunkt Verkehr Previous: Forschungsverbund Verkehrssimulation und Umweltwirkungen

Webmaster <www@zpr.uni-koeln.de>, 7. Apr. 1997