**
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

Each edge is assigned a value , which is the length of edge, that is, the distance between cities

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
; where

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)