Traveling Salesman Problem (TSP)¶

The Traveling Salesman Problem (TSP) is one of the most extensively studied combinatorial optimization problems, fundamental both in theoretical computer science and operations research. The TSP concerns finding the shortest possible route that a traveling salesman can take to visit each city exactly once and return to the origin city. This problem is famously complex, classified as NP-hard, meaning there is no known polynomial-time algorithm to solve it for all cases. The significance of TSP lies in its ability to model various real-world problems, ranging from logistics to the manufacture of microchips, making it a cornerstone problem in optimization and algorithm design.

At each step, the agent chooses a city to visit. 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.

In [17]:

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

True

Generate Problem Data¶

In [18]:

json_data = {}

num_visits = 10
num_vehicles = 1

json_data = {} num_visits = 10 num_vehicles = 1

Set Coordinates of depot and visits¶

In [19]:

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

Set Vehicles¶

In [20]:

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

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

Set Solver Config¶

In [21]:

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

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

Visualize the Solution¶

In [23]:

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
for i in range(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 for i in range(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()