All subjects · Mathematics · WDM11 (D1)

The travelling salesman problem

The travelling salesman problem (TSP) asks for the shortest tour that visits every vertex and returns to the start. No efficient algorithm is known for large networks, so D1 finds bounds instead.

Tours

A tour visits every vertex and returns to the start. In the classical problem each vertex is visited exactly once (a Hamiltonian cycle). In the practical problem vertices may be visited more than once, which is often what a real delivery driver would do.

The triangle inequality

The classical problem is solved on a complete network that satisfies the triangle inequality: the longest side of any triangle is at most the sum of the other two, so going direct is never longer than going via another vertex.

Converting a practical problem

Replace the network by a complete network of shortest distances: for each pair of vertices, the entry is the shortest route between them (found by inspection). This table satisfies the triangle inequality, so classical methods apply. A tour in the new table may stand for a route that passes through other vertices in the original network.

Bounds

Since the optimal tour is hard to find, you find an upper bound (the length of a real tour, so the optimum is no longer) and a lower bound (the optimum cannot be shorter). Write lower bound ≤ optimal ≤ upper bound, and choose the best (smallest upper, largest lower) bound found.

Worked example

Network R has a direct edge QS of 13, but Q to R to S is 12. What goes in the QS cell of the table of shortest distances?

  1. The table needs the shortest route, not the direct edge.
  2. QR + RS = 5 + 7 = 12

Answer: 12

Key idea: Classical TSP: every vertex exactly once on a complete network with the triangle inequality. Practical problems are converted with a table of shortest distances. Find bounds: lower ≤ optimal ≤ upper.

Check yourself

  1. Network R has no direct edge PT. Find the entry for PT in the table of shortest distances.
    Show answer

    18. P to R to T is 18 and P to R to S to T is 19, so 18.

  2. Find the entry for QT in the table of shortest distances for network R.
    Show answer

    15. Q to R to S to T = 5 + 7 + 4 = 16; Q to R to T = 15; Q to S to T = 17. So 15.

  3. Which set of distances breaks the triangle inequality for triangle XYZ?
    • XY = 4, YZ = 5, XZ = 9
    • XY = 6, YZ = 6, XZ = 6
    • XY = 4, YZ = 5, XZ = 11
    • XY = 3, YZ = 4, XZ = 5
    Show answer

    XY = 4, YZ = 5, XZ = 11. 4 + 5 = 9 < 11, so going X to Y to Z is shorter than going direct.

  4. What is the difference between the classical and practical travelling salesman problems?
    • Classical uses directed networks; practical does not
    • Classical visits each vertex exactly once; practical allows repeat visits
    • Classical needs a lower bound only
    • Practical tours need not return to the start
    Show answer

    Classical visits each vertex exactly once; practical allows repeat visits. Classical tours are Hamiltonian cycles; practical tours may pass through a vertex more than once.

  5. A tour of length 64 has been found, and a lower bound of 57. What can be said about the optimal tour length d?
    • d = 64
    • d = 57
    • d ≥ 64
    • 57 ≤ d ≤ 64
    Show answer

    57 ≤ d ≤ 64. The optimum is no longer than any tour found, and no shorter than a lower bound.

  6. Upper bounds of 62, 64 and 70 and lower bounds of 52, 56 and 57 have been found. Which interval is the best?
    • 52 ≤ d ≤ 70
    • 57 ≤ d ≤ 62
    • 56 ≤ d ≤ 64
    • 57 ≤ d ≤ 70
    Show answer

    57 ≤ d ≤ 62. The best upper bound is the smallest (62); the best lower bound is the largest (57).

Practise with instant feedback

Sources

Last updated 7 November 2026. Spotted a mistake? Tell us.