Get best of the week

So erstellen Sie ein Transportmodell für mehrere Agenten

Hallo Habr!

Stellen Sie sich vor, wir haben die Aufgabe, eine neue Straße zu bauen. Sie können eine Autobahn mit zwei Fahrspuren in jede Richtung bauen, aber was ist, wenn dies nicht ausreicht? Oder im Gegenteil, es stellt sich heraus, dass ein Streifen ausreichen würde, aber für die Umsetzung des Projekts mussten viele Grundstücke gekauft werden? In beiden Fällen ist die Entscheidung unwirksam. Um solche Risiken zu minimieren, wenden sich Transportplaner an die Computermodellierung, um Hilfe zu erhalten. Dieser Artikel ist ein kurzer Exkurs in die Welt der Multi-Agent-Modellierung.



Mit dem Modell, das eine Kopie des realen Verkehrssystems ist, können Sie den erforderlichen Durchsatz auf jedem Abschnitt der projizierten Straße schätzen, verschiedene Rückverfolgungsoptionen ausprobieren oder beispielsweise die Amortisationszeit eines Projekts schätzen, wenn es sich im Rahmen einer öffentlich-privaten Partnerschaft um eine mautpflichtige Straße handelt. Es können jedoch auch andere wichtige Aufgaben gelöst werden: Wie können optimale öffentliche Verkehrswege organisiert und die potenziellen Einnahmen der Betreiber berechnet werden? Wie kann das Vorhandensein eines Parkplatzmangels in einem bestimmten Gebiet und in vielen anderen Bereichen bewertet werden?

Am interessantesten ist, dass jeder im Zeitalter der freien Software ein ähnliches Modell bauen kann!

Eines der am häufigsten verwendeten Multi-Agent-Modellierungswerkzeuge ist Open Source.MATSim (Multi-Agent-Transportsimulation) .

MATSim simuliert das Verhalten einzelner Agenten. Ein Agent ist eine Computerdarstellung eines Individuums in der realen Welt. Jeder dieser Agenten hat einen Tagesplan, auf dessen Grundlage er von einer Aktivität zur nächsten wechselt (z. B. Heimarbeitsheim, Heiminstitut-Heimarbeit, Heimarbeitsgeschäft1-Arbeit2-Heim usw.) und erstellt daher die Nachfrage nach Straßeninfrastruktur. Eine schematische Darstellung des Tagesplans sieht ungefähr so ​​aus:

Bild

Um realistische Pläne von Agenten zu erstellen, die das tatsächliche Verhalten der Menschen während des Tages widerspiegeln, werden die Gesamtzahl der Bewohner der Agenten, ihre Umsiedlung, Arbeitsorte, Studienorte, Standorte von Geschäften, Einkaufszentren, Bahnhöfen und anderen Tätigkeitsorten berücksichtigt. Zur Validierung der Nachfrage wird das Modell auch anhand von Felduntersuchungen kalibriert: Erkennung und Berechnung der Flüsse von Überwachungskameras und Drohnen mithilfe eines neuronalen Netzes oder beispielsweise manuelle Intensitätsmessungen auf Straßen.

Bild

Während der Simulation werden die Agenten über das Netzwerk verteilt und ahmen das realistische Verhalten der Menschen nach: Bei der Umsetzung ihres Plans nehmen Autos einen Platz auf der Straße und auf Parkplätzen ein, Benutzer öffentlicher Verkehrsmittel nehmen im Bus Platz und interagieren miteinander. Wenn viele Agenten jeweils eine Straße auswählen, Staus und Staus entstehen. Alles ist wie in der realen Welt!

Nach Abschluss der Simulation wird die Erfüllung der täglichen Pläne der Agenten bewertet, die als Bewertung bezeichnet werden. Der Agent erwirbt während des Aktivitätsprozesses Versorgungseinheiten und verliert diese während der Bewegung. Dementsprechend verlieren Agenten, die in einen Stau geraten sind, mehr Versorgungseinheiten als Agenten, die sich auf freien Straßen bewegen.

Nach jeder Iteration erstellen einige Agenten ihren Plan auf der Grundlage von Informationen über die Auslastung des Straßennetzes neu, um ihre Leistung zu verbessern: Agenten können die Abfahrtszeit, das Transportmittel oder die Route ändern. Die übrigen Agenten halten sich an ihre bisherigen Pläne, die im Programmspeicher gespeichert sind.

Idealerweise sollte nach der Simulation ein Nash-Gleichgewicht erreicht werden - das heißt, eine Situation, in der kein Agent seine Position verbessern kann, ohne die Position anderer Agenten zu verschlechtern. Normalerweise ist dies die Situation, die sich im Laufe der Zeit auf den Straßen der Stadt entwickelt, da die Bewohner die Erfahrungen des Vortages täglich überdenken. Hierzu werden im Rahmen eines Szenarios mindestens 200 Iterationen durchgeführt. Der gesamte MATSim-Arbeitszyklus sieht ungefähr so ​​aus:

Bild

Von der Theorie zur Praxis!


