Capacitated Vehicle Routing Problem with Time Windows (CVRPTW)¶

Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) environment is the inherient type of problem from CVRP. At each step, the agent chooses a customer to visit depending on the current location, the remaining capacity, and the service time. When the agent visits a customer, the remaining capacity is updated and there requires a service time. If the remaining capacity is not enough to visit any customer, the agent must go back to the depot. If the agent arrives at one customer before the starting of the service time, it has to wait until the starting time. The agent can not visit a customer outside the time windows. The cost is the length of the path.

Observations

• location of the depot.
• locations and demand of each customer.
• current location of the vehicle.
• the remaining customer of the vehicle.
• the current time.
• service durations of each location.
• time windows of each location.

Constrains

• the tour starts and ends at the depot.
• each customer must be visited exactly once.
• the vehicle cannot visit customers exceed the remaining customer.
• the vehicle can return to the depot to refill the customer.
• the vehicle must start the service within the time window of each location.

Finish Condition

• the vehicle has visited all customers and returned to the depot.

Reward

• (minus) the negative length of the path.

In [31]:

import random
import numpy as np
import os
import requests

# load .env file with API key. Alternatively, set the API key
# as OAASIS_API_KEY="..."
from dotenv import load_dotenv; load_dotenv() 

import random import numpy as np import os import requests # load .env file with API key. Alternatively, set the API key # as OAASIS_API_KEY="..." from dotenv import load_dotenv; load_dotenv()

Out[31]:

True

Generate Problem Data¶

In [32]:

json_data = {}

num_visits = 10
num_vehicles = 3

json_data = {} num_visits = 10 num_vehicles = 3

Set Coordinates of depot and visits¶

In [33]:

from datetime import datetime

# Depot
depot = {
    "name": "depot_1", 
    "index": 0, 
    "coordinate": {
        "lng": random.uniform(126.734, 127.269), # Longitude range of Seoul
        "lat": random.uniform(37.413, 37.715), # Latitude range of Seoul
    },
}
json_data["depot"] = depot

# Visits with time windows
visits = [
    {
        "name": f"visit_{visit_idx + 1}",
        "index": visit_idx + 1,
        "coordinate": {
            "lng": random.uniform(126.734, 127.269), # Longitude range of Seoul
            "lat": random.uniform(37.413, 37.715), # Latitude range of Seoul
        },
        "time_window": [
            datetime(2026, 7, 30, 0, 0, 0).isoformat(),
            datetime(2026, 7, 31, 23, 0, 0).isoformat()
        ],
        "volume": 10,
    }
    for visit_idx in range(num_visits)
]
json_data["visits"] = visits

from datetime import datetime # Depot depot = { "name": "depot_1", "index": 0, "coordinate": { "lng": random.uniform(126.734, 127.269), # Longitude range of Seoul "lat": random.uniform(37.413, 37.715), # Latitude range of Seoul }, } json_data["depot"] = depot # Visits with time windows visits = [ { "name": f"visit_{visit_idx + 1}", "index": visit_idx + 1, "coordinate": { "lng": random.uniform(126.734, 127.269), # Longitude range of Seoul "lat": random.uniform(37.413, 37.715), # Latitude range of Seoul }, "time_window": [ datetime(2026, 7, 30, 0, 0, 0).isoformat(), datetime(2026, 7, 31, 23, 0, 0).isoformat() ], "volume": 10, } for visit_idx in range(num_visits) ] json_data["visits"] = visits

Set Vehicles¶

In [34]:

vehicles = [
    {
        "name": f"vehicle_{vehicle_idx + 1}",
        "volume_capacity": 77,
        "vehicle_type": "car",
    }
    for vehicle_idx in range(num_vehicles)
]
json_data["vehicles"] = vehicles

vehicles = [ { "name": f"vehicle_{vehicle_idx + 1}", "volume_capacity": 77, "vehicle_type": "car", } for vehicle_idx in range(num_vehicles) ] json_data["vehicles"] = vehicles

Set Solver Config¶

In [35]:

# note that the delivery_start_time is the time when the vehicle can start to deliver the first visit
# and is required for this problem
json_data["delivery_start_time"] = datetime(2026, 7, 30, 0, 0, 0).isoformat()

json_data["option"] = {
    "objective_type": "minsum",
    "timelimit": 3,
    "distance_type": "euclidean",
}

# note that the delivery_start_time is the time when the vehicle can start to deliver the first visit # and is required for this problem json_data["delivery_start_time"] = datetime(2026, 7, 30, 0, 0, 0).isoformat() json_data["option"] = { "objective_type": "minsum", "timelimit": 3, "distance_type": "euclidean", }

