🧩 Constraint Solving POTD:Problem of the Day: Dial-a-Ride Problem (DARP)

[github-actions[bot]]

Problem Statement

The Dial-a-Ride Problem is a variant of vehicle routing where you must serve a set of passenger requests, each with a pickup location and a delivery location. A fleet of vehicles must efficiently route to collect passengers and deliver them to their destinations, subject to:

• Vehicle capacity constraints (number of passengers or weight)
• Time window constraints at pickup and delivery locations
• Ride quality constraints (maximum ride time between pickup and delivery)
• Time constraints (e.g., drivers must complete all deliveries by end of shift)

Concrete Instance

Imagine 6 passenger requests in a city, 2 vehicles with capacity 3, and a service window from 8:00 AM to 5:00 PM:

Request	Pickup	Delivery	Time Window	Ride Limit
1	Downtown	Airport	8:00–9:00	20 min
2	Hospital	Home	9:00–12:00	30 min
3	Home	Shopping	10:00–13:00	25 min
4	Office	Hospital	8:30–11:30	20 min
5	Airport	Downtown	11:00–14:00	30 min
6	Shopping	Home	13:00–17:00	25 min

Goal: Find vehicle routes and schedules that serve all requests while minimizing total travel time, violations of time windows, or the number of vehicles.

Why It Matters

• Ride-hailing & demand-responsive transit: Companies like Uber, Lyft, and dial-a-bus systems use DARP to efficiently match drivers to passengers while honoring time preferences and service quality.
• Healthcare & social services: Non-emergency medical transportation and social service trips for elderly/disabled populations use DARP to coordinate pickups and deliveries with limited vehicles.
• Logistics & parcel delivery: Same-day delivery services with pickup and drop-off requirements solve DARP variants to optimize routes across urban zones.

Modeling Approaches

Approach 1: Mixed-Integer Programming (MIP)

Paradigm: Mathematical programming with binary and continuous variables.

Decision variables:

• x[i,j,v,t] = 1 if vehicle v travels directly from location i to j at time step t; 0 otherwise
• a[i,v] = arrival time of vehicle v at location i
• n[i,v] = net passenger load in vehicle v after visiting location i (positive for pickups, negative for deliveries)

Key constraints:

• Vehicle flow: Each request must have exactly one vehicle assigned
• Capacity: 0 ≤ n[i,v] ≤ capacity[v] at all locations
• Time windows: time_window_start[i] ≤ a[i,v] ≤ time_window_end[i]
• Ride time: a[delivery[r],v] - a[pickup[r],v] ≤ max_ride_time[r]
• Subtour elimination: Prevent disconnected cycles (standard TSP-like constraints)

Trade-offs:

• ✅ Exact optimal solutions possible (with solver like CPLEX, Gurobi)
• ❌ Scales poorly beyond ~50 requests (NP-hard core)
• ❌ Time-indexed formulation becomes large; arc-indexed versions are more compact

Approach 2: Constraint Programming (CP)

Paradigm: Logic-based search with rich global constraints.

Decision variables:

• succ[i] = next location visited after i in the route sequence
• vehicle[r] = which vehicle serves request r
• time[i] = arrival time at location i
• load[i] = passenger load after visiting i

Key constraints:

• Cumulative: Global constraint ensuring vehicle capacity is never violated along the route
• Circuit: Ensures each vehicle forms a valid cycle (home → pickups/deliveries → home)
• Disjunctive: Two pickups from same request cannot be separated if unassigned
• Element: Link successor variables to time array with travel-time lookup
• Custom propagators: Ride-time bounds, time-window consistency

Trade-offs:

• ✅ Richer propagation; CP can prune infeasibilities earlier
• ✅ Handles asymmetric travel times and complex time constraints naturally
• ❌ Slower on purely continuous-time versions (often requires discretization)
• ❌ Custom propagators needed for ride-time constraints to be effective

Example Model (MiniZinc Pseudo-code)

int: n = 12;  % 2 × (6 requests) + depot
int: m = 2;   % vehicles
int: depot = 0;
array[1..n] of int: is_pickup;  % 1 for pickup, -1 for delivery, 0 for depot
array[1..n] of int: paired_with;  % pairing: pickup[i] <-> delivery[paired_with[i]]

var 1..n: route[1..n];  % permutation of locations
var 1..m: vehicle_for_request[1..6];
var 0..1000: arrival[1..n];

% Each location visited exactly once (TSP-like)
constraint all_different(route);

% Time windows
constraint forall(i in 1..n)(
  time_window_start[i] <= arrival[route[i]] (n/redacted)  arrival[route[i]] <= time_window_end[i]
);

% Pickup must occur before delivery
constraint forall(req in 1..6)(
  let { int: p = pickup_location[req]; int: d = delivery_location[req]; } in
  position(route, p) < position(route, d)
);

% Ride time limit
constraint forall(req in 1..6)(
  let { int: p = pickup_location[req]; int: d = delivery_location[req]; } in
  arrival[d] - arrival[p] <= max_ride_time[req]
);

% Capacity constraints (simplified)
constraint cumulative(/* load profile */);

solve minimize sum(i in 1..n-1)(distance[route[i], route[i+1]]);

Key Techniques

1. Insertion Heuristics & Local Search

• Cheapest insertion: Start with a partial route and greedily insert unserved requests at positions that minimize detour
• 2-opt & 3-opt local search: Remove and reconnect route segments to escape local optima
• Often used as initial solutions for exact methods or as anytime algorithms for real-time systems

2. Time-Window Propagation & Forward-Backward Checking

• Forward pass: Compute earliest feasible arrival at each location given pickups must precede deliveries
• Backward pass: Compute latest feasible departure from each location to meet downstream time windows
• Dramatically reduces search space; tightens bounds on vehicle load and timing variables

3. Symmetry Breaking & Dominance

• Vehicle symmetry: Assign an arbitrary total ordering to vehicles to avoid exploring equivalent solutions
• Request grouping: Break ties by prioritizing high-time-window requests or those with tight ride limits
• Dominance pruning: If solution A serves a subset with lower cost than partial solution B, prune B

Challenge Corner

Question for you: Suppose you can offer incentives to passengers willing to adjust their time windows by up to 30 minutes (e.g., a 5% discount if they depart 15 minutes earlier). How would you model and solve this as a combined optimization and negotiation problem? Would you:

1. Enumerate all time-window variants and solve independent DARPs?
2. Extend the DARP model with a discount variable for each request?
3. Use a two-stage approach: first plan optimal routes, then identify which passengers could accept incentives to reduce cost?

Which approach scales best for 100 requests across 10 vehicles?

References

• Cordeau, J. F., Gendreau, M. (2007). "The Dial-a-Ride Problem: Models and Algorithms." Journal of the Operational Research Society, 58(4), 534–546.

• Parragh, S. N., Doerner, K. F., Hartl, R. F. (2008). "A Survey on Optimization Problems for Vehicle Routing and Logistics." Computers & Operations Research, 35(2), 490–510.

• Rossi, F., van Beek, P., Walsh, T. (Eds.). (2006). Handbook of Constraint Programming. Elsevier. [Chapter on Dynamic Routing and VRP variants]

• OR-Tools VRPTW Example: (developers.google.com/redacted)

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · ~8 AIC · ⌖ ~13 AIC · ⊞ 6.5K · ◷

• expires on Nov 1, 2026, 3:34 AM UTC-08:00

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #72076.