Integrated Balanced and Staggered Routing in Autonomous Mobility-on-Demand Systems

Repository for the paper "Integrated Balanced and Staggered Routing in Autonomous Mobility-on-Demand Systems"
by Antonio Coppola, Gerhard Hiermann, Dario Paccagnan, Michel Gendreau, and Maximilian Schiffer.

---

Getting Started

Prerequisites

Ensure you have the following installed:

• Python 3.11.9
• A C++ compiler compatible with pybind11 (for compiling the C++ modules)

Installation

1. Clone the Repository

   Clone this repository to your local machine.

2. Environment Setup

   • Mark the src folder as a source directory in your IDE.
   • Install Python dependencies listed in requirements.txt.

   If you encounter issues with Fiona or GDAL, consider using precompiled wheel files available from
   Gohlke’s Pythonlibs.

---

3. C++ Module Integration

• Navigate to cpp_module/lib and follow the instructions in readme.md to install or link pybind11.
• This project includes two C++ modules:
  • cpp_module: contains the main algorithm for solving the routing problem.
  • kspwlo: implements the k-shortest paths with limited overlap (Chondrogiannis et al., 2020).
• Compile the modules using the provided scripts in the scripts/ folder.
• After compilation, ensure that the correct configuration is loaded by setting
  C_MAKE_CONFIGURATION = "release" (or "debug") in main.py.

---

4. Data Download Instructions

This project relies on datasets hosted on Zenodo. Download them using the link below:

After downloading, place the extracted folders in the following locations:

• ./sets_of_experiments/
  Contains the results and scripts used to reproduce the figures in the paper.

• ./data/nyc_tlc_data/
  Preprocessed NYC TLC data used to generate instances.

• ./data/staggered_routing_benchmark/
  Contains benchmark solutions generated by the matheuristic used for comparison.

---

5. Generating Instances

You can generate instances in two ways:

• Open and run src/instance_generator/__init__.py after setting the desired parameters. Instances will be saved to the data/ directory.
• Alternatively, run the main application. If the required instance is not already present, it will be generated automatically.

---

6. Running the Code

Once the environment is set up and the C++ modules are compiled, you can run the application by executing main.py.

---

7. Parameter Configuration

All parameters are defined in src/utils/input_data.py. These govern both instance generation and solver behavior.

Instance Parameters (InstanceParams)

• network_name: Name of the network JSON file (e.g., "manhattan_100_with_500M_shortcuts.json").
• day: Day used for trip sampling (1–31).
• months: Number of months used to aggregate data for trip sampling.
• max_flow_allowed: Maximum allowed flow (in seconds per vehicle).
• dataset_time_window: Time window for trip selection (in hours).
• list_of_slopes: Slopes of the piecewise-linear (PWL) delay function.
• list_of_thresholds: Thresholds where PWL slope changes occur.
• poly_alpha, poly_beta, poly_gamma: Parameters for the polynomial delay function (used if type_of_delays = "poly").
• staggering_cap: Maximum staggering allowed per trip, in percentage.
• deadline_factor: Multiplier for computing trip deadlines.
• num_alternative_paths: Number of alternative paths generated per trip.
• path_similarity_theta: Similarity threshold for alternative paths (between 0 and 1).
• kspwlo_algo: Algorithm used for alternative path generation (e.g., "svp_plus", "onepass").
• fraction_controlled: Fraction of trips that are controlled (between 0 and 1).
• type_of_delays: Delay model to use ("pwl" or "poly").
• stag_benchmark_comparison: If True, loads benchmark instances used for comparison.

Solver Parameters (SolverParams)

• algo: Optimization algorithm used (e.g., "LNS").
• mode: Strategy applied ("STAG", "BAL", or "INTEG").
• goal: Optimization objective ("WELFARE" or "PROFIT").
• verbose: If True, prints progress during execution.
• set_of_experiments: Name used to group and store experiment results.

If using LNS as algorithm, the following parameters apply:

• LNS_initial_pool_size: Initial percentage of trips included in the solution pool.
• LNS_destroy_percentage: Fraction of the solution destroyed per iteration.
• LNS_improve_with_ls: Whether to apply local search after each repair step.
• LNS_insertion_order: Order in which trips are inserted (e.g., "EARLIEST_FIRST", "HIGHEST_DELAY_FIRST").
• LNS_time_limit: Runtime limit in seconds.
• LNS_min_diff_start_times: Minimum time separation between candidate departure times (in seconds).
• LNS_max_destroy_attempts: Maximum number of destroy attempts per iteration.

---

8. Results

Results are saved under the sets_of_experiments directory. The folder structure reflects both instance and solver configurations.

You can use the set_of_experiments parameter (e.g., "ALGO_PERFORMANCE") to organize results into dedicated subdirectories.

If you'd like to reproduce the results hosted on Zenodo, you can find the corresponding parameter presets in the file PRESETS.py.

---

Support

For questions, suggestions, or bug reports, please open an issue on GitHub or contact the contributors via email.

---

License

This project is licensed under the MIT License.