Introduction

Please do not distribute. ©

THIS DOCUMENTATION IS A WORK-IN-PROGRESS, MANY CHAPTERS ARE STILL EMPTY

METROPOLIS2

METROPOLIS2 is an agent-based transport simulator.

Its main features are:

• Mode choice (with an arbitrary number of modes, road vehicles are explicitly modeled)
• Continuous-time departure-time choice
• Deterministic route choice (for road vehicles)
• Agent based (each agent is an autonomous entity with its own characteristics and choices)
• Modeling of road congestion (using speed-density functions and bottlenecks)
• Intermediary stops (with schedule preferences and stopping time at each intermediary point)

What is this book?

This is the official documentation of METROPOLIS2, intended for anyone wanting to learn how to use the simulator and how it works. It is designed to accumulate everything there is to know on METROPOLIS2, including

• How to use it?
• What are its theoretical foundations?
• How it works?
• What are the tools associated with METROPOLIS2?

Getting Started

This chapter of the book teaches how to write and understand the input files, how to run the simulator and how to read and understand the output files. It is intended for the users that want to run small- or large-scale simulations with METROPOLIS2. It can be read in any order. The users should not be afraid to skip some sections and come back to them when needed.

Glossary

• Agent: Autonomous entity choosing and performing one (and only one) travel alternative for each simulated day.
• Alternative: See travel alternative.
• Car: Denote a commonly used vehicle type, or a specific vehicle instance of this vehicle type.
• Destination: Ending node of a trip.
• Edge: Segment of the road-network graph representing a road.
• Intersection: Point where multiple roads cross / intersect. Represented by a node on the road-network graph.
• Link: See road or edge.
• Mode: Mean / manner of performing a trip (e.g., car, public transit, walking).
• Node: Point at the intersection of multiple edges on the road-network graph.
• Origin: Starting node of a trip.
• Road: Segment of the road network that is used by vehicles to move around.
• Road network: Infrastructures that can be used by vehicles to perform road trips. It is defined as a graph of nodes and edges.
• Road trip: Trip to go from an origin to a destination using a vehicle traveling on the road network.
• Route: Sequence of edges, or equivalently roads, representing the trip made by a vehicle on the road network to connect an origin to a destination.
• Travel alternative: Sequence of trips to be performed by an agent. The sequence can be empty if the agent is not traveling.
• Trip: Act of traveling from one place to another. See road trip and virtual trip.
• Vehicle: Object, such as a car, that can move / travel on a road network.
• Vehicle type: Definition of the characteristics shared by multiple vehicles.
• Virtual trip: Trip with an exogenous travel time (i.e., a travel time independent from the choices of the other agents).

Input

The main input file of METROPOLIS2 is a JSON file defining the parameters of the simulation. This file gives the path to the other input files to be read by METROPOLIS2. These input files can be in either Parquet or CSV format and they are divided two categories:

• Population input: the collection of agents, with their travel alternatives to simulate.
• Road network: the definition of the infrastructure that can be used by road vehicles.

Parameters

Table of Contents

• Examples
• Format
  • Path
  • InputFiles
  • LearningModel
    • Linear learning model
    • Exponential learning model
    • Unadjusted Exponential learning model
    • Quadratic learning model
    • Genetic learning model
  • RoadNetworkParameters

The parameters of a METROPOLIS2’s simulation are defined in a JSON file.

Examples

Minimal working example:

{
  "input_files": {
    "agents": "input/agents.parquet",
    "alternatives": "input/alternatives.parquet"
  },
  "period": [21600.0, 43200.0]
}

Complete example:

{
  "input_files": {
    "agents": "input/agents.parquet",
    "alternatives": "input/alts.parquet",
    "trips": "input/trips.parquet",
    "edges": "input/edges.parquet",
    "vehicle_types": "input/vehicles.parquet",
    "road_network_conditions": "input/edge_ttfs.parquet"
  },
  "output_directory": "output/",
  "period": [0.0, 86400.0],
  "road_network": {
      "recording_interval": 50.0,
      "approximation_bound": 1.0,
      "spillback": true,
      "backward_wave_speed": 4.0,
      "max_pending_duration": 20.0,
      "constrain_inflow": true,
      "algorithm_type": "Best"
  },
  "learning_model": {
    "type": "Exponential",
    "value": 0.01
  },
  "init_iteration_counter": 1,
  "max_iterations": 2,
  "update_ratio": 1.0,
  "random_seed": 19960813,
  "nb_threads": 8,
  "saving_format": "Parquet",
  "only_compute_decisions": false
}

Format

The following table describes all the possible key-value pairs in the parameters JSON file.

Path

The input files and output directory of the simulation are defined in the parameters JSON file as paths.

Each path is a string representing either a relative path or an absolute path. The relative paths are interpreted as being relative to the directory where the parameters file is located. In case of issues when working with relative paths, try with absolute paths.

We recommend using slash / instead of backslash \ in the paths.

InputFiles

The value corresponding to the key input_files must be a JSON Object with the following key-value pairs.

LearningModel

Let \( \hat{T}_{\kappa} \) be the expected travel-time function for iteration \( \kappa \) and let \( T_{\kappa} \) be the simulated travel-time function at iteration \( \kappa \).

METROPOLIS2 supports the following learning models.

Linear learning model

\[ \hat{T}_{\kappa+1} = \frac{1}{\kappa + 1} T_{\kappa} + \frac{\kappa}{\kappa + 1} \hat{T}_{\kappa}, \] such that, by recurrence, \[ \hat{T}_{\kappa+1} = \frac{1}{\kappa} \sum_{i=0}^{\kappa} T_{\kappa}. \]

JSON representation:

{
  [...]
  "learning_model": {
    "type": "Linear"
  }
  [...]
}

Exponential learning model

\[ \hat{T}_{\kappa+1} = \frac{\lambda}{a_{\kappa+1}} T_{\kappa} + (1 - \lambda) \frac{a_{\kappa}}{a_{\kappa+1}} \hat{T}_{\kappa}, \] with \[ a_{\kappa} = 1 - (1 - \lambda)^{\kappa}, \] such that, by recurrence, \[ \hat{T}_{\kappa+1} = \frac{1}{a_{\kappa}} \lambda \sum_{i=0}^{\kappa} (1 - \lambda)^i T_{\kappa}. \]

The parameter \( \lambda \) is called the smoothing factor. With \( \lambda = 0 \), the exponential learning model is equivalent to a linear learning model (see above). With \( \lambda = 1 \), the predicted values for the next iteration are equal to the simulated values, i.e., \( \hat{T}_{\kappa+1} = T_{\kappa} \).

