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-
- 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
prepare and Adjacency matrix
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.
