TSP Routes Optimizer
Quantum version of the TSP (Travelling Salesperson Problem) algorithm for route optimization.
Description
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
Brand
QCentroid

Additional information
Additional information
Sustainability focus | |
---|---|
Sector | |
Use case | |
UN SDG supported |
How To
How To
# 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
df = pd.read_csv("concap.csv") df = df[['CapitalName', 'CapitalLatitude', 'CapitalLongitude']] df.rename(columns={"CapitalName": "city", "CapitalLatitude": "lat", "CapitalLongitude": "lon"}, inplace=True)
# 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'
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.
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.
# 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": "..."}
# 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": {
}
}
]
}
qapitan_api = Qapitan(QAPITAN_PUBLIC_API, PAYLOAD_USER)
header = qapitan_api.login()
{'username': 'sergio@qapitan.com', 'password': 'qapitan'}
response_json = qapitan_api.execute(header=header, problem='tsp', payload=PAYLOAD_TSP_1)
job_name = response_json['job']
response_json
{'detail': 'Authorized. Processing file', 'job': 'P7IITMWOW2T1'}
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
# Let us include the order in the dataframe
df_city['order'] = [order.index(i) for i in range(len(cities))]
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
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()