Pickup And Delivery Problem (PDP)

General Overview

The Pickup and Delivery Problem (PDP) involves planning routes where items, goods, or people are picked up at one location and delivered to another specific destination. Each task includes two linked parts: a pickup point and a delivery point that must be visited in the correct sequence.

This kind of routing is common in parcel delivery, ride-sharing, and freight transport, where what is collected must also be dropped off at the correct destination while maintaining efficient route planning.

---

Use Cases

Common real-world scenarios include:

• Couriers collecting parcels from senders and delivering to specific recipients.
• Ride-sharing services matching drivers to passengers' pickup and drop-off points.
• Technicians transporting equipment between designated sites.
• Recycling collection where materials are picked up and transported to processing centers.

In all of these, proper sequencing of pickups before deliveries ensures service quality while minimizing travel time and operational costs.

---

How It Works

This problem plans routes where items must be picked up at one location and delivered to a specific destination, ensuring correct pickup-delivery sequencing. Key points to pay attention to:

• Each job consists of linked pickup and delivery tasks that must be served in order
• Pickup must occur before delivery for each shipment
• All vehicles must have identical profiles, capacities, and time windows
• Vehicles start and end at the same depot location
• Job pickup and delivery locations cannot be at the depot
• Time windows can be defined for both pickup and delivery phases

---

General Validation

Before building or solving a PDP request, confirm:

• The jobs list must contain at least one job.
• The vehicles must have the same start location.
• The vehicles must have the same end location.
• The vehicles must return to start location.
• The vehicles must have the same profile.
• The vehicles must have the same capacity.
• The vehicles must have the same time window.
• The jobs must have different start and end locations.
• The job pickup locations cannot be at the depot.
• The job delivery locations cannot be at the depot.

---

Example

Scenario:

A courier company must pick up packages from several customers and deliver them to specified addresses. Each package must be collected first before being dropped off. The company has three delivery vans, all operating between 8 AM and 6 PM with the same capacity.

Goal:

Find routes that ensure each pickup is scheduled before its corresponding delivery, vehicle capacities are not exceeded, deliveries happen within the allowed time windows, and total travel distance and cost are minimized.

Minimal Example Payload:

{
  "vehicles": [
    {
      "id": "van_1",
      "start": [0, 0],
      "end": [0, 0],
      "constraints": {
        "profile": "car",
        "capacity": 50,
        "time_window": ["08:00:00", "18:00:00"],
        "per_km": 1000,
        "per_hour": 3600,
        "max_travel_time": 36000,
        "max_tasks": 6
      }
    },
    {
      "id": "van_2",
      "start": [0, 0],
      "end": [0, 0],
      "constraints": {
        "profile": "car",
        "capacity": 50,
        "time_window": ["08:00:00", "18:00:00"],
        "per_km": 1000,
        "per_hour": 3600,
        "max_travel_time": 36000,
        "max_tasks": 6
      }
    },
    {
      "id": "van_3",
      "start": [0, 0],
      "end": [0, 0],
      "constraints": {
        "profile": "car",
        "capacity": 50,
        "time_window": ["08:00:00", "18:00:00"],
        "per_km": 1000,
        "per_hour": 3600,
        "max_travel_time": 36000,
        "max_tasks": 6
      }
    }
  ],
  "jobs": [
    {
      "id": "package_1",
      "amount": 10,
      "start": {
        "coordinate": [5, 5],
        "time_window": ["09:00:00", "11:00:00"],
        "setup": 120,
        "service": 300
      },
      "end": {
        "coordinate": [10, 15],
        "time_window": ["09:00:00", "11:00:00"],
        "setup": 120,
        "service": 180
      }
    },
    {
      "id": "package_2",
      "amount": 15,
      "start": {
        "coordinate": [8, 3],
        "setup": 150,
        "service": 360,
        "time_window": ["09:00:00", "11:00:00"],
      },
      "end": {
        "coordinate": [15, 20],
        "setup": 90,
        "service": 240,
        "time_window": ["10:00:00", "13:00:00"]
      }
    },
    {
      "id": "package_3",
      "amount": 20,
      "start": {
        "coordinate": [12, 7],
        "setup": 180,
        "service": 420,
        "time_window": ["14:00:00", "17:00:00"]
      },
      "end": {
        "coordinate": [20, 25],
        "setup": 120,
        "service": 300,
        "time_window": ["14:00:00", "17:00:00"]
      }
    }
  ],
  "options": {
    "problem": "PDP",
    "objective": "distance",
    "solver": "heuristic",
    "map": "cartesian"
  }
}