Pickup and Delivery Problem (PDP)

Every pickup location is strictly paired with a specific delivery location. A vehicle must visit both nodes in the pair to complete the service. This is fundamentally different from the Vehicle Routing Problem (VRP), where nodes are independent. In PDP, a request is an indivisible pair of stops.

• Example: A ride-hailing trip from Point A to Point B.
• Example: A cargo container moving from a port to a warehouse.
• Violation: Visiting a delivery node without first visiting its corresponding pickup node invalidates the solution.

For any given pair, the pickup location must be visited before the delivery location in the vehicle's route sequence. This temporal ordering is non-negotiable. The constraint ensures that goods are on board the vehicle before an attempt is made to unload them.

• Impact: This creates a directed dependency graph that solvers must respect.
• Complexity: Precedence dramatically increases the computational difficulty compared to unconstrained routing.

The load picked up at the origin must remain on the vehicle until it is dropped off at the destination. This dynamic loading profile means the vehicle's occupied capacity fluctuates along the route, not just at a single depot.

• Constraint: The total load of all active requests on a vehicle must never exceed its maximum capacity at any point.
• Planning: Solvers must track the on-board inventory state vector as a function of the route sequence.

Both the pickup and the delivery nodes can have independent hard or soft time windows. A feasible solution requires the vehicle to arrive within the allowed interval at both locations, factoring in the travel time between them.

• Hard Windows: The vehicle must wait if it arrives early; the solution is infeasible if it arrives late.
• Soft Windows: Late arrivals incur a penalty cost in the objective function.
• Coupling Effect: The pickup time window directly constrains the feasible arrival time at the delivery node.

In real-world PDPs, the fleet is rarely uniform. Vehicles have different capacities, equipment (e.g., refrigeration, tail lifts), and cost profiles. A valid assignment must match the physical requirements of the goods to the capabilities of the vehicle.

• Skill Matching: A hazardous material pickup requires a certified vehicle.
• Cost Optimization: Assigning a large truck to a small parcel is inefficient; the solver must balance fixed and variable vehicle costs.

Unlike the immediate transfer assumed in basic models, advanced PDP variants allow a vehicle to pick up a load and continue making other pickups or deliveries before dropping it off. This is known as interleaving.

• Benefit: Enables higher vehicle utilization and consolidation.
• Challenge: The state space explodes as the solver must track multiple active shipments simultaneously, making it a much harder optimization problem than the Dial-a-Ride Problem (DARP) where immediate delivery is often assumed.

Platforms like Uber and Lyft represent a massive-scale, real-time PDP where pairing (matching a specific rider to a specific driver) and precedence (pickup must occur before drop-off) are fundamental. The system must continuously solve a dynamic PDP, assigning new requests to a fleet of moving vehicles while minimizing waiting time and detours. Key constraints include vehicle capacity and real-time traffic conditions.

The transport of lab specimens, pharmaceuticals, and medical devices between hospitals, clinics, and labs is a critical PDP application. Time windows are rigid, and cold chain integrity must be maintained. A specimen pickup at a doctor's office is paired with a specific drop-off at a diagnostic lab, with strict precedence. Failure can lead to sample degradation and diagnostic delays.

LTL carriers consolidate multiple shipments from different shippers into a single trailer. This is a complex PDP where each shipment has a unique origin-destination pair. The optimization involves sequencing pickups and deliveries across a network of terminals to maximize trailer utilization while respecting individual delivery windows. A shipment picked up in Chicago for delivery in Dallas cannot be unloaded before its paired destination.

Services like Instacart and DoorDash operate a multi-echelon PDP. First, a shopper picks up items from a store (first pickup) and delivers them to a customer (first drop-off). In batch orders, a single driver handles multiple such paired tasks simultaneously. The system must enforce pairing (the correct groceries for the correct customer) and precedence (shop, then deliver) while managing perishable goods time constraints.

Delivering ready-mix concrete or steel beams to a job site is a PDP with hard physical constraints. Concrete, for example, has a limited shelf life (approx. 90 minutes) from batching (pickup) to pouring (delivery). The paired pickup at the batch plant and delivery to the specific pour site must be precisely sequenced. Delays violate the precedence constraint and result in material waste and project setbacks.

Municipal waste collection is a large-scale PDP where a vehicle picks up waste from a specific location (a bin) and delivers it to a paired disposal facility (a landfill or recycling center). Pairing ensures recyclables go to the correct material recovery facility, not a general landfill. Precedence dictates that collection must precede disposal. Route optimization minimizes fuel consumption and vehicle wear.