Solve the Problem¶

In [ ]:

OAASIS_API_KEY = os.getenv("OAASIS_API_KEY", None)
assert OAASIS_API_KEY is not None, "Please provide an API key!"

headers = {"X-API-KEY": OAASIS_API_KEY, "Accept": "application/vnd.omelet.v2+json"}
product_url = "https://routing.oaasis.cc/api/vrp"

response = requests.post(product_url, json=json_data, headers=headers)

if response.status_code == 200:
    print("Processed succesfully!")
    print("Response:")
    print(response.json())
else:
    print("The request failed. Status code:", response.status_code)
    print(response.json())

OAASIS_API_KEY = os.getenv("OAASIS_API_KEY", None) assert OAASIS_API_KEY is not None, "Please provide an API key!" headers = {"X-API-KEY": OAASIS_API_KEY, "Accept": "application/vnd.omelet.v2+json"} product_url = "https://routing.oaasis.cc/api/vrp" response = requests.post(product_url, json=json_data, headers=headers) if response.status_code == 200: print("Processed succesfully!") print("Response:") print(response.json()) else: print("The request failed. Status code:", response.status_code) print(response.json())

Visualize the Solution¶

In [ ]:

import matplotlib.pyplot as plt
from matplotlib import colormaps

resp = response.json()["routing_engine_result"]

fig, ax = plt.subplots(1, figsize=(4, 4))


coordinates = [[depot["coordinate"]["lat"], depot["coordinate"]["lng"]]]
coordinates.extend([
    [visit["coordinate"]["lat"], visit["coordinate"]["lng"]] for visit in visits
])

# Scatter the coordinates of the depot and visits
ax.scatter(coordinates[0][0], coordinates[0][1], color="tab:red", marker="x")
for i in range(1, len(coordinates)):
    ax.scatter(coordinates[i][0], coordinates[i][1], color="tab:blue")

# Plot the route
num_routes = len(resp["routes"])
colors = colormaps.get_cmap("tab10")
# colors = cm.get_cmap("tab10", num_routes)


for route_idx, route_obj in enumerate(resp["routes"]):
    routes = route_obj["route_index"]
    route_color = colors(route_idx)
    for step_idx in range(len(routes) - 1):
        src_idx = routes[step_idx]
        dst_idx = routes[step_idx + 1]
        src_x, src_y = coordinates[src_idx]
        dst_x, dst_y = coordinates[dst_idx]
        ax.annotate(
            "",
            xy=(dst_x, dst_y),
            xytext=(src_x, src_y),
            arrowprops=dict(
                arrowstyle="-|>", 
                color=route_color,
                lw=1.2,
            ),
            size=15,
            annotation_clip=False,
        )

# Label and title
ax.set_xlabel('Latitude')
ax.set_ylabel('Longitude')
ax.set_title(f'Cost = {resp["solution_cost_details"]["total_objective_cost"]}')

# Grid
ax.grid(axis='both', color='black', alpha=0.1)

plt.tight_layout()

import matplotlib.pyplot as plt from matplotlib import colormaps resp = response.json()["routing_engine_result"] fig, ax = plt.subplots(1, figsize=(4, 4)) coordinates = [[depot["coordinate"]["lat"], depot["coordinate"]["lng"]]] coordinates.extend([ [visit["coordinate"]["lat"], visit["coordinate"]["lng"]] for visit in visits ]) # Scatter the coordinates of the depot and visits ax.scatter(coordinates[0][0], coordinates[0][1], color="tab:red", marker="x") for i in range(1, len(coordinates)): ax.scatter(coordinates[i][0], coordinates[i][1], color="tab:blue") # Plot the route num_routes = len(resp["routes"]) colors = colormaps.get_cmap("tab10") # colors = cm.get_cmap("tab10", num_routes) for route_idx, route_obj in enumerate(resp["routes"]): routes = route_obj["route_index"] route_color = colors(route_idx) for step_idx in range(len(routes) - 1): src_idx = routes[step_idx] dst_idx = routes[step_idx + 1] src_x, src_y = coordinates[src_idx] dst_x, dst_y = coordinates[dst_idx] ax.annotate( "", xy=(dst_x, dst_y), xytext=(src_x, src_y), arrowprops=dict( arrowstyle="-|>", color=route_color, lw=1.2, ), size=15, annotation_clip=False, ) # Label and title ax.set_xlabel('Latitude') ax.set_ylabel('Longitude') ax.set_title(f'Cost = {resp["solution_cost_details"]["total_objective_cost"]}') # Grid ax.grid(axis='both', color='black', alpha=0.1) plt.tight_layout()