The parameter \( \lambda \) must be between 0 and 1.

JSON representation (where “value” corresponds to the \( \lambda \) parameter):

{
  [...]
  "learning_model": {
    "type": "Exponential",
    "value": 0.05
  }
  [...]
}

Unadjusted Exponential learning model

\[ \hat{T}_{\kappa+1} = \lambda T_{\kappa} + (1 - \lambda) \hat{T}_{\kappa}. \]

The parameter \( \lambda \) must be between 0 and 1.

JSON representation (where “value” corresponds to the \( \lambda \) parameter):

{
  [...]
  "learning_model": {
    "type": "ExponentialUnadjusted",
    "value": 0.05
  }
  [...]
}

Quadratic learning model

\[ \hat{T}_{\kappa+1} = \frac{\sqrt{\kappa}}{\sqrt{\kappa} + 1} T_{\kappa} + \frac{1}{\sqrt{\kappa} + 1} \hat{T}_{\kappa}. \]

JSON representation:

{
  [...]
  "learning_model": {
    "type": "Quadratic"
  }
  [...]
}

Genetic learning model

\[ \hat{T}_{\kappa+1} = \big(T_{\kappa} \cdot \hat{T}_{\kappa}^{\kappa}\big)^{1 / (\kappa + 1)}. \]

JSON representation:

{
  [...]
  "learning_model": {
    "type": "Genetic"
  }
  [...]
}

RoadNetworkParameters

The RoadNetworkParameters value is an Object with the following key-value pairs:

Agents

Table of Contents

• CSV / Parquet representation
  • Agents
  • Alternatives
  • Trips
  • Additional constraints
• Modeling considerations
  • No-trip alternatives
  • Discrete Choice Model
    • Deterministic choice model
    • Logit choice model
  • Departure-Time Choice
    • Constant
    • Discrete
    • Continuous
  • Trip types
    • Road trips
    • Virtual trips

CSV / Parquet representation

In METROPOLIS2, agents can choose between various travel alternatives, where each travel alternative is composed of one or more trips. Following this hierarchy, the population input is divided in three files:

• agents.parquet (or agents.csv)
• alts.parquet (or alts.csv)
• trips.parquet (or trips.csv)

Agents

Alternatives

Trips

Additional constraints

• At least one alternative in alts.parquet for each agent_id in agents.parquet.
• For each trip in trips.parquet, a corresponding pair (agent_id, alt_id) must exist in alts.parquet.

Modeling considerations

No-trip alternatives

It is not mandatory to have at least one trip for each alternative. When there is an alternative with no trip, the agent will simply not travel during the simulated day. The constant_utility parameter can be used at the alternative-level to set the utility of the alternative.

Discrete Choice Model

In METROPOLIS2, there are two types of discrete choice models: Deterministic and Logit.

Deterministic choice model

With a deterministic choice model, the alternative with the largest utility is chosen.

A deterministic choice model can have up to two parameters: u and constants. The parameter u must be a float between 0.0 and 1.0. This parameter is only used in case of tie (there are two or more alternatives with the exact same utility). If there are two such alternatives, the first one is chosen if u <= 0.5; the second one is chosen otherwise. If there are three such alternatives, the first one is chosen is u <= 0.33; the second one is chosen if 0.33 < u <= 0.67; and the third one is chosen otherwise. And so on for 4 or more alternatives.

The parameter constants is a list of values which are added to the utility of each alternative before the choice is computed. If the number of constants does not match the number of alternatives, the values are cycled over. For example, assume that there are three alternatives with utility [1.0, 2.0, 3.0]. If the given constants are [0.1, 0.5], then the final utilities used to make the choice will be: [1.1, 2.5, 3.1] (the first constant is used twice). If the given constants are [0.1, 0.5, 0.7, 0.9], then the final utilities used to make the choice will be: [1.1, 2.5, 3.7] (the last constant is ignored). A few considerations should be noted:

• The constants can be used to represent the draws of random perturbations in a discrete-choice model. For example, to simulate a Probit in METROPOLIS2, you can draw as many Gaussian random variables as there are alternatives and put the draws in the constants parameter.
• For travel alternatives (alt_choice.type), it is recommended to add the constant value to the utility of the alternative directly (constant_utility parameter). This is not possible however when using a deterministic choice model for the departure-time choice (dt_choice.model.type).
• It is recommended to set as many constants as there are alternatives to prevent confusion.
• In the output, the constant value for the selected alternative is not return in the utility of this alternative. It is part of the expected_utility however.

Logit choice model

With a Logit choice model, alternatives are chosen with a probability given by the Multinomial Logit formula:

\[ p_j = \frac{e^{V_j / \mu}}{\sum_{j’} e^{V_{j’} / \mu}}. \]

A Logit choice model has two parameters:

• u (float between 0.0 and 1.0)
• mu (float larger than 0.0)

The parameter mu represents the variance of the extreme-value distributed random terms in the Logit theory.

The parameter u indicates how the alternative is chosen from the Logit probabilities (See Inverse transform sampling).

Departure-Time Choice

There are three possible types for the departure-time choice of an alternative: Constant, Discrete, Continuous.

Constant

There is no choice, the departure time for the alternative is always equal to the given departure-time (dt_choice.departure_time).

The expected_utility of this alternative is equal to the utility computed for this departure time, using the expected travel time.

Discrete

The agent chooses a departure-time among various departure-time intervals, of equal length.

The choice intervals depends on the parameters dt_choice.period and dt_choice.interval. For example, if the period is [08:00, 09:00] and the interval is 20 minutes, the choice intervals are [08:00, 08:20], [08:20, 08:40] and [08:40, 09:00]. The choice is then computed based on the expected utilities at the center of the intervals (i.e., at 08:10, 08:30 and 08:50 in the example), using a Discrete choice model.

The dt_choice.offset parameter can be used to shift the selected departure time. For example, if the agent selects the interval [08:20, 08:40] and the offset is -120, the selected departure time will be 08:28 (the center 08:30, minus 2 minutes for the offset). It is recommended to set the offset value to uniform draws in the interval [-interval_length / 2, interval_length / 2] so that the departure times are uniformly spread in the chosen departure time intervals.

Continuous

A departure time is chosen with a probability given by the Continuous Logit formula:

\[ p(t) = \frac{e^{V(t) / \mu}}{\int_{t_0}^{t_1} e^{V(\tau) / \mu} \text{d} \tau}, \]

where \( [t_0, t_1] \) is the period of the departure-time choice (parameter dt_choice.period).

