How does the practical TSP differ?

Every vertex is visited at least once, so vertices and arcs can be repeated.

What is the triangle inequality?

The direct distance between two vertices is no more than the distance via a third.

How do you make a network complete?

Use the least distance between each pair of vertices as the arc weight.

What does any tour give?

An upper bound for the shortest tour.

State the nearest neighbour algorithm.

Go to the nearest unvisited vertex each time, then return to the start.

A direct arc replacing part of a route, which can improve the upper bound.

Method for a lower bound?

Delete a vertex, find the MST of the rest, then add the two shortest arcs at the deleted vertex.

How do you choose the best lower bound?

Try deleting different vertices and take the largest value.

How do you write the final answer using bounds?

Lower bound ≤ shortest tour ≤ best upper bound.

When is a tour known to be optimal?

When the lower bound equals its length.

The Travelling Salesman problemEdexcel A-Level Further Maths: Flashcards

Card 1 of 120 of 12 known

Question

What does the classical TSP require?

Tap or press Space to reveal

Tap card or press Space to flip

See all 12 cards

What does the classical TSP require?: A Hamiltonian cycle: every vertex visited exactly once, returning to the start, on a complete network.
How does the practical TSP differ?: Every vertex is visited at least once, so vertices and arcs can be repeated.
What is the triangle inequality?: The direct distance between two vertices is no more than the distance via a third.
How do you make a network complete?: Use the least distance between each pair of vertices as the arc weight.
What does any tour give?: An upper bound for the shortest tour.
State the nearest neighbour algorithm.: Go to the nearest unvisited vertex each time, then return to the start.
Upper bound from a minimum spanning tree?: Twice the weight of the tree.
What is a shortcut?: A direct arc replacing part of a route, which can improve the upper bound.
Method for a lower bound?: Delete a vertex, find the MST of the rest, then add the two shortest arcs at the deleted vertex.
How do you choose the best lower bound?: Try deleting different vertices and take the largest value.
How do you write the final answer using bounds?: Lower bound ≤ shortest tour ≤ best upper bound.
When is a tour known to be optimal?: When the lower bound equals its length.

Exam questions on The Travelling Salesman problem

A salesman must visit each of towns A, B, C, D and E once, starting and finishing at A. The distances in km between the towns are: AB 12, AC 10, AD 14, AE 8, BC 3, BD 7, BE 9, CD 6, CE 11 and DE 12.
Use the nearest neighbour algorithm, starting at A, to find an upper bound for the length of the shortest route.2 marks
A courier must visit depots A, B, C, D and E and return to the start. The only direct roads and their lengths in km are: AB 6, BC 4, CD 5, DE 3, AE 12, BD 11 and CE 10.
Find the least distance between B and D, and the least distance between C and E.2 marks
A delivery driver must visit five shops A, B, C, D and E, starting and finishing at A, and visiting each shop exactly once. The distances in km between the shops are: AB 15, AC 22, AD 25, AE 18, BC 10, BD 20, BE 12, CD 14, CE 16 and DE 9. These distances satisfy the triangle inequality.
Find a lower bound for the length of the shortest route by deleting shop A.3 marks

See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).