🧩 Constraint Solving POTD:Pickup and Delivery Problem (PDP) — Routing with Paired Requests

[github-actions[bot]]

Today's category: Routing | Date: 2026-03-26

---

Problem Statement

The Pickup and Delivery Problem (PDP) asks: given a fleet of vehicles and a set of transportation requests, find minimum-cost routes such that each request is picked up at one location and delivered to another, with all vehicle capacity and ordering constraints respected.

Concrete Instance (5 requests, 2 vehicles)

Depot: node 0
Vehicles: 2, each with capacity 3
Requests (pickup node → delivery node, demand):
  R1: node 1 → node 6,  demand 1
  R2: node 2 → node 7,  demand 2
  R3: node 3 → node 8,  demand 1
  R4: node 4 → node 9,  demand 1
  R5: node 5 → node 10, demand 2
```

**Goal**: Assign each request to a vehicle and sequence visits so that:
1. Each vehicle starts and ends at the depot (node 0)
2. For every request `Ri`, the vehicle visits pickup node `i` **before** delivery node `i+5`
3. Vehicle load never exceeds capacity
4. Total travel distance is minimized

A valid solution might assign {R1, R2, R3} to Vehicle 1 (route: 0→1→2→6→7→3→8→0) and {R4, R5} to Vehicle 2 (route: 0→4→5→9→10→0).

**Input**: Distance matrix `d[i][j]`, requests `(p_i, d_i, q_i)` (pickup, delivery, demand), vehicle capacity `Q`.  
**Output**: A route per vehicle visiting paired pickups before deliveries.

---

### Why It Matters

- **Ride-hailing & dial-a-ride**: Every Uber/Lyft or paratransit system is essentially a PDP — passengers are paired origin-destination requests assigned to drivers in real time.
- **Last-mile logistics**: Courier services with returns (pick up from customer, deliver to warehouse) and direct shipments both fit the PDP structure, making it central to e-commerce logistics.
- **Healthcare transport**: Hospital patient transfers and blood/organ logistics require strict precedence (pickup before delivery) with tight time windows and capacity limits.

---

### Modeling Approaches

#### Approach 1 — Constraint Programming (CP)

**Decision variables**:
- `next[i]` — successor of node `i` in the route (circuit representation)
- `vehicle[i]` — which vehicle serves node `i`
- `position[i]` — sequence position of node `i`
- `load[i]` — cumulative load when leaving node `i`

**Key constraints**:
```
// Pairing: same vehicle for pickup and delivery
vehicle[p_i] = vehicle[d_i]   for all i

// Precedence: pickup before delivery on the route
position[p_i] < position[d_i]  for all i

// Capacity (running load)
load[p_i] = load[prev(p_i)] + q_i
load[d_i] = load[prev(d_i)] - q_i
0 ≤ load[i] ≤ Q

// Route structure: circuit per vehicle
circuit(next[i] : i ∈ vehicle_k_nodes)  for each vehicle k
```

The global `circuit` constraint enforces Hamiltonian path structure and enables powerful propagation. The `position` variable makes precedence linear.

**Trade-offs**: CP excels at proving optimality on small–medium instances; propagation on `circuit` + precedence prunes heavily but search space grows exponentially with request count.

---

#### Approach 2 — Mixed-Integer Programming (MIP)

Uses a **three-index arc-flow** formulation:

**Decision variables**:
- `x_{ijk} ∈ {0,1}` — vehicle `k` traverses arc `(i,j)`
- `t_{ik}` — arrival time of vehicle `k` at node `i` (for time-window extensions)

**Key constraints**:
```
// Flow conservation at each node
∑_j x_{ijk} = ∑_j x_{jik} = y_{ik}   (vehicle k visits node i)

// Pairing on same vehicle
y_{p_i, k} = y_{d_i, k}   for all i, k

// Precedence via subtour elimination (MTZ-style)
u_{p_i, k} + 1 ≤ u_{d_i, k}   (pickup position < delivery position)

// Capacity
∑_i q_i · y_{ik} ≤ Q   (aggregate; tighter with running-load constraints)

// Objective
min ∑_{i,j,k} d[i][j] · x_{ijk}

Trade-offs: MIP has strong LP relaxation bounds; branch-and-cut with valid inequalities (subtour, pairing cuts) solves real-world instances well. However, the model size is O(n² · K) binary variables, which is expensive for large n.

