Kurzfassung

Die zunehmende Komplexität moderner agentenbasierter Modelle für die Verkehrsnachfrage stellt Herausforderungen in Bezug auf den erforderlichen Speicherplatz und die Rechenzeit dar. Die Verbesserung der Effizienz und Skalierbarkeit dieser Simulationen ist von entscheidender Bedeutung, um statistisch zuverlässige Prognosen für umfassende Studien über Verkehrssysteme und die Auswirkungen von Strategien und Maßnahmen zu erstellen. Moderne Ansätze aus der Parallelverarbeitung wurden bereits in anderen agentenbasierten Modellen angewandt, um Agentenentscheidungen simultan auszuwerten und damit die Rechenzeit zu reduzieren.

In diesem Beitrag stellen wir zwei Ansätze vor, um die Effizienz von agentenbasierten Verkehrsnachfragemodellen durch Parallelisierung zu erhöhen. Als Fallstudie verwenden wir die Abhängigkeit von gemeinsam genutzten Fahrzeugen im Haushalt und die damit verbundene Verkehrsmittelwahl. Der erste Ansatz beinhaltet Strategien zur Synchronisierung der Agenten, wie z. B. die Gruppierung der Agenten nach Haushalten und Mutex-Sperren für die Fahrzeugzuweisung in den Haushalten. In einem zweiten Ansatz wird das Modell vereinfacht, um die Abhängigkeiten zwischen den Agenten zu reduzieren, sodass zuvor abhängige Agenten parallel berechnet werden können.

Die Ergebnisse zeigen eine deutliche Reduktion der Rechenzeit bis zu einem Beschleunigungsfaktor von 24,5 bei der Verwendung von 32 Kernen.

Der Fachvortrag zur Veranstaltung ist im Volltext verfügbar. Das PDF enthält alle Bilder und Formeln.

1 Einleitung

Verkehrsnachfragemodelle sind ein bewährtes Instrument zur Vorhersage der Auswirkungen von verkehrspolitischen und -planerischen Maßnahmen. Ein Forschungsschwerpunkt sind agentenbasierte Verkehrsnachfragemodelle (agent-based travel demand models, ABTDM), die das Mobilitätsverhalten auf der Ebene einzelner Personen (Agenten) modellieren und somit einen höheren Detaillierungsgrad als herkömmliche aggregierte Modelle ermöglichen [1]. Da ABTDMs typischerweise stochastische Modelle anwenden, um das Mobilitätsverhalten zu replizieren, sind oft mehrere Simulationsläufe notwendig, um statistisch signifikante Ergebnisse zu erzielen. Insbesondere in Anbetracht des Aufkommens neuer Mobilitätsdienste wie Bikesharing, Carsharing und Ridepooling mit relativ kleinen Nutzendengruppen erfordert deren begrenzte Stichprobengröße wiederholte Simulationen. Dies gilt auch für die Betrachtung von kleineren sozialen Gruppen, wie Personen mit eingeschränkter Mobilität.

Kwak et al. [2] betonen die Wichtigkeit der Berechnung mehrerer Durchläufe und raten davon ab, nur eine Stichprobe der Grundgesamtheit zu simulieren, da dies den Simulationsfehler erheblich erhöht. Die Forderung nach mehreren Simulationsläufen stellt jedoch eine Herausforderung in Bezug auf die Rechenzeit bzw. den verfügbaren Arbeitsspeicher dar.

In den letzten Jahren hat sich die Entwicklung von Prozessoren von einer Erhöhung der Taktrate auf die parallele Verwendung von mehreren Prozessoren verlagert. Bei diesem Ansatz werden Probleme in Teilaufgaben unterteilt, die gleichzeitig auf mehreren parallelen Kernen berechnet werden. Paralleles Rechnen bietet dadurch das Potential, die Rechenzeit erheblich zu verkürzen.

Die praktische Anwendung von ABTDMs ist derzeit meist auf Forschungsanwendungen beschränkt [3]. Die Verkürzung der Rechenzeiten durch Parallelisierung könnte diese Modelle in der Praxis besser nutzbar machen. Der hohe Detailgrad in ABTDMs führt jedoch zu Abhängigkeiten und Interaktionen zwischen Agenten, wie z. B. die gemeinsame Nutzung von Fahrzeugen in einem Haushalt oder die Buchung von Mitfahrgelegenheiten oder Carsharing-Diensten. Dies erschwert die Definition von Teilaufgaben, die unabhängig voneinander parallel gerechnet werden können. Um eine parallele Berechnung unabhängiger Aufgaben zu erreichen, kann das Modell vereinfacht werden, indem die Abhängigkeiten zwischen den Agenten verringert werden.

Im Rahmen der Parallelverarbeitung sind verschiedene Techniken wie Message Passing oder Shared Memory entwickelt worden und haben sich inzwischen etabliert [4]. Diese Techniken können eingesetzt werden, um die parallele Ausführung von Aufgaben zu koordinieren, wenn Abhängigkeiten zwischen den Agenten bestehen.

In diesem Beitrag wird versucht, ein agentenbasiertes Verkehrsnachfragemodell durch Parallelisierung zu beschleunigen. Dabei werden zwei Ansätze miteinander verglichen: Modellvereinfachung und Agentensynchronisation. Der Fokus liegt dabei auf der Betrachtung von Abhängigkeiten zwischen den Agenten bei der Verkehrsmittelwahl. Genauer gesagt wird die gemeinsame Nutzung im Haushalt geteilter Fahrzeugen analysiert.

Die Verfügbarkeit von individuell genutzten Fahrzeugen wie Pkw kann sowohl auf Haushaltsebene [5, 6, 7] als auch auf individueller Ebene [8, 9, 10, 11, 12] modelliert werden. Da beide Ansätze gute Ergebnisse liefern, werden die Auswirkungen einer Vereinfachung des zugrundeliegenden Modells untersucht, indem die Fahrzeugverfügbarkeit von der Haushaltsebene auf die Personenebene geführt wird. Mit diesem vereinfachten Modell können die Entscheidungen der Agenten parallel berechnet werden.

Des Weiteren werden die Synchronisierung durch Agentengruppierung und gegenseitigen Ausschluss analysiert, wie sie in anderen Forschungsbereichen verwendet werden. Zudem werden verschiedene Synchronisierungsstrategien für gemeinsam genutzte Fahrzeuge vorgeschlagen.

