Multi Depot Heterogeneous Vehicle Routing Problem With Time Windows (MDHVRPTW)

General Overview

The Multi-Depot Heterogeneous Vehicle Routing with Time Windows problem is one of the most realistic and complex logistics challenges where multiple vehicles with different capabilities must serve customers from various depot locations while respecting strict time constraints. The aim is to design efficient routes that minimize costs while ensuring every delivery happens within the required time windows.

This model mirrors how modern delivery and service fleets operate, especially when managing diverse fleets across multiple locations with precise timing requirements.

---

Use Cases

Common real-world scenarios include:

• Retail and grocery distribution across multiple regional warehouses with delivery time commitments.
• Technician dispatching from various service centers to scheduled appointments.
• Urban delivery fleets combining trucks, vans, and bike couriers with customer time preferences.
• Municipal services like waste collection where different vehicle types serve districts on strict schedules.

In all of these, coordinating multiple depot locations, vehicle capabilities, and timing requirements reduces operational costs while maintaining service quality.

---

How It Works

This problem coordinates multiple vehicle types from different depot locations to serve customers within strict time windows while optimizing costs. Key points to pay attention to:

• Each job requires pickup and delivery locations with specific time windows
• Vehicles have different capabilities (capacity, costs, skills, operational hours)
• Multiple depot locations serve as starting and ending points for different vehicles
• Time windows must be respected for both jobs and vehicle availability
• Vehicle skills and restrictions must match job requirements
• Cost optimization considers fixed fees, per-km costs, and per-hour costs across vehicle types

---

General Validation

Before building or solving a MDHVRPTW request, confirm:

• There is at least one job defined.
• All jobs start from a valid depot.
• Pickup and delivery locations are unique and valid.
• All vehicles have start and end depots defined.
• Vehicle capacities, working hours, and skills match the job requirements.
• Time windows are consistent and do not overlap with vehicle availability.

---

Example

Scenario:

A company has two warehouses in different parts of a city, and a fleet composed of trucks and vans. Each vehicle starts and ends at its respective warehouse. The company must deliver products to customers within strict time windows—some require delivery between 9 AM and 11 AM, others between 2 PM and 5 PM.

Goal:

Design routes so that each vehicle departs from its own warehouse, deliveries respect customer time windows, vehicle capacities and operating costs are considered, and total travel distances and costs are minimized.

Minimal Example Payload:

{
  "vehicles": [
    {
      "id": "truck_1",
      "start": [41.0000, 28.9000],
      "end": [41.0000, 28.9000],
      "constraints": {
        "profile": "truck",
        "capacity": 100,
        "time_window": ["08:00:00", "18:00:00"],
        "per_km": 2000,
        "per_hour": 4000,
        "fixed": 5000,
        "max_distance": 80000,
        "max_tasks": 10
      }
    },
    {
      "id": "van_1",
      "start": [41.0500, 28.9500],
      "end": [41.0500, 28.9500],
      "constraints": {
        "profile": "car",
        "capacity": 50,
        "time_window": ["09:00:00", "17:00:00"],
        "per_km": 1000,
        "per_hour": 3000,
        "fixed": 3000,
        "max_distance": 60000,
        "max_tasks": 8
      }
    }
  ],
  "jobs": [
    {
      "id": "customer_1",
      "amount": 30,
      "start": {
        "coordinate": [41.0000, 28.9000],
        "setup": 300,
        "service": 600,
        "time_window": ["08:00:00", "18:00:00"]
      },
      "end": {
        "coordinate": [41.0100, 28.9100],
        "setup": 120,
        "service": 300,
        "time_window": ["09:00:00", "11:00:00"]
      },
      "priority": 50
    },
    {
      "id": "customer_2",
      "amount": 20,
      "start": {
        "coordinate": [41.0500, 28.9500],
        "setup": 240,
        "service": 480,
        "time_window": ["09:00:00", "17:00:00"]
      },
      "end": {
        "coordinate": [41.0600, 28.9600],
        "setup": 90,
        "service": 240,
        "time_window": ["14:00:00", "17:00:00"]
      },
      "priority": 50
    }
  ],
  "options": {
    "problem": "MDHVRPTW",
    "objective": "cost",
    "solver": "heuristic",
    "map": "geographic"
  }
}