The travelling salesman problem

The travelling salesman problem

Spec 3.2 · Edexcel International A Level Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • The travelling salesman problem asks for the shortest tour: a route that visits every vertex and returns to the start.
  • In the classical problem each vertex is visited exactly once; in the practical problem vertices may be revisited.
  • A complete network with nn vertices has (n−1)!2\frac{(n-1)!}{2} different tours, so only small networks can be solved by listing.
  • The triangle inequality holds when the longest side of every triangle is no longer than the sum of the other two.
  • If a vertex has only one arc, no classical tour exists.

The problem and tours

The problem asks for a route of minimum length that visits every vertex and returns to the start. Such a closed walk is called a tour.

The travelling salesman problem (TSP) asks for a route of minimum length that visits every vertex of an undirected network. A walk that visits every vertex and returns to its starting vertex is a tour.

Examples are a delivery driver visiting customers or a drilling machine moving between holes.

No quick method always gives the best tour for a large network, so for exam networks we list tours or find bounds.

  1. 1

    Start

    at the depot or first vertex

  2. 2

    Visit every vertex

    using the arcs of the network

  3. 3

    Return

    to the start vertex to complete the tour

Then back to step 1

A tour

What makes a walk a tour?

The classical problem

In the classical problem each vertex is visited exactly once, normally on a complete graph. A complete network with nn vertices has (n−1)!2\frac{(n-1)!}{2} different tours.

In the classical TSP each vertex is visited exactly once, apart from the start, which is also the finish. A tour that does this is a cycle through all the vertices.

It is normally set on a complete graph, where every pair of vertices is joined by an arc.

A tour and its reverse count as the same tour. For n=4n=4 there are 3 tours and for n=5n=5 there are 12.

If a vertex has only one arc, no classical tour exists: the tour would have to enter and leave by the same arc.

01020304050603n = 4n = 5n = 6Number of verticesNumber of tours
Different tours in a complete network, (n − 1)! ÷ 2

How many different tours are there in a complete network with 5 vertices?

The practical problem

In the practical problem a vertex may be revisited, which is needed when the network is not complete or a vertex can only be reached through another.

In the practical TSP a vertex may be revisited. A van delivering to shops along a one-road spur must go in and come out again.

If the network is a tree, every arc must be travelled twice, so the shortest tour has length twice the total weight of the arcs.

In general, list sensible tours, add up each total and compare. If a vertex is joined only to BB by an arc of weight ww, that arc adds 2w2w to the tour.

ABC
A network where B is the only link between A and C: a tour such as A–B–C–B–A must revisit B

Classical

Each vertex visited:
Exactly once
Network:
Complete graph
Tour is:
A cycle through every vertex

Practical

Each vertex visited:
May be revisited
Network:
Any connected network
Tour is:
Dead ends are allowed
Two versions of the problem

A network is a tree with total arc weight 2020. What is the length of the shortest tour that visits every vertex and returns to the start?

The triangle inequality

A complete network satisfies the triangle inequality if, in every triangle, the longest side is no longer than the sum of the other two.

This says that going directly between two vertices is never longer than going through a third. Straight-line distances satisfy it.

If a network does not satisfy it, some direct arc is longer than a route through another vertex, so the practical and classical problems can have different answers.

To show it fails, find one triangle where the longest side is greater than the sum of the other two, such as 30>15+1030>15+10.

435ABC
Triangle inequality: the longest side (5) is no longer than the sum of the other two (3 + 4 = 7)
  • Triangle inequalitylongest side ≤ sum of the other two

A triangle in a network has sides 1212, 55 and 66. Does it satisfy the triangle inequality?

Finding the shortest tour

List every tour systematically, give each its length as a sum, and choose the shortest.

A complete network with four vertices WW, XX, YY, ZZ has three tours starting at WW: WW-XX-YY-ZZ-WW, WW-XX-ZZ-YY-WW and WW-YY-XX-ZZ-WW.

For five vertices list the 12 tours by fixing the start, listing orders of the other four vertices and dropping reversals. Always show every tour you considered.

w=20w=35w=25w=15w=30w=10WXYZ
A complete network on four vertices

Worked example

Find the shortest tour in the network above.

Which tour in the example has length 95?

Exam skills

State whether the problem is classical or practical, give each tour as a list of vertices ending at the start, and show its length as a sum.

To explain why no classical tour exists, name a vertex that is joined to only one other vertex.

When a new arc is added, find a tour that uses it, write its length with the unknown, and compare with the previous best tour to form an inequality.

  1. 1

    State the problem type

    classical (visit each vertex once) or practical (revisits allowed)

  2. 2

    List each tour

    as vertices, ending at the start

  3. 3

    Show its length

    as a sum of arc weights

Setting out an answer
  • Length of a toursum of its arcs, back to the start

Why does no classical tour exist if a vertex is joined to just one other vertex?

Try an exam question

A complete network has vertices A, B, C and D with AB = 12, AC = 9, AD = 15, BC = 7, BD = 11 and CD = 8. List all the different tours that start and finish at A, give the length of each, and state the shortest.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

How many different tours are there, starting and finishing at PP, if a tour and its reverse are counted as the same?

1 mark, marked against the mark scheme

Revision notes