TSP Routes Optimizer

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


Category:

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)

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.