The only possible choice model for a continuous departure-time choice is "Logit", with parameters u and mu.

Trip types

There are two types of trips: road and virtual.

Road trips

Road trips represent a trip on the road network from a given origin to a given destination, using a given vehicle type. The parameter class.route can be used to force the vehicle to follow a route.

Virtual trips

Virtual trips represent a trip with an exogenous travel time (independent of the other agents’ choices).

Road Network

Table of Contents

• CSV / Parquet representation
  • Edges
  • Vehicle types
  • Additional constraints

CSV / Parquet representation

In METROPOLIS2, a road network is composed of a collection of edges and a collection of vehicle types. A road network is thus represented by two CSV or Parquet files:

• edges.parquet (or edges.csv)
• vehicles.parquet (or vehicles.csv)

Edges

Vehicle types

Additional constraints

• There must be no edges with the same pair (source, target) (i.e., no parallel edges).

Running

Output

Iteration Results

Table of Contents

The file iteration_results.parquet (or iteration_results.csv) stores aggregate results for each iteration run by the simulator. The file is updated during the simulation, i.e., the results for an iteration are stored as soon as this iteration ends.

The format of this file is described in the table below. Many variables consist in four columns: the mean, standard-deviation, minimum and maximum of the variable over the population. A variable denoted as var_* in the table indicates that the results contain four variables: var_mean, var_std, var_min and var_max.

Population Results

Table of Contents

• Agent results
• Trip results
• Route results

METROPOLIS2 returns up to three files for the results of the agents.

• agent_results.parquet (or agent_results.csv): results at the agent-level
• trip_results.parquet (or trip_results.csv): results at the trip-level
• route_results.parquet (or route_results.csv): details of the routes taken (for road trips)

Agent results

Trip results

Route results

Road-Network Conditions

Table of Contents

METROPOLIS2 returns three files describing the road-network conditions:

• net_cond_exp_edge_ttfs.parquet (or net_cond_exp_edge_ttfs.csv): expected road-network conditions for the last iteration.
• net_cond_next_exp_edge_ttfs.parquet (or net_cond_next_exp_edge_ttfs.csv): expected road-network conditions for the iteration after the last iteration.
• net_cond_sim_edge_ttfs.parquet (or net_cond_sim_edge_ttfs.csv): simulated road-network conditions during the last iteration.

The road-network conditions are represented as a piecewise-linear travel-time function for each vehicle type and each edge of the road network. The output files report the breakpoints (x, y) of these piecewise-linear travel-time functions, where the x value corresponds to the departure time and the y value corresponds to the travel time. The three files follow the same format described in the table below.

Advanced topics

Inverse transform sampling Logit or simulated Logit

This section explains how METROPOLIS2 can simulate a Multinomial Logit model by either using inverse transform sampling or including the epsilon draws in the utility and selecting the best alternative deterministicly.

These two options have different implications on the input requirements and the output values.

Input: Inverse transform sampling only requires a u and mu parameters; simulated Logit requires epsilon draws for all alternatives.

Output: Inverse transform sampling returns the logsum of the choice as expected_utility; simulated Logit returns the utility of the selected alternative (including the epsilon draw) as expected_utility).

WARNING. This section is still incomplete.

Parallel edges

One limitation of the routing algorithm of METROPOLIS2 is that it cannot handle parallel edges properly. Two edges are parallel if they both have the same source and target node.

If METROPOLIS2 is run with parallel edges, a warning will be shown and the simulator will have an unpredictable behavior (i.e., it might crash or the results might be incorrect).

If you want to run METROPOLIS2 using a road network with parallel edges it is nevertheless possible using the following workaround.

The workaround consists in creating a dummy edge with null length so that the two edges are no longer parallel, without affecting the shortest paths. More precisely, let say that you want to simulate a road network with two parallel edges, with id 1 and 2, from source node 1 to target node 3. If you create a dummy edge, with id 3 and length 0, going from source node 2 to target node 3 and if you set the target node of edge 2 to 2 (instead of 3), then the you get a road network that is topologically identical but without any parallel edges.

Therefore, if your road network is defined by the following edges in edges.csv:

edge_id,source,target,speed,length,lanes,bottleneck_flow
1,1,3,20.0,10000.0,1.0,0.5
2,1,3,10.0,10000.0,1.0,0.25

Then, you should use the following modified edges.csv file to simulate properly this road network with METROPOLIS2:

edge_id,source,target,speed,length,lanes,bottleneck_flow
1,1,3,20.0,10000.0,1.0,0.5
2,1,2,10.0,10000.0,1.0,0.25
3,2,3,10.0,0.0,1.0,

Simulating road tolls

The current version of METROPOLIS2 does not allow to simulate road tolls. This limitation is due to the routing algorithm which cannot consider tolls or any other criteria different from travel time.

This limitation might be lifted in a future version of METROPOLIS2. In the meantime, some limited forms of tolls can be simulated, by leveraging the flexible alternative choice model of METROPOLIS2. The basic principle relies on defining two alternatives for the agents: an alternative where they pay the toll and can take the tolled roads and an alternative where they do not pay the toll but are limited to the non-tolled roads. In this way, the choice between taking a tolled road or not is made at the alternative-choice level and not at the route-choice level.

Route Choice: Two parallel roads

Consider a simple road network with two parallel roads:

• North road (id 1, toll of $2)
• South road (id 2, no toll)

To reach their destination, the agents can either take the North road and pay a $2 toll or take the South road without paying a toll. This route choice can be simulating in METROPOLIS2 by considering two alternatives for any agent:

• Alternative 1 (toll alternative): constant_utility is set to -2 (the toll amount), there is a single "Road" trip with class.route value set to [1] (i.e., the agent is forced to take the North road).
• Alternative 2 (no-toll alternative): constant_utility is set to 0, there is a single "Road" trip with class.route value set to [2] (i.e., the agent is forced to take the South road).

Then, if the alternative-choice model (alt_choice.model) is set to "Deterministic", the agents will choose the choice that minimizes their utility between taking the North road and pay a $2 toll or taking the South road without any toll, considering the expected travel time of either road.

The following files define a simulation with a single agent choosing between a tolled road and a non-tolled road.

parameters.json

{
  "period": [
    0,
    3600
  ],
  "road_network": {
    "recording_interval": 60,
    "spillback": false,
    "max_pending_duration": 0.0
  },
  "learning_model": {
    "type": "Exponential",
    "value": 0.01
  },
  "max_iterations": 1,
  "input_files": {
    "agents": "agents.csv",
    "alternatives": "alts.csv",
    "trips": "trips.csv",
    "edges": "edges.csv",
    "vehicle_types": "vehicles.csv"
  },
  "output_directory": "output",
  "saving_format": "CSV"
}

