Vehicle Routing Problem (VRP)

General Overview

The Vehicle Routing Problem (VRP) extends the Traveling Salesman Problem by introducing multiple vehicles to handle a set of deliveries or service tasks. The main objective is to design routes for a fleet of vehicles so that all tasks are completed with minimum total distance, time, or cost, while respecting problem constraints.

This foundational problem serves as the basis for many real-world logistics scenarios where multiple vehicles must coordinate to serve customers efficiently from a central location.

---

Use Cases

Common real-world scenarios include:

• Courier companies distributing parcels with a fleet of delivery vans.
• Retail supply chains handling store replenishments across multiple locations.
• Municipal services like garbage collection or street cleaning operations.
• Food delivery companies optimizing routes for multiple drivers simultaneously.

In all of these, coordinating multiple vehicles reduces total travel time and operational costs while ensuring all customers receive service.

---

How It Works

This problem designs efficient routes for multiple vehicles serving customers from a central depot to minimize total travel cost while ensuring all customers are served. Key points to pay attention to:

• Multiple vehicles start and return to the same depot
• Each customer is visited exactly once
• All vehicles must have the same profile and characteristics
• All jobs start from the same location (depot)
• Each job must have unique end locations

---

General Validation

Before building or solving a VRP 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 jobs must have the 1 amount.
• The vehicles must have the same profile.

---

Example

Scenario:

A company has 3 delivery vans starting from the same depot and needs to deliver packages to 10 customers. Each vehicle can handle any customer, and there are no capacity limits.

Goal:

Design routes that minimize the total distance traveled by all vehicles combined while ensuring each customer is visited exactly once.

Minimal Example Payload:

{
  "vehicles": [
    {
      "id": "vehicle_1",
      "start": [0, 0],
      "end": [0, 0],
      "constraints": {
        "profile": "car",
        "per_km": 1000,
        "max_tasks": 5
      }
    },
    {
      "id": "vehicle_2",
      "start": [0, 0],
      "end": [0, 0],
      "constraints": {
        "profile": "car",
        "per_km": 1000,
        "max_tasks": 5
      }
    },
    {
      "id": "vehicle_3",
      "start": [0, 0],
      "end": [0, 0],
      "constraints": {
        "profile": "car",
        "per_km": 1000,
        "max_tasks": 5
      }
    }
  ],
  "jobs": [
    {
      "id": "job_1",
      "amount": 1,
      "start": {
        "coordinate": [0, 0]
      },
      "end": {
        "coordinate": [10, 10]
      }
    },
    {
      "id": "job_2",
      "amount": 1,
      "start": {
        "coordinate": [0, 0]
      },
      "end": {
        "coordinate": [15, 15]
      }
    },
    {
      "id": "job_3",
      "amount": 1,
      "start": {
        "coordinate": [0, 0]
      },
      "end": {
        "coordinate": [20, 5]
      }
    }
  ],
  "options": {
    "problem": "VRP",
    "objective": "distance",
    "solver": "heuristic",
    "map": "cartesian"
  }
}