TSP Routes Optimizer

Quantum version of the TSP (Travelling Salesperson Problem) algorithm for route optimization.

Category: Optimization

Description

An optimization algorithm by QCentroid

The TSP or Travelling Salesperson Problem is a classic optimization problem. The problem is, essentially, the following:

We are a Salesperson and we must visit several cities in order to sell all our products to as many people as possible. The cities are distant from each other, so we cannot sell anything in the middle of the travel. In addition, the travel makes us lose money since there are some expenses, manteinance and accomodation, to defray. Thus, we are interested in finding the route with the less possible travel time.

This problem is known to be NP-Complete, that is, it is really hard to find the optimal solution to it. If we want to visit N cities, then we must find the optimal path among N! possible itineraries. Comparing one solution to another one is easy, but finding the best one is similar to looking for a needle in a haystack.

In this example, we need to determine a list of cities to visit. These cities should be the capitals of any country in the world. There are some additional calculations to extract the distances between all different pairs of cities. Then, a matrix with distances is introduced into the QCentroid API, who looks for the optimal solution in an easy way. The solution is showed afterwards.

Take into account that the hardest piece of this problem is finding the optimal solution. This step is completely addressed by the QCentroid, while the users / cabin boys and girls do not have to worry about it.

Brand

QCentroid

Additional information

Sustainability focus	Yes
Sector	Industry, Logistics
Use case	Routing optimization
UN SDG supported	GOAL 11

How To

This is an example Jupyter Notebook to use the TSP solver in the QCentroid Platform.

In [1]:

# Import some auxiliary packages. Make sure that all packages are installed

import pandas as pd
from geopy import distance 
import numpy as np
from Qapitan import Qapitan # Qapitan SDK
import time
from IPython.display import display, clear_output

In [2]:

df = pd.read_csv("concap.csv")
df = df[['CapitalName', 'CapitalLatitude', 'CapitalLongitude']]
df.rename(columns={"CapitalName": "city", "CapitalLatitude": "lat", "CapitalLongitude": "lon"}, inplace=True)

In [3]:

# Introduce your cities here. Make sure they are capitals. If the cities are not in our database, an Error will
# raise in the next cell

cities = ['Berlin', 'Tokyo', 'Vienna', 'Washington', 'Madrid', 'London', 'Lisbon', 'Paris', 'Moscow']
starting_city = 'Tokyo'

In [4]:

df_city = df[df['city'].isin(cities)].reset_index()
assert(len(df_city) == len(cities)), "Some cities are not recognized!"

cities = df_city['city'] # Order is normalized
first_city = int(df_city[df_city['city'] == starting_city].index[0])

We compute now the distance matrix. Note that the distances are normalized to be not larger than 1, and the the diagonal terms are always -1. This is done to understand that the Traveler cannot go from one city to the same one.

In [5]:

distances = np.zeros((len(cities),)*2)

for i in range(len(cities)):
    for j in range(i):
        distances[i, j] = distance.distance((df_city.loc[i, "lat"], df_city.loc[i, "lon"]), (df_city.loc[j, "lat"], df_city.loc[j, "lon"])).km
        distances[j, i]

distances = .5*(distances + distances.T)
distances/= np.max(distances)
distances -= np.eye(len(cities))

distances = [list(d.flatten()) for d in distances]

Now we are moving towards using the QCentroid API to solve the problem.

In [6]:

# Import required packages and stablish the parameters

import json
import requests

# Get your private endpoint and credentials from our team - info@qapitan.com
QAPITAN_PUBLIC_API = "https://api.qcentroid.xyz"
PAYLOAD_USER = {"username": "...", "password": "..."}

Now it is time to define the problem. In particular, the algorithm and provider must be specified. We are in the advent of quantum computing, and thus we will use simulations by now. We use an annealing scheme simulated using the DWave technology.

In [7]:

# You can specify the exact Solver you want to use from a specific provider or hardware. 
# Or you can rely on our platform to get the best in class

solver_name = "Solver_Qapitan_QUBO_Framework-Tsp-annealing_sim-dwave-local"
#solver_name = "Solver_Qapitan_QUBO_Framework-Tsp-geneticalgorithm-classic-local"

PAYLOAD_TSP_1 = {
    "data": {
        "number_nodes": len(distances),
        "weight_matrix": distances,
        "first_node": first_city
    },
    "solvers":[
    {
        "name": solver_name,
        "extra_arguments": {
        }
    }
    ] 
}

In [8]:

qapitan_api = Qapitan(QAPITAN_PUBLIC_API, PAYLOAD_USER)
header = qapitan_api.login()

{'username': 'sergio@qapitan.com', 'password': 'qapitan'}

In [9]:

response_json = qapitan_api.execute(header=header, problem='tsp', payload=PAYLOAD_TSP_1)
job_name = response_json['job']

In [10]:

response_json

Out[10]:

{'detail': 'Authorized. Processing file', 'job': 'P7IITMWOW2T1'}

In [11]:

result = qapitan_api.get_result(header=header, job_name=job_name)
print(result)

while(job_name not in result['job'] or (result['job'][job_name]['status'] != 'FINISHED' and result['job'][job_name]['status'] != 'ERROR')):
    print(job_name)

    if(job_name in result['job']):
        display(result['job'][job_name]['status'])
    else:
        display('LOADING')
    time.sleep(3)
    clear_output(wait=True)
    result = qapitan_api.get_result(header=header, job_name=job_name)
    print(result)
    

