Traveling salesman problem, often abbreviated as TSP is an optimization problem whose

foundation is based on Graph theory.The traveling salesman problem (TSP) asks the following question:“Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?”

The cheaper solution is the optimum solution for this problem. As the name of the problem implies, the problem deals with finding the most optimum route for a salesman to reach to its customers sequentially in a most optimized way possible and return to the origin.

Various algorithms which claim to solve this problem are: Ant colony approach, Heuristic

algorithm etc. The algorithm which proves to solve this problem is known as ‘Dijkshatra’s

algorithm’.** Google uses this algorithm in their navigation app: ‘Google maps’.** It is one of the most extensively studied problems in optimization. The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips, movement of the mechanical arm on PCB design machine etc.

Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments and the concept distance represent the traveling times or cost, or a similarity measure between DNA fragments.