2 Literaturübersicht

Um die hohen Rechenzeiten in agentenbasierten Modellen zu reduzieren, werden in der Literatur verschiedene Strategien diskutiert. Nach Kwak et al. [2] besteht ein gängiger Ansatz darin, nur einen Teil der synthetisch erzeugten Bevölkerung zu simulieren. Betrachtet man jedoch das Ergebnis, so führen selbst vollständig simulierte Bevölkerungen zu hohen Fehlerquoten, die mehrere Simulationsläufe erfordern. Daher wird die Verwendung einer Stichprobe, d.h. die Simulation von weniger als 100 % der Bevölkerung, nicht empfohlen. Ein weiterer Ansatz zur Beschleunigung der Simulation besteht darin, die Anzahl möglicher Ziele für eine Aktivität zu reduzieren. Saleem et al. [13] stellen fest, dass die Berechnungszeit quadratisch mit der Anzahl der möglichen Ziele wächst. Die Abweichung des resultierenden Modal Split und der Reisezeit liegt im reduzierten Fall unter 2 %.

Beide Konzepte konzentrieren sich jedoch ausschließlich auf die Modellvereinfachung und vernachlässigen Ansätze aus dem Bereich der Parallelverarbeitung. Dies wurde von Zhou et al. [14] untersucht, sie evaluieren das Potenzial der parallelen Berechnung der Hauptaktivität von Haushaltsmitgliedern unter Verwendung eines Grafikprozessors (GPU). Um die Interaktion innerhalb des Haushalts zu berücksichtigen, werden die Agenten eines Haushalts sortiert und anschließend gemeinsam berechnet. Diese Anwendung der GPU-basierten Parallelisierung ermöglicht einen großen Geschwindigkeitszuwachs, hängt aber stark von der Anzahl der Haushalte und der einbezogenen Alternativen ab. Shook et al. [15] und Gong et al. [16] untersuchen die Parallelisierung von agentenbasierten Modellen für geografische Systeme. Beide verwenden räumliche Partitionierung und Synchronisation von Agenten an den Rändern der Partitionen. Tang et al. [17] simulieren mit einem parallelen Diffusionsmodell die Entwicklung der Meinung benachbarter Agenten bezüglich zukünftiger Landnutzung. Neben Partitionierung und Message-Passing wenden sie auch eine zeitliche Synchronisation zwischen Iterationsschritten an, sodass sich die Agenten simultan zeitgebunden bewegen.

Dobler [18] entwickelt eine parallelisierte Umlegung für MATSim durch die gleichzeitige Simulation von Fahrzeugwarteschlangen auf Knoten oder Verbindungen. Sie synchronisieren auch zwischen Zeitschritten und zwischen Aktualisierungen von Knoten und Kanten, um Fahrzeuge in ihre neuen Warteschlangen zu verschieben.

Im Bereich der Verkehrsnachfragemodellierung standen in den letzten Jahren agentenbasierte Modelle im Mittelpunkt der Forschung. Sie können das Mobilitätsverhalten einzelner Agenten und die Auswirkungen von Richtlinien und Maßnahmen auf dieses Verhalten und damit auf die resultierende Verkehrsnachfrage modellieren. Durch die Modellierung einer Bevölkerung als einzelne Agenten bieten diese Modelle die Möglichkeit, Interaktionen und Abhängigkeiten zwischen einzelnen Agenten zu modellieren.

Eine solche Abhängigkeit zwischen Agenten, welche die Parallelisierung des Modells erschwert, ist die gemeinsame Nutzung von Pkw in einem Haushalt. Da Pkw-Besitz und -Verfügbarkeit in diversen Modellen unterschiedlich modelliert werden, folgt hier ein Überblick über die verschiedenen Ansätze. Der Pkw-Besitz einer Person oder eines Haushalts wird meist aus Umfragen abgeleitet und als diskrete Entscheidung modelliert. Der Pkw-Besitz allein sagt jedoch nichts darüber aus, ob der Pkw von einem Agenten (zu einem bestimmten Zeitpunkt) genutzt werden kann. Dies wird im Folgenden als Pkw-Verfügbarkeit bezeichnet.

Einen Überblick über verschiedene Modelle des Pkw-Besitzes geben beispielsweise Barthel- mes et al. [19], sowie de Jong et al. [20] oder Anowar et al. [21]. Im Allgemeinen haben sich die Modelle mit zunehmender Rechenleistung und Datenverfügbarkeit von aggregierten zu disaggregierten und mikroskopischen Modellen entwickelt [19, 11].

Eine explizite Modellierung der Pkw-Verfügbarkeit ermöglicht es Interaktionen innerhalb eines Haushalts sowie unterschiedliche Grade der gemeinsamen Nutzung von Fahrzeugen zu berücksichtigen [7]. Im ABTDM mobiTopp wird die Pkw-Verfügbarkeit auf Haushaltsebene modelliert und berücksichtigt somit die Interaktion zwischen den Agenten eines Haushalts [5]. Ein ähnlicher Ansatz wird auch von Vovsha et al. [6] verwendet.

Allerdings tun dies nicht alle Modelle zur Pkw-Verfügbarkeit. In MATSim sind Haushalte optional, was dazu führt, dass die Verfügbarkeit auf einzelne Agenten beschränkt ist [8, 9]. Danalet und Mathys [10] modelliert die Pkw-Verfügbarkeit ebenfalls auf individueller Ebene und unterscheidet zwischen einem Pkw, der immer, nach Absprache oder nie verfügbar ist. Sowohl Loder und Axhausen [11] als auch Hillel et al. [7] verwenden eine binäre Unterscheidung von immer oder nie verfügbar, wobei die Gesamtzahl der im Haushalt verfügbaren Pkw dennoch korrekt modelliert wird Hillel et al. [7]. Nach Kowald et al. [12] kann die Pkw-Verfügbarkeit eines Agenten auch als das Verhältnis von Pkw zu Agenten mit einem Führerschein innerhalb eines Haushalts größer oder gleich 0,5 definiert werden.

