Vehicle Routing Problem With Heterogeneous Fleet (VRPH)

General Overview

The Vehicle Routing Problem with Heterogeneous Fleet (VRPH) involves planning routes for fleets consisting of different types of vehicles rather than identical ones. Some vehicles have larger capacities, move faster, operate only within specific hours, or require special skills to complete certain tasks.

This approach focuses on efficient route planning while considering the important differences between vehicle capabilities, costs, and operational constraints to maximize fleet utilization.

---

Use Cases

Common real-world scenarios include:

• Mixed fleet deliveries where trucks, vans, and bikes work together, each assigned tasks based on capacity and cost.
• Specialized services requiring certified drivers or special handling matched to the right vehicle.
• Municipal operations like waste collection with different vehicle types assigned to specific districts.
• Cost optimization scenarios choosing between expensive high-capacity vehicles and cheaper smaller ones.

In all of these, matching the right vehicle type to appropriate tasks reduces operational costs while maintaining service quality.

---

How It Works

This problem optimizes routes using vehicles with different capabilities, capacities, and costs to match the right vehicle type to appropriate tasks. Key points to pay attention to:

• Vehicles have different characteristics (capacity, costs, skills, availability)
• Vehicle skills must match job requirements for specialized tasks
• All vehicles start and end at the same depot location
• Jobs may require specific vehicle capabilities or certifications
• Cost optimization considers different vehicle types and their operational costs
• Vehicle limits (distance, time, number of jobs) must be respected

---

General Validation

Before building or solving a VRPH request, confirm:

• The jobs list must contain at least one job.
• The start location of the vehicles must be in the start location of the jobs.
• 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.

---

Example

Scenario:

A delivery company has three different vehicles: a large truck, a small van, and a bike courier. Each vehicle has different capacity limits, cost rates, and time availabilities. The company needs to deliver packages from a warehouse to various customers, with some deliveries requiring special handling skills available only with the van driver.

Goal:

Create routes that ensure each package is delivered on time, the right vehicle with the right capacity and skills serves each job, and total operational costs are minimized.

Minimal Example Payload:

{
  "vehicles": [
    {
      "id": "large_truck",
      "start": [0, 0],
      "end": [0, 0],
      "constraints": {
        "profile": "truck",
        "capacity": 50,
        "time_window": ["07:00:00", "19:00:00"],
        "per_km": 1500,
        "per_hour": 2000,
        "fixed": 500,
        "max_tasks": 8
      }
    },
    {
      "id": "small_van",
      "start": [0, 0],
      "end": [0, 0],
      "constraints": {
        "profile": "car",
        "capacity": 20,
        "time_window": ["08:00:00", "18:00:00"],
        "per_km": 1000,
        "per_hour": 1500,
        "fixed": 200,
        "max_tasks": 6
      }
    },
    {
      "id": "bike_courier",
      "start": [0, 0],
      "end": [0, 0],
      "constraints": {
        "profile": "car",
        "capacity": 5,
        "time_window": ["09:00:00", "17:00:00"],
        "max_distance": 20000,
        "per_km": 500,
        "per_hour": 500,
        "fixed": 50,
        "max_tasks": 4
      }
    }
  ],
  "jobs": [
    {
      "id": "job_1",
      "amount": 10,
      "start": {
        "coordinate": [0, 0],
        "setup": 300,
        "service": 600,
        "time_window": ["07:00:00", "19:00:00"]
      },
      "end": {
        "coordinate": [5, 10],
        "setup": 120,
        "service": 240,
        "time_window": ["09:00:00", "12:00:00"]
      }
    },
    {
      "id": "job_2",
      "amount": 15,
      "start": {
        "coordinate": [0, 0],
        "setup": 300,
        "service": 600,
        "time_window": ["07:00:00", "19:00:00"]
      },
      "end": {
        "coordinate": [10, 15],
        "setup": 180,
        "service": 300,
        "time_window": ["10:00:00", "14:00:00"]
      }
    },
    {
      "id": "job_3",
      "amount": 3,
      "start": {
        "coordinate": [0, 0],
        "setup": 300,
        "service": 600,
        "time_window": ["07:00:00", "19:00:00"]
      },
      "end": {
        "coordinate": [12, 5],
        "setup": 60,
        "service": 180,
        "time_window": ["13:00:00", "16:00:00"]
      }
    }
  ],
  "options": {
    "problem": "VRPH",
    "objective": "cost",
    "solver": "heuristic",
    "map": "cartesian"
  }
}