Vehicle Routing Problem With Time Windows (VRPTW)

General Overview

The Vehicle Routing Problem with Time Windows (VRPTW) deals with planning routes for multiple vehicles so that deliveries or tasks are completed not only efficiently but also within specific time frames. Unlike basic route planning, every task must be completed during a set time window, making scheduling more realistic and practical.

This approach combines route optimization with strict timing requirements, ensuring that vehicles arrive at the right place at the right time while minimizing total travel costs.

---

Use Cases

Common real-world scenarios include:

• Delivery services that must meet customer availability times and preferences.
• Waste collection that must finish during permitted hours and noise regulations.
• Home healthcare visits scheduled for specific appointment times with patients.
• School buses or public transport that follow strict timetables and schedules.

In all of these, punctuality is as important as route efficiency, ensuring customer satisfaction while maintaining operational effectiveness.

---

How It Works

This problem creates vehicle routes that ensure all deliveries occur within specific time windows while minimizing travel costs and respecting timing constraints. Key points to pay attention to:

• Each job has a time window defining when service must occur
• All vehicles have defined working hours and operational schedules
• Vehicles start and return to the same depot location
• All vehicles must have the same profile, capacity, and time window
• Jobs start from the depot but end at unique customer locations
• Timing constraints must be respected for both jobs and vehicle availability

---

General Validation

Before building or solving a VRPTW 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.
• The vehicles must have the same profile.
• The vehicles must have the same capacity.
• The vehicles must have the same time window.

---

Example

Scenario:

A delivery company needs to deliver parcels to 20 customers. Each customer is only available to receive deliveries between certain hours (e.g., 9 AM to 11 AM, or 2 PM to 4 PM). There are 4 delivery trucks, each with a capacity limit.

Goal:

Plan routes so that each customer is visited exactly once and within their time window, no truck exceeds its capacity, all trucks start and end at the warehouse, and the total driving distance is as short as possible while respecting time constraints.

Minimal Example Payload:

{
  "vehicles": [
    {
      "id": "truck_1",
      "start": [0, 0],
      "end": [0, 0],
      "constraints": {
        "profile": "truck",
        "capacity": 100,
        "time_window": ["08:00:00", "18:00:00"],
        "per_km": 1500,
        "per_hour": 4000,
        "max_travel_time": 32400
      }
    },
    {
      "id": "truck_2",
      "start": [0, 0],
      "end": [0, 0],
      "constraints": {
        "profile": "truck",
        "capacity": 100,
        "time_window": ["08:00:00", "18:00:00"],
        "per_km": 1500,
        "per_hour": 4000,
        "max_travel_time": 32400
      }
    },
    {
      "id": "truck_3",
      "start": [0, 0],
      "end": [0, 0],
      "constraints": {
        "profile": "truck",
        "capacity": 100,
        "time_window": ["08:00:00", "18:00:00"],
        "per_km": 1500,
        "per_hour": 4000,
        "max_travel_time": 32400
      }
    }
  ],
  "jobs": [
    {
      "id": "customer_1",
      "amount": 5,
      "start": {
        "coordinate": [0, 0],
        "setup": 180,
        "service": 300,
        "time_window": ["08:00:00", "18:00:00"]
      },
      "end": {
        "coordinate": [5, 4],
        "setup": 60,
        "service": 240,
        "time_window": ["09:00:00", "11:00:00"]
      }
    },
    {
      "id": "customer_2",
      "amount": 4,
      "start": {
        "coordinate": [0, 0],
        "setup": 180,
        "service": 300,
        "time_window": ["08:00:00", "18:00:00"]
      },
      "end": {
        "coordinate": [7, 8],
        "setup": 75,
        "service": 220,
        "time_window": ["09:00:00", "11:00:00"]
      }
    },
    {
      "id": "customer_3",
      "amount": 6,
      "start": {
        "coordinate": [0, 0],
        "setup": 180,
        "service": 300,
        "time_window": ["08:00:00", "18:00:00"]
      },
      "end": {
        "coordinate": [15, 5],
        "setup": 90,
        "service": 300,
        "time_window": ["14:00:00", "16:00:00"]
      }
    },
    {
      "id": "customer_4",
      "amount": 8,
      "start": {
        "coordinate": [0, 0],
        "setup": 180,
        "service": 300,
        "time_window": ["08:00:00", "18:00:00"]
      },
      "end": {
        "coordinate": [18, 7],
        "setup": 120,
        "service": 360,
        "time_window": ["14:00:00", "16:00:00"]
      }
    }
  ],
  "options": {
    "problem": "VRPTW",
    "objective": "distance",
    "solver": "heuristic",
    "map": "cartesian"
  }
}