Capacitated Vehicle Routing Problem (CVRP)

General Overview

The Capacitated Vehicle Routing Problem (CVRP) defines a delivery planning challenge where a fleet of vehicles with limited carrying capacity must deliver goods to a set of customers optimally. The primary aim is to design routes so that each customer is visited exactly once, while ensuring vehicle capacity limits are not exceeded and total travel distance or cost is minimized.

This problem extends basic vehicle routing by introducing capacity constraints, making it more realistic for real-world logistics operations where vehicles have physical limitations.

---

Use Cases

Common real-world scenarios include:

• Supply chain and logistics management for last-mile delivery operations.
• E-commerce deliveries requiring efficient parcel distribution with load limits.
• Waste collection services where garbage trucks have limited volume capacity.
• Postal and utility services operating daily planned routes with weight restrictions.

In all of these, careful management of vehicle capacity ensures efficient resource utilization while meeting all customer demands.

---

How It Works

This problem creates optimal routes for capacity-constrained vehicles to serve customers while ensuring no vehicle exceeds its carrying capacity limit. Key points to pay attention to:

• At least one job must be defined
• Each job is visited exactly once
• Each job has specific demand requirements (e.g., number of packages)
• All jobs start from the same location (depot)
• Vehicles start and return to the depot (closed routes)
• Each vehicle has a capacity limit
• All vehicles must have the same profile (speed, travel cost, etc.)

---

General Validation

Before building or solving a CVRP request, confirm:

• The jobs list must contain at least one job.
• The jobs must have the same start location.
• The jobs must have unique end locations.
• The vehicles must have the same start location.
• The vehicles must have the same start location as the jobs.
• The vehicles must return to start location.
• The vehicles must have the same profile.
• The vehicles must have the same capacity.

---

Example

Scenario:

A delivery company has 3 vehicles with capacity limits and needs to deliver packages to 5 customers. Each customer has a specific demand (number of packages), and vehicles must start and end at the central depot.

Goal:

Design routes that ensure each customer is served exactly once, the load on each vehicle's route cannot exceed its capacity, and the total cost or travel distance is minimized.

Minimal Example Payload:

{
  "vehicles": [
    {
      "id": "vehicle_1",
      "start": [0, 0],
      "end": [0, 0],
      "constraints": {
        "profile": "car",
        "capacity": 15,
        "per_km": 1000,
        "per_hour": 3600,
        "max_travel_time": 28800
      }
    },
    {
      "id": "vehicle_2",
      "start": [0, 0],
      "end": [0, 0],
      "constraints": {
        "profile": "car",
        "capacity": 15,
        "per_km": 1000,
        "per_hour": 3600,
        "max_travel_time": 28800
      }
    },
    {
      "id": "vehicle_3",
      "start": [0, 0],
      "end": [0, 0],
      "constraints": {
        "profile": "car",
        "capacity": 15,
        "per_km": 1000,
        "per_hour": 3600,
        "max_travel_time": 28800
      }
    }
  ],
  "jobs": [
    {
      "id": "job_1",
      "amount": 5,
      "start": {
        "coordinate": [0, 0]
      },
      "end": {
        "coordinate": [10, 15],
        "service": 240
      }
    },
    {
      "id": "job_2",
      "amount": 7,
      "start": {
        "coordinate": [0, 0]
      },
      "end": {
        "coordinate": [20, 10]
      }
    },
    {
      "id": "job_3",
      "amount": 3,
      "start": {
        "coordinate": [0, 0]
      },
      "end": {
        "coordinate": [10, 25]
      }
    },
    {
      "id": "job_4",
      "amount": 4,
      "start": {
        "coordinate": [0, 0]
      },
      "end": {
        "coordinate": [25, 18]
      }
    }
  ],
  "options": {
    "problem": "CVRP",
    "objective": "distance",
    "solver": "heuristic",
    "map": "cartesian"
  }
}