agents.csv

agent_id,alt_choice.type
0,Deterministic

alts.csv

agent_id,alt_id,dt_choice.type,dt_choice.departure_time,constant_utility,total_travel_utility.one
0,0,Constant,0.0,-2.0,-0.01
0,1,Constant,0.0,0.0,-0.01

trips.csv

agent_id,alt_id,trip_id,class.type,class.origin,class.destination,class.vehicle,class.route
0,0,0,Road,1,3,1,1
0,1,1,Road,1,3,1,2

edges.csv

edge_id,source,target,speed,length,lanes,bottleneck_flow
1,1,3,20.0,10000.0,1.0,0.5
2,1,2,10.0,10000.0,1.0,0.25
3,2,3,10.0,0.0,1.0,

vehicles.csv

vehicle_id,headway,pce
1,8.0,1.0

NOTE. The class.route parameter is not supported for the CSV file format as lists are not supported. In this case however, the two routes consist in a single edge so they can be added to the CSV file without relying on lists.

NOTE. The edges.csv file has three edges, even though the road network is supposed to have only two edges. This is because parallel edges are not supported in METROPOLIS2 (see Parallel edges for more).

There is an alternative way to simulate the same simulation without relying on the class.route parameter. This can be done by using the road restrictions feature of METROPOLIS2 to prevent the agents who did not pay the toll from taking the tolled road. Compared to the previous simulation files, the following changes must be made.

First, the trips.csv must specify a different vehicle type for the trip of the toll alternative (vehicle type with id 1) and the no-toll alternative (vehicle type with id 2). The class.route parameter can also be removed.

agent_id,alt_id,trip_id,class.type,class.origin,class.destination,class.vehicle
0,0,0,Road,1,3,1
0,1,1,Road,1,3,2

Then, the vehicles.csv file must define the two vehicle types with the road restriction:

vehicles.csv

vehicle_id,headway,pce,restricted_edges
1,8.0,1.0,
2,8.0,1.0,1

The two vehicle types are identical but the vehicle type of id 2 cannot take the edge of id 1 (the tolled North road).

NOTE. Like the class.route parameter, the restricted_edges parameter in vehicles.csv is not supported for the CSV format as it expects a list. But, again, we only need to specify one edge id in the list in this example which is the only case where restricted_edges can be specified with the CSV format.

NOTE. Cordon tolls can be simulated simulated easily using the same principle:

1. Create two alternatives for each agent (the first one with the toll paid and the second one without any toll paid)
2. Create two different vehicle types (the first one that is allowed everywhere on the road network and the seconde one that cannot access any edge inside the cordon area)
3. Create trips for the first alternative using the first vehicle type and trips for the second alternative using the second vehicle type.

NOTE. It is possible to simulate two or more tolled roads, with different toll amounts. With just two tolled roads, 4 alternatives and 4 vehicle types must be created: (i) paying no toll and taking no tolled road, (ii) paying the first toll amount and being able to take the first tolled road, (iii) paying the second toll amount and being able to take the second tolled road and (iv) paying both toll amounts and being able to take both tolled roads. As the number of tolled roads increases, this solution becomes very complex and computationally intensive. With n tolled roads, the number of alternatives and vehicle types to include is 2^n.

Mode choice

Even though the alternative choice model was used as a kind of route choice model in the previous example, this does not mean that simulating tolls is incompatible with simulating a mode choice model. Indeed, the previous example can be completed by adding a third alternative with a "Virtual" trip to represent, for example, a public-transit trip. In this case, the agent would choose the alternative maximizing his / her utility between taking the car with the tolled road, taking the car without the tolled road and taking public transit.

Using a "Logit" alternative choice model in this case does not really make sense because the IID assumption is not satisfied. If you nevertheless want to simulate a binary Logit model between car and public transit, where the car mode can be either with or without the toll, this is possible in the following way:

1. Draw two random values with Gumbel distribution, one for car and one for public transit.
2. Add the car random value to the constant_utility parameter for the two car alternatives (toll and no-toll).
3. Add the public-transit random value to the constant_utility parameter for the public-transit alternative.
4. Set the alternative choice model to "Deterministic".

If the number of agents is very large (each with their own random values), this methodology is equivalent to simulating a binary Logit model between car and public transit, with a deterministic choice between toll and no-toll for the car mode. See Discrete Choice Model for more.

Departure-time choice

So far, we have only considered a "Constant" departure time. When a Continuous Logit departure-time choice model is used, the results are not consistent with the decision tree of the agents. The reason is that the route choice decision is supposed ot be after the departure-time choice decision in the decision tree but, in METROPOLIS2, the alternative choice decision is above the departure-time choice decision.

In principle, the agents should choose their departure time knowing the route decision (including the toll decision) that they would do given any departure time. Therefore, the expected utility (logsum) from the deparure-time choice model should look like

\[ \ln \int_\tau e^{\max(V^{\text{toll}}(\tau), V^{\text{no-toll}}(\tau))} \text{d} \tau. \]

However, when the toll decision is simulating using the two-alternative specification proposed above, the expected utility from the combined alternative and departure-time choice looks like

\[ \max\left(\ln \int_\tau e^{V^{\text{toll}}(\tau)} \text{d} \tau, \ln \int_\tau e^{V^{\text{no-toll}}(\tau)} \text{d} \tau\right). \]

The two formula are not equivalent in the general case. Simulating tolls is thus not compatible with the "Continuous" departure-time model (unless one is ready to assume a different decision tree).

The "Discrete" departure-time model is compatible with tolls if a "Deterministic" choice model is used. In particular, tolls are compatible with a Multinomial Logit model for both departure-time choice and mode-choice, if the random epsilon values are drawn. See Inverse transform sampling Logit or simulated Logit for more.

Implementation Details

Supply side

Travel-time functions

Table of Contents

• Internal representation
  • TTF as a constant value
  • TTF as a piecewise-linear function
• Travel-time functions in JSON files

Metropolis makes heavy use a travel-time functions (e.g., when representing an edge’s weight or a travel-time function for an origin-destination pair). A travel-time function (TTF for short) is a function \(f: t \mapsto f(t)\), which gives for any departure time \(t \in [t_0, t_1]\) a travel time \(f(t)\), where \([t_0, t_1]\) is called the departure-time period. For any departure time outside of the departure-time period, the travel time is assumed to be infinite.

