Metropolis

Introduction

What is Metropolis?

Metropolis is a transport simulator with the following characteristics:
  • based on economic theory (utility maximization)
  • multi-modal (it includes private and public transports)
  • dynamic (congestion is time-dependent and departure times are endogenous)
  • mesoscopic (vehicle flow are aggregated at link-level)
  • agent-based (each individual is modeled as an autonomous entity)
  • adapted to large-scale scenario (up to 1 million roads and 10 millions agents)
  • easy to use (there are tools to easily import data and analyze the results)

Team

Main members:
Name Status Affiliation Functions
de Palma, André Professor THEMA, CY Cergy Paris Université modeling, management
Javaudin, Lucas PhD Student THEMA, CY Cergy Paris Université modeling, development

Team

Other members:
Name Status Affiliation Functions
Ghoslya, Samarth PhD Student Sapienza University of Rome / THEMA, CY Cergy Paris Université ride-sharing extension
Le Frioux, Romuald PhD Student THEMA, CY Cergy Paris Université environment extension

Team

Scientific advisers:
Name Status Affiliation
Coulombel, Nicolas Associate Professor LVMT, École des ponts ParisTech
Geroliminis, Nikolas Professor LUTS, École Polytechnique Fédérale de Lausanne
Lindsey, Robin Professor Sauder School of Business, University of British Columbia
Picard, Nathalie Professor BETA, University of Strasbourg

Team

Former members:
Name Status Affiliation Functions
Bouajaja, Ismaïl Intern CY Tech, CY Cergy Paris Université development
Kuhn, Theotime Intern École Centrale de Pékin / BETA, University of Strasbourg application to Strasbourg
Marchal, Fabrice PhD Student THEMA, Universiy of Cergy-Pontoise modeling, development
Mohamed El Hacen, Ahmed Intern CY Tech, CY Cergy Paris Université web development
Ndiaye, Abass Research engineer THEMA, CY Cergy Paris Université web development
Nesterov, Yurii Professor CORE, Université Catholique de Louvain modeling

History of the Project

  • 1997-2009: Simulator v1 [C++] (de Palma, Marchal, Nesterov)
  • 2001-2009: Interface for the simulator v1 [Java] (Marchal)
  • 2018-2021: Web interface for the simulator v1 [Python Django] (Javaudin et al.)
  • 2021-: Simulator v2 [Rust] (de Palma, Javaudin)
  • 2021-: Interface for the simulator v2 [Python + JavaScript] (Javaudin et al.)

Scope of Use

  • Road and urban planning by local governments
  • Analysis of transport phenomena by economic or engineering researchers
  • Teaching of transportation theory to students

Basic Principle

  • Metropolis is an iterative model
  • At each iteration, four models are run successively (network skims computation, pre-day model, within-day model and day-to-day model)
  • The simulation stops when a convergence criteria is met or when the maximum number of iterations is reached

Input of the Model

The input of Metropolis can be divided in three main categories:
  • Road network
  • Population (list of agents and their characteristics)
  • Simulation parameters

Input of the Model

Road network

  • Edges (or links, or roads) and their characteristics:
    • Speed
    • Length
    • Number of lanes
    • Speed-density function
    • Bottleneck capacity
  • Vehicle types and their characteristics:
    • Headway between two vehicles
    • Passenger car equivalent
    • Speed function (representing speed limits)
    • Road restrictions

Input of the Model

Population

  • Mode choice model (e.g., Logit, deterministic)
  • Description of the modes (or trips) available to the agent


A mode / trip is characterized by
  • Departure-time model (exogenous departure time, continuous Logit model or multinomial Logit model)
  • An arbitrary number of legs


Legs are characterized by
  • Origin node, destination node and vehicle type (for road legs)
  • Exogenous travel-time function (for virtual legs)
  • Travel-utility function (a function of the travel time)
  • Schedule-utility function (a function of the arrival time)

Input of the Model

Simulation Parameters

  • Simulated period
  • Learning model (Markov process describing how agent learns from one iteration to another)
  • Stopping criteria (e.g., maximum number of iteration, minimum value for EXPECT)
  • Road-network parameters (recording interval, spillback enabled, approximation bounds, algorithm used)

Output of the Model

The output of Metropolis can be divided in three main categories:
  • Aggregated results
  • Agent-specific results
  • Road-specific results