Soweit den Autoren bekannt ist, wurde Parallelisierung noch nicht auf ABTDMs mit Abhängigkeiten bei der Verkehrsmittelwahl angewendet. Die Literaturrecherche zeigt, dass paralleles Rechnen im Bereich ABTDM für die Modellierung der Hauptaktivitäten von Haushalten [14] und die Umlegung [18] angewendet wurde. In beiden Fällen können Agenten so gruppiert werden, dass die resultierenden parallelen Berechnungen unabhängig sind. Daher werden im Folgenden auch Strategien für die Synchronisierung von Agenten untersucht, wenn keine unabhängigen Gruppen definiert werden können.

3 Ansatz

In dieser Arbeit wird eine vereinfachte Version des mobiTopp-Frameworks [5, 22, 23] für agentenbasierten Verkehrsnachfragemodelle angewendet, wobei sich auf relevante Kernaspekte für die Bewertung der Parallelisierung konzentriert wird.

In der Simulation werden die Aktivitäten und die dazwischen liegenden Wege aller Agenten simuliert, einschließlich der Wahl des Ziels und des Verkehrsmittels. Ziel- und Verkehrsmittelwahl werden mit Hilfe von Discrete-Choice-Modellen bestimmt. Für diese Arbeit werden multinomiale Logit-Modelle verwendet, wie im Abschnitt Modellvereinfachung beschrieben. Die Simulation basiert auf Verkehrszellen. Die Verkehrsnachfrage wird ohne Umlegung berechnet. Für diese Arbeit werden folgende Verkehrsmittel beachtet: zu Fuß (foot), Fahrrad (bike), Öffentlicher Verkehr (public transport), Pkw als Fahrer:in (car) und Pkw als Mitfahrer:in (passenger).

In jeder Entscheidungssituation wird die Menge dieser Alternativen auf folgende Weise gefiltert, so dass sie nur die verfügbaren Verkehrsmittel enthält: Agenten ohne Führerschein oder ohne eigenes Fahrrad können niemals car bzw. bike benutzen. Außerdem ist car bei der Abfahrt von zu Hause nur verfügbar, wenn mindestens ein Haushalts-Pkw zu Hause ist. Nach der Bestimmung ihrer Verfügbarkeit wird der Nutzen jedes infrage kommenden Verkehrsmittels berechnet und die Wahl durch Auswertung eines multinomialen Logit-Modells bestimmt. Wenn schließlich der Modus car gewählt wurde, nimmt der Agent einen Haushalts-Pkw. Dieses allgemeine Verfahren ist in Abbildung 1 dargestellt.

In den folgenden Abbildungen 1 bis 6 wird angenommen, dass die beispielhafte Verkehrsmittelwahl der gezeigten Agenten zu car ausgewertet wird; außerdem wird angenommen, dass die (initiale) Prüfung der Pkw-Verfügbarkeit positiv ist. In diesen Abbildungen bezeichnet T die Menge der Simulationsschritte, die in chronologischer Reihenfolge iteriert werden, und P die Menge aller Agenten. t_i ∈ T ist ein einzelner Zeitschritt, der eine Menge von Agenten (entweder Personen p oder Haushalte h) enthält. Eine beispielhafte Person i eines Haushalts j wird mit p^hj_i bezeichnet.

Es werden zwei Ansätze untersucht, um eine parallele Nachfragesimulation zu erreichen: Erstens werden mehrere Strategien für die Synchronisierung von Agenten entwickelt, um Abhängigkeiten zwischen Agenten während der parallelen Berechnung zu behandeln. Zweitens wird eine Modellvereinfachung verwendet, um diese Abhängigkeiten zu beseitigen, indem die Fahrzeugverfügbarkeit auf der Ebene von Personen statt auf der Ebene von Haushalten modelliert wird.

3.1 Agentensynchronisation

Diese Arbeit befasst sich damit, die Verkehrsnachfrage einer Bevölkerung innerhalb eines Untersuchungsgebiets zu bestimmen. In diesem Abschnitt werden die Synchronisationsstrategien für die Wahl des Verkehrsmittels vorgestellt und deren Übertragbarkeit auf andere Arten von Abhängigkeiten diskutiert. Im Abschnitt Auswertung wird die Übertragbarkeit beispielhaft für Carsharing-Abhängigkeiten untersucht.

Trotz der Aufteilung der Verkehrsnachfragesimulation in die Berechnung individueller Entscheidungen sind diese Aufgaben immer noch voneinander abhängig, da Mitglieder desselben Haushalts sich Haushaltsfahrzeuge teilen und bei paralleler Berechnung dasselbe Fahrzeug doppelt ´buchen´ könnten. Dieser kritische Codeabschnitt des Entscheidungsprozesses ist in Abbildung 1 hervorgehoben.

Abbildung 1: Eine sequentielle Ausführung der Verkehrsmittelwahl. Der kritische Codeabschnitt (rot markiert) kann bei paralleler Ausführung ohne ordnungsgemäße Synchronisierung zu Koflikten führen.

Außerdem können zwei Entscheidungen von zwei Agenten p^h₁ und p^h₂ im selben Haushalt von einander abhängig sein, auch wenn sie zu unterschiedlichen Zeiten stattfinden. Daher müssen alle Agenten synchron im Zeitverlauf simuliert werden. In unserer Simulation wird ein diskreter Zeitschritt von einer Minute verwendet. Innerhalb jedes Zeitschritts können alle Entscheidungen parallel berechnet werden. Der nächste Zeitschritt kann jedoch erst gestartet werden, wenn alle Entscheidungen des aktuellen Zeitschritts getroffen wurden. Es wird eine Synchronisationsbarriere verwendet, die wartet, bis alle Kerne ihre Aufgaben beendet haben, bevor die Aufgaben des nächsten Zeitschritts abgearbeitet werden. Im Folgenden wird auf die Parallelisierung von Aufgaben (d. h. Verkehrsmittelwahl) innerhalb eines einzelnen Zeitschritts eingegangen.

Ein erster intuitiver Ansatz, die so genannte Agentengruppierung [24], besteht darin, voneinander abhängige Agenten zu identifizieren und sie so zu gruppieren, dass keine zwei Gruppen voneinander abhängige Agenten enthalten. Bei der Abhängigkeit von einem gemeinsamen Haushalt ist die Agentengruppierung trivial, da jeder Agent zu genau einem Haushalt gehört. Somit ist es möglich, die Haushalte den Kernen zuzuordnen. Innerhalb jedes Haushalts werden die Entscheidungen der Agenten sequentiell berechnet, während unabhängige Haushalte parallel verarbeitet werden, wie in Abbildung 2 dargestellt. Auf diese Weise kann kein Fahrzeug von zwei Agenten gleichzeitig zugewiesen werden, so dass keine Synchronisierung erforderlich ist.

