The travelling salesman problem (TSP)¶
Definition 1: The travelling salesman problem
Given:
-
a set \(\mathscr{V} = \{1,2,\dots,n\}\) of \(n\) cities,
-
for each pair of distinct cities \(i,j \in \mathscr{V}\), a distance \(d_{ij} \in \Z_{\ge 1}\), with \(d_{ij}=d_{ji}\),
the travelling salesman problem (TSP) asks to find a closed route that starts from a city, visits every other city exactly once and returns to the starting city, so that the total distance travelled is minimized.
Assumptions
-
We make the following assumptions:
-
There are at least three cities (with one or two cities there is only one route). Formally:
\[ n \ge 3 \] -
The distances are symmetric (travelling from \(i\) to \(j\) costs as much as travelling from \(j\) to \(i\)). Formally:
\[ d_{ij}=d_{ji},~~~~ \forall i,j \in \mathscr{V},~ i\neq j \]
-
What the course does on this problem¶
| Technique | Where |
|---|---|
| Definition | Ch. 6 «Routing problems» |
| Formulations | Ch. 13 «Formulations of routing problems» |
| Heuristics | Ch. 29 «Heuristic algorithms: definitions»; Ch. 30 «Constructive heuristics»; Ch. 31 «Local search»; Ch. 32 «Metaheuristics» |
| MIP heuristics | Ch. 33 «MIP heuristics for the classical problems» |
| Approximation | Ch. 39 «The TSP: the general case and the metric case» |
| Exercises | Ch. 6 (7 exercises); Ch. 13 (5 exercises); Exercise 29.3; Ch. 30 (3 exercises); Ch. 31 (3 exercises); Ch. 32 (7 exercises); Ch. 39 (3 exercises) |
Properties¶
-
Strongly NP-hard: it contains the Hamiltonian cycle problem (Ch. 1).
-
Lower bound \(\lceil \frac12 \sum_i (a_i+b_i) \rceil\), with \(a_i, b_i\) the two shortest edges at city \(i\) (Ch. 6).
-
Nearest neighbour from city \(1\) gives \(25\) on the five-city instance of Ch. 6, whose optimum is \(18\) (Ch. 6).
Formulations¶
-
The MTZ model eliminates the subtours with \(n-1\) position variables \(u_i\); the DFJ model with \(2^{n-1}-n\) subtour constraints, added only when violated (Ch. 13).
-
The MTZ relaxation is weak; on the instance of Ch. 6 the bounds are \(16\) (assignment), \(17\) (MTZ) and \(18\) (DFJ) (Ch. 13).
Heuristics¶
-
Multi-start nearest neighbour and the insertion heuristics NI, FI and CI all reach \(18\) on the instance of Ch. 6 (Ch. 30).
-
2-opt evaluates each of its \(\frac{n(n-3)}{2}\) moves in \(O(1)\) and turns the tour of length \(25\) into an optimal one in two moves (Ch. 31).
-
Or-opt and VND escape the local optima of 2-opt (Ch. 31).
-
Simulated annealing, tabu search, iterated local search, GRASP and LNS are compared on TSP20 (optimum \(291\)) (Ch. 32).
MIP heuristics¶
- With the subtour constraints the LP optimum of the instance of Ch. 6 is integer: rounding gives \(18\), gap \(0\%\) (Ch. 33).