In Metropolis, departure time is always expressed in number of seconds since midnight and travel time is expressed in number of seconds. For example, the value 36062.3 can be decomposed as 10 * 60 * 60 + 1 * 60 + 2 + 0.3 so it can represent, depending on context, a departure time of 10:01:02.3 or a travel time of 10 hours, 1 minute, 2 seconds and 300 milliseconds.

Internal representation

Internally, travel-time functions are represented as a value that can take two types: a constant value or a piecewise-linear function.

TTF as a constant value

When a TTF is represented as a constant value \(c\), it means that the TTF is a constant function \(f: t \mapsto c\). In this case, the departure-time period is always assumed to be \((-\infty, +\infty)\) (i.e., any departure time is possible).

TTF as a piecewise-linear function

Any piecewise-linear function \(f: x \mapsto f(x)\) can be represented as a list of breakpoints \([(x_0, y_0), \dots, (x_n, y_n)]\), where the value \(f(x)\) for any \(x \in [x_i, x_{i+1})\) is given by the linear interpolation between the points \((x_i, y_i)\) and \((x_{i+1}, y_{i+1})\).

In Metropolis, since version 0.3.0, the \( x_i \) values must always be evenly spaced and thus, a piecewise-linear function can be represented by three components:

• A vector with the values \( [y_0, \dots, y_n] \).
• The period start \( x_0 \).
• The spacing between \( x \) values, i.e., the value \( \delta x \) such that \( \delta x = x_{i+1} - x_i, \: \forall i \in [1, n - 1] \).

The spacing \( \delta x \) between \( x \) values is set by the road-network parameter recording_interval. The period start, \( x_0 \), and the period end, \( x_0 + n \cdot \delta x \), are set by the simulation parameter period.

WARNING. When an user gives piecewise-linear breakpoint functions as input (for example, in the JSON file with the road-network weights), the functions must have all (i) the same number of \( y \) values, (ii) the same period start \( x_0 \) and (iii) the same spacing \( \delta x \). The simulator does not check that these rules are satisfied but unspecified behavior can occur if they are not.

Travel-time functions in JSON files

SOME INFORMATIONS ON THIS SECTION MIGHT BE OUTDATED

Travel-time functions appear multiple time in the input and output JSON files of Metropolis so it is important to understand how they are written as JSON data.

To represent a constant TTF, you simply need to give the constant travel time (in number of seconds) as a float. For example, a travel time of 90 seconds can be represented as

90.0

To represent a piecewise-linear TTF, you need to give an Object with three fields

• points: an Array of float representing the \( y \) values (in seconds)
• start_x: a float representing the period start \( x_0 \) (in seconds)
• interval_x: a float representing the spacing between \( x \) values (in seconds)

For example, the following input

{
  "points": [10.0, 20.0, 16.0],
  "start_x": 10.0,
  "interval_x": 10.0
}

represents a piecewise-linear TTF where the travel time is

• Infinity for departure time 00:00:09 (infinity before the start of the period),
• 10 seconds for departure time 00:00:10,
• 11 seconds for departure time 00:00:11 (interpolation between 10 and 20),
• 20 seconds for departure time 00:00:20,
• 18 seconds for departure time 00:00:25 (interpolation between 20 and 10),
• 16 seconds for departure time 00:00:30,
• 16 seconds for departure time 00:00:35 (equal to last breakpoint for a departure time later than the last breakpoint).

Simulating Trips

WARNING. This chapter is not completely up to date with the last version (the spillback effect is not discussed).

Only travel alternatives with at least one road trip are simulated. The travel alternatives with only virtual trips can be simulated outside of the supply model.

From the demand model, we know the departure time from the origin of the first trip of the travel alternative.

The trip is simulated by executing timestamped events.

A road event is composed of the following variables:

• agent: Index of the agent simulated.
• alternative: Description of the alternative to simulate.
• at_time: Execution time of the event.
• trip_position: Index of the current trip in the alternative.
• edge_position: Index of the current edge in the trip’s route.
• route: Current trip’s route being followed.
• current_event: Description of the current edge entry event (edge entry time, edge exit bottleneck entry time, etc.).
• event_type: Type of the event.

There are 7 types of events:

• BeginsVirtualTrip: the agent starts a virtual trip.
• LeavesOrigin: the agent leaves the origin of a trip.
• EntersInBottleneck: the agent enters the in-bottleneck of an edge.
• EntersRoadSegment: the agent enters the running part of an edge.
• EntersOutBottleneck: the agent enters the out-bottleneck of an edge.
• ExitsEdge: the agent exits an edge.
• ReachesDestination: the agent reaches the destination of a trip.

At the start of the supply model, an event is created for each simulated travel alternative. The event type is BeginsVirtualTrip if the first trip of the event is virtual, otherwise, the event type is LeavesOrigin. The execution time of the event is set to the chosen departure time, plus the origin delay.

BeginsVirtualTrip

When a BeginsVirtualTrip event is executed:

• Compute the trip travel time using the input TTF of the virtual trip.
• Store the departure time, arrival time and utility of the trip.
• If this trip is not the last trip of the trip chain, create a new BeginsVirtualTrip or LeavesOrigin event (according to the next trip type) and set the event execution time to the arrival time of the current trip plus the stopping time.
• If this trip is the last trip of the trip chain, compute and store agent-level results (global arrival time, total utility and travel time, etc.).

LeavesOrigin

When a LeavesOrigin event is executed:

• Store the departure time of the trip.
• Compute the fastest route between origin and destination and expected arrival time at destination, given the departure time from origin.
• Set the route variable to the computed route and set the edge_position variable to 0.
• Store the expected arrival time at destination.
• Compute and store the route free-flow travel time, route length and global free-flow travel time.
• Set the next event to EntersInBottleneck and execute it immediately.

EntersInBottleneck

When a EntersInBottleneck event is executed:

• Set the current edge according to the route and edge_position values.
• Record the entry time on the edge’s entry bottlenec.
• Set the type of the next event to EntersRoadSegment.
• Check the status of the bottleneck: if it is open, the next event can be executed immediately, if it is close the event will be executed when the bottleneck open again (the bottleneck entity is responsible for executing the next event).

EntersRoadSegment

When a EntersInBottleneck event is executed:

• Record the entry time on the edge’s road segment.
• Compute the travel time on the edge’s road segment given the current density of vehicle on this segment and the vehicle of the road trip.
• Set the type of the next event to EntersOutBottleneck.
• Set the execution time of the next event to the current time plus the travel time on the road segment.

EntersOutBottleneck

When a EntersOutBottleneck event is executed:

