# Quantum Opt’z: Travelling Salesman Problem

## How to find the optimized path for the TSP using Quantum computing?

In this article, we discuss about travelling salesman problem and we solve the problem to find the optimized route using variational method.

Setup:

To solve this problem we convert the problem similar to graph coloring problem.

The traveling salesman problem (TSP) is to find a routing of a salesman who starts from a home location, visits a prescribed set of cities and returns to the original location in such a way that the total distance travelled is minimum and each city is visited exactly once.

It is an NP-hard problem in combinatorial optimization.

Use cases:

we can using this TSP solution technique to solve the

• Machine Scheduling Problems
• Cellular Manufacturing
• Arc Routing Problems
• Frequency Assignment Problem
• data analysis in psychology
• X-Ray crystallography
• overhauling gas turbine engines
• warehouse order-picking problems
• minimizing wall paper cutting waste
• school bus routing
• postal deliveries
• Genome Sequencing
• Drilling Problems
• guiding lasers for crystal art
• Design of global navigation satellite system surveying networks
• and so on…

Types:

There are two types of TSP problems are there-

1. Symmetric

In the symmetric TSP, the distance between two cities is the same in each opposite direction.

2. Asymmetric

In the asymmetric TSP, paths may not exist in both directions, or the distances might be different.

Quantum Solution:

we solve this problem using QAOA algorithm with IBM Qiskit library.

import the dependencies

generate a list which represents the latitudes and longitudes, in our problem we take 4 nodes.

prepare node assignment for the each position.

generate a geometric graph with the generated positions.

by using euclidean distance we calculate the edge length(distance) or weight and update the same to graph

draw graph using below function

below graph generated using the above function

create binary variables using below code block

prepare cost function

minimize the cost function

applying constraints

converting the doc plex model to Quadratic model

convert binary string to paths

running the algorithm

output

References:

qiskit textbook, IITM course by (@Prabha M, Anil Prabhakar), IBM Quantum Challenge (2021, 2022), Wikipedia, stack exchange and open source materials.