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.
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…
There are two types of TSP problems are there-
In the symmetric TSP, the distance between two cities is the same in each opposite direction.
In the asymmetric TSP, paths may not exist in both directions, or the distances might be different.
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
converting the doc plex model to Quadratic model
convert binary string to paths
running the algorithm