11 AS1: Ridesharing Watertaxi Rotterdam

Static Optimization under Advance Reservation System

Author

Breno A. Beirigo

Published

March 1, 2026

11.1 Introduction

AS1 focuses on exact optimization. You will formulate the dial-a-ride problem (DARP) as a mixed-integer linear program (MILP), implement it as a CLI solver, and evaluate it on shared benchmarks. This part trains careful modeling, debugging, and objective design.

11.2 Learning objectives

You will learn to:

translate a DARP description into a correct MILP (constraints and units),
generate testing instances based on a service context,
implement single- and multi-objective variants and compare them,
run reproducible computational experiments,
benchmark your model on public instances and design your own,
analyze results and write managerial recommendations.

I Have No Data (No one Does!)

It is common in transportation optimization to work without access to proprietary data. Instead, practitioners build models based on service descriptions, public statistics, and benchmark instances. This assignment simulates this setting: you will design instances based on the Rotterdam watertaxi service description and public statistics.

Your goal is to build a model that captures the key operational aspects of the service and produces credible results that can inform managerial decisions.

11.3 Case study: Rotterdam Water Taxi

The Rotterdam water-taxi service is marketed as Watertaxi Rotterdam and provides on-demand passenger transport between docks. In this assignment, you will model the service setting (docks, requests, vessels, and service promises), not a specific proprietary dispatch system.

Service website (Watertaxi Rotterdam): https://www.watertaxirotterdam.nl/
Operating company (Flying Fish): https://www.flying-fish.tech/

Figure 11.1: Watertaxi Rotterdam operated by Flying Fish.

Operational Settings

In AS1, you will work with static snapshots where all requests in an instance are known upfront. To keep the project data-free and solvable, we use baseline assumptions for fleet size, service promises, and demand patterns.

Table Table 11.1 lists baseline settings and descriptive statistics that you can use to calibrate and sanity-check synthetic instances.

Note that service quality settings are included:

maximum ride-time ratio = 2.0 (i.e., actual ride time ≤ 2 × direct ride time),
pickup time-window width = 3 minutes (i.e., the passenger waits up to 3 minutes before boarding).

Table 11.1: Baseline assumptions for synthetic watertaxi instances.

Synthetic data setting	Baseline value
Available vessels	18
Vessel capacity	12 passengers
Effective cruising speed (travel-time calibration)	47 km/h
Stop handling time (if modeled explicitly)	180 s
Docks (total vs used)	Around 50 used
Share of pooled trips (target for calibration)	~10%
Passengers per request (group size)	Mostly 1–4; mode 3
Typical direct-trip duration (sanity check)	Most trips < 10 min
Pickup time-window width (advance reservations)	3 min
Max ride-time ratio	2.0
Operating hours (vehicle shifts)	07:00–24:00
Depot	Choose a central dock and document it

11.4 Background: Dial-a-ride problem (DARP)

In the static DARP, all requests are known before vehicles depart. Each request \(r\) has a pickup node \(p(r)\), a drop-off node \(d(r)\), a passenger count, and time windows. Your goal is to produce feasible vehicle routes that respect operational constraints and optimize a series of key performance indicators (KPIs). The DARP extends the vehicle routing problem with pickups and deliveries (VRPPD) by emphasizing service-quality constraints (e.g., time windows, waiting time, and maximum ride time); see Cordeau (2006) for background and benchmark instances.

Ride-pooling is the on-demand consolidation of multiple passenger requests into shared vehicle trips, with routing and assignment decisions made over time. Compared with fixed-line public transport, ride-pooling trades schedule simplicity for responsiveness and potentially higher fleet productivity.

Many ride-pooling systems can be modeled (approximately) as dial-a-ride problems.

11.5 Deliverables

This assignment is divided into three phases:

Phase 1: Static MILP implementation and evaluation (see Section 12.5.1).
Phase 2: Instance design for the watertaxi case and managerial insights (see Section 11.5.2).
Phase 3: Coverage of objective functions (see Section 11.5.3).

You will submit one repository per group containing:

Your MILP implementation, operable via the command line interface (CLI).
Your designed watertaxi instances in the required format.
A report documenting your implementation, instance design, and analysis (ICCL template):
- Phase 1: Model description, validation on toy classic instances, and results on benchmark instances (max. 3 pages).
- Phase 2: Instance design rationale, results under different objectives, managerial insights, limitations (max. 3 pages).
Your results file results.csv containing all runs on benchmark instances.
Your run artifacts under runs/ (one folder per experiment containing routes.csv at minimum).
A self-contained dashboard (dashboard.html) generated from your results (provide a one-command build step in your README).
A README with instructions to run your code and reproduce your results, explaining your project architecture and design choices.