Abbildung 2: Haushaltsgruppierung: Haushalte werden parallel verarbeitet, während ihre Mitglieder nacheinander auf demselben Kern verarbeitet werden.

Die Gruppierung nach Haushalt ergibt relativ kleine Gruppen: Laut United Nations [25] machen Haushalte mit 6 oder mehr Mitgliedern in den meisten Ländern nur einen geringen Anteil aus. So hatten beispielsweise 2010 über 90 % der Haushalte in den USA fünf oder weniger Mitglieder.

Diese Technik lässt sich jedoch kaum auf gemeinsam genutzte Fahrzeuge oder Abhängigkeiten von Agenten im Allgemeinen übertragen. Bei der Untersuchung von Carsharing sind beispielsweise alle Agenten, die aus derselben Zone abreisen, voneinander abhängig, da sie alle dasselbe Carsharing-Fahrzeug anfordern könnten. Die Gruppierung von Agenten nach Abfahrtszone kann zu beliebig großen Gruppen führen, insbesondere wenn es mehrere Carsharing-Anbieter und Agenten mit mehr als einer Mitgliedschaft gibt. Dies schmälert jedoch das Potenzial der Parallelisierung, da große Mengen abhängiger Agenten sequentiell verarbeitet werden müssen.

Wenn die Abhängigkeitsstrukturen zwischen den Agenten zu komplex werden, um unabhängige Gruppen zu berechnen, oder wenn die abhängigen Gruppen zu groß werden, sodass der Parallelisierungseffekt verschwindet, wird die Agentengruppierung ungeeignet. Alternativ können Parallelisierungsstrategien mit voneinander abhängigen Aufgaben untersucht werden, die eine Synchronisierung der Agenten erfordern. Dies wird im Folgenden exemplarisch für die Abhängigkeit von gemeinsam genutzten Hauhaltsfahrzeugen beschrieben und erläutert, wobei die Techniken so konzipiert sind, dass sie auch auf andere Abhängigkeiten zwischen Agenten anwendbar sind, wie z. B. Ridepooling und Car-Sharing-Dienste (dies wird in Abschnitt Auswertung untersucht). Bei der Berechnung voneinander abhängiger Aufgaben auf mehreren Kernen sind in der Praxis zwei Strategien üblich: Message Passing und Shared Memory. In dieser Arbeit wird die Synchronisierung über Shared Memory verwendet, da sie keine zusätzliche Kommunikationskosten zur Aufrechterhaltung der Simulationskonsistenz erfordert.

Im Kontext dieser Arbeit ist der gemeinsame Speicher, auf den die voneinander abhängigen parallelen Aufgaben zugreifen, eine Liste der verfügbaren gemeinsamen Haushaltsfahrzeuge. Sobald ein Agent (der von zu Hause losfährt) entscheidet, welches Verkehrsmittel er benutzen möchte, wird die Verfügbarkeit eines Haushaltsfahrzeugs geprüft. Falls vorhanden, wird der Nutzen für die Nutzung des Pkw zusammen mit dem Nutzen aller anderen verfügbaren Verkehrsmittel berechnet. Mit Hilfe eines Logit-Modells wird eine der verfügbaren Verkehrsarten ausgewählt. Wenn die gewählte Verkehrsart car ist, wird dem Agenten eines der Haushalts-Pkw zugewiesen.

Wenn nicht sorgfältig vorgegangen wird, können zwei parallel abgehandelte Agenten das das selbe Fahrzeug reservieren und die Simulation in einen inkonsistenten Zustand versetzen. Dieser kritische Codeabschnitt ist in Abbildung 3 gelb markiert.

Um diese Art von Wettlaufsituation zu vermeiden, können sogenannte „Mutual Exclusive Locks“ (Mutex-Sperren) eingesetzt werden, um den kritischen gemeinsamen Speicher vor parallelem Zugriff zu schützen. Wenn ein Task (parallele Berechnungsaufgabe auf einem der Kerne) versucht, eine freie Mutex-Sperre zu akquirieren, wird er zum alleinigen Eigentümer der Sperre. Andere Tasks können die Sperre nicht mehr akquirieren, bis sie freigegeben wird. Wenn eine Mutex-Sperre bereits im Besitz eines anderen Tasks ist, muss der anfordernde Task warten, bis die Sperre freigegeben wird.

In einem ersten Versuch wird eine Mutex-Sperre auf diesen kritischen Codeabschnitt angewendet. Da nicht alle Agenten voneinander abhängig sind, kann für jeden Haushalt eine eigene Sperre eingerichtet werden. Auf diese Weise kann nur ein Agent pro Haushalt diesen synchronisierten, kritischen Codeabschnitt betreten und seine Moduswahl durchführen, wie in Abbildung 3 gezeigt. Diese umfassende Synchronisierung repliziert jedoch das Verhalten der oben beschriebenen Agentengruppierung: Alle voneinander abhängigen Agenten werden nacheinander berechnet, da sie sich durch ihre Mutex-Sperre gegenseitig blockieren.

Abbildung 3: Parallele Personen: alle Bearbeiter werden parallel bearbeitet, nur ein Mitglied pro Haushalt darf den gesperrten kritischen Codebereich betreten..

Um eine stärkere Parallelisierung zu erreichen, sollte die teure Berechnung der Nutzenfunktionen und die Auswertung der Logitfunktion außerhalb des synchronisierten Codeabschnitts verschoben werden, damit sie unabhängig parallel berechnet werden kann. Nur die eigentliche ‘Fahrzeugbuchung‘ ist kritisch, da sie den gemeinsamen Speicher verändert. Für das Modell der Verkehrsmittelwahl ist es jedoch erforderlich, die Verfügbarkeit von gemeinsam genutzten Haushaltsfahrzeugen zu bewerten. Durch die Auslagerung der Nutzenberechnung und der Verfügbarkeitsprüfung aus dem synchronisierten Codeabschnitt kann nicht mehr davon ausgegangen werden, dass die zuvor ermittelte Fahrzeugverfügbarkeit korrekt ist. Daher muss die Verfügbarkeit innerhalb des synchronisierten Codeabschnitts erneut geprüft werden, bevor das Fahrzeug tatsächlich zugewiesen wird. Wenn das Fahrzeug nicht mehr verfügbar ist, weil es in der Zwischenzeit besetzt wurde, muss die Verkehrsmittelwahl erneut ohne die Alternative car ausgewertet werden. Auf diese Weise kann die erste Verfügbarkeitsprüfung ohne Sperrung als Verfügbarkeitsabschätzung verwendet werden. Unter der Annahme, dass solche Konflikte nur selten auftreten, sollten die Kosten für die Neuberechnung einiger Verkehrsmittelwahlen durch den Vorteil der parallelen Berechnung aller anderen Wahlmöglichkeiten aufgewogen werden. Dieser Ansatz wird in Abbildung 4 veranschaulicht.

