Dial-a-Ride Problem (DARP)

A binding constraint that limits the total time a passenger spends inside the vehicle. This prevents circuitous detours that would otherwise be mathematically optimal for fleet efficiency but unacceptable for human comfort.

• Direct Ride Time: The theoretical minimum time if the vehicle traveled directly from pickup to drop-off.
• Maximum Deviation: Typically expressed as a multiplier of direct ride time (e.g., 1.5x) or an absolute cap (e.g., +30 minutes).
• Non-Linear Penalty: Violations incur steep, often exponential penalties in the objective function to ensure feasibility.

Hard or soft intervals defining the earliest and latest acceptable times for pickup and delivery events. Unlike cargo, passengers penalize both earliness and lateness asymmetrically.

• Hard Windows: The vehicle must arrive within the interval; early arrivals require waiting at the curb.
• Soft Windows: Violations are permitted but incur a cost, modeling real-world flexibility.
• Two-Sided Windows: Both pickup and drop-off have independent windows, creating a coupled temporal constraint that links the entire route.

A multi-dimensional constraint in DARP that goes beyond simple weight limits. Passenger vehicles must account for heterogeneous resource types simultaneously.

• Seated Capacity: Maximum number of passengers legally permitted to be seated.
• Wheelchair Positions: Dedicated securement locations that cannot be occupied by standard passengers.
• Mixed Fleet: Different vehicle types (sedan, van, accessible bus) with distinct capacity profiles are assigned based on passenger requirements.

A logical constraint ensuring that for each passenger request, the pickup event strictly occurs before the corresponding drop-off event, and both are served by the same vehicle.

• Coupled Stops: The pickup and drop-off form an indivisible pair; you cannot reassign one without the other.
• No Interleaving Violation: A passenger's drop-off cannot occur before their pickup, even if the vehicle visits other locations in between.
• Vehicle Consistency: The same vehicle that performs the pickup must perform the delivery, preventing handoffs.

A constraint limiting how long a vehicle can idle at a pickup location before the passenger boards. This prevents excessive early arrivals from degrading service perception.

• Curb-to-Curb Service: The model assumes the vehicle is ready when the passenger arrives; long waits indicate poor scheduling.
• Driver Schedule Impact: Excessive waiting reduces the effective utilization of the driver's shift and can violate labor regulations.
• Dynamic Adjustment: In real-time DARP, wait time limits influence whether a new request can be inserted into an existing route.

A global constraint on the total elapsed time from vehicle departure to return to depot, driven by driver shift limits and labor regulations rather than passenger comfort.

• Hours of Service: In many jurisdictions, commercial drivers are legally limited to a maximum driving window (e.g., 10 hours).
• Break Scheduling: Long routes must incorporate mandatory rest periods, adding complexity to the optimization.
• Depot Return: The vehicle must complete all assigned pickups and deliveries and return to the depot before the shift limit expires.

The broader optimization class from which DARP is derived. PDP models the transport of goods or passengers between specific paired origins and destinations, enforcing a strict precedence constraint—a pickup must occur before its corresponding delivery. Unlike standard VRPs that service single-point demands, PDPs manage paired transactions, making them the foundational structure for courier services, less-than-truckload shipping, and paratransit systems.

The canonical combinatorial optimization challenge that underpins all fleet routing. VRP seeks to determine the optimal set of routes for a fleet of vehicles to service a geographically dispersed set of customers, minimizing total travel cost while respecting constraints like vehicle capacity and route duration. DARP extends this by adding passenger-specific service quality metrics, transforming a pure logistics problem into one with a human-centric objective function.

A defining DARP constraint that limits the total time a passenger spends in the vehicle. This is not merely a time window but a service quality guarantee that prevents circuitous detours. Typically expressed as a ratio relative to the direct travel time, it ensures that shared-ride efficiency does not come at the cost of excessive individual inconvenience. Violating this constraint renders a solution infeasible, making it a hard constraint in exact methods.

A dominant metaheuristic for solving large-scale DARP instances in practice. ALNS iteratively improves a solution by destroying a portion of the route plan (removing passengers) and repairing it (reinserting them optimally). An adaptive layer tracks the performance of different destroy and repair heuristics, dynamically selecting the most effective operators. This self-tuning mechanism allows ALNS to escape local optima and handle the complex, tightly constrained search space of real-world paratransit operations.

Hard or soft intervals defining when a pickup or delivery must occur. In DARP, two distinct time windows govern each passenger: the desired pickup time and the desired drop-off time. Soft windows allow violations with a penalty cost, while hard windows render a solution infeasible if breached. The interplay between time windows and maximum ride time creates a tightly constrained temporal problem that distinguishes DARP from freight-oriented routing.

A declarative paradigm well-suited to DARP's feasibility-rich environment. Rather than specifying an algorithm, the modeler declares variables (arrival times, vehicle assignments), their domains, and the constraints (precedence, capacity, time windows). A solver uses propagation and search to prune infeasible assignments. This approach excels at finding any feasible solution in highly constrained dial-a-ride scenarios where optimization is secondary to simply meeting all passenger service guarantees.