Get best of the week

Comment créer un modèle de transport multi-agents

Bonjour, Habr!

Imaginez que nous ayons la tâche de construire une nouvelle route. Vous pouvez construire une autoroute à deux voies dans chaque direction, mais que faire si cela ne suffit pas? Ou, au contraire, il s'avère qu'une bande suffirait, mais pour la mise en œuvre du projet il a fallu acheter de nombreux terrains? Dans les deux cas, la décision sera sans effet. Pour minimiser ces risques, les planificateurs des transports se tournent vers la modélisation informatique pour obtenir de l'aide. Cet article est une brève digression dans le monde de la modélisation multi-agents.



À l'aide du modèle, qui est une copie du système de transport réel, vous pouvez estimer le débit nécessaire sur chaque tronçon de la route projetée, essayer différentes options de traçage, ou, par exemple, estimer la période de récupération d'un projet s'il s'agit d'une route à péage dans le cadre d'un partenariat public-privé. Mais d'autres tâches importantes peuvent être résolues: comment organiser les itinéraires de transport public optimaux et calculer les revenus potentiels des opérateurs, comment évaluer la présence d'une pénurie de places de stationnement dans une zone particulière, et bien d'autres.

Ce qui est le plus intéressant, c'est que n'importe qui peut construire un modèle similaire à l'ère du logiciel libre!

L'un des outils de modélisation multi-agents les plus courants est l'open source.MATSim (Simulation de transport multi-agents) .

MATSim simule le comportement d'agents individuels. Un agent est une représentation informatique d'un individu dans le monde réel. Chacun de ces agents a un plan quotidien, sur la base duquel il passe d'une activité à une autre (par exemple, maison-travail-maison, maison-institut-travail-maison, maison-atelier-travail1-travail2-maison, etc.), créant d'où la demande d'infrastructures routières. Une représentation schématique du plan quotidien ressemble à ceci:

image

Afin de créer des plans réalistes pour les agents qui refléteront le comportement réel des personnes pendant la journée, le nombre total de résidents des agents, leur réinstallation, lieux de travail, étude, emplacement des magasins, centres commerciaux, gares et autres lieux d'activité sont pris en compte. Pour valider la demande, le modèle est également calibré sur la base d'enquêtes de terrain: reconnaissance et calcul des flux de caméras de surveillance et de drones à l'aide d'un réseau de neurones ou, par exemple, des mesures manuelles d'intensité sur les routes.

image

Lors de la simulation, les agents sont répartis sur le réseau, imitant le comportement réaliste des personnes: la mise en œuvre de leur plan, les voitures occupent une place sur la route et les parkings, les usagers des transports en commun prennent place dans le bus, et interagissent également entre eux et, si de nombreux agents choisissent une route à la fois, des embouteillages et des encombrements sont créés. Tout est comme dans le monde réel!

Une fois la simulation terminée, une évaluation est faite de la réalisation des plans quotidiens des agents, appelée notation. L'agent acquiert des unités utilitaires en cours d'activité et les perd lors du mouvement. En conséquence, les agents pris dans un embouteillage perdent plus d'unités utilitaires que les agents circulant sur des routes libres.

Après chaque itération, certains agents reconstruisent leur plan sur la base d'informations sur la charge du réseau routier de manière à améliorer leurs performances: les agents peuvent changer l'heure de départ, changer le mode de transport ou changer l'itinéraire. Les agents restants adhèrent à leurs plans précédents, qui sont stockés dans la mémoire du programme.

Idéalement, après la simulation, un équilibre de Nash devrait être atteint - c'est-à-dire une situation où aucun agent ne peut améliorer sa position sans aggraver la position d'autres agents. C'est généralement la situation qui évolue au fil du temps sur les routes de la ville, compte tenu de la repensée quotidienne de l'expérience de la veille par ses habitants. Pour cela, au moins 200 itérations sont effectuées dans le cadre d'un scénario. L'ensemble du cycle de travail MATSim ressemble à ceci:

image

De la théorie à la pratique!