Abbildung 4: Parallele Präferenz: alle Agenten werden parallel verarbeitet. Ein bevorzugter Modus wird parallel berechnet, lediglich die tatsächliche Fahrzeugzuweisung wird synchronisiert. Wenn bei der Buchung kein Pkw (Auto) verfügbar ist, wird die Wahl des Modus neu bewertet.

3.2 Modellvereinfachung

Ein zweiter Ansatz ist die Modellvereinfachung, um die Abhängigkeiten zwischen den Agenten zu reduzieren. Durch die Beseitigung dieser Abhängigkeiten müssen Agenten-Agenten-Interaktionen nicht nachträglich aufgelöst werden, sondern können ganz vermieden werden. Dies ermöglicht es, die Entscheidungen der nun unabhängige Agenten parallel auf verschiedenen Kernen zu berechnen.

Derzeit wird die Verfügbarkeit von Pkw in mobiTopp auf der Haushaltsebene modelliert [5]. Die Anzahl der Pkw in einem Haushalt wird mit einem Logit-Modell bestimmt, das mit einer repräsentativen Stichprobe aus einer großen nationalen Haushaltsbefragung kalibriert wird [26]. Wenn Agenten während der Simulation mit einem Pkw von zu Hause wegfahren, wird es für andere Haushaltsmitglieder unzugänglich gemacht, bis der Agent nach Hause zurückkehrt. Auf diese Weise wird die Fahrzeugverfügbarkeit modelliert und mit jedem abreisenden und ankommenden Haushaltsmitglied dynamisch aktualisiert.

Im Rahmen der Modellvereinfachung wird auf die genaue Erfassung der verfügbaren Pkw verzichtet. In der Simulation nehmen die Agenten jedoch keine Fahrzeugzuweisung mehr vor. Das bedeutet, dass die Agenten bei der Verkehrsmittelwahl immer noch den Modus car auswählen können, aber die Haushalts-Pkw werden nie bewegt, so dass sie nicht synchronisiert werden müssen, wie in Abbildung 5 gezeigt. Anstatt eine detaillierte Fahrzeugzuweisung zu modellieren, wird ein personenspezifisches, diskretes Attribut für die Fahrzeugverfügbarkeit eingeführt. Ähnlich wie in Danalet und Mathys [10] wird in dieser Arbeit unterschieden, ob ein Pkw nie, teilweise oder immer für einen Agenten verfügbar ist. Dies wird wie folgt bestimmt:

• Wenn es in einem Haushalt keine Pkw gibt, kann ein Pkw von keinem Agenten dieses Haushalts genutzt werden und ist daher nie verfügbar.
• Gibt es in einem Haushalt mindestens so viele Pkw wie Agenten mit Führerschein, ist das Auto immer für alle diese Agenten verfügbar.
• Gibt es in einem Haushalt mehr Personen mit einem Führerschein als Pkw, so ist der Pkw für alle Personen in diesem Haushalt nur teilweise verfügbar. Daher ist das hier gewählte Vorgehen restriktiver als das von Kowald et al. [12] in Abschnitt 2 beschriebene.

Diese Anpassung allein würde zu einer erheblichen Überschätzung der Pkw-Nutzung als Fahrer und Beifahrer im Verkehrsmittelwahlmodell führen. Daher wurde das multinomiale Logit-Modell für die Verkehrsmittelwahl angepasst und rekalibriert, um die ursprüngliche Verkehrsmittelaufteilung zu reproduzieren. So wurden neue Parameter für die Modi car und car as passenger integriert, um die teilweise Verfügbarkeit zu berücksichtigen. Da die Auswirkungen der angepassten Pkw-Verfügbarkeit auf die anderen Verkehrsträger des Modells marginal sind, mussten keine weiteren Änderungen vorgenommen werden. Dieser Ansatz ermöglicht die Anpassung bestehender Modelle für parallele Berechnungen, ohne dass ein völlig neues Verkehrsmittelwahlmodell entwickelt werden muss. Außerdem lassen sich so die Ergebnisse besser mit dem Basismodell vergleichen, da nur geringfügige Änderungen vorgenommen wurden.

Abbildung 5: Parallele Personen: keine Abhängigkeiten und keine Mutex-Sperren aufgrund der Modellvereinfachung.

Der Hauptvorteil der Modellvereinfachung besteht darin, dass sie eine andere Parallelisierungsstrategie ermöglicht. Bei Abhängigkeiten zwischen den Agenten muss die Simulation in vorgegebenen Zeitschritten synchronisiert werden, um einen konsistenten Zustand zu gewährleisten - die Aktionen der Agenten werden entsprechend ihrer Auftrittszeit verarbeitet (S_{T imeSync}). Durch die Beseitigung von Abhängigkeiten kann jeder Agent völlig unabhängig von den Aktionen anderer Agenten simuliert werden. Bei der Strategie der vollständigen Unabhängigkeit (S_Indep) werden nicht die Zeitscheiben, sondern die Agenten verarbeitet. Abbildung 6 verdeutlicht den operativen Unterschied zu den anderen zeitsynchronisierten Algorithmen.

Abbildung 6: Völlständig unabhängige Ausführung: Der gesamte Aktivitätsplan jedes Agenten wird parallel simuliert, ohne dass eine Synchronisierung in Zeitschritten erfolgt.

4 Auswertung und Ergebnisse

