Capacitated Vehicle Routing Problem (CVRP)¶

Capacitated Vehicle Routing Problem (CVRP) environment. At each step, the agent chooses a customer to visit depending on the current location and the remaining capacity. When the agent visits a customer, the remaining capacity is updated. If the remaining capacity is not enough to visit any customer, the agent must go back to the depot. The reward is 0 unless the agent visits all the cities. In that case, the reward is (-)length of the path: maximizing the reward is equivalent to minimizing the path length.

Observations

• location of the depot.
• locations and demand of each customer.
• current location of the vehicle.
• the remaining customer of the vehicle.

Constrains

• the tour starts and ends at the depot.
• each customer must be visited exactly once.
• the vehicle cannot visit customers exceed the remaining capacity.
• the vehicle can return to the depot to refill the capacity.

Finish Condition

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

Reward

• (minus) the negative length of the path.

In [9]:

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[9]:

True

Generate Problem Data¶

In [10]:

json_data = {}

num_visits = 10
num_vehicles = 3

json_data = {} num_visits = 10 num_vehicles = 3

Set Coordinates of depot and visits¶

In [11]:

# 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

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
        },
        "volume": 10,
    }
    for visit_idx in range(num_visits)
]
json_data["visits"] = visits

# 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 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 }, "volume": 10, } for visit_idx in range(num_visits) ] json_data["visits"] = visits

Set Vehicles¶

In [12]:

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 [13]:

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

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

Solve the Problem¶

In [14]:

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())

Processed succesfully!
Response:
{'routing_engine_result': {'routes': [{'vehicle_name': 'vehicle_1', 'route_index': [0, 1, 5, 3, 0], 'route_name': ['depot_1', 'visit_1', 'visit_5', 'visit_3', 'depot_1'], 'route_cost_details': {'objective_cost': 48520, 'distance_cost': 48520, 'duration_cost': 0, 'fixed_cost': 0}}, {'vehicle_name': 'vehicle_2', 'route_index': [], 'route_name': [], 'route_cost_details': {'objective_cost': 0, 'distance_cost': 0, 'duration_cost': 0, 'fixed_cost': 0}}, {'vehicle_name': 'vehicle_3', 'route_index': [0, 8, 9, 4, 7, 2, 10, 6, 0], 'route_name': ['depot_1', 'visit_8', 'visit_9', 'visit_4', 'visit_7', 'visit_2', 'visit_10', 'visit_6', 'depot_1'], 'route_cost_details': {'objective_cost': 91071, 'distance_cost': 91071, 'duration_cost': 0, 'fixed_cost': 0}}], 'unassigned_visit_indices': [], 'unassigned_visit_names': [], 'solution_cost_details': {'total_objective_cost': 139591, 'total_distance_cost': 139591, 'total_duration_cost': 0, 'max_distance_cost': 91071, 'max_duration_cost': 0, 'total_fixed_cost': 0, 'unassigned_penalty_cost': 0}}, 'status': 'feasible', 'detail': 'Successfully processed', 'job_id': '720f98f0d49d4457982f0e12617568a2'}

Visualize the Solution¶

In [15]:

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()