Output of the Model

Aggregate results

  • Mode shares
  • Congestion level (relative difference between actual and free-flow travel time) [mean, std., min. and max.]
  • Travel time for each mode [mean, std., min. and max.]
  • Distance traveled for each mode [mean, std., min. and max.]
  • Utility (or generalized cost) [mean, std., min. and max.]
  • Welfare (expected utility from the choices made) [mean, std., min. and max.]

Output of the Model

Agent-specific results

  • Expected utility (or surplus)
  • Utility (or generalized cost)
  • Departure time, arrival time and travel time
  • Chosen mode
  • Route taken (for road modes), with the entry and exit time of each road

Output of the Model

Road-specific results

  • Expected time-dependent travel times at edge level
  • Expected time-dependent travel times at OD level

Theoretical Modeling

Network skims computation

  • Input: time-dependent travel-time function for each road of the road-network graph
  • Step 1: compute a time-dependent Hierarchy Overlay of the graph
  • Step 2: compute search spaces for each origin and destination node
  • Step 3: compute profile queries for each origin-destination pair
  • Output: time-dependent travel-time function for each origin-destination pair (with at least one trip)
Geisberger, R. and Sanders, P., 2010. Engineering time-dependent many-to-many shortest paths computation. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

Pre-Day Model

  • Input: time-dependent travel-time function for each origin-destination pair
  • Departure-time choice: choose the departure time of the agent, given the travel-time function, the schedule-utility and travel-utility functions and the mode (continuous Logit model)
  • Route choice: choose the route that minimizes the travel time of the agent for the departure time chosen
  • Mode choice: choose the mode of the agent, given the expected utility for each mode available (Logit model, deterministic model or any other choice model)
  • Output: mode, departure-time and route chosen by each agent

Bottleneck Equation

  1. Given the travel-time function faced by the agent, Metropolis computes the generalized cost of the agent for any possible departure time
  2. Metropolis computes the probability to leave at any possible departure time using the Logit formula
  3. A departure time is chosen using inverse transform sampling

Within-Day Model

  • Input: mode, departure-time and route chosen by each agent
  • Event-based model: all events that occur in the network are simulated successively, in chronological order
  • Examples of events: vehicle enters road, vehicle exits road bottleneck, road bottleneck opens
  • Record the simulated travel times of each road, at given time intervals
  • Output: time-dependent travel-time function for each road

Modeling Congestion

  • Speed-density function: speed on the edge is a function of the density of vehicles on the edge when entering it
  • Bottleneck: the entry (resp. exit) of the edge is blocked for \( 1/s \) seconds after a vehicle enters (resp. exits) the edge, where \( s \) is the capacity in vehicle per second
  • Queue propagation (or spillback): a vehicle cannot enter an edge if it is full (the total length of vehicles on the edge exceeds its total length)

Day-to-Day Model

  • Input: expected and simulated time-dependent travel-time function for each road
  • Compute the expected travel-time functions for next iteration given the expected and simulated travel-time functions of current iteration, using a Markov process (e.g., exponential process with weight $\lambda$ for simulated values)
  • Stop the simulation if a stopping criteria is reached (e.g., maximum number of iterations, departure-time shift threshold)
  • Output: expected time-dependent travel-time function for each road

Running Metropolis

Basic Principle

Running the Metropolis simulator can be summarized by these three steps:
  1. Write the input JSON files
  2. Run the simulator in a terminal
  3. Read and analyze the output JSON files

Input Files

Metropolis requires 3 input JSON files:
  • Road-network: list of edges with their characteristics, list of vehicle types with their characteristics
  • Agent file: list of the agents with their characteristics (including modes available)
  • Simulation parameters
Optional input JSON file:
  • Road-network weights: travel-time function at the edge-level to initialized the expected travel times

Units

  • Time: number of seconds since midnight (10AM is 36 000)
  • Travel time: number of seconds
  • Length: meters
  • Speed: meters per second (50 km/h is 50 ÷ 3.6 m/s)
  • Value of time: utility unit (e.g., €, $ or an abstract unit) per second
  • Flow: vehicle length (in meters) per second

Road Network JSON File

