Ortools Pickup Delivery Routing

Pickup And Delivery Routing

Use this skill when each job has related pickup and dropoff or delivery events that must be served together. Apply it after the base routing model has a time dimension and before solving.

Implementation Flow

1. Create one pickup node and one dropoff node per job.
2. Add same-vehicle and precedence constraints for every pair.
3. Apply the customer-facing time windows and service-time convention from the problem statement.
4. Choose optional-service handling: independent pairs, or connected request sets.
5. After solving, postprocess connected sets, rebuild route sequences if needed, and re-audit feasibility before counting served jobs or writing output.

Pair Structure

• Represent pickup and dropoff as separate service nodes connected by a shared job ID.
• Pickup demand is positive; dropoff demand is negative. Depot nodes have zero demand and zero service time.
• Add routing.AddPickupAndDelivery(pickup_index, dropoff_index) for each pair.
• Add explicit constraints for the actual business rules:
  • same vehicle: routing.VehicleVar(pickup_index) == routing.VehicleVar(dropoff_index)
  • pickup before dropoff: time_dimension.CumulVar(pickup_index) <= time_dimension.CumulVar(dropoff_index)

Time Windows And Service Times

• Apply customer time windows to the service event promised to the customer. Appointment and dial-a-ride problems often constrain dropoff arrival; pickup windows can be derived by subtracting direct pickup-to-dropoff travel time from the dropoff window.
• If a problem statement gives explicit pickup and dropoff time-window formulas, implement those formulas directly. Service time belongs in the time transit from a node to the next node; do not change the stated window formula to compensate for service time unless the problem explicitly says to.

Pair Constraint Skeleton

Use this pattern after adding the time dimension. It enforces the paired-service relationship for each job. Add optional-service logic separately after deciding whether jobs are independent pairs or members of connected request sets.

solver = routing.solver()

for job in jobs:
    pickup_index = manager.NodeToIndex(job.pickup_node)
    dropoff_index = manager.NodeToIndex(job.dropoff_node)

    routing.AddPickupAndDelivery(pickup_index, dropoff_index)
    solver.Add(routing.VehicleVar(pickup_index) == routing.VehicleVar(dropoff_index))
    solver.Add(time_dimension.CumulVar(pickup_index) <= time_dimension.CumulVar(dropoff_index))

    if job.dropoff_window is not None:
        low, high = job.dropoff_window
        time_dimension.CumulVar(dropoff_index).SetRange(low, high)
    if job.pickup_window is not None:
        low, high = job.pickup_window
        time_dimension.CumulVar(pickup_index).SetRange(low, high)

Optional And Connected Service

• First decide whether each optional job is independent or belongs to a connected request set. Independent jobs may be skipped on their own; connected request sets should be optimized as a group.
• For connected request sets, prefer the CP-style grouped disjunction pattern below when search quality matters. Treat it as a search-friendly relaxation: local search may keep partial groups, and postprocessing enforces the final all-or-none business rule.
• Some domains connect multiple pickup-delivery pairs for one passenger, order, shipment, or care plan. This is a special case: apply all-or-none handling only when the problem says a connected set must be fully served or fully rejected.
• For CP-style optional connected sets, put the set's pickup nodes in one disjunction with max_cardinality=len(request_set) and a very large group penalty, such as len(request_set) * request_penalty. This makes pickup service drive the served-job objective for the connected set.
• Add each corresponding dropoff node as optional with zero penalty. The pickup-delivery constraints still tie feasible served pairs together, while zero-penalty dropoff optionality avoids forcing orphan dropoffs when a pickup or connected set is skipped.
• Use this grouped-disjunction-plus-postprocessing pattern instead of hard equality constraints across the connected set when local search quality matters. Hard all-or-none constraints can make insertion and local search much harder on large optional pickup-delivery instances.
• This grouped-disjunction pattern may allow partial connected sets during search. If the domain treats partial connected sets as unserved, do not count partial sets as served; remove their service nodes and rebuild the route order, or reject the candidate if rebuilding breaks feasibility.

The complete modeling shape for connected optional pickup-delivery service is:

solver = routing.solver()

for job in jobs:
    pickup_index = manager.NodeToIndex(job.pickup_node)
    dropoff_index = manager.NodeToIndex(job.dropoff_node)
    routing.AddPickupAndDelivery(pickup_index, dropoff_index)
    solver.Add(routing.VehicleVar(pickup_index) == routing.VehicleVar(dropoff_index))
    solver.Add(time_dimension.CumulVar(pickup_index) <= time_dimension.CumulVar(dropoff_index))

for request_set in connected_request_sets:
    pickup_indices = [manager.NodeToIndex(job.pickup_node) for job in request_set]
    routing.AddDisjunction(
        pickup_indices,
        len(request_set) * request_penalty,
        len(request_set),
    )

for job in jobs:
    routing.AddDisjunction([manager.NodeToIndex(job.dropoff_node)], 0)