Skip to content

Routing problems

Catalogue of combinatorial problems · Catalogue (PDF)

  • Given \(n\) cities and the distance \(d_{ij}\) between every ordered pair, a solution is a tour that visits every city exactly once and returns to the first one.

  • The objective is to minimize the total length of the tour; the members differ in the properties of the distances, symmetric, metric or asymmetric.

  • The Hamiltonian cycle problem is the decision problem on a graph: it asks whether a tour made of edges of the graph exists.

Problem Acronym Difference
Travelling salesman problem TSP The central problem of the family.
Metric travelling salesman problem metric TSP The special case of the TSP with the triangle inequality, where approximation guarantees exist.
Asymmetric travelling salesman problem ATSP The TSP is the special case of the ATSP in which \(d_{ij}=d_{ji}\) for all \(i,j\); an ATSP instance has \((n-1)!\) tours.
Hamiltonian cycle problem HCP With \(d_{ij}=1\) on the edges and a large distance elsewhere, \(G\) is Hamiltonian if and only if \(z(I_G)=n\): the TSP contains it.