Your repo will look like this:

watertaxi-submission-group-<your_group_id>/
|-- watertaxi/
|   |-- __init__.py
|   |-- main.py                 (CLI entry)
|   `-- ...                     (your codebase)
|-- data/
|   |-- benchmarks/
|   |   `-- darp_cordeau_2006/...
|   `-- instances/
|       |-- tlm-as1-toy-group-<your_group_id>/...
|       |-- tlm-as1-watertaxi-toy-group-<your_group_id>/...
|       `-- watertaxi_group-<your_group_id>/...
|-- reports/
|   |-- src/
|   |   `-- ... (latex source files, figures, etc.)
|   `-- ... tlm-as1-watertaxi-rotterdam-group-<your_group_id>.pdf
|-- tests/
|   |-- __init__.py
|   |-- test_cordeau_toy_instances.py
|   `-- test_watertaxi_toy_instances.py
|-- runs/ (run outputs)
|   `-- <experiment_name>/
|       |-- routes.csv
|       `-- ...
|-- requirements.txt
|-- results.csv
|-- .gitignore
|-- dashboard.html (last generated dashboard)
`-- README.md (details about your implementation and instructions)

Figure 11.2: Minimal required repository structure. You can add more files and folders as needed, but this is the baseline for organization and submission.

No network at grading time

The grader runs your CLI offline. Do not download benchmark instances, maps, or APIs at runtime. Include all required instance and network files in your repository.

Phase 1: Static MILP implementation and evaluation

Wire up a CLI runner that can solve Cordeau (2006) benchmark instances (sets a2–a4) with the following flags:
- --instance-path <path> (benchmark instance file path; or a watertaxi instance folder when --model watertaxi)
- --distance-calculation <method> (distance calculation method: euclidean, haversine, or time)
- --time_limit <seconds> (wall-clock cap for AS1, default 30min=1800s)
- --output <dir> (output root for artifacts, default runs; CLI writes to <dir>/<experiment_name>/)
- --objective <spec> (objective specification):
  - Single: obj
  - Weighted-sum: obj1=weight1;obj2=weight2;...
  - Lexicographic: obj1;obj2;...
- --experiment_name <name> (optional; if omitted, derive from instance + objective)
- --model <model_name> (default darp; use watertaxi for the company case)

Benchmark instance units (Cordeau 2006)

The Cordeau (2006) benchmark files use:

time values in minutes (T, time windows, service times, and L), and
coordinates x, y in a Euclidean plane.

For this assignment, treat coordinates as kilometers and use unit speed (1 km/min = 60 km/h), so Euclidean distance in km equals travel time in minutes. Convert to seconds and meters in your output files and KPIs.

Produce one result row in results.csv per run with the following fields:
- timestamp: the time when the run was executed.
- The input fields:
  - experiment_name: unique name for the experiment (e.g., <instance_id>_<objective_mode>...)
  - instance_id: unique instance identifier (e.g., the instance file name)
  - n_requests: total number of requests
  - n_vehicles: total number of vehicles
  - vehicle_capacity: capacity of the vehicles
  - max_ride_time_s: maximum allowed ride time (seconds; required for the Cordeau benchmarks)
  - max_ride_ratio: maximum ride-time ratio (optional; use for watertaxi instances if applicable)
  - max_route_duration_s: maximum allowed route duration
  - distance_calculation: method used for distance calculation (euclidean, haversine, time)
- The KPIs:
  - n_rejected: number of rejected requests
  - n_carried_passengers: total number of served passengers (counting pooling)
  - total_distance_m: total distance traveled by all vehicles (meters)
  - vehicles_used: number of vehicles that served at least one request
  - total_wait_s: total pickup delay (served only; relative to earliest pickup time)
  - total_ride_s: total in-vehicle time (served only)
  - max_wait_s: worst pickup delay (served only; relative to earliest pickup time)
  - max_ride_s: worst in-vehicle time (served only)
  - deadhead_distance_m: total distance traveled with zero passengers
  - deadhead_time_s: total time traveled with zero passengers
  - makespan_s: maximum route finish time across all vehicles
  - total_drive_time_s: total driving time across all vehicles
  - wall_clock_runtime_s: total wall-clock runtime of the run (including IO + solve)
- objective: objective mode used:
  - single: distance, unserved, etc.
  - weighted: weighted sum (distance=1;wait=0.5, etc.)
  - lex: lexicographic (unserved;vehicles;distance, etc.)
