This repository implements optimization methods for dynamic ride-sharing: passenger requests arrive continuously over time and become eligible for service only after their release times. The goal is to assign requests to vehicles in real time so as to minimize waiting times and trip delays, while building feasible routes that respect vehicle capacity, passenger service requirements, and the current state of the fleet. Once dispatch instructions are issued, the actions they contain are treated as committed and cannot be revised. Travel times are assumed deterministic, and vehicles are not required to return to their initial locations.
The underlying routing problem is a Dial-a-Ride Problem (DARP) (equivalently, a pickup-and-delivery problem with paired requests). The code solves it with a tractable column generation framework embedded in a rolling horizon: at each decision epoch a static DARP is solved via a set-partitioning master problem, and feasible vehicle routes are generated by a labeling / SPPRC pricing subproblem.
This repository accompanies two related research papers and provides the C++ solver, the Python data-preparation and analysis pipeline, the benchmark instance sets, and the scripts needed to reproduce the experiments.
The repository supports two complementary algorithmic workflows:
| Workflow | Name | Idea |
|---|---|---|
| B-CG | Batch-based Column Generation | An accelerated CG embedded within a rolling horizon with fixed epoch length (e.g. 30 s). |
| A-CG | Anytime Column Generation | An anytime CG method embedded in a flexible rolling horizon: epoch length is determined by the realized computation time rather than a fixed batching interval. |
B-CG (Batch / Accelerated Column Generation). Time is divided into fixed epochs. Within each epoch, newly arrived and still-unserved requests are batched and the static DARP is solved with column generation, accelerated by pruning strategies, truncated labeling, and pickup limits.
A-CG (Anytime Column Generation). A-CG reinterprets CG as an anytime procedure that captures most of the solution improvement in the first pricing iterations and stops early (via a passive or active iteration-based stopping policy). It is embedded in a flexible rolling horizon where each new epoch begins as soon as an executable plan is available, and it reuses information across epochs. A lightweight idle-vehicle repositioning mechanism improves spatial coverage.
The B-CG and A-CG terminology is used consistently across this repository, the parameter reference, and the reproducibility guide.
dynamic-ips/
├── cpp/ C++ column-generation solver
├── python/ Data-preparation pipeline and result visualization
├── computational_scripts/ Experiment generation and SLURM submission
└── data/ Benchmark instance sets (Git LFS) + ToyExample
data/ToyExample/ is a tiny, self-contained instance that the solver runs by
default when launched with no arguments — handy for smoke-testing a build.
See the subfolder READMEs for full details:
- C++ solver — build and run the solver, run experiments.
- Python pipeline — prepare datasets and reproduce all figures.
| Goal | Where to look |
|---|---|
| Smoke-test a build on a tiny instance | Toy example — run cpp/bin/realtime_DARP with no args |
| Build and run the solver | C++ solver |
| Generate / run experiment commands (local or SLURM) | Reproducibility guide |
| Configure solver behavior (parameters) | Parameter reference |
| Reproduce B-CG figures | Python pipeline → B-CG plotting script |
| Reproduce A-CG figures | Python pipeline → A-CG plotting script |
| Prepare datasets from raw data | Python pipeline |
Both benchmark sets are derived from New York City Taxi and Limousine Commission (NYC TLC) trip records (2015–2016) and use a Manhattan network of virtual stop locations with a precomputed travel-time matrix.
| Dataset | Network | Reference / Zenodo |
|---|---|---|
| NYC-DARP-Benchmark (this work) | Manhattan virtual-stop network (1102 stops) | Amiri, Legrain & El Hallaoui (2026), doi:10.5281/zenodo.20452171 |
| Riley_Benchmark | 1718-cell Manhattan grid | Riley, Legrain & Van Hentenryck (2026), doi:10.5281/zenodo.18745880 |
Both benchmark sets live under data/ and are tracked with Git LFS.
Install Git LFS (git lfs install) before cloning so the instance files are
fetched, or run git lfs pull afterwards.
This repository contains also the code and instructions for downloading the data, regenerating the network (if desired), and regenerating the instances in the Python pipeline. The benchmark folder layout is documented in the C++ solver README.
The end-to-end workflow is:
- Build the solver — compile the C++ code with a Gurobi (or CPLEX) backend. See the C++ solver README.
- Run experiments — generate command files and run them locally or on a SLURM cluster. See the Reproducibility guide.
- Analyze and plot — regenerate the B-CG and A-CG figures with the Python plotting scripts. See the Python pipeline.
To cite the datasets, use the Zenodo DOIs listed in the Datasets section.
This project is released under the MIT License © 2026 Laboratory for Combinatorial Optimization in Real-time Environment. Note that this repository does not include CPLEX/Gurobi binaries; those remain under their respective licenses.
Corresponding author: Elahe Amiri
For bugs and reproducibility questions, open a GitHub issue once the public repository URL is available.