• Record the entry time on the edge’s exit bottleneck.
• Set the type of the next event to ExitsEdge.
• Check the status of the bottleneck: if it is open, the next event can be executed immediately, if it is close the event will be executed when the bottleneck open again (the bottleneck entity is responsible for executing the next event).

ExitsEdge

When a ExitsEdge event is executed:

• Record the exit time on the edge.
• Store the edge taken in the results, with its entry time.
• Increment the road time, in-bottleneck time and out-bottleneck time of the current trip according to the recorded timings for the edge taken.
• If the current edge is the last edge of the route, then the destination is reached so the next event type is set to ReachesDestination and the next event is executed immediately.
• If the current edge is not the last edge of the route, the edge_position variable is incremented by 1, the next event type is set to EntersEdge and the next event is executed immediately.

ReachesDestination

When a ReachesDestination event is executed:

• Compute the total travel time of the trip.
• Store
• Store the arrival time and utility of the trip.
• If this trip is not the last trip of the trip chain, create a new BeginsVirtualTrip or LeavesOrigin event (according to the next trip type) and set the event execution time to the arrival time of the current trip plus the stopping time.
• If this trip is the last trip of the trip chain, compute and store agent-level results (global arrival time, total utility and travel time, etc.).

Congestion and spillback modeling

Table of Contents

• Vehicle types
• Exit bottleneck
  • Definition
  • Simulation
  • Recording

An edge of the road network is composed of three parts:

• An entry bottleneck (or in bottleneck) that limits the flow of vehicle entering the edge.
• A running part where the vehicles travel at a speed given by a speed-density function.
• An exit bottleneck (or out bottleneck) that limits the flow of vehicle exiting the edge.

These three components are presented in more details in the following sections.

Vehicle types

Each vehicle type of a road network is characterized by:

• A headway: length between the head of the vehicle and the head of the following vehicle (headway should be given under traffic jam or low speed conditions).
• A passenger-car equivalent (PCE): weight of the vehicle compared to a standard passenger car, in bottleneck scenarios.
• A speed function: vehicle speed as a function of the speed for the base vehicle.
• Allowed edges: list of edges that the vehicle can take (all edges are allowed if empty).
• Restricted edges: list of edges that the vehicle cannot take (all edges are allowed if empty).

Exit bottleneck

Definition

Each edge of the road network has an exit bottleneck with a flow \( s^o \), expressed in PCE per second. The value \( s^o \) is called the output flow of the edge. When not specified, the output flow is \( s^o = \infty \), i.e., there is no restriction to the flow of vehicles that can exit the edge.

When the output flow is finite, i.e., \( s^o < \infty \), then each time a vehicle with a PCE \( v^{PCE} \) exits the edge, the exit bottleneck is closed for a duration of \( v^{PCE} / s^o \) seconds. For example, if the output flow is \( s^o = 0.5 \) PCE / second, and a standard passenger car (\( v^{PCE} = 1 \)) exits the edge, then the exit bottleneck gets closed for 2 seconds. Therefore, with an output flow of \( s^o = 0.5 \), there can at most be 1800 PCE vehicles exiting the edge in a hour. The value \( 3600 \cdot s^o \) is usually called the output capacity of the edge.

Simulation

When the within-day model starts, a BottleneckState is created for each edge of the road network with a finite output flow. The BottleneckState holds the timing of the next opening of the bottleneck (by default set to 0.0) and a queue of vehicles waiting at the bottleneck (empty by default).

Additionnally, events BottleneckEvent are used to simulate the opening of a bottleneck. A BottleneckEvent holds the execution time of the event (i.e., the opening time of the bottleneck), the index of the edge the bottleneck belongs to and an indicator for entry or exit bottleneck.

Assume that a vehicle \( v \) with PCE \( v^{PCE} \) reaches the end of an edge with output flow \( s^o \) at time \( t \).

• If \( t \) is later than the bottleneck’s next opening, it means that the bottleneck is open. Then, the vehicle exits the edge and the next opening is set to \( t + v^{PCE} / s^o \).
• If \( t \) is earlier than the bottleneck’s next opening and the bottleneck queue is empty, it means that the bottleneck is closed and an event needs to be created. Then, a BottleneckEvent is created with an execution time set to the bottleneck’s next opening. The vehicle \( v \) is inserted in the bottleneck queue. The next opening time is increased by \( v^{PCE} / s^o \).
• If \( t \) is earlier than the bottleneck’s next opening and the bottleneck queue is non-empty, it means that the bottleneck is closed and an event has been created to let the next vehicle pass when it opens again. Then, the vehicle \( v \) is pushed to the end of the bottleneck queue. The next opening time is increased by \( v^{PCE} / s^o \).

When a BottleneckEvent is executed at time \( t \), the next vehicle in the bottleneck queue is allowed to exit the edge. The next opening time of the bottleneck is set to \( t + v^{PCE} / s^o \). If the queue is not empty, the BottleneckEvent is set to execute again at time \( t + v^{PCE} / s^o \).

Note. For edges with an infinite output flow, the simulator behaves like if the exit bottleneck is always open.

Recording

The within-day model needs to record the observed waiting times as a function of the entry times in the bottleneck. Therefore, a piecewise-linear time function is built with a period and an interval length defined by the parameters period and recording_interval (see Travel-time functions for more details).

Demand side

Tools

Apart from the simulator itself, many tools have been developed to help users or extend the model.

These tools include:

• A script to compute time-dependent routing queries
• A script to import a network from OpenStreetMap data
• A script to import a network from HERE data
• A script to add connectors to a network
• A script to compute air pollution from the results of a simulation

Routing queries

INFORMATIONS ON THIS PAGE ARE OUTDATED

The file compute_travel_times is a standalone executable that ships with every version of Metropolis. It can be used to run efficiently many time-dependent routing queries on a graph. Internally, it uses the same algorithms as Metropolis.

Table of Contents

• Terminology
  • Graph
  • Query source / target variants
  • Query objective function variants
• Getting Started
• Algorithms
• Graph file
• Queries file
• Weights file
• Parameters file
• Node order file
• Output file
• Overlay file

Terminology

Graph

• Static graph A graph where all edges’ weights (which usually represent travel times) are constant.
• Time-dependent graph A graph where some (or all) edges’ weights are functions \(f(t)\) that yields the travel time on the edge for any time \(t\).

Query source / target variants