Zur Evaluierung der entwickelten Modelle werden diese auf die Stadt Hamburg angewandt. Das Untersuchungsgebiet besteht aus 2715 Verkehrszellen und die simulierte Bevölkerung besteht aus 1.041.545 Haushalten und 1.871.371 Einzelpersonen. Der Simulationszeitraum wird auf einen einzigen Tag festgelegt, da dies ausreicht, um die Auswirkungen der Parallelisierung zu beobachten. Im Folgenden wird die Methodik vorgestellt, mit der die Auswirkungen der entwickelten Parallelisierungsstrategien sowohl auf die Rechenzeit als auch auf die Qualität der Simulationsergebnisse bewertet werden.

Die Rechenzeit wird sowohl für die Synchronisationsstrategien Haushaltsgruppierung (O_Hh), parallele Personen (O_Person), parallele Präferenz (O_Retry) als auch für die Modellvereinfachungsstrategien zeitsynchronisiert (S_{T imeSync}) und vollständig unabhängig (S_Indep) wie oben beschrieben bewertet. Um ihre Skalierbarkeit zu messen, wurden alle Strategien mit 4, 8, 16 und 32 Kernen simuliert. Im Folgenden wird eine Kombination aus Strategie und Kernanzahl als Konfiguration bezeichnet. Die simulierten Konfigurationen und die gemessenen Zeiten sind in der rechten Hälfte der Tabelle 1 aufgeführt. Alle Konfigurationen wurden auf einer Hochleistungs-Workstation mit der folgenden Spezifikation ausgeführt: AMD EPYC 7374 Prozessor (16 physische, 32 logische Kerne) mit 3,20 GHz Basisgeschwindigkeit (4,7 GHz effektive Geschwindigkeit) und 256 GB RAM mit 3,2 GHz.

Tabelle 1: Überblick über die bewerteten Strategien und gemessenen Zeiten über die Anzahl Kerne.

Zum Vergleich wurde eine sequential baseline-Simulation (mit und ohne Modellvereinfachung) mit einem einzigen Kern (O_Seq, S_Seq) berechnet. Die beobachtete Varianz der Berechnungszeit ist vernachlässigbar. Daher wird im Folgenden nur die mittlere Berechnungszeit jeder Konfiguration betrachtet.

Abbildung 7: Verringerung der Rechenzeit im Vergleich zur sequentiellen Ausführung bei Synchronisierung der Agenten (links) und Vereinfachung des Modells (rechts).

Abbildung 7 zeigt die Ergebnisse der Leistungsmessungen für die Konfigurationen Agentensynchronisation (links) und Modellvereinfachung (rechts) im Vergleich zur sequenziellen Ausführung. In beiden Fällen ist die Ausführungszeit auf die sequenzielle Ausführungszeit normiert. Sie zeigen, dass die Anwendung einer der Parallelisierungstechniken die Simulationszeit bei der Verwendung von 32 Kernen erheblich auf 4-5% der ursprünglichen Berechnungszeit reduziert. Die drei vorgestellten Synchronisationsstrategien O_Hh, O_Person und O_Retry unterscheiden sich nur wenig. S_Indep zeigt eine etwas höhere Reduktion der Rechenzeit im Vergleich zu S_{T imeSync}.

Abbildung 8: Vergleich der Agentensynchronisierung (O_Hh) und der Modellvereinfachung (S_Indep) anhand von Berechnungszeit (links), Beschleunigung (Mitte) und Effizienz (rechts).

Abbildung 8 vergleicht die Leistung der Strategie Haushaltsgruppierung unter Verwendung des ursprünglichen Modells (O_Hh) und der vollständig unabhängigen Ausführung des vereinfachten Modells (S_Indep). Links ist erkennbar, dass die vollständig unabhängige Ausführung eine geringfügig höhere Reduzierung der Berechnungszeit bewirkt. Sie ist zwischen 19% und 24% schneller (außer bei 8 Kernen, wo sie nur 9% schneller ist). Mittig dargestellt ist die resultierende Beschleunigung (parallele Berechnungszeit geteilt durch sequenzielle Berechnungszeit). Bei bis zu 8 Kernen ist S_Indep etwas schneller als O_Hh , aber bei 16 und 32 Kernen übertrifft es letzteres deutlich. Für 32 Kerne erreicht O_Hh einen Speedup von 18,4, während S_Indep einen Speedup von 24,5 erreicht. Rechts ist die Effizienz (Beschleunigung geteilt durch die Anzahl der Kerne) von O_Hh und S_Indep dargestellt. Haushaltsgruppierung O_Hh hat eine sehr hohe Effizienz nahe 1,0 bis zu 8 Kernen, die dann auf 0,58 für 32 Kerne abfällt. Die vollständig unabhängige Ausführung S_Indep zeigt eine bemerkenswert hohe Effizienz > 1,0, die damit die sequenzielle Basissimulation übertrifft. Dies ist möglich, weil bei vollständig unabhängiger Ausführung auf die zeitliche Synchronisierung der Agenten verzichtet wird, die bei der sequentiellen Methode verwendet wurde. Bei 32 Kernen sinkt die Effizienz von S_Indep auf 0,73.

Abbildung 9: Agenten-Synchronisationsstrategien bei künstlich verstärkten Abhängigkeiten: Rechenzeit (links), Beschleunigung (Mitte) und Effizienz (rechts).

Um die Übertragbarkeit des gewählten Ansatzes abzuschätzen und die entwickelten Synchronisationsstrategien zu differenzieren, wurden zusätzliche, künstliche Abhängigkeiten zwischen Agenten mit derselben Heimatzelle eingeführt (um z.B. eine Art künstliches Carsharing oder Ridepooling nachzubilden). Für diese künstliche, stark abhängige Population werden erneut eine sequenzielle Basissimulation (A_Seq) und die drei Strategien: Zonengruppierung (A_Zone), synchronisierte Personen (A_Person) und synchronisierte Wiederholung (A_Retry) simuliert. Die relative Rechenzeit, die Beschleunigung und die Effizienz des Experiments mit der verstärkten Abhängigkeit sind in Abbildung 9 für verschiedene Anzahlen von Rechenkernen dargestellt. Es zeigt sich, dass die Strategie synchronisierte Wiederholung (A_Retry) die beiden anderen Ansätze mit einem Beschleunigungsfaktor von 6,33 gegenüber 3,12 und 2,73 deutlich übertrifft. Durch die Verstärkung der Abhängigkeiten wird die maximal erreichbare Beschleunigung im Vergleich zu den nur haushaltsinternen Abhängigkeiten merklich reduziert.