clear_output(wait=True)
# Print result
print("Execution Result:")
print(result['job'][job_name])

Execution Result:

{'status': 'FINISHED', 'started_at': '02/14/2022, 11:30:35', 'end_at': '02/14/2022, 11:32:18', 'executions': {'Solver_Qapitan_QUBO_Framework-Tsp-annealing_sim-dwave-local': {'started_at': '', 'end_at': '02/14/2022, 11:32:06', 'status': 'SUCCESS', 'data': {'number_nodes': 9, 'weight_matrix': [[-1.0, 0.0928905987022528, 0.04694935086215485, 0.8195861037747975, 0.20610242983222293, 0.14984150359756676, 0.16221866632606863, 0.11061985338530292, 0.6393368646950607], [0.0928905987022528, -1.0, 0.07876878065960502, 0.871856272558227, 0.1301633997356444, 0.22320362091321194, 0.09438196495830918, 0.03043392341100998, 0.5531225417393408], [0.04694935086215485, 0.07876878065960502, -1.0, 0.8005577500884857, 0.20725094940209698, 0.1444375154597699, 0.16753415181952686, 0.08337944844717389, 0.60228649206033], [0.8195861037747975, 0.871856272558227, 0.8005577500884857, -1.0, 1.0, 0.6716120211410962, 0.9659752131950059, 0.8580411400375108, 0.9784418065294282], [0.20610242983222293, 0.1301633997356444, 0.20725094940209698, 1.0, -1.0, 0.3503457718059238, 0.04513758926685113, 0.1420212668742666, 0.5146943773650063], [0.14984150359756676, 0.22320362091321194, 0.1444375154597699, 0.6716120211410962, 0.3503457718059238, -1.0, 0.3085842685873344, 0.22427634920329914, 0.7020701942643062], [0.16221866632606863, 0.09438196495830918, 0.16753415181952686, 0.9659752131950059, 0.04513758926685113, 0.3085842685873344, -1.0, 0.11321023669429198, 0.5464618635812399], [0.11061985338530292, 0.03043392341100998, 0.08337944844717389, 0.8580411400375108, 0.1420212668742666, 0.22427634920329914, 0.11321023669429198, -1.0, 0.5295916723054901], [0.6393368646950607, 0.5531225417393408, 0.60228649206033, 0.9784418065294282, 0.5146943773650063, 0.7020701942643062, 0.5464618635812399, 0.5295916723054901, -1.0]], 'first_node': 3}, 'arguments': {}, 'result': [[3, 7, 5, 8, 0, 2, 6, 1, 4, 3], [3.8627534155758125, 3.8627534155758125]]}}}

In [12]:

# We retrieve the final result now, order
# We transform the output string into a list of numbers

order = qapitan_api.get_best_result(header, response_json['job'])

order = [int(o) for o in order[0]]

print(order)

[3, 7, 5, 8, 0, 2, 6, 1, 4, 3]

We have now the optimal order to travel around the world! Let us paint it

In [13]:

# Let us include the order in the dataframe

df_city['order'] = [order.index(i) for i in range(len(cities))]

In [14]:

df_city = df_city.sort_values(by=['order'])
route = ''
for city in df_city['city']:
    route += city + ', '
    
route += starting_city
print('The optimal route is n', route)

The optimal route is: Tokyo, London, Moscow, Washington, Vienna, Berlin, Madrid, Paris, Lisbon, Tokyo

In [15]:

import plotly.graph_objects as go
# Now we draw the route to follow. Notice that the red line stands for the travel back home
fig = go.Figure(data=go.Scattergeo(
    locationmode = 'USA-states',
        lon = df_city['lon'],
        lat = df_city['lat'],
        text = df_city['city'],
        mode = 'markers+text',
    name="cities",  showlegend=False, 
        ))

# draw the paths between the capitals
for i in range(len(cities)):
    fig.add_trace(go.Scattergeo(
        locationmode = 'USA-states',
        lon=[df_city.loc[order[i],"lon"],df_city.loc[order[i+1],"lon"]], 
        lat=[df_city.loc[order[i],"lat"],df_city.loc[order[i+1],"lat"]], 
        name="-".join([df_city.loc[order[i],"city"],df_city.loc[order[i+1],"city"]]),
        mode="lines", line_color="#000000", showlegend=False))
    
# the last path
fig.add_trace(go.Scattergeo(
        locationmode = 'USA-states',
        lon=[df_city.loc[order[-2],"lon"],df_city.loc[order[-1],"lon"]], 
        lat=[df_city.loc[order[-2],"lat"],df_city.loc[order[-1],"lat"]], 
        name="-".join([df_city.loc[order[-2],"city"],df_city.loc[order[-1],"city"]]),
        mode="lines", line_color="#ff0000", showlegend=False))

fig.update_layout(
        title = 'Shortest Route Between Cities',
    font_size=16
    )
fig.show()

TSP Routes Optimizer

Description

Description

An optimization algorithm by QCentroid

Brand

Brand

QCentroid

Additional information

Additional information

How To

How To

Related products

Credit Risk Optimizer

Knapsack Optimizer

EV Charging Stations Placement