• Point-to-point query Shortest path from a node \(u\) to a node \(v\).
• Single-source (or single-target) query Shortest paths from a node \(u\) to all other nodes of the graph (in reverse for single-target queries).
• All-to-all query Shortest paths from any node \(u\) to any node \(v\) of the graph.
• One-to-many (or many-to-one) query Shortest paths from a node \(u\) to all other nodes in a set \(T\) of target nodes (in reverse for many-to-one queries).
• Many-to-many query Shortest paths from a set \(S\) of source nodes to a set \(T\) of target nodes.

Query objective function variants

• Static query In a graph with constant edge weights, query \(S(s, t)\) that returns the minimum travel time between a source node \(s\) and a target node \(t\).
• Earliest-arrival query In a time-dependent graph, query \(EA(s, t, \tau_0)\) that returns the earliest possible arrival at a target node \(t\), when leaving from a source node \(s\) at time \(\tau_0\).
• Travel-time profile query In a time-dependent graph, query \(TTP(s, t)\) that returns a function \(f(\tau)\) that yields the minimum travel-time, from source \(s\) to target \(t\), given any possible departure time \(\tau\).
• Multicriteria query When the cost function maximizes multiple criteria, query that returns a Pareto set of shortest paths, from source to target.

Getting Started

The help message of the command explains how to run the command and set the input and output file paths.

To print the help message, use

$ ./compute_travel_times --help
Compute efficiently earliest-arrival or profile queries

Usage: compute_travel_times [OPTIONS] --queries <QUERIES> --graph <GRAPH> --output <OUTPUT>

Options:
      --queries <QUERIES>
          Path to the file where the queries to compute are stored

      --graph <GRAPH>
          Path to the file where the graph is stored

      --weights <WEIGHTS>
          Path to the file where the graph weights are stored. If not specified, the weights are read from the graph file (with key "weight")

      --parameters <PARAMETERS>
          Path to the file where the parameters are stored

      --output <OUTPUT>
          Path to the file where the output should be stored

      --input-order <INPUT_ORDER>
          Path to the file where the node ordering is stored (only for intersect and tch). If not specified, the node ordering is computing automatically

      --output-order <OUTPUT_ORDER>
          Path to the file where the node ordering should be stored (only for intersect and tch). If not specified, the node ordering is not saved

      --output-overlay <OUTPUT_OVERLAY>
          Path to the file where the hierarchy overlay should be stored (only for intersect and tch). If not specified, the hierarchy overlay is not saved

  -h, --help
          Print help (see a summary with '-h')

  -V, --version
          Print version

The command takes as input 5 JSON files (3 of them are optional).

• Graph file which contains a description of the graph to use as input
• Queries file which contains the queries (earliest-arrival or profile) to execute
• Weights file (optional) which contains the edges’ weights to use as input (if not specified, the weights are read from the graph file)
• Parameters file (optional) which contains the parameters of the algorithm to run
• Node order file (optional) which contains the node order to use for pre-processing (useful to speed-up the pre-processing part of the contraction hierarchy when using the same graph multiple times)

The command yields as output 3 JSON files (2 of them are optional).

• Output file which contains the results of the queries and other secondary results
• Node order file (optional) which contains the node order that can be used to speed-up the pre-processing when running the command with the same graph later
• Overlay file (optional) which contains the description of the hierarchy overlay graph

These 5 input files and 3 output files are described more accurately below.

Algorithms

The routing script can run three different algorithm types.

• Dijkstra: standard time-dependent fastest-path algorithm
• Time-dependent contraction hierarchies (TCH)
• Intersection

The characteristics and use cases for the algorithm are given below.

• Dijkstra: No pre-processing; slow queries. To be used when running a small number of queries.
• TCH: Long pre-processing time; fast queries. To be used when running many queries with different sources and targets.
• Intersection: Longest pre-processing time; fastest queries. To be used when running many queries limited to a relatively small set of sources and targets (i.e., many-to-many-like queries).

You can specify 4 different values for the algorithm to run: Best, Dijkstra, TCH and Intersection. When specifying Best, the algorithm to run is chosen as follows.

• Dijkstra if there are less than 100 queries.
• Intersection if there are more than 100 queries and less than 2 % of the nodes are used as source and less than 2 % of the nodes are used as target.
• TCH otherwise.

TCH reference:

Batz, G. V., Geisberger, R., Sanders, P., & Vetter, C. (2013). Minimum time-dependent travel times with contraction hierarchies. Journal of Experimental Algorithmics (JEA), 18, 1-1.

Intersection algorithm reference:

Geisberger, R., & 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.

Graph file

The graph file contains a list of directed edges used to build the graph where the queries are run.

There is no constraint for the number of edges that the graph can have. Also, the graph does not have to be connected (the travel time between two unconnected nodes is infinite).

The nodes are assumed to be number from 0 to n-1, where n is the number of nodes (with at least one incoming or outgoing edge) in the graph.

This JSON file must be an Array of Objects where each Object represents an edge and has the following fields:

• source (integer): index of the source node
• target (integer): index of the target node
• weight (TTF, optional): travel time on the edge (see Representing travel-time functions)

If the weight is not specified, it is assumed to be a constant travel time of 1 second.

An example of triangle graph would be

[
  {
    "source": 0,
    "target": 1,
    "weight": 30.0
  },
  {
    "source": 1,
    "target": 2,
    "weight": {
      "points": [10.0, 20.0, 15.0],
      "start_x": 0.0,
      "interval_x": 10.0
    }
  },
  {
    "source": 2,
    "target": 0
  }
]

Note. Usually, the nodes of a graph are identified by some unique ids. These ids are not used here, only the nodes’ indices are used. It is the users’ responsibility to map an unique index (between 0 and n-1) to each node id of the graph.

For example, one could assume that the node with index 0 is the node with the smallest id, the node with index 1 is the node with the second-smallest id and so on. In this case, for a graph with 3 nodes with ids 101, 103 and 104, the node id 101 corresponds to index 0, the node id 103 corresponds to index 1 and the node id 104 corresponds to index 2.

