12 AS2: Ridesharing Watertaxi Rotterdam
Heuristic Optimization for On-Demand Requests
12.1 Introduction
AS2 focuses on heuristic optimization. Upon recognizing the limitations of exact methods for large-scale, real-world problems, AS2 challenges you to design and implement heuristic algorithms that can produce high-quality solutions within practical time frames.
12.2 Learning objectives
You will learn to:
- create constructive heuristics that quickly generate feasible solutions,
- design local search methods to iteratively improve solutions,
- implement metaheuristics to overcome local search limitations and explore the solution space,
- re-optimize solutions in response to dynamic changes,
- benchmark heuristic performance against exact methods and public instances,
- apply heuristics to real-world-inspired instances and analyze trade-offs between solution quality and computational efficiency,
- communicate your heuristic design, implementation, and insights effectively through reports and dashboards.
Bonus (competition): Your team can earn extra points through a two-phase competition (see Section 12.6).
12.3 Case Study: Rotterdam Water Taxi
Watertaxi Rotterdam is a highly flexible, on-demand passenger transport service operating in the city of Rotterdam, Netherlands. It provides rides between docks across the River Maas. In this assignment, you will take on the role of the operations provider (Flying Fish) to address on-demand ride-pooling optimization challenges in this setting. You will model the service setting (docks, requests, vessels, and service promises), design synthetic instances reflecting realistic demand patterns, and implement heuristic algorithms to optimize operations under different objectives.
At Watertaxi Rotterdam, human control is paramount: planners and skippers have the final say at all times and can adapt instantly as new information arrives. The Flying Fish system therefore plays a decision-support role: it suggests routes and helps validate them, but any plan can be overridden at any point by someone in the field.
Bookings can be confirmed up to 2 minutes before departure, and the service aims to keep delays within 2 minutes. But during busy periods, many walk-up passengers (often recreational, without reservations) appear at the last minute and ask the skipper to take them on board. It would be odd to say no if capacity allows (the boat has 12 seats), so these passengers are promptly picked up.
From a sequential decision-making perspective, the system operates in a rolling-horizon fashion where:
- New information (e.g., reservations, shifts) comes in.
- Flying Fish creates a plan (P1).
- Schedulers validate but sometimes alter P1, leading to P2. The trick here is that sometimes they don’t have enough time to inform the system: think of someone calling at the last minute from a jetty and asking for a ride.
- Skippers take P2 and implement a revised plan, P3, to account for information unfolding in the field (the map is not the territory, after all).
In this setting, the post-decision state can be highly uncertain: passengers suddenly appear or disappear, routes change to adapt to operational conditions, and so on.
Benchmarking: What is the best static plan under perfect information?
As information unfolds, the system needs to re-optimize and adapt. But what if we had perfect information about all requests upfront? What would be the best static plan in that case? This is the question we will address in AS2, where you will design heuristics to solve the static optimization problem for larger instances that are intractable for exact methods.
You will evaluate your heuristics on single-day instances of the Rotterdam case to establish a performance upper bound (i.e., the best static plan under perfect information) and analyze trade-offs between solution quality and computational efficiency.
Dynamic optimization and re-optimization: How to adapt as information unfolds?
We will consider the dynamic problem faced by the system as information unfolds. However, for simplicity, we will exclude the role of schedulers and skippers in this assignment and focus on the system’s ability to re-optimize in response to new information. In other words, the final plan will depend only on the information available to the system at each decision point, without manual overrides (think of a fully automated system).
12.4 Preliminary Steps
To start this assignment, accept its template on GitHub Classroom.
We are using GitHub Classroom for assignment submission, grading, and feedback purposes. However, if this were implemented in practice (e.g., in a company setting), you would likely create a new branch in your existing repository (e.g., as2-heuristics), building on top of your AS1 codebase and adding new features for the heuristics. Assuming AS1 code was working “in production” (i.e., being used by schedulers and skippers), you would need to ensure that your patch (i.e., the new heuristic code) is robust and does not break existing functionality.
12.5 Task Overview
This assignment is divided into three phases:
- Phase 1: Static heuristic implementation and evaluation (see Section 12.5.1).
- Phase 2: Dynamic re-optimization heuristic (see Section 12.5.2).
- Phase 3: Managerial scenario analysis (see Section 12.5.3).
Phase 1: Static Heuristics Implementation and Evaluation
In Phase 1, you will implement and evaluate heuristic algorithms. You will start with a constructive heuristic to quickly generate feasible solutions, then design a local search method to iteratively improve those solutions, and finally implement a metaheuristic to further enhance solution quality by escaping local optima.
You will evaluate your heuristics on two types of instances:
- DARP benchmark instances from Cordeau (2006), which are widely used in the literature and have known best solutions (BKS) for comparison (see Section 12.9.1).
- A large-scale instance inspired by the Rotterdam watertaxi case, which reflects real-world complexity and operational settings (see Section 12.9.2).
Constructive Heuristic (CON)
Develop a constructive heuristic that can quickly generate a feasible solution.
Requirements: Your constructive heuristic should produce a feasible solution that beats a vanilla Nearest Neighbor Heuristic on the defined criteria.
Local Search (LS)
Design a local search method that iteratively improves the solution generated by your constructive heuristic. This method should explore the neighborhood of the current solution and make improvements based on defined criteria.
Requirements: Your local search method should take the solution from your constructive heuristic and improve it. It should show improvement in solution quality compared to the initial constructive solution. You should compare the results of your local search method against a simple 2-opt local search to demonstrate its effectiveness.
Metaheuristic (MH)
Implement a metaheuristic algorithm that further enhances solution quality by escaping local optima and exploring a broader solution space.
Requirements: Your metaheuristic should take the solution from your local search method and further improve it. It should show improvement in solution quality compared to the local search method.
Phase 2: Dynamic Re-optimization Heuristic
In Phase 1, you focused on static optimization with perfect information. By running your metaheuristic on the watertaxi instance (see Section 12.9.2), you established a performance upper bound for the static problem. Now you know the theoretical minimum fleet size, total waiting time, and total distance if you had perfect information about all requests upfront.
In Phase 2, you will design a heuristic that adapts the solution as new information (i.e., new requests) arrives in a dynamic setting. This heuristic should quickly re-optimize the existing solution to accommodate new requests while maintaining service quality.
Your heuristic will receive:
- A day’s worth of requests (with their pickup and drop-off locations, appearance times, and passenger counts).
- A time bucket (e.g., 15 seconds, 30 seconds) that defines how often the heuristic can re-optimize the solution.
- A time limit (in seconds) for each re-optimization step.
- The fleet size found in Phase 1 (i.e., the best static solution under perfect information) as a reference point.
Requirements: Your dynamic re-optimization heuristic should split the day into time buckets and re-optimize the solution at each bucket as new requests arrive. It should run within the specified time limit for each re-optimization step and beat a vanilla cheapest (i.e., lowest increase in distance) insertion heuristic.
Three bucket settings will be evaluated:
DY-R: Re-optimize at every request arrival (i.e., the bucket is defined by the arrival of new requests).DY-15: Re-optimize every 15 seconds of simulated time (i.e., read the requests that arrived in[0s, 15s), then re-optimize; then read the requests that arrived in[15s, 30s), and so on).DY-30: Re-optimize every 30 seconds of simulated time.
The time buckets refer to simulated time (time in the instance), not wall-clock time. The wall-clock time limit per re-optimization step controls how long your algorithm is allowed to compute at each bucket.
Phase 3: Managerial Scenario Analysis
Based on the domain knowledge you have gained about the Rotterdam watertaxi case, you will design a scenario analysis. This involves systematically varying one aspect of the problem and analyzing how it affects key performance indicators (KPIs).
Conduct a controlled what-if study by changing one modeling assumption regarding, for example, operational settings and service levels, running a controlled experiment, and translating KPI deltas into clear managerial recommendations. This will help you understand the trade-offs involved in different operational decisions and provide actionable insights for the water taxi service.
Experimental discipline:
- Pick one scenario family.
- Define at least three levels (low / baseline / high).
- Keep everything else fixed to avoid confounding.
- Report both means and variability (multiple seeds) when randomness exists.
- Present a KPI summary table across levels and a brief recommendation translating KPIs into an operator decision.
12.6 Competition
The competition has two phases. Each phase awards 5 bonus points to the winning team.
| Phase | What is compared | Benchmark | Time limit | Deadline | Bonus |
|---|---|---|---|---|---|
| Phase A: Best Metaheuristic | Fleet Size, Total Waiting, Distance (, Wall Time) | Best score among teams (same instances/settings) | 5 min per instance | In 2 weeks | +5 pts |
| Phase B: Best Dynamic Re-optimization | #Unserved requests, Total Waiting, Distance (, Wall Time) | Cheapest insertion baseline | 5 s per re-optimization step | In 4 weeks | +5 pts |
To get the points, the winning team must record a short video (max. 5 minutes) explaining their approach and results, and submit it to the course staff by the deadline.
12.7 Command-Line Interface (CLI)
Your CLI must accept the following flags:
--instance-path <path>(benchmark instance file path; or a watertaxi instance folder when--model watertaxi)--model <model_name>(defaultdarp; usewatertaxifor the company case)--method <method>(solver method; see table below)--objective <spec>(objective specification)--time-limit <seconds>(wall-clock cap for the run)--output <dir>(output root for artifacts, defaultruns)--experiment-name <name>(optional; if omitted, derive from instance + method + objective)--seed <int>(random seed for reproducibility; default 42)--fleet-size <int>(used for dynamic re-optimization methods to provide the static solution fleet size as a reference)
--time-limit flag overrides the defaults.
| Method code | Description | Default time limit |
|---|---|---|
nn |
Nearest Neighbor Heuristic | 60 s |
con |
Constructive Heuristic | 60 s |
2opt |
2-opt Local Search | 300 s |
ls |
Your Local Search | 300 s |
mh |
Your Metaheuristic | 300 s |
dy-r |
Dynamic re-opt (per request) | 5 s per step |
dy-15 |
Dynamic re-opt (15 s buckets) | 5 s per step |
dy-30 |
Dynamic re-opt (30 s buckets) | 5 s per step |
For the objective, we will use fixed specification:
- For DARP benchmarks:
distance(minimize total travel distance). - For watertaxi instance (metaheuristics):
vehicles;wait;distance(minimize number of vehicles, then waiting time, then distance). - For watertaxi instance (dynamic re-optimization):
unserved;wait;distance(minimize number of unserved requests, then waiting time, then distance).
Example usage:
# Run metaheuristic on a Cordeau instance with 5-minute time limit
python -m watertaxi.main --instance-path data/benchmarks/darp_cordeau_2006/a7-56.txt \
--method mh --objective distance --time-limit 300 --seed 42
# Run dynamic re-optimization on a watertaxi instance
python -m watertaxi.main --instance-path data/instances/watertaxi/ \
--model watertaxi --method dy-15 --objective "unserved;wait;distance" \
--time-limit 5 --fleet-size 1812.8 Maximum Running Times
To ensure fair comparison and practical evaluation, the following time limits apply:
| Context | Time limit | Notes |
|---|---|---|
| Static heuristics (NN, CON) on benchmarks | 60 s per instance | Should converge well before this |
| Static heuristics (2OPT, LS, MH) on benchmarks | 5 min per instance | Reported CPU run times by Ho et al. (2018) are mostly lower |
| Static heuristics on watertaxi-1000 | 10 min per instance | Larger instance needs more time |
| Dynamic re-optimization per step (DY-R, DY-15, DY-30) | 5 s per step | Must return best solution found so far when time expires |
Your algorithms must respect the time limit. If the time limit is reached, return the best solution found so far. Use the --time-limit flag (or max_runtime_sec parameter) to control this. Algorithms that exceed the time limit will be terminated and graded on whatever output is available.
You are not required to run the algorithms for the full time limit if they converge earlier. When using randomness in your heuristics (e.g., in the constructive heuristic or metaheuristic), repeat the experiment at least 3 times with different random seeds. Report the seeds so your results are reproducible.
12.9 Instances
DARP Benchmark Instances
You will benchmark the performance of your heuristics against the Cordeau (2006) DARP benchmark instances. The BKS reported in Ho et al. (2018) will serve as a reference for solution quality. You will report your results in a structured table (see template in Table 12.4) and analyze the trade-offs between solution quality and computational efficiency.
NN = Nearest Neighbor, CON = Constructive Heuristic, 2OPT = 2-opt Local Search, LS = Local Search, MH = Metaheuristic. The Gap column shows the percentage gap relative to the BKS: Gap = 100 × (Heuristic − BKS) / BKS. Requirement: \(f_\text{MH} \leq f_\text{LS} \leq f_\text{CON} \leq f_\text{NN}\), where \(f\) is the objective function value.
| Instance | Method | Result | Gap (%) | Runtime (s) |
|---|---|---|---|---|
| a7-56 | BKS | 1234 | 0 | |
| a7-56 | NN | |||
| a7-56 | CON | |||
| a7-56 | 2OPT | |||
| a7-56 | LS | |||
| a7-56 | MH |
Cordeau (2006) provides 48 benchmark instances of varying sizes and characteristics, organized by problem size (number of requests and vehicles) and type (“a” and “b”). Type “a” instances are generally considered easier to solve than type “b” instances due to their more structured nature, while type “b” instances are more challenging due to their random distribution of requests.
We will focus on the following 12 instances for benchmarking, which represent a range of problem sizes and complexities:
- a7-56, a7-70, a7-84 (type “a”, 56–84 requests, 7 vehicles)
- a8-64, a8-80, a8-96 (type “a”, 64–96 requests, 8 vehicles)
- b7-56, b7-70, b7-84 (type “b”, 56–84 requests, 7 vehicles)
- b8-64, b8-80, b8-96 (type “b”, 64–96 requests, 8 vehicles)
Considering 5 heuristic methods (NN, CON, 2OPT, LS, MH) and 12 instances, you will run at least 60 experiments1 for benchmarking. This will allow you to analyze the performance of your heuristics across different instance types and sizes and compare them against the best-known solutions.
Watertaxi Instance
You will run your methods on the provided watertaxi instance that includes 2,000 requests. You must respect the following assumptions for this instance:
Service quality settings:
- Maximum ride-time ratio: 2.0 (i.e., actual ride time ≤ 2 × direct ride time)
- Pickup time-window width: 15 min (i.e., the passenger waits up to 15 min before boarding)
Operational settings:
- Vessel capacity: 12 passengers
- No mid-water detours: vessels always depart from a dock
- Operating hours: 07:00–24:00 (last vessel return to depot before 24:00)
- Depot location: Hotel New York (dock ID 44 in the network)
- Vessels can wait at docks for new requests, but cannot wait on the water (i.e., no “floating” waiting)
- Speed of vessels: 47 km/h. Durations are calculated using this speed and rounded up to the nearest second (e.g., 4800 m ÷ (47 / 3.6) = 368.09 s → 369 s)
- Boarding time per passenger: 15 seconds (e.g., if 3 passengers board at the same stop, add 45 seconds to the stop duration)
Network settings:
- 47 docks across the Rotterdam waterways (see
network.jsonfor details) - Dock-to-dock distances calculated using shortest paths on a hexagonal grid approximating the waterway network
Similarly to the DARP benchmarks, you will report your results in a table (see template in Table 12.5) and analyze the trade-offs between solution quality and computational efficiency.
| Instance | Method | #Vehicles | Total Waiting (s) | Total Distance (m) | Runtime (s) |
|---|---|---|---|---|---|
| watertaxi-1000 | NN | ||||
| watertaxi-1000 | CON | ||||
| watertaxi-1000 | 2OPT | ||||
| watertaxi-1000 | LS | ||||
| watertaxi-1000 | MH | ||||
| watertaxi-1000 | DY-R | ||||
| watertaxi-1000 | DY-15 | ||||
| watertaxi-1000 | DY-30 |
Files:
12.10 Deliverables
You will submit one repository per group containing:
- Your heuristic implementations, operable via the CLI.
- Your results file
results.csvcontaining all runs on benchmark and watertaxi instances. - Your run artifacts under
runs/(one folder per experiment containingroutes.csvat minimum). - A report documenting your implementation, results, and analysis (ICCL template).
- 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.
Results File (results.csv)
Produce one result row in results.csv per run with the following fields:
timestamp: the time when the run was executed.- Input fields:
experiment_name,instance_id,n_requests,n_vehicles,vehicle_capacity,max_ride_time_s(ormax_ride_ratio),method,seed. - KPIs:
n_rejected,n_carried_passengers,total_distance_m,vehicles_used,total_wait_s,total_ride_s,max_wait_s,max_ride_s,deadhead_distance_m,deadhead_time_s,makespan_s,total_drive_time_s,wall_clock_runtime_s. objective: objective mode used (same format as AS1).objective_value: final objective value achieved.
Repository Structure
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/
| `-- watertaxi/
| |-- network.json
| |-- watertaxi-1000.csv
| `-- (other instance files, the competition test set)
|-- reports/
| |-- src/
| | `-- ... (latex source files, figures, etc.)
| `-- tlm-as2-watertaxi-rotterdam-group-<your_group_id>.pdf
|-- tests/
| |-- __init__.py
| `-- ... (your test files)
|-- 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)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.
12.11 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_seqstarts at 0 for eachvehicle_idand increases by 1.node_typeis one ofSTART_DEPOT,PICKUP,DROPOFF,END_DEPOT.distance_prev_mandtravel_time_prev_sdescribe the leg from the previous stop to this stop (use 0 for the first stop of each vehicle).
vehicle_id,stop_seq,node_id,node_type,request_id,load_passengers,distance_prev_m,travel_time_prev_s,arrival_s,departure_stw_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.4841Read it like this:
- Vehicle 7 starts at depot node 10.
- It drives 180 s to pick up R12 at node 21 and arrives exactly at
tw_start_s. - It boards for 180 s and departs at 3780.
- It drives 240 s to drop off at node 44, services for 180 s, and returns.
12.12 Report
The report aims to:
- Explain the heuristics you implemented and how they work.
- Discuss the results of your heuristics on the Cordeau benchmarks and watertaxi instances.
- Derive managerial insights from your scenario analysis.
Your report should include the following sections:
- Introduction (max. 1 page):
- Briefly introduce the methods you implemented.
- Describe the experimental settings (e.g., computer specifications, Python version, etc.) in max. 3 sentences.
- Constructive Heuristic Algorithm (max. 1 page):
- Describe the constructive heuristic algorithm you developed (labeled as CON).
- Provide pseudocode for the algorithm.
- Local Search Algorithm (max. 1 page):
- Describe the local search algorithm you developed (labeled as LS).
- Provide pseudocode for the algorithm.
- Metaheuristic Algorithm (max. 2 pages):
- Describe the metaheuristic algorithm you developed (labeled as MH).
- Provide pseudocode for the algorithm.
- Dynamic Re-optimization Heuristic (max. 2 pages):
- Describe the dynamic re-optimization heuristic you developed (labeled as DY).
- Provide pseudocode for the algorithm.
- Results and Analysis (max. 2 page):
- Present the results of your heuristics on the Cordeau benchmarks in a structured table (see template in Table 12.4). Full results can be in the appendix; summary statistics in the main text.
- Present the results of your heuristics on the watertaxi instance in a structured table (see template in Table 12.5). Full results can be in the appendix; summary statistics in the main text (compare with the MH solution, the supposedly best static solution under perfect information).
- Water Taxi Managerial Scenario Analysis (max. 1 page):
- Motivate a “what-if” research question.
- Present KPI results across at least three levels (the default baseline + two variations) in a structured table.
- Discuss the practical implications for the operations.
- Explain the trade-offs involved and provide a clear recommendation for the operator based on your findings.
Charts, figures, etc., are welcome as long as the maximum page limit is respected.
12.13 Grading Criteria
Your assignment will be graded using the criteria below.
| # | Deliverable | Weight | Criteria |
|---|---|---|---|
| 1 | Constructive Algorithm (CON) | 10% | Correctness, Efficiency, Report, Coverage |
| 2 | Local Search Algorithm (LS) | 20% | Correctness, Efficiency, Report, Coverage |
| 3 | Meta-Heuristic of Your Choice | 30% | Correctness, Efficiency, Report, Creativity, Coverage |
| 4 | Dynamic Re-optimization Heuristic | 20% | Correctness, Efficiency, Report, Coverage |
| 5 | Managerial Scenario Analysis | 10% | Relevance and Depth of Analysis |
| 6 | Report | 10% | Quality of writing, clarity, and presentation |
The criteria for each individual deliverable are as follows:
- Correctness: The algorithm must generate feasible routes.
- Efficiency: The algorithm should beat their respective baselines (CON > NN, LS > 2OPT, MH > LS, DY > cheapest insertion) and run within the specified time limits.
- Creativity: The meta-heuristic algorithm should demonstrate creativity and innovation in tackling the routing problem. Creativity will be evaluated across the results of the class (A: top-tier = 100%, B: middle-tier = 80%, C: bottom-tier = 60%).
- Report: The report should clearly explain the design and implementation of the algorithm, as well as the results and insights derived from it.
- Coverage: The algorithm should be implemented and evaluated on both the DARP benchmarks and the watertaxi instance, demonstrating its applicability across different settings.
- Relevance and Depth of Analysis: The managerial scenario analysis should address a relevant and meaningful research question for the water taxi service.
- Quality of writing, clarity, and presentation: The report should be well-written, clear, and effectively communicate the methods, results, and insights within the page limit.
We will run your CLI to verify correctness, efficiency, and coverage. Please ensure your CLI works end-to-end.
12.14 Tips
A pragmatic development approach: Adopt an iterative strategy. First, get something working end-to-end, no matter how basic. Then, incrementally refine and improve.
Control randomness (seed): Controlling randomness with a seed is highly recommended for reproducibility. Otherwise, you cannot say with confidence whether an improvement came from your intervention or from a lucky draw. Consider repeating random-based methods multiple times to ensure consistent performance.
Time management in code: Time management must be done inside your algorithm. Use the
--time-limitargument to limit the runtime appropriately. When time expires, return the best solution found so far.
12.15 Recommended Reading
If you use randomness in your heuristics (e.g., in the constructive heuristic or metaheuristic), repeat the experiment at least 3 times with different random seeds. Report the seeds so your results are reproducible.↩︎