---

Approach 3 — Local Search / Large Neighborhood Search (LNS)

Practical large-scale solvers use metaheuristics on top of a feasible solution:

• Represent each solution as a sequence of nodes per vehicle
• Operators: relocate a request (move pickup+delivery pair to another vehicle/position), swap two requests between vehicles, or apply 3-opt moves respecting precedence
• LNS: repeatedly destroy (remove k random requests) and repair (reinsert with a greedy/CP sub-solver) the solution

Trade-offs: Scales to thousands of requests; no optimality guarantee but finds high-quality solutions quickly. The destroy-repair cycle respects pairing naturally by treating each request as an atomic unit.

Example Model (MiniZinc CP Sketch)

include "circuit.mzn";

int: n_req;                   % number of requests
int: n_nodes = 2*n_req + 2;   % pickup nodes, delivery nodes, 2 depots
int: n_vehicles;
int: capacity;

array[1..n_nodes] of int: demand;  % positive at pickup, negative at delivery
array[1..n_nodes, 1..n_nodes] of int: dist;

% next[i]: successor of node i in the unified route
array[1..n_nodes] of var 1..n_nodes: next;
array[1..n_nodes] of var 1..n_nodes: position;
array[1..n_nodes] of var 0..capacity: load;
array[1..n_nodes] of var 1..n_vehicles: vehicle;

% Each vehicle forms a circuit through its assigned nodes + depot
constraint circuit(next);

% Pairing: pickup i and delivery i+n_req on same vehicle
constraint forall(i in 1..n_req)(
  vehicle[i] = vehicle[i + n_req]
);

% Precedence: pickup before delivery
constraint forall(i in 1..n_req)(
  position[i] < position[i + n_req]
);

% Load propagation (simplified)
constraint forall(i in 1..n_nodes)(
  load[next[i]] = load[i] + demand[next[i]]
);
constraint forall(i in 1..n_nodes)(load[i] >= 0);

solve minimize sum(i in 1..n_nodes)(dist[i, next[i]]);

---

Key Techniques

1. Pairing Propagation

The pairing constraint (vehicle[p_i] = vehicle[d_i]) interacts with capacity and route-length constraints. CP solvers can propagate this eagerly: if placing pickup p_i on vehicle k would make the delivery unreachable (capacity exceeded, route too long), both are pruned simultaneously.

2. Precedence-Based Dominance

In branch-and-bound, any partial route where a delivery appears before its pickup can be pruned immediately — no completion can be feasible. This makes precedence constraints extremely effective at cutting the search tree, especially combined with position-based bounds.

3. Request-Level LNS (Shaw Removal)

Paul Shaw's relatedness-based removal heuristic selects requests to remove based on similarity (nearby pickups, overlapping time windows, same vehicle in the current solution). Reinserting related requests tends to find improving moves faster than random removal, making LNS highly effective for large PDP instances.

---

Challenge Corner

Think about it: The classic PDP assumes a homogeneous fleet. How would you extend the model if each vehicle has a different capacity and a maximum route duration limit?

Specifically: can you formulate a single MIP constraint that simultaneously enforces capacity and duration limits without doubling the number of arc variables? What valid inequalities would you add to strengthen the LP relaxation?

Bonus: The pairing constraint creates a natural symmetry — swapping all pickups and deliveries of two vehicles gives an equivalent solution if the vehicles are identical. What symmetry-breaking constraints eliminate this redundancy, and how do they interact with the LNS search?

---

References

1. Parragh, Doerner & Hartl (2008) — A Survey on Pickup and Delivery Problems (Journal of Business Economics) — comprehensive taxonomy of PDP variants.
2. Ropke & Pisinger (2006) — An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows (Transportation Science) — the seminal LNS paper for PDP.
3. Berbeglia, Cordeau & Laporte (2010) — Dynamic Pickup and Delivery Problems (European Journal of Operational Research) — covers online/dynamic variants.
4. Hooker, J.N. (2011) — Integrated Methods for Optimization — Chapter 9 covers hybrid CP/MIP for routing problems including PDP structure.

AI generated by Constraint Solving — Problem of the Day · history

• expires on Apr 2, 2026, 12:56 PM UTC

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #23233.