Traveling salesman problem

From Glossary

Jump to: navigation, search

Given LaTeX: n points and a cost matrix, LaTeX: [c_{ij}], a tour is a permutation of the LaTeX: n points. The points can be cities, and the permutation the visitation of each city exactly once, then returning to the first city (called home). The cost of a tour, LaTeX: <i_1, i_2, \dots, i_{n-1}, i_n, i_1>, is the sum of its costs:

LaTeX: 
c_{i_1 i_2} + c_{i_2 i_3} + \dots + c_{i_{n-1} i_n} + c_{i_n i_1},

where LaTeX: (i_1, i_2, \dots, i_n) is a permutation of LaTeX: \{1,\dots,n\}. The TSP is to find a tour of minimum total cost. The two common integer programming formulations are:


ILP: LaTeX: \min \left\{ \sum_{ij} c_{ij} x_{ij} : x \in P, \, x_ij \in \{0, 1\} \right\}


Subtour elimination constraints: LaTeX: \sum_{i,j \in V} x_{ij} \le |V| - 1 \mbox{ for } \empty \ne V \subset \{1, \dots , n \} (V \ne \{ 1, \dots, n \} ),


where LaTeX: 
x_{ij} = \begin{cases}
1 & \mbox{ if city } j \mbox{ follows city } i \mbox{ in the tour} \\
0 & \mbox{ otherwise}
\end{cases}


QAP: LaTeX: 
\min \left\{ \sum_{ij} c_{ij} \left( \sum_{k=1}^{n-1} x_{ik} x_{j \, k+1} + x_{i n} x_{j 1} \right) : x \in P, \, x_{i j} \in \{0 , 1\}
\right\} ,


where LaTeX: 
x_{(i, j)} = \begin{cases}
1 & \mbox{ if city } j \mbox{ follows city } i \mbox{ in the tour} \\
0 & \mbox{ otherwise}
\end{cases}


In each formulation, LaTeX: P is the assignment polytope. The subtour elimination constraints in ILP eliminate assignments that create cycles, such as shown in the following figure:

Image:Tsp-subtour.gif

The first subtour is eliminated by LaTeX: V = \{1, 2, 3\}, which requires LaTeX: x_{12} + x_{23} + x_{31} \le 2. The second subtour is eliminated by LaTeX: V = \{4, 5\}, which requires LaTeX: x_{45} + x_{54} \le 1.

In ILP, it is easy to incorporate missing arcs: replace the subscripts LaTeX: (ij) with an arc index, LaTeX: k. Then, the subtour elimination constraints have sums over arcs whose head is in LaTeX: V. The quadratic assignment problem formulation (QAP) is well suited to certain solution methods, such as neural networks.

When the cost matrix is symmetric, it is called the symmetric TSP. When the points are in the plane, and the cost matrix is the Euclidean distance matrix, it is called the Euclidean TSP. See the n-Opt heuristic.


Views
Personal tools