Note. When time-dependent functions are used as edges’ weigth, they must all have the same start_x and interval_x values and the same number of points. (Nevertheless, it is possible to mix time-dependent and constant travel times.

Alternatively, instead of using Objects, you can use Arrays to represent edges, where the first value is an integer corresponding to the source node, the second value is an integer corresponding to the target node and the third value (optional) is a TTF. Then, the above example can be written more compactly as

[
  [0, 1, 30.0],
  [
    1,
    2,
    {
      "points": [10.0, 20.0, 15.0],
      "start_x": 0.0,
      "interval_x": 10.0
    }
  ],
  [2, 0]
]

Queries file

The queries file contains all the queries that should be executed by the command.

There is no constraint for the number of queries. Available query types are point-to-point earliest-arrival queries and point-to-point profile queries (see Terminology).

This JSON file must be an Array of Objects where each Object represents a query and has the following fields:

• id (integer): index of the query (used to match the output)
• source (integer): index of the source node
• target (integer): index of the target node
• departure_time (float, optional): time of departure from the source node, in number of seconds since midnight (leave empty for profile queries)

Alternatively, instead of using Objects, you can use Arrays where the first value is an integer corresponding to the query’s id, the second value is an integer corresponding to the source node, the third value is an integer corresponding to the target node and the fourth value (optional) is a float corresponding to the departure time.

For example, if you want to run an earliest-arrival query from node 0 to node 1 with departure time 70.0 (i.e., 00:01:10) and a profile query from node 2 to node 3, you can use the following

[
  {"id": 1, "source": 0, "target": 1, "departure_time": 70.0},
  {"id": 2, "source": 2, "target": 3}
]

or

[
  [1, 0, 1, 70.0],
  [2, 0, 2]
]

Weights file

The weights file is an optional file that can be used to specify the weights of the graph’s edges.

When using a weights file, you do not have to specify the weights of all the edges in it. The following priority order is used to set the weight of an edge.

1. Use the weight specified for this edge in the weights file.
2. Use the weight specified for this edge in the graph file (see Graph file).
3. Use a constant weight of 1 second.

This JSON file must be an Object whose keys are the edge indices and whose values are TTF with the travel-time function of the edges (see Representing travel-time functions).

The following example set a travel time of 30 seconds for edge index 0 and a time-dependent travel time for edge index 1.

{
  "0": 30.0,
  "1": {
    "points": [10.0, 20.0, 15.0],
    "start_x": 0.0,
    "interval_x": 10.0
  }
}

Note. When time-dependent functions are used as edges’ weigth, they must all have the same start_x and interval_x values and the same number of points. (Nevertheless, it is possible to mix time-dependent and constant travel times.

Parameters file

The parameters file contains a set of parameters used by the routing script.

All parameters have default values. If the parameters file is not set, all parameters are set to their default value.

The parameter algorithm (string, optional) is used to choose the algorithm to run. Possible values are "Best" (default), "Dijkstra", "TCH" or "Intersection" (see Algorithms).

The parameter output_route (boolean, optional) is used to control whether the routes should be an output of the script (for earliest-arrival queries only). The default is to not output the routes.

The parameter nb_thread (integer, optional) controls the number of threads used to compute queries in parallel. The default is to use as many threads as possible.

There is another parameter contraction which is used to control how the hierarchy overlay is built. It is recommended to keep the default values (note that it should not impact the results, only the speed of the contraction process).

Below is an example of Parameters file.

{
  "algorithm": "Dijkstra",
  "output_route": true,
  "nb_threads": 8
}

Node order file

The node order file is both an input and output file which contains the order in which the graph’s nodes should be contracted to build the contraction hierarchy.

The majority of the computation time of the pre-processing part of the command is due to the computation of the node ordering through a heuristic. Hence, this pre-processing part can be sped-up significantly if the node ordering is already known. The main goal of this file is thus to allow to re-use the same node ordering when running the command multiple times with the same graph.

Note. The best node ordering (i.e., the node ordering which gives the fastest query-response time) depends on the graph and the edges’ weights. If the weight of a single edge changes or if an edge is added / removed, then the best node ordering can be different. In practice, the same node ordering can be used with good results if the changes are small (i.e., only a few edges were added or removed, or the weights slightly changed).

This file is not relevant for the Dijkstra algorithm.

This JSON file is simply an Array with as many integers as there are nodes in the graph. The value at index i of the Array represents the order of the node with index i.

When given as output, the values are ranging from 1 to n, where n is the number of nodes in the graph, but, in the input file, you can use any non-negative value. Nodes with smaller values are contracted earlier. If two nodes have the same value, the one with the smallest index is contracted first.

The example Node order file below implies that the nodes are contracted in this order 1 -> 0 -> 2.

[2, 1, 3]

Output file

The Output file contains the results of the queries given as input and some secondary results.

This JSON file is an Object with two keys, results and details.

The value for key results is an Array with the query results.

• For earliest-arrival queries, when output_route is false, the value is an Array [id, tt], where id (integer) is the query’s id and tt (float) is the earliest possible arrival time from source to target, given the departure time from source.
• For earliest-arrival queries, when output_route is true, the value is an Array [id, tt, route], where id (integer) is the query’s id, tt (float) is the earliest possible arrival time from source to target, given the departure time from source, and route is an Array of integers representing the edge indices of the fastest route.
• For profile queries, the value is an Array [id, ttf], where id (integer) is the query’s id and ttf (TTF) is the minimum-travel-time function from source to target.

If the travel time or travel-time function is "null", it means that the source and target nodes are not connected.

The value for key details is an Object with the following keys.

• nb_queries: Number of queries run.
• preprocessing_time: Total time spent on the pre-processing part, in seconds.
• query_time: Total time spent on computing queries, in seconds.
• query_time_per_query: Average time spent per query (excluding the pre-processing time), in seconds.
• total_time: Total time spent.
• total_time_per_query: Total time spent per query (including the pre-processing time), in seconds.

Below is an example of Output file for one earliest-arrival query and two profile queries (where the first one returns a constant travel-time function), with output_route set to false.

[
  {
    "results": [
      [1, 29430.0],
      [2, 325.0],
      [3,
        {
          "points": [70.0, 90.0, 70.0],
          "start_x": 18000.0,
          "interval_x": 9000.0
        }
      ]
    ]
  },
  {
    "details": {
      "nb_queries": 3,
      "preprocessing_time": 3.0,
      "query_time": 0.6,
      "query_time_per_query": 0.2,
      "total_time": 3.6,
      "total_time_per_query": 1.2
    }
  }
]

Below is the same example when output_route is set to true.

[
  {
    "results": [
      [1, 29430.0, [1, 2, 0]],
      [2, 325.0],
      [3,
        {
          "points": [70.0, 90.0, 70.0],
          "start_x": 18000.0,
          "interval_x": 9000.0
        }
      ]
    ]
  },
  {
    "details": {
      "nb_queries": 3,
      "preprocessing_time": 3.0,
      "query_time": 0.6,
      "query_time_per_query": 0.2,
      "total_time": 3.6,
      "total_time_per_query": 1.2
    }
  }
]

Overlay file

The Overlay file is an output file which contains the description of the hierarchy overlay graph.

This file is mainly useful for debugging purposes.