- The solver KPIs (AS1):
  - objective_value: final objective value achieved
  - best_bound (or lb): best known lower bound
  - mip_gap: final MIP optimality gap
  - runtime_s: total runtime in seconds
  - solver_status: solver termination status (OPTIMAL, TIME_LIMIT, etc.)
Produce one run folder per experiment under runs/ (e.g., runs/<experiment_name>/) and write routes.csv in the required format (see Section 12.11).
Model the classic multi-vehicle DARP and solve the MILP using Gurobi.
Validate your model using at least 5 toy instances. Explain why these instances test key aspects of your model (capacity, time windows, ride-time ratio, etc.) and show that your model can solve them optimally.
- Save the toy instances as tlm-as1-toy-group-<your_group_id> in the data/instances/ folder.
Copy the benchmark instances into your repository under data/benchmarks/darp_cordeau_2006/.
Use your CLI to produce the complete results on the Cordeau-type a2–a4 instances with a time limit of 30 minutes per instance. Use the best-known solutions reported in Ho et al. (2018) as a reference.
Report your results in a table with the following:
- N: number of requests
- K: number of vehicles
- Q: vehicle capacity
- L: maximum ride time
- BKS: best known solution
- Obj: your objective value
- Gap (%): optimality gap (if optimal known)
- Runtime (s): total runtime in seconds

Phase 2: Instance Design for Company Case

Collect (or build) a Rotterdam waterway network and dock set.

Required files for each watertaxi instance:
- network.json: nodes and directed edges (distances and travel times).
- vehicles.csv: fleet and shift windows.
- requests.csv: pickup/drop-off pairs, time windows, and passenger counts.
- manifest.json (optional but recommended): metadata, units, etc. (tip: search how to write a good dataset “manifest” file for inspiration).
Examples:

Listing 11.1: Example vehicles.csv file for a watertaxi instance with 3 vehicles, each with a capacity of 12 passengers and a full-day shift.

vehicle_id,capacity,shift_start_s,shift_end_s,origin_node_id
V1,12,0,86400,10
V2,12,0,86400,11
V3,12,0,86400,12

Listing 11.2: Example requests.csv file for a watertaxi instance with 2 requests.

request_id,pickup_id,dropoff_id,n_passengers,earliest_pickup_s,latest_pickup_s,earliest_dropoff_s,latest_dropoff_s
R1,10,11,2,25200,25800,25800,26400
R2,11,10,3,25800,26400,26400,27000

Listing 11.3: Example network.json file used by a watertaxi instance.

{
  "nodes": [
    {
      "id": 10,
      "name": "Wilhelminaplein",
      "lat": 51.9072,
      "lon": 4.4841,
      "service_time_s": 60,
      "dwell_time_s": 30
    },
    {
      "id": 11,
      "name": "Hotel New York",
      "lat": 51.9057,
      "lon": 4.4862,
      "service_time_s": 60,
      "dwell_time_s": 30
    }
  ],
  "edges": [
    {"from_id": 10, "to_id": 11, "distance_m": 320, "travel_time_s": 40},
    {"from_id": 11, "to_id": 10, "distance_m": 320, "travel_time_s": 40}
  ]
}

Time convention (watertaxi instances)

Use seconds from start of day (0 = 00:00) in your instance files and route outputs. Represent 24:00 as 86400.

Validate your model using at least 5 toy watertaxi instances. Explain why these instances test key aspects of your model and show that your model can solve them optimally.
- Save the toy instances as tlm-as1-watertaxi-toy-group-<your_group_id> in the data/instances/ folder.
Based on the company case description, design at least 10 watertaxi instances that reflect realistic demand patterns and operational constraints.
- Explain the logic behind your instance design (demand generation, time windows, fleet size, etc.).
- Format them as one folder per instance following the watertaxi schema above.
- Save them under data/instances/watertaxi_group-<your_group_id>/ (one subfolder per instance).
Add to your CLI the model watertaxi, which should take care of other specifics of the watertaxi case (e.g., additional constraints, if any).
Using your instances, analyze the performance of your MILP model under different objective configurations:
- Weighted-sum with 3 different weight sets (explain why these are chosen).
- Lexicographic with 3 different priority tiers (explain why these are chosen).
- Single-objective runs for at least 3 different objectives (e.g., distance, unserved, vehicles) and explain why these are chosen.
Report your results in a comprehensive table that includes, at minimum, the following fields:
- Instance ID: unique identifier for each instance
- Objective Configuration: description of the objective mode used
- Requests (N): number of requests
- Vehicles (K): number of vehicles
- Capacity (Q): vehicle capacity
- Max Ride-Time Ratio (L%): maximum ride-time ratio
- Objective Value (Obj): your objective value
- Optimality Gap (%): optimality gap (if optimal known)
- Runtime (s): total runtime in seconds
Discuss the trade-offs observed between different objective configurations in terms of service quality (e.g., served requests, wait times) and operational costs (e.g., total distance traveled, vehicles used).
Discuss the limitations of your instance design, the trade-offs observed, and potential improvements for future work (AS2!).