Pour exécuter le premier scénario, nous avons besoin d'Intellij IDEA (ou Eclipse) avec Java 1.8 à bord.
Nous ouvrons l'IDE, clonons le référentiel MATSim à partir du github et notre premier scénario est prêt à fonctionner! Si simple. Mais voyons d'abord quels fichiers d'entrée nous utilisons. Pour la simulation la plus simple, il y en a trois: réseau, plans, config.

RĂ©seau


Le fichier réseau est le réseau sur lequel les agents se déplacent. Il se compose de nœuds et de nœuds / liens. Chaque lien a des attributs différents: type, longueur de segment, débit, vitesse maximale, nombre de voies, trafic à sens unique, modes de transport autorisés, etc.

image

La création manuelle d'un réseau urbain est difficile, peu pratique et inefficace. Par exemple, notre réseau de Saint-Pétersbourg comprend 26 000 nœuds et 46 000 liens. Mais il y a de bonnes nouvelles. La grille peut être convertie à partir d'OpenStreetMap puis modifiée à l'aide de JOSM, qui est également open-source.

Des plans


Le fichier des plans est une représentation structurée des plans quotidiens des agents. Dans le scénario initial, nous avons 100 agents qui partent en voiture (mode = ”voiture”) le matin (end_time = ”05:59”) de chez eux (type = ”h”, lien = ”1”) pour travailler (type = ”W”, link = ”20”), après quoi après un certain temps (dur = ”02:30”) ils rentrent chez eux.



Config


Enfin, dans le fichier de configuration, tous les paramètres nécessaires sont définis pour exécuter le script. MATSim se compose de modules que vous pouvez personnaliser, ajouter ou supprimer au besoin.
De nombreux paramètres du fichier de configuration sont intuitifs, mais vous pouvez également toujours regarder ce que l'on appelle. Livre MATSim . Nous allons maintenant considérer seulement deux modules.
Les paramètres de notation sont définis dans le module planCalcScore: par exemple, un agent reçoit une pénalité de 18 unités pour les arrivées tardives. utilité par heure (respectivement, être en retard de 10 minutes équivaut à perdre 3 unités utilitaires); la performance d'une activité (par exemple, effectuer) apporte 6 unités utilitaires par heure, et conduire une voiture coûte les mêmes 6 unités utilitaires par heure. Pour trouver des paramètres de notation réalistes, les sondages d'opinion sont le plus souvent utilisés pour analyser le «coût» temps. »

Dans le module de stratégie, les paramètres de replanification sont configurés, par exemple, quel est le pourcentage des agents (ModuleProbability) va essayer la nouvelle route (ReRoute) au cours de la prochaine itération.



Ainsi, l'objectif de la simulation est d'aider l'agent du point A au point B au plus bas coût.

Exécution de script


Il est temps d'ouvrir RunMatsim runner et d'exécuter notre premier script!

Les résultats de la simulation seront dans le dossier de sortie à la racine du projet. Les principaux fichiers de visualisation sont le réseau et les événements. Le fichier d'événements contient des informations par seconde sur toutes les actions de chaque agent, donc en fonction de ce fichier, vous pouvez restaurer l'image complète du mouvement de tous les agents. Vous pouvez visualiser les résultats à l'aide de Via .
Pour des résultats plus représentatifs, j'augmenterai le nombre d'agents à 500. C'est ainsi que la distribution de 500 agents s'occupe de la première itération ...



Au début de l'itération, les agents ont calculé le chemin le plus court en utilisant DijkstraÀ la suite de quoi l'intensité du trafic dans une section du réseau a dépassé son débit, une congestion s'est formée. Mais que faire si vous leur donnez la possibilité d'essayer différents itinéraires?



Après 200 itérations (~ 5 minutes), les agents ont été redistribués sur le réseau, le niveau de charge de la liaison ne dépasse plus 0,5 et le temps de trajet moyen pour tous les agents a diminué de 14% (5 minutes). Hourra, nous avons surmonté le bouchon!

Oh, si seulement c'était aussi simple que ça! En réalité, les systèmes de transport sont beaucoup plus compliqués. Dans les articles suivants, je vais vous dire comment j'ai participé au développement de modèles de Saint-Pétersbourg et d'autres villes et comment nous avons résolu des problèmes pratiques sur des cas réels. Scientia potentia est!



Publié par Andrey Kolomatsky, analyste des transports à OTSLab.

More articles:


All Articles