METROPOLIS2 Course

Routing

Lucas Javaudin

2025

Overview

  • METROPOLIS2 relies on time-dependent Contraction Hierarchies algorithms
  • Pre-processing phase: nodes are "contracted" from least "important" to most "important"; contracting a node entail removing it and the adjacent edges, while creating shortcut edges to maintain fastest paths
  • Two types of queries:
    • Earliest-arrival query: Retrieve the earliest arrival time (= the minimum travel time) and the corresponding path, for a given origin-destination pair and departure time from origin
    • Profile query: Retrieve the travel-time function, for a given origin-destination pair (minimum travel time for all possible departure times)

Query Types

Earliest-arrival query
  • Input: Origin (Cergy); Destination (Saint-Denis); Departure-time (8 a.m.)
  • Output: Arrival time: 9:10 a.m.
Profile query
  • Input: Origin (Cergy); Destination (Saint-Denis)
  • Output:

Using Routing Algorithms

  • The routing algorithms of METROPOLIS2 can be used independently from the simulator: "Run routing" button on the GUI version or "routing_cli" executable on the CLI version
  • Four input files:
    • Parameters (JSON)
    • Queries (CSV or Parquet)
    • Edges (CSV or Parquet)
    • [Optional] Edges' travel-time functions (CSV or Parquet)
  • Three output files:
    • Earliest-arrival query results (CSV or Parquet)
    • Profile query results (CSV or Parquet)
    • Running times (JSON)

Edges Input File

  • Similar format than the Edges input file of METROPOLIS2
  • Column travel_time: constant travel time on the edge

Edges' TTF Input File

  • Specify for some edges the travel-time function to be used instead of the constant travel time
  • The travel-time function is given as a list of breakpoints (departure time, travel time)
  • Format very similar to METROPOLIS2's output file for road-network conditions

Queries Input File

  • query_id: Identifier of the query (used in the results)
  • origin: Identifier of the origin node
  • destination: Identifier of the destination node
  • departure_time: Departure time from origin
  • If departure time is omitted: profile query; otherwise: earliest-arrival query

Routing Parameters JSON File


						{
							"input_files": {
								"queries": "queries.csv",
								"edges": "edges.csv",
								"edge_ttfs": "edge_ttfs.csv"
							},
							"output_directory": "output",
							"saving_format": "CSV"
							"algorithm": "TCH",
							"output_route": true,
							"nb_threads": 8,
						}
  • input_files: Path to the three input files (absolute or relative to the "parameters.json" file)
  • output_directory: Path to the output directory (absolute or relative to the "parameters.json" file)
  • saving_format: "CSV" or "Parquet"
  • algorithm: "Best", "TCH", "Intersect", or "Dijkstra"
  • output_route: Whether to compute and return the fastest paths (only for earliest-arrival queries, incompatible with "Intersect")
  • nb_threads: Number of threads to use when running (Default is to use the maximum available)

Earliest-Arrival Queries Results

  • File ea_results.csv (or .parquet):
  • Input graph:
  • Input files:

Profile Queries Results

  • File profile_results.csv (or .parquet):
  • Input graph:
  • Input files:

Beyond Earliest Arrivals

  • When all the edges' travel-time functions are constant, the time-dependent routing algorithm is equivalent to a static routing algorithm
  • The travel_time values can be set to something else (e.g., edge's length) and the algorithm will minimize with respect to this metric
  • To compute the length of the shortest path, set the values to the edges' length and run earliest-arrival queries with a departure time of 0