The Travel Salesman Problem (TSP)
Intuitively, the TSP is the problem of a salesman who wants
to find, starting from his home town, a shortest possible trip through a given
set of customer cities and to return to its home town; visiting exactly once
each city. More formally, it can be represented by a complete weighted graph
G = (V,E) with V being the set of nodes, representing
the cities, and E the set of edges fully connecting the nodes
Each edge is assigned a value , which is the length of edge, that is, the distance between cities i and j, with . The TSP is the problem of finding a minimal length Hamiltonian cycle of the graph. For symmetric TSPs, the distances between the cities are independent of the direction of traversing the arcs, that is, for every pair of nodes.
The arc set is a solution for the TSP if it is a simple cycle of length in G.
The objective function of the TSP is
In the figure bellow we can se an schema of a typical input for the TSP and its solution.
Figure 1: Typical input for TSP (left) and its Output (right)