Um das erste Szenario auszuführen, benötigen wir Intellij IDEA (oder Eclipse) mit Java 1.8 an Bord.
Wir öffnen die IDE, klonen das MATSim-Repository vom Github und unser erstes Szenario kann ausgeführt werden! So einfach. Aber lassen Sie uns zuerst sehen, welche Eingabedateien wir verwenden. Für die einfachste Simulation gibt es drei davon: Netzwerk, Pläne, Konfiguration.

Netzwerk


Die Netzwerkdatei ist das Netzwerk, in dem sich Agenten bewegen. Es besteht aus Knoten und Knoten / Links. Jede Verbindung hat unterschiedliche Attribute: Typ, Länge des Segments, Durchsatz, Höchstgeschwindigkeit, Anzahl der Fahrspuren, Einbahnverkehr, zulässige Verkehrsträger usw.

Bild

Das manuelle Erstellen eines Stadtnetzes ist schwierig, unpraktisch und ineffizient. Zum Beispiel besteht unser St. Petersburg-Netz aus 26.000 Knoten und 46.000 Verbindungen. Aber es gibt gute Nachrichten. Das Raster kann aus OpenStreetMap konvertiert und dann mit JOSM bearbeitet werden, das ebenfalls Open Source ist.

Pläne


Die Planungsdatei ist eine strukturierte Darstellung der täglichen Pläne von Agenten. Im ersten Szenario haben wir 100 Agenten, die morgens (end_time = ”05:59”) mit dem Auto (mode = ”car”) von zu Hause (type = ”h”, link = ”1”) zur Arbeit (type =) fahren "W", link = "20"), nach einiger Zeit (dur = "02:30") kehren sie nach Hause zurück.



Konfig


Schließlich werden in der Konfigurationsdatei alle erforderlichen Einstellungen festgelegt, um das Skript auszuführen. MATSim besteht aus Modulen, die Sie nach Bedarf anpassen, hinzufügen oder entfernen können.
Viele der Einstellungen in der Konfigurationsdatei sind intuitiv, aber Sie können auch immer in die sogenannten schauen. MATSim-Buch . Jetzt betrachten wir nur zwei Module.
Die Bewertungsparameter werden im planCalcScore-Modul festgelegt: Beispielsweise erhält ein Agent eine Strafe von 18 Einheiten für verspätete Ankunft. Stromversorgung pro Stunde (jeweils 10 Minuten Verspätung entspricht dem Verlust von 3 Stromversorgungseinheiten); Die Leistung einer Aktivität (z. B. Leistung) bringt 6 Versorgungseinheiten pro Stunde mit sich, und das Autofahren kostet die gleichen 6 Versorgungseinheiten pro Stunde. Um realistische Bewertungsparameter zu finden, werden Meinungsumfragen am häufigsten zur Analyse der „Kosten“ verwendet. Zeit. “

Im Strategiemodul werden Neuplanungsparameter konfiguriert, z. B. wie viel Prozent der Agenten (ModuleProbability) die neue Route (ReRoute) während der nächsten Iteration ausprobieren.



Ziel der Simulation ist es daher, dem Agenten zu helfen, zu den niedrigsten Kosten von Punkt A nach Punkt B zu gelangen.

Skript ausführen


Zeit, RunMatsim Runner zu öffnen und unser erstes Skript auszuführen!

Die Simulationsergebnisse befinden sich im Ausgabeordner im Stammverzeichnis des Projekts. Die Hauptdateien für die Visualisierung sind Netzwerk und Ereignisse. Die Ereignisdatei enthält pro Sekunde Informationen zu allen Aktionen der einzelnen Agenten. Auf der Grundlage dieser Datei können Sie das vollständige Bild der Bewegung aller Agenten wiederherstellen. Sie können die Ergebnisse mit Via visualisieren .
Für repräsentativere Ergebnisse werde ich die Anzahl der Agenten auf 500 erhöhen. So sieht die Verteilung von 500 Agenten nach der ersten Iteration aus ...



Zu Beginn der Iteration berechneten die Agenten den kürzesten Weg mit DijkstraInfolgedessen überstieg die Verkehrsintensität in einem Abschnitt des Netzwerks seinen Durchsatz, was zu einer Überlastung führte. Aber was ist, wenn Sie ihnen die Möglichkeit geben, verschiedene Routen auszuprobieren?



Nach 200 Iterationen (~ 5 Minuten) wurden die Agenten über das Netzwerk neu verteilt, die Verbindungslast überschreitet nun nicht mehr 0,5 und die durchschnittliche Reisezeit für alle Agenten verringerte sich um 14% (5 Minuten). Hurra, wir haben den Korken überwunden!

Oh, wenn es nur so einfach wäre! In der Realität sind Transportsysteme viel komplizierter. In den folgenden Artikeln werde ich Ihnen erzählen, wie ich an der Entwicklung von Modellen für St. Petersburg und andere Städte teilgenommen habe und wie wir praktische Probleme in realen Fällen gelöst haben. Scientia potentia est!



Gepostet von Andrey Kolomatsky, Transport Analyst bei OTSLab.

More articles:


All Articles