Pickup and Delivery Problem (PDP)

The defining characteristic of the PDP is the temporal ordering requirement. For every request, the pickup node must be visited before the delivery node on the same route. This transforms the problem from a simple sequencing task into a complex combinatorial challenge where inserting a new request requires validating that no existing precedence relationships are violated. Violations lead to infeasible routes where a vehicle arrives to deliver goods it has not yet collected.

Each transportation request consists of a coupled pair of locations: an origin and a destination. The same vehicle must service both nodes. This pairing constraint prevents solutions where one vehicle picks up a load and another delivers it, which would be valid in a standard Vehicle Routing Problem (VRP). Mathematically, this introduces linking constraints that tightly couple decision variables, significantly increasing the problem's computational complexity.

Unlike the Capacitated VRP where load monotonically decreases, PDP vehicle loads fluctuate dynamically. A vehicle's load increases at pickup nodes and decreases at delivery nodes. This creates a non-monotonic load profile along the route. Feasibility checks must verify that the vehicle's capacity is never exceeded at any point, requiring cumulative load tracking rather than a simple sum of total demand.

PDPs frequently incorporate hard time windows at both pickup and delivery locations. A request may specify a morning pickup window and an afternoon delivery window. The travel time between the paired nodes imposes a minimum time separation, while customer requirements impose a maximum ride time. Satisfying these intersecting temporal constraints while sequencing multiple requests on a single vehicle is a core algorithmic challenge.

The Dial-a-Ride Problem is the passenger-transport variant of the PDP. It introduces service quality constraints absent in freight PDPs:

• Maximum ride time: A passenger cannot be on board longer than a multiple of the direct travel time.
• Maximum wait time: Limits on how long a vehicle can idle before pickup. These constraints make DARP significantly more constrained than freight PDPs and are critical for paratransit and ride-sharing services.

PDPs are NP-hard, making exact solutions impractical for large instances. Common solution methods include:

• Adaptive Large Neighborhood Search (ALNS): Iteratively destroys and repairs parts of the solution, adapting operator selection based on performance.
• Mixed-Integer Linear Programming (MILP): Formulates the problem with binary decision variables for arc traversal and continuous variables for load and time tracking.
• Column Generation: Decomposes the problem into a master problem selecting routes and a pricing subproblem generating feasible PDP routes with negative reduced cost.

A specialized PDP variant focused on passenger transportation rather than goods. DARP adds stringent service quality constraints that are absent in cargo PDPs, including maximum ride time limits for each passenger and maximum deviation from direct travel time. The objective balances operator costs against user inconvenience, making it a multi-objective optimization challenge. Common in paratransit services and autonomous shuttle routing.

A declarative paradigm exceptionally well-suited for PDP's combinatorial complexity. Rather than specifying a step-by-step algorithm, you define variables, their domains, and the logical constraints between them. A solver then systematically prunes the search space using propagation algorithms. Constraint programming excels at handling the precedence constraints and time windows that define PDP, often outperforming mixed-integer programming on highly constrained instances.

A dominant metaheuristic for solving large-scale PDP instances where exact methods fail. ALNS iteratively destroys a portion of the current solution (e.g., removing random pickup-delivery pairs) and then repairs it using insertion heuristics. An adaptive layer tracks the performance of each destroy and repair operator, dynamically selecting the most effective ones. This self-tuning mechanism makes ALNS robust across diverse PDP variants without manual parameter tuning.

A critical constraint in time-sensitive PDP variants. Each pickup and delivery location has a defined hard or soft time interval within which service must begin. Hard windows render solutions infeasible if violated; soft windows incur a penalty cost. In PDP, time windows are paired—a delay at pickup cascades to the delivery window, requiring algorithms to propagate temporal constraints forward. This coupling dramatically increases the problem's computational difficulty.