Example Road Network JSON File

						
{
  "graph": {
    "edges": [
      [
        0,
        1,
        {
          "base_speed": 10.0,
          "length": 10.0,
          "constant_travel_time": 1.0,
          "bottleneck_flow": 1.0,
          "lanes": 2,
          "speed_density": {
            "type": "FreeFlow"
          },
          "overtaking": true
        }
      ],
      [
        1,
        2,
        {
          "base_speed": 20.0,
          "length": 10.0,
          "speed_density": {
            "type": "ThreeRegimes",
            "value": {
              "beta": 1.1,
              "jam_density": 0.2,
              "jam_speed": 2.0,
              "min_density": 0.8
            }
          }
        }
      ]
    ]
  },
  "vehicles": [
    {
      "headway": 10.0,
      "pce": 1.0
    },
    {
      "headway": 30.0,
      "pce": 5.0,
      "speed_function": {
        "type": "Piecewise",
        "value": [
          [
            0.0,
            0.0
          ],
          [
            25.0,
            25.0
          ],
          [
            100.0,
            25.0
          ]
        ]
      },
      "restricted_edges": [
        1
      ]
    }
  ]
}

Agent JSON File

Example Agent JSON File

						
[
  {
    "id": 1,
    "mode_choice": {
      "type": "Logit",
      "value": {
        "u": 0.5,
        "mu": 1.0
      }
    },
    "modes": [
      {
        "type": "Trip",
        "value": {
          "legs": [
            {
              "class": {
                "type": "Road",
                "value": {
                  "origin": 0,
                  "destination": 1,
                  "vehicle": 0
                }
              },
              "stopping_time": 600.0,
              "travel_utility": {
                "type": "Polynomial",
                "value": {
                  "a": 1.0,
                  "b": -0.003
                }
              },
              "schedule_utility": {
                "type": "None"
              }
            },
            {
              "class": {
                "type": "Virtual",
                "value": 300.0
              },
              "travel_utility": {
                "type": "Polynomial",
                "value": {
                  "b": -0.003
                }
              }
            }
          ],
          "departure_time_model": {
            "type": "ContinuousChoice",
            "value": {
              "period": [
                0.0,
                200.0
              ],
              "choice_model": {
                "type": "Logit",
                "value": {
                  "u": 0.5,
                  "mu": 1.0
                }
              }
            }
          },
          "origin_schedule_utility": {
            "type": "None"
          },
          "destination_schedule_utility": {
            "type": "AlphaBetaGamma",
            "value": {
              "t_star_low": 30.0,
              "t_star_high": 30.0,
              "beta": 1.0,
              "gamma": 4.0
            }
          },
          "pre_compute_route": true
        }
      },
      {
        "type": "Trip",
        "value": {
          "legs": [
            {
              "class": {
                "type": "Virtual",
                "value": 900.0
              }
            }
          ],
          "departure_time_model": {
            "type": "Constant",
            "value": 50.0
          }
        }
      }
    ]
  }
]

Parameters JSON File

Example Parameters JSON File

						
{
  "period": [
    0.0,
    200.0
  ],
  "network": {
    "road_network": {
      "recording_interval": 50.0,
      "approximation_bound": 1.0,
      "spillback": true,
      "max_pending_duration": 20.0,
      "algorithm_type": "Best"
    }
  },
  "learning_model": {
    "type": "Exponential",
    "value": {
      "alpha": 0.99
    }
  },
  "init_iteration_counter": 1,
  "stopping_criteria": [
    {
      "type": "MaxIteration",
      "value": 2
    },
    {
      "type": "DepartureTime",
      "value": [
        0.01,
        100.0
      ]
    }
  ],
  "update_ratio": 1.0,
  "random_seed": 19960813,
  "nb_threads": 24
}

Running the Simulator

Output Files

Metropolis output 7 different file types:
  • log.txt: text file with the log of the simulation
  • report.html: HTML file with a summary table and graphs
  • iteration{n}.json: JSON file with aggregate results, for each iteration
  • running_time.json: JSON file with running times for the different parts of the simulator
  • agent_results.json.zst: compressed JSON file with agent-specific results
  • skim_results.json.zst: compressed JSON file with network skim results (i.e., OD pair travel times)
  • weight_results.json.zst: compressed JSON file with network weight results (i.e., edges' travel times)

report.html

iteration{n}.json

agent_results.json

skim_results.json

weight_results.json