Phase 3: Coverage of Objective Functions

Once your CLI is operational, ensure it supports the objective functions listed in Table 11.2. You will need to implement the logic to compute each KPI and integrate it into your MILP model. The goal is to allow users to flexibly specify different objectives when running your solver via the CLI. Note that the top 6 objectives are required; the rest are optional but recommended.

Table 11.2: Objective function options (the goal is to minimize).

OF Code	Description	Required/Optional
`unserved`	rejected requests	Required
`vehicles`	vehicles used	Required
`distance`	total travel distance	Required
`drive_time`	total driving time	Required
`wait`	total pickup waiting time	Required
`ride`	total in-vehicle time	Required
`ride_excess`	excess ride time vs direct	Optional
`makespan`	maximum route duration	Optional
`balance_range`	workload range across vehicles	Optional
`max_wait`	worst pickup waiting time	Optional
`max_ride_excess`	worst excess ride time	Optional
`deadhead_distance`	empty (zero-load) distance	Optional
`deadhead_time`	empty (zero-load) time	Optional

11.6 The Routes in Folder `runs/`

For grading and plotting, the smallest valid header is shown in Listing 12.1. This allows us to parse the routes and compute service KPIs.

Write one routes.csv per run under runs/<experiment_name>/routes.csv. Use the conventions below:

stop_seq starts at 0 for each vehicle_id and increases by 1.
node_type is one of START_DEPOT, PICKUP, DROPOFF, END_DEPOT.
distance_prev_m and travel_time_prev_s describe the leg from the previous stop to this stop (use 0 for the first stop of each vehicle).

Listing 11.4: Minimal column set for routes.csv. Each row represents a single stop event.

vehicle_id,stop_seq,node_id,node_type,request_id,load_passengers,distance_prev_m,travel_time_prev_s,arrival_s,departure_s

Listing 11.5: Tiny route with time windows (tw_start_s, tw_end_s), service, and lat/lon.

vehicle_id,stop_seq,node_id,node_type,request_id,load_passengers,distance_prev_m,travel_time_prev_s,tw_start_s,tw_end_s,arrival_s,waiting_s,service_duration_s,departure_s,lat,lon
7,0,10,START_DEPOT,,0,0,0,0,28800,0,0,0,0,51.9072,4.4841
7,1,21,PICKUP,R12,3,1400,180,3600,3900,3600,0,180,3780,51.9057,4.4862
7,2,44,DROPOFF,R12,0,2100,240,0,0,4020,0,180,4200,51.9123,4.4721
7,3,10,END_DEPOT,,0,1600,200,0,28800,4400,0,0,4400,51.9072,4.4841

Read it like this:

Vehicle 7 starts at depot node 10.
It drives 180s to pick up R12 at node 21 and arrives exactly at tw_start_s.
It boards for 180s and departs at 3780.
It drives 240s to drop off at node 44, services for 180s, and returns.

11.7 Grading Criteria

Your assignment will be graded using the criteria below.

(automated) MILP correctness and CLI completeness (40%) Accurate modeling of the DARP, correct implementation of constraints and supported objective modes, and successful end-to-end execution via the CLI. We will run your CLI on a suite of benchmark and course instances to verify correctness and completeness (including shared toy instances, watertaxi toy instances, and watertaxi instances).
Instance design quality (20%) Realism and relevance of your watertaxi instances (demand patterns, time windows, fleet settings, and operational constraints). Correctness is assessed precisely: a correct reference model should be able to solve your instances optimally (at least for the toy-size set).
Analysis and insights (20%) Depth and rigor of your analysis across objective configurations (single / weighted / lexicographic), and the quality of the managerial insights supported by KPIs and evidence.
Report and code quality (10%) Clarity of your report and codebase: do you explain what you implemented, why you made the choices you made, how you validated, and what the results mean? (Good structure, readable code, and clear assumptions.)
Dashboard and reproducibility (10%) Quality of the generated dashboard and how easy it is to reproduce results from scratch using your CLI and README (clear steps, deterministic runs, correct artifacts).

Blackbox Testing

We will run your CLI on a hidden set of test instances to verify correctness and completeness. If your code does not run end-to-end, you will receive a zero for the automated grading portion. Make sure your CLI works exactly as specified and that all required functionalities are implemented.