Capacitated Vehicle Routing Problem (CVRP) with Preference¶

Capacitated Vehicle Routing Problem (CVRP) with preference 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. Each agent has it's preferred area. 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.
• the preference matrix of vehicles.

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 with preference punishment.

In [1]:

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

True

Generate Problem Data¶

In [2]:

json_data = {}

num_visits = 10
num_vehicles = 3

json_data = {} num_visits = 10 num_vehicles = 3

Set Coordinates of depot and visits¶

In [3]:

# 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 [4]:

vehicles = [
    {
        "name": f"vehicle_{vehicle_idx + 1}",
        "volume_capacity": 77,
        "vehicle_type": "car",
        "visit_preference": np.random.randint(0, 4, num_visits).tolist(),
    }
    for vehicle_idx in range(num_vehicles)
]
json_data["vehicles"] = vehicles

vehicles = [ { "name": f"vehicle_{vehicle_idx + 1}", "volume_capacity": 77, "vehicle_type": "car", "visit_preference": np.random.randint(0, 4, num_visits).tolist(), } for vehicle_idx in range(num_vehicles) ] json_data["vehicles"] = vehicles

Set Solver Config¶

In [5]:

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

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, 5, 9, 10, 7, 8, 4, 0], 'route_name': ['depot_1', 'visit_5', 'visit_9', 'visit_10', 'visit_7', 'visit_8', 'visit_4', 'depot_1'], 'route_cost_details': {'objective_cost': 112166, 'distance_cost': 112166, '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, 6, 3, 1, 2, 0], 'route_name': ['depot_1', 'visit_6', 'visit_3', 'visit_1', 'visit_2', 'depot_1'], 'route_cost_details': {'objective_cost': 60029, 'distance_cost': 60029, 'duration_cost': 0, 'fixed_cost': 0}}], 'unassigned_visit_indices': [], 'unassigned_visit_names': [], 'solution_cost_details': {'total_objective_cost': 172195, 'total_distance_cost': 172195, 'total_duration_cost': 0, 'max_distance_cost': 112166, 'max_duration_cost': 0, 'total_fixed_cost': 0, 'unassigned_penalty_cost': 0}}, 'status': 'feasible', 'detail': 'Successfully processed', 'job_id': '1cc55b0e07ad4f0f90d29cab3a09a045'}

Visualize the Solution¶

In [7]:

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