Get best of the week

How to create a multi-agent transport model

Hello, Habr!

Imagine that we have a task to build a new road. You can build a highway with two lanes in each direction, but what if this is not enough? Or, on the contrary, it turns out that one strip would be enough, but for the implementation of the project it was necessary to buy many land plots? In both cases, the decision will be ineffective. To minimize such risks, transport planners turn to computer modeling for help. This article is a brief digression into the world of multi-agent modeling.



Using the model, which is a copy of the real transport system, you can estimate the necessary throughput on each section of the projected road, try different tracing options, or, for example, estimate the payback period of a project if it comes to a toll road in the framework of a public-private partnership. But other important tasks can be solved: how to organize optimal public transport routes and calculate the potential revenue of operators, how to assess the presence of a shortage of parking spaces in a particular area, and many others.

What is most interesting is that anyone can build a similar model in the era of free software!

One of the most common multi-agent modeling tools is open source.MATSim (Multi-Agent Transport Simulation) .

MATSim simulates the behavior of individual agents. An agent is a computer representation of an individual in the real world. Each such agent has a daily plan, based on which he moves from one activity to another (for example, home-work-home, home-institute-work-home, home-shop-work1-work2-home, etc.), creating thus the demand for road infrastructure. A schematic representation of the daily plan looks something like this:

image

In order to create realistic plans of agents that will reflect the real behavior of people during the day, the total number of agent residents, their resettlement, places of work, study, location of shops, shopping centers, train stations and other places of activity are taken into account. To validate demand, the model is also calibrated based on field surveys: recognition and calculation of the flows of surveillance cameras and drones using a neural network or, for example, manual measurements of intensity on roads.

image

During the simulation, the agents are distributed over the network, imitating the realistic behavior of people: implementing their plan, cars occupy a place on the road and parking places, public transport users take places on the bus, and also interact with each other and, if many agents select one road at a time, traffic jams and congestion are created. Everything is like in the real world!

After the simulation is completed, an assessment is made of the fulfillment of the daily plans of agents, called scoring. The agent acquires utility units in the process of activity and loses them during the movement. Accordingly, agents caught in a traffic jam lose more utility units than agents moving along free roads.

After each iteration, some agents rebuild their plan on the basis of information about the load of the road network in such a way as to improve their performance: agents can change the departure time, change the mode of transport, or change the route. The remaining agents adhere to their previous plans, which are stored in the program memory.

Ideally, after the simulation, a Nash equilibrium should be achieved - that is, a situation where no agent can improve his position without worsening the position of other agents. Usually this is the situation that develops over time on the roads of the city, given the daily rethinking of the experience of the previous day by its residents. For this, at least 200 iterations are carried out in the framework of one scenario. The entire MATSim work cycle looks something like this:

image

From theory to practice!


To run the first scenario, we need Intellij IDEA (or Eclipse) with Java 1.8 on board.
We open the IDE, clone the MATSim repository from the github and our first scenario is ready to run! So simple. But let's first see what input files we use. For the simplest simulation, there are three of them: network, plans, config.

Network


The network file is the network on which agents move. It consists of nodes and nodes / links. Each link has different attributes: type, length of segment, bandwidth, maximum speed, number of lanes, one-way traffic, allowed modes of transport, etc.

image

Creating a city grid manually is difficult, impractical and inefficient. For example, our St. Petersburg grid consists of 26 thousand nodes and 46 thousand links. But there is good news. The grid can be converted from OpenStreetMap and then edited using JOSM, which is also open-source.

Plans


The plans file is a structured representation of the daily plans of agents. In the initial scenario, we have 100 agents who leave by car (mode = ”car”) in the morning (end_time = ”05:59”) from home (type = ”h”, link = ”1”) to work (type = ”W”, link = ”20”), after which after some time (dur = ”02:30”) they return home.



Config


Finally, in the config file, all the necessary settings are set to run the script. MATSim consists of modules that you can customize, add, or remove as needed.
Many of the settings in the config file are intuitive, but you can also always look into the so-called. MATSim Book . Now we will consider only two modules.
Scoring parameters are set in the planCalcScore module: for example, an agent receives a penalty of 18 units for late arrivals. utility per hour (respectively, being late for 10 minutes is equivalent to losing 3 utility units); performing some activity (for example, performing) brings 6 utility units per hour, and driving a car costs the same 6 utility units per hour. To search for realistic scoring parameters, opinion polls are most often used to analyze the “cost time. ”

In the strategy module, re-planning parameters are configured, for example, what percentage of the agents (ModuleProbability) will try the new route (ReRoute) during the next iteration.



Thus, the goal of the simulation is to help the agent get from point A to point B at the lowest cost.

Script run


Time to open RunMatsim runner and run our first script!

The simulation results will be in the output folder in the root of the project. The main files for visualization are network and events. The events file contains per-second information about all the actions of each agent, therefore, based on this file, you can restore the full picture of the movement of all agents. You can visualize the results using Via .
For more representative results, I will increase the number of agents to 500. This is how the distribution of 500 agents looks like after the first iteration ...



At the beginning of the iteration, the agents calculated the shortest way using DijkstraAs a result of which the traffic intensity in one section of the network exceeded its throughput, a congestion formed. But what if you give them the opportunity to try different routes?



After 200 iterations (~ 5 minutes), the agents were redistributed over the network, the link load level now does not exceed 0.5, and the average travel time for all agents decreased by 14% (5 minutes). Hooray, we have overcome the cork!

Oh, if only it were that simple! In reality, transport systems are much more complicated. In the following articles I will tell you how I participated in the development of models of St. Petersburg and other cities and how we solved practical problems on real cases. Scientia potentia est!



Posted by Andrey Kolomatsky, Transport Analyst at OTSLab.

More articles:


All Articles