Dial-a-Ride Problem (DARP)

Unlike standard Vehicle Routing Problems, DARP enforces a strict precedence constraint. A user's pickup location must be visited before their associated delivery location by the same vehicle. This pairing prevents logical errors where a passenger is dropped off before being picked up, requiring sophisticated constraint programming to maintain route feasibility.

DARP operates under hard time windows for both pickup and delivery. A vehicle must arrive at the pickup location within a user-specified interval (e.g., 8:00–8:15 AM) and reach the destination within a promised window. Violating these windows is infeasible, making temporal constraints the primary driver of solution complexity.

A defining quality-of-service metric in passenger DARP is the maximum user ride time. The algorithm must ensure that the total time a passenger spends in the vehicle does not exceed a threshold relative to the direct travel time. This prevents circuitous detours and ensures service quality, adding a non-linear constraint to the optimization.

DARP models often incorporate heterogeneous fleets with varying capacities and accessibility features (e.g., wheelchair-accessible vans). The optimization must match specific user requirements to appropriate vehicle types. Capacity is measured in seats or wheelchair slots, and the load must never exceed the vehicle's limit at any point along the route.

• Static DARP: All trip requests are known in advance, allowing for global optimization before the operating day begins.
• Dynamic DARP: Requests arrive in real-time throughout the day. The algorithm must immediately decide whether to accept or reject a trip and insert it into an existing route, requiring fast re-optimization heuristics like Adaptive Large Neighborhood Search (ALNS).

DARP optimization balances conflicting objectives on a Pareto Frontier. The primary goals include minimizing total fleet travel distance and maximizing the number of served requests, while minimizing user ride time and waiting time. A common approach is to minimize a weighted sum of operator costs and user inconvenience, treating excessive ride time as a soft penalty or hard constraint.

The broader class of routing problems to which DARP belongs. PDP requires goods or passengers to be transported between specific pickup and delivery locations, enforcing pairing (a single vehicle handles both) and precedence (pickup must occur before delivery) constraints. DARP is essentially a PDP with strict passenger-centric time windows and ride-time limits.

The foundational combinatorial optimization challenge of determining optimal routes for a fleet of vehicles servicing geographically dispersed customers. DARP extends the VRP by adding simultaneous pickup and delivery operations, user-specific time windows, and maximum ride-time constraints that prevent excessively long passenger journeys.

A VRP variant where each service location must be visited within a hard or soft time interval. DARP inherits this constraint but applies it bidirectionally: both the pickup and the delivery must occur within the passenger's specified windows. Violating a time window in DARP directly degrades the quality of service for a specific individual.

A dominant metaheuristic for solving DARP instances. LNS iteratively destroys a portion of the current solution (e.g., removing several passengers from their routes) and then repairs it by reinserting them optimally. This allows the algorithm to escape local optima by making large structural changes to the routing plan in each iteration.

DARP is inherently multi-objective, requiring trade-offs between conflicting goals:

• Minimize fleet size and total vehicle distance
• Maximize passenger convenience (minimize ride time and waiting)
• Maximize on-time performance Solutions are evaluated on a Pareto frontier, where improving one objective necessarily degrades another.

A machine learning system critical to real-world DARP execution. While the optimization algorithm plans routes, the ETA engine provides accurate travel time predictions by analyzing historical traffic patterns, real-time congestion, and driver behavior. This ensures the time windows used in the DARP model reflect ground-truth conditions rather than optimistic estimates.