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 V.
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 \bgroup\color{gris}$T \subseteq E$\egroup is a solution for the TSP if it is a simple cycle of length \bgroup\color{gris}$\vert V\vert$\egroup in G.

The objective function of the TSP is \bgroup\color{gris}$\min \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}
d_{ij} x_{ij}$\egroup; where
\begin{displaymath}
x_{ij} = \left\{ \begin{array}{ll} 1 &\mbox{if the TSP tour includes (i,j)}\\
0 & \mbox{otherwise} \end{array} \right.
\end{displaymath}

\bgroup\color{gris}$
\begin{array}{ll}
\sum_{k=1}^{i-1} x_{ki}+\sum_{k=i+1}^{n} ...
... < \vert\mathcal{Z}\vert, & \emptyset
\subset Z \subset V\\
\end{array}$\egroup

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)