Zusätzlich zu den Auswirkungen auf die Leistung wird die durch die Modellvereinfachung verursachte Verzerrung der Simulationsergebnisse bewertet. Zu diesem Zweck werden die Simulationsergebnisse des ursprünglichen Modells (O_Seq) mit den Ergebnissen des vereinfachten Modells (S_Seq) in Bezug auf vier Schlüsselindikatoren verglichen: Modal Split, Fahrleistung, Fahrtweitenverteilung und Fahrzeitverteilung, wie in Abbildung 10 dargestellt. Alle vier Diagramme zeigen nur geringe Unterschiede zwischen dem ursprünglichen und dem vereinfachten Modell.

Die Anwendung eines statistischen t-Tests mit einer Signifikanzschwelle von p = 0, 05 deutet darauf hin, dass es keinen signifikanten Unterschied zwischen den Simulationsergebnissen des ursprünglichen und des vereinfachten Modells hinsichtlich aller vier Schlüsselindikatoren gibt. Analog dazu zeigen auch die parallelen Ausführungen des ursprünglichen und des vereinfachten Modells keine signifikanten Unterschiede in den Simulationsergebnissen im Vergleich zu den sequenziellen Ausführungen. Diese Auswertungen sind jedoch nur ein erster Anhaltspunkt. Abhängig von der jeweiligen Fragestellung kann es sein, dass die Haushaltsabhängigkeit von Pkw wichtig ist und dadurch diese Vereinfachung ungeeignet ist.

Abbildung 10: Vergleich der Ergebnisse des ursprünglichen und des vereinfachten Modells: Modal Split (oben links), Fahrleistung (oben rechts), Fahrstrecke (unten links) und Fahrzeit (unten rechts).

5 Fazit

Die Ergebnisse zeigen, dass die Anwendung der Parallelisierung auf ein ABTDM die Rechenzeit erheblich reduziert. Mit der effizientesten Strategie der vollständig unabhängigen Ausführung konnte die Rechenzeit eines einzelnen Simulationslaufs von 25,8 auf 1,1 Stunden reduziert werden. Somit können etwa 24 parallelisierte Simulationsläufe innerhalb der ursprünglichen Simulationszeit berechnet werden.

Die in dieser Arbeit vorgestellte Wiederholungs-Strategie (O_Retry) lässt sich nicht trivial auf Nested-Logit-Modelle übertragen. Die Prüfung der Verkehrsmittelverfügbarkeit erfordert zusätzliche Sorgfalt, um eine unverzerrte Verkehrsmittelwahl zu gewährleisten, da die Alternativen in den Logit-Nests nicht unabhängig sind. Eine geschätzte Fahrzeugverfügbarkeit kann sich auf die Auswahlwahrscheinlichkeit verwandter Verkehrsmittel auswirken. Wenn die Schätzung während der Verkehrsmittelzuweisung nicht mehr gültig ist, muss die Verkehrsmittelwahl neu bewertet werden, selbst wenn ein konfliktfreies Verkehrsmittel gewählt wurde. In Zukunft könnte diese Synchronisationsstrategie erweitert werden, um auch mit Modellen kompatibel zu sein, die abhängige Alternativen enthalten.

Bei der Analyse der Abhängigkeit von gemeinsam genutzten Haushaltsfahrzeugen zeigen unsere Ergebnisse, dass alle Strategien eine ähnliche Reduzierung der Berechnungszeit aufweisen. Die Anwendung eines vereinfachten Modells, das alle Abhängigkeiten zwischen den Agenten beseitigt, macht die Berechnung jedoch etwas schneller als die anderen Strategien. Daher ist die Anwendung einer unsynchronisierten Ausführungsstrategie nur dann zu empfehlen, wenn alle Abhängigkeiten zwischen den Agenten entfernt werden können (einschließlich Abhängigkeiten, die sich über mehrere Zeitschritte erstrecken). Das vereinfachte Modell zeigt keinen Vorteil gegenüber den Synchronisationsstrategien, wenn die Zeitsynchronisation nicht entfernt wird.

Es ist zu beachten, dass sich die Parallelisierung nachteilig auf die Reproduzierbarkeit auswirkt, da die Reihenfolge der Wahlentscheidungen zufällig schwankt. Zwischen zwei Simulationsläufen mit identischen Eingabedaten konnten keine signifikanten Unterschiede festgestellt werden. Dies sollte jedoch in zukünftigen Forschungsarbeiten untersucht werden, insbesondere bei der Untersuchung von Szenarien mit umfangreichen Abhängigkeiten zwischen den Agenten.

Schließlich wird die Übertragbarkeit der vorgestellten Synchronisationsstrategien eingeschätzt, indem die Anzahl der Abhängigkeiten zwischen den Agenten künstlich erhöht wird. Die Ergebnisse zeigen, dass der höchste Geschwindigkeitszuwachs erzielt wird, wenn die vorläufigen Verkehrsmittel parallel berechnet werden und nur die tatsächliche Fahrzeugzuweisung synchronisiert wird (wobei die Wahl des Verkehrsmittels möglicherweise neu bewertet werden muss). Es wird erwartet, dass Zuweisungskonflikte und damit eine Neubewertung der Verkehrsmittelwahl selten genug auftreten, sodass der Nutzen der parallelen Berechnung der Verkehrsmittelpräferenzen die Kosten der Neubewertung überwiegt. Diese vielversprechenden Ergebnisse deuten darauf hin, dass diese Strategien auch für Abhängigkeiten zwischen Agenten, z. B. bei Carsharing und Ridepooling, geeignet sind.

In zukünftiger Forschung sollen die untersuchten Szenarien erweitert und Situationen mit Sharing- und Pooling-Fahrzeugen eingeführt werden. Auf diese Weise lässt sich die aufgestellte Hypothese überprüfen, ob die vorgeschlagene Synchronisierung auch dann anwendbar und effizient ist, wenn zusätzliche Abhängigkeiten zwischen Agenten hinzukommen, auch über Haushalte hinaus.

Darüber hinaus könnten auch andere Arten von Abhängigkeiten (außer gemeinsam genutzten Fahrzeugen), wie gemeinsame Fahrten oder Aktivitäten, untersucht werden. In diesen Fällen sind sowohl der Prozess der gemeinsamen Entscheidungsfindung als auch eine effiziente parallele Implementierung von Interesse. Wenn diese gemeinsamen Entscheidungsabhängigkeiten ebenfalls parallel berechnet werden können, könnte ein allgemeines Konzept für die Synchronisierung von Abhängigkeiten zwischen Agenten entwickelt werden.

