Metric travelling salesman problem (metric TSP)

Catalogue of combinatorial problems · Routing problems · Catalogue (PDF)

Definition 1: Metric travelling salesman problem

A TSP instance is metric if its distances satisfy the triangle inequality

\[ d_{ij} \le d_{ik} + d_{kj} \qquad \text{for all distinct } i,j,k \in \mathscr{V}. \]

The metric travelling salesman problem (metric TSP) is the TSP restricted to metric instances.

What the course does on this problem

Technique	Where
Definition	Ch. 6 «Routing problems»
Formulations	Ch. 13 «Formulations of routing problems»
Heuristics	Ch. 30 «Constructive heuristics»
Approximation	Ch. 39 «The TSP: the general case and the metric case»
Exercises	Exercise 6.4; Ch. 39 (2 exercises)