6 Literatur

1. Yoram Shiftan & Moshe Ben-Akiva. (2011). A practical policy-sensitive, activity-based, travel-demand model. The Annals of Regional Science, 47: S. 517–541.
2. Min-Ah Kwak, TA Arentze, E de Romph, & S Rasouli. (2012). Activity-based dynamic traffic modeling: Influence of population sampling fraction size on simulation error. 13th International Conference on Travel Behaviour Research (IATBR 2012), July 15-20, 2012, Toronto, Canada, S. 1–17.
3. Andrew T Crooks & Alison J (2011). Introduction to agent-based modelling. Agent-based models of geographical systems, S. 85–105. Springer.
4. David B Skillicorn & Domenico (1998). Models and languages for parallel computation. Acm Computing Surveys (Csur), 30(2): S. 123–169.
5. Nicolai Mallig, Martin Kagerbauer, & Peter (2013). mobitopp – a modular agentbased travel demand modelling framework. Procedia Computer Science, 19:S. 854–859. ISSN 1877-0509. doi: https://doi.org/10.1016/j.procs.2013.06.114. The 4th International Conference on Ambient Systems, Networks and Technologies (ANT 2013), the 3rd Inter- national Conference on Sustainable Energy Information Technology (SEIT-2013).
6. Peter Vovsha, Joel Freedman, Vladimir Livshits, & Wu Sun. (2011). Design features of activity-based models in practice: Coordinated travel–regional activity modeling Transportation Research Record, 2254(1): S. 19–27. doi: 10.3141/2254-03.
7. Tim Hillel, Janody Pougala, Patrick Manser, Raphael Luethi, Wolfgang Scherr, & Michel Bierlaire. (2020). Modelling mobility tool availability at a household and individual level: A case study of switzerland. hEART conference. Lyon, France.
8. Francesco Ciari, Michael Balmer, & Kay W. Axhausen. (2007). Mobility tool ownership and mode choice decision processes in multi-agent transportation Zurich. ETH Zurich, IVT. doi: 10.3929/ethz-a-005564854. 7th Swiss Transport Research Conference (STRC 2007).
9. Andreas Horni, Kai Nagel, & Kay Axhausen, (2016). Multi-Agent Transport Simu- lation MATSim. Ubiquity Press, London. doi: 10.5334/baw.
10. Antonin Danalet & Nicole (2018). Mobility resources in switzerland in 2015. Swiss Transport Research Conference. Ascona, Switzerland.
11. Allister Loder & Kay W. Axhausen. (2018). Mobility tools and use: Accessibility’s role in switzerland. Journal of Transport and Land Use, 11(1):S. 367–385. ISSN 19387849.
12. Matthias Kowald, Barbara Kieser, Nicole Mathys, & Andreas (2017). Determinants of mobility resource ownership in switzerland: changes between 2000 and 2010. Trans- portation, 44(5):S. 1043–1065. ISSN 1572-9435. doi: 10.1007/s11116-016-9693-7.
13. Mohammad Saleem, Oskar Blom Västberg, & Anders Karlström. (2018). An activity based demand model for large scale Procedia computer science, 130:S. 920–925.
14. Han Zhou, JL Dorsman, Maaike Snelder, Erik de Romph, & Michel (2019). Gpu-based parallel computing for activity-based travel demand models. Procedia Computer Science, 151:S. 726–732.
15. Eric Shook, Shaowen Wang, & Wenwu (2013). A communication-aware framework for parallel spatially explicit agent-based models. International Journal of Geographical Information Science, 27(11): S. 2160–2181.
16. Zhaoya Gong, Wenwu Tang, David A Bennett, & Jean-Claude (2013). Parallel agentbased simulation of individual-level spatial interactions within a multicore computing envi- ronment. International Journal of Geographical Information Science, 27(6): S. 1152–1170.
17. Wenwu Tang, David A Bennett, & Shaowen (2011). A parallel agent-based model of land use opinions. Journal of Land Use Science, 6(2-3):S. 121–135.
18. Christoph (2010). Implementation of a time step based parallel queue simulation in matsim. 10th Swiss Transport Research Conference. Monte Verita, Ascona.
19. Lukas Barthelmes, Michael Heilig, Christian Klinkhardt, Martin Kagerbauer, & Peter Vortisch. (2022). The effects of spatial characteristics on car ownership and its impacts on agent-based travel demand Procedia Computer Science, 201:S. 296–304. ISSN 1877-0509. doi: https://doi.org/10.1016/j.procs.2022.03.040. The 13th International Con- ference on Ambient Systems, Networks and Technologies (ANT) / The 5th International Conference on Emerging Data and Industry 4.0 (EDI40).
20. Gerard de Jong, James Fox, Andrew Daly, Marits Pieters, & Remko (2004). Com- parison of car ownership models. Transport Reviews, 24(4):S. 379–408. doi: 10.1080/ 0144164032000138733.
21. Sabreena Anowar, Naveen Eluru, & Luis Miranda-Moreno. (2014). Alternative modeling approaches used for examining automobile ownership: A comprehensive review. Transport Reviews, 34(4):S. 441–473. doi: 10.1080/01441647.2014.915440.
22. Nicolai Mallig & Peter (2017). Modeling travel demand over a period of one week: The mobitopp model. arXiv preprint arXiv:1707.05050.
23. Jelle Kübler, Lars Briem, & Nicolai mobiTopp: https://github.com/kit-ifv/mobitopp, (2022).
24. Younes Delhoum, Rachid Belaroussi, Francis Dupin, & Mahdi Zargayouna. (2020). Activity-based demand modeling for a future urban Sustainability, 12(14):S. 5821.
25. United Nations. (2017). Household size and composition around the world, 2017. Data booklet, http://www.un.org/en/development/desa/population/publications.
26. Claudia Nobis & Tobias Mobilität in Deutschland 2017 - Mobility in Germany 2017. Technical report, BMVI, infas, DLR, IVT, infas 360., Bonn, Berlin, (2018). URL https://www.mobilitaet-in-deutschland.de/pdf/MiD2017_Ergebnisbericht.pdf.