Hard Further Maths Travelling salesman problem Questions

Challenging, exam-style Further Maths Travelling salesman problem questions with worked solutions. Stretch yourself on the hardest travelling-salesman, nearest-neighbour, upper-bound, lower-bound problems.

travelling-salesmannearest-neighbourupper-boundlower-boundminimum-spanning-treepractical-problem
Further Maths34 questionsStep-by-step solutions
Question 1
9 markschallenging
A network has vertices AA, BB, CC, DD, EE and FF. Not every pair of vertices is joined directly by an arc. The arcs of the network and their weights are AB=19AB=19, AC=23AC=23, AD=57AD=57, AF=67AF=67, BC=14BC=14, BE=18BE=18, BF=54BF=54, CD=38CD=38, CF=51CF=51, DE=50DE=50. In the practical travelling salesman problem a vertex may be visited more than once, so the algorithms are applied to the complete network of least distances, in which the distance between two vertices is the length of the shortest route between them; this table of least distances satisfies the triangle inequality. Using the table of least distances, delete vertex EE to find a lower bound for the length of the optimal practical tour.
Show worked solution

Worked solution

  1. Find the least distance from AA to EE

    A→B→E=37;\quadA→C→B→E=55;\quadA→D→E=107;\quadA→C→D→E=111A\to B\to E=37;\quadA\to C\to B\to E=55;\quadA\to D\to E=107;\quadA\to C\to D\to E=111

    There is no direct arc from AA to EE, so the least distance is the length of the shortest route, A\to B\to E.

  2. Enter the least distance AE=37AE=37 in the table of least distances

    AE=37AE=37

    The shortest route A\to B\to E has length 3737.

  3. Find the least distance from BB to DD

    B→C→D=52;\quadB→E→D=68;\quadB→A→D=76;\quadB→A→C→D=80B\to C\to D=52;\quadB\to E\to D=68;\quadB\to A\to D=76;\quadB\to A\to C\to D=80

    There is no direct arc from BB to DD, so the least distance is the length of the shortest route, B\to C\to D.

  4. Enter the least distance BD=52BD=52 in the table of least distances

    BD=52BD=52

    The shortest route B\to C\to D has length 5252.

  5. Find the least distance from CC to EE

    C→B→E=32;\quadC→A→B→E=60;\quadC→D→E=88;\quadC→F→B→E=123C\to B\to E=32;\quadC\to A\to B\to E=60;\quadC\to D\to E=88;\quadC\to F\to B\to E=123

    There is no direct arc from CC to EE, so the least distance is the length of the shortest route, C\to B\to E.

  6. Enter the least distance CE=32CE=32 in the table of least distances

    CE=32CE=32

    The shortest route C\to B\to E has length 3232.

  7. Delete vertex EE and every arc joined to it

    remaining vertices:  A,  B,  C,  D,  F\text{remaining vertices}:\;A,\;B,\;C,\;D,\;F

    The lower bound is built from the network on the other 55 vertices.

  8. List the arcs of the remaining network in ascending order

    BC=14,  AB=19,  AC=23,  CD=38,  CF=51,  BD=52,  BF=54,  AD=57,  AF=67,  DF=89BC=14,\;AB=19,\;AC=23,\;CD=38,\;CF=51,\;BD=52,\;BF=54,\;AD=57,\;AF=67,\;DF=89

    A minimum spanning tree for these 55 vertices is now needed.

  9. Build the minimum spanning tree of the remaining network

    AB=19,  BC=14,  CD=38,  CF=51AB=19,\;BC=14,\;CD=38,\;CF=51

    Each arc chosen is the shortest arc joining the tree built so far to a vertex not yet in it.

  10. Add the lengths of the arcs of the residual tree

    19+14+38+51=12219+14+38+51=122

    The residual minimum spanning tree has total weight 122122.

  11. Add back the two shortest arcs from EE

    EB=18,  EC=32EB=18,\;EC=32

    In any tour, vertex EE is joined to exactly two other vertices, so at least the two shortest arcs at EE must be used.

  12. Note that all the distances in this network are different

    distinct weights  ⇒  the nearest neighbour is never ambiguous\text{distinct weights}\;\Rightarrow\;\text{the nearest neighbour is never ambiguous}

    With no two arcs of equal length, the nearest unvisited vertex is always unique, so the algorithm has a single well-defined output.

  13. Recall that the nearest-neighbour algorithm gives an UPPER bound

    optimal tour≤any tour found by nearest neighbour\text{optimal tour}\leq\text{any tour found by nearest neighbour}

    The nearest-neighbour algorithm produces a genuine tour, and the optimal tour cannot be longer than a tour we have actually found.

  14. Recall that deleting a vertex gives a LOWER bound

    residual minimum spanning tree+two shortest arcs≤optimal tour\text{residual minimum spanning tree}+\text{two shortest arcs}\leq\text{optimal tour}

    Removing a vertex from any tour leaves a path through the other vertices, which is a spanning tree of them, so it is at least as long as the minimum spanning tree.

  15. Add the two shortest arcs to the weight of the residual tree

    122+18+32=172122+18+32=172

    Deleting EE gives a lower bound of 172172 for the length of the optimal tour.

Answer
172172
Question 2
9 markschallenging
A network has vertices AA, BB, CC, DD, EE and FF. Not every pair of vertices is joined directly by an arc. The arcs of the network and their weights are AB=57AB=57, AC=28AC=28, AD=59AD=59, AE=55AE=55, BF=35BF=35, CD=16CD=16, CF=15CF=15, DE=61DE=61, DF=37DF=37, EF=45EF=45. In the practical travelling salesman problem a vertex may be visited more than once, so the algorithms are applied to the complete network of least distances, in which the distance between two vertices is the length of the shortest route between them; this table of least distances satisfies the triangle inequality. Using the table of least distances, delete vertex BB to find a lower bound for the length of the optimal practical tour.
Show worked solution

Worked solution

  1. Find the least distance from AA to FF

    A→C→F=43;\quadA→C→D→F=81;\quadA→D→C→F=90;\quadA→B→F=92A\to C\to F=43;\quadA\to C\to D\to F=81;\quadA\to D\to C\to F=90;\quadA\to B\to F=92

    There is no direct arc from AA to FF, so the least distance is the length of the shortest route, A\to C\to F.

  2. Enter the least distance AF=43AF=43 in the table of least distances

    AF=43AF=43

    The shortest route A\to C\to F has length 4343.

  3. Find the least distance from BB to CC

    B→F→C=50;\quadB→A→C=85;\quadB→F→D→C=88;\quadB→A→D→C=132B\to F\to C=50;\quadB\to A\to C=85;\quadB\to F\to D\to C=88;\quadB\to A\to D\to C=132

    There is no direct arc from BB to CC, so the least distance is the length of the shortest route, B\to F\to C.

  4. Enter the least distance BC=50BC=50 in the table of least distances

    BC=50BC=50

    The shortest route B\to F\to C has length 5050.

  5. Find the least distance from BB to DD

    B→F→C→D=66;\quadB→F→D=72;\quadB→A→C→D=101;\quadB→A→D=116B\to F\to C\to D=66;\quadB\to F\to D=72;\quadB\to A\to C\to D=101;\quadB\to A\to D=116

    There is no direct arc from BB to DD, so the least distance is the length of the shortest route, B\to F\to C\to D.

  6. Enter the least distance BD=66BD=66 in the table of least distances

    BD=66BD=66

    The shortest route B\to F\to C\to D has length 6666.

  7. Delete vertex BB and every arc joined to it

    remaining vertices:  A,  C,  D,  E,  F\text{remaining vertices}:\;A,\;C,\;D,\;E,\;F

    The lower bound is built from the network on the other 55 vertices.

  8. List the arcs of the remaining network in ascending order

    CF=15,  CD=16,  AC=28,  DF=31,  AF=43,  AD=44,  EF=45,  AE=55,  CE=60,  DE=61CF=15,\;CD=16,\;AC=28,\;DF=31,\;AF=43,\;AD=44,\;EF=45,\;AE=55,\;CE=60,\;DE=61

    A minimum spanning tree for these 55 vertices is now needed.

  9. Build the minimum spanning tree of the remaining network

    AC=28,  CF=15,  CD=16,  EF=45AC=28,\;CF=15,\;CD=16,\;EF=45

    Each arc chosen is the shortest arc joining the tree built so far to a vertex not yet in it.

  10. Add the lengths of the arcs of the residual tree

    28+15+16+45=10428+15+16+45=104

    The residual minimum spanning tree has total weight 104104.

  11. Add back the two shortest arcs from BB

    BF=35,  BC=50BF=35,\;BC=50

    In any tour, vertex BB is joined to exactly two other vertices, so at least the two shortest arcs at BB must be used.

  12. Note that all the distances in this network are different

    distinct weights  ⇒  the nearest neighbour is never ambiguous\text{distinct weights}\;\Rightarrow\;\text{the nearest neighbour is never ambiguous}

    With no two arcs of equal length, the nearest unvisited vertex is always unique, so the algorithm has a single well-defined output.

  13. Recall that the nearest-neighbour algorithm gives an UPPER bound

    optimal tour≤any tour found by nearest neighbour\text{optimal tour}\leq\text{any tour found by nearest neighbour}

    The nearest-neighbour algorithm produces a genuine tour, and the optimal tour cannot be longer than a tour we have actually found.

  14. Recall that deleting a vertex gives a LOWER bound

    residual minimum spanning tree+two shortest arcs≤optimal tour\text{residual minimum spanning tree}+\text{two shortest arcs}\leq\text{optimal tour}

    Removing a vertex from any tour leaves a path through the other vertices, which is a spanning tree of them, so it is at least as long as the minimum spanning tree.

  15. Add the two shortest arcs to the weight of the residual tree

    104+35+50=189104+35+50=189

    Deleting BB gives a lower bound of 189189 for the length of the optimal tour.

Answer
189189
Question 3
9 markschallenging
A network has vertices AA, BB, CC, DD, EE and FF. Not every pair of vertices is joined directly by an arc. The arcs of the network and their weights are AB=28AB=28, AC=65AC=65, AE=61AE=61, BC=56BC=56, BE=26BE=26, BF=36BF=36, CD=66CD=66, CE=19CE=19, DE=60DE=60, EF=44EF=44. In the practical travelling salesman problem a vertex may be visited more than once, so the algorithms are applied to the complete network of least distances, in which the distance between two vertices is the length of the shortest route between them; this table of least distances satisfies the triangle inequality. Using the table of least distances, apply the nearest-neighbour algorithm starting at CC to find an upper bound for the length of the optimal practical tour.
Show worked solution

Worked solution

  1. Find the least distance from AA to DD

    A→B→E→D=114;\quadA→E→D=121;\quadA→C→D=131;\quadA→B→E→C→D=139A\to B\to E\to D=114;\quadA\to E\to D=121;\quadA\to C\to D=131;\quadA\to B\to E\to C\to D=139

    There is no direct arc from AA to DD, so the least distance is the length of the shortest route, A\to B\to E\to D.

  2. Enter the least distance AD=114AD=114 in the table of least distances

    AD=114AD=114

    The shortest route A\to B\to E\to D has length 114114.

  3. Find the least distance from AA to FF

    A→B→F=64;\quadA→B→E→F=98;\quadA→E→F=105;\quadA→E→B→F=123A\to B\to F=64;\quadA\to B\to E\to F=98;\quadA\to E\to F=105;\quadA\to E\to B\to F=123

    There is no direct arc from AA to FF, so the least distance is the length of the shortest route, A\to B\to F.

  4. Enter the least distance AF=64AF=64 in the table of least distances

    AF=64AF=64

    The shortest route A\to B\to F has length 6464.

  5. Find the least distance from BB to DD

    B→E→D=86;\quadB→E→C→D=111;\quadB→C→D=122;\quadB→C→E→D=135B\to E\to D=86;\quadB\to E\to C\to D=111;\quadB\to C\to D=122;\quadB\to C\to E\to D=135

    There is no direct arc from BB to DD, so the least distance is the length of the shortest route, B\to E\to D.

  6. Enter the least distance BD=86BD=86 in the table of least distances

    BD=86BD=86

    The shortest route B\to E\to D has length 8686.

  7. Start the tour at CC

    visited={C}\text{visited}=\left\{C\right\}

    The nearest-neighbour algorithm must be given a starting vertex; a different start can give a different tour.

  8. From CC the nearest unvisited vertex is EE

    CE=19running total=19CE=19\quad\text{running total}=19

    The arcs from CC to the unvisited vertices are CE=19CE=19,\;CB=45CB=45,\;CF=63CF=63,\;CA=65CA=65,\;CD=66CD=66, and the shortest of these is CE=19CE=19.

  9. From EE the nearest unvisited vertex is BB

    EB=26running total=45EB=26\quad\text{running total}=45

    The arcs from EE to the unvisited vertices are EB=26EB=26,\;EF=44EF=44,\;EA=54EA=54,\;ED=60ED=60, and the shortest of these is EB=26EB=26.

  10. From BB the nearest unvisited vertex is AA

    BA=28running total=73BA=28\quad\text{running total}=73

    The arcs from BB to the unvisited vertices are BA=28BA=28,\;BF=36BF=36,\;BD=86BD=86, and the shortest of these is BA=28BA=28.

  11. From AA the nearest unvisited vertex is FF

    AF=64running total=137AF=64\quad\text{running total}=137

    The arcs from AA to the unvisited vertices are AF=64AF=64,\;AD=114AD=114, and the shortest of these is AF=64AF=64.

  12. From FF the nearest unvisited vertex is DD

    FD=104running total=241FD=104\quad\text{running total}=241

    The arcs from FF to the unvisited vertices are FD=104FD=104, and the shortest of these is FD=104FD=104.

  13. Note that all the distances in this network are different

    distinct weights  ⇒  the nearest neighbour is never ambiguous\text{distinct weights}\;\Rightarrow\;\text{the nearest neighbour is never ambiguous}

    With no two arcs of equal length, the nearest unvisited vertex is always unique, so the algorithm has a single well-defined output.

  14. Recall that the nearest-neighbour algorithm gives an UPPER bound

    optimal tour≤any tour found by nearest neighbour\text{optimal tour}\leq\text{any tour found by nearest neighbour}

    The nearest-neighbour algorithm produces a genuine tour, and the optimal tour cannot be longer than a tour we have actually found.

  15. Add the arc lengths to find the length of the tour

    19+26+28+64+104+66=30719+26+28+64+104+66=307

    The nearest-neighbour tour from CC is C\to E\to B\to A\to F\to D\to C, of length 307307; this is an upper bound for the optimal tour.

Answer
307307
Question 4
9 markschallenging
A network has vertices AA, BB, CC, DD, EE and FF. Not every pair of vertices is joined directly by an arc. The arcs of the network and their weights are AB=26AB=26, AE=20AE=20, AF=24AF=24, BC=49BC=49, BD=45BD=45, BE=33BE=33, BF=46BF=46, CF=56CF=56, DE=66DE=66, EF=37EF=37. In the practical travelling salesman problem a vertex may be visited more than once, so the algorithms are applied to the complete network of least distances, in which the distance between two vertices is the length of the shortest route between them; this table of least distances satisfies the triangle inequality. Using the table of least distances, apply the nearest-neighbour algorithm starting at AA to find an upper bound for the length of the optimal practical tour.
Show worked solution

Worked solution

  1. Find the least distance from AA to CC

    A→B→C=75;\quadA→F→C=80;\quadA→E→B→C=102;\quadA→E→F→C=113A\to B\to C=75;\quadA\to F\to C=80;\quadA\to E\to B\to C=102;\quadA\to E\to F\to C=113

    There is no direct arc from AA to CC, so the least distance is the length of the shortest route, A\to B\to C.

  2. Enter the least distance AC=75AC=75 in the table of least distances

    AC=75AC=75

    The shortest route A\to B\to C has length 7575.

  3. Find the least distance from AA to DD

    A→B→D=71;\quadA→E→D=86;\quadA→E→B→D=98;\quadA→F→B→D=115A\to B\to D=71;\quadA\to E\to D=86;\quadA\to E\to B\to D=98;\quadA\to F\to B\to D=115

    There is no direct arc from AA to DD, so the least distance is the length of the shortest route, A\to B\to D.

  4. Enter the least distance AD=71AD=71 in the table of least distances

    AD=71AD=71

    The shortest route A\to B\to D has length 7171.

  5. Find the least distance from CC to DD

    C→B→D=94;\quadC→F→B→D=147;\quadC→B→E→D=148;\quadC→F→A→B→D=151C\to B\to D=94;\quadC\to F\to B\to D=147;\quadC\to B\to E\to D=148;\quadC\to F\to A\to B\to D=151

    There is no direct arc from CC to DD, so the least distance is the length of the shortest route, C\to B\to D.

  6. Enter the least distance CD=94CD=94 in the table of least distances

    CD=94CD=94

    The shortest route C\to B\to D has length 9494.

  7. Start the tour at AA

    visited={A}\text{visited}=\left\{A\right\}

    The nearest-neighbour algorithm must be given a starting vertex; a different start can give a different tour.

  8. From AA the nearest unvisited vertex is EE

    AE=20running total=20AE=20\quad\text{running total}=20

    The arcs from AA to the unvisited vertices are AE=20AE=20,\;AF=24AF=24,\;AB=26AB=26,\;AD=71AD=71,\;AC=75AC=75, and the shortest of these is AE=20AE=20.

  9. From EE the nearest unvisited vertex is BB

    EB=33running total=53EB=33\quad\text{running total}=53

    The arcs from EE to the unvisited vertices are EB=33EB=33,\;EF=37EF=37,\;ED=66ED=66,\;EC=82EC=82, and the shortest of these is EB=33EB=33.

  10. From BB the nearest unvisited vertex is DD

    BD=45running total=98BD=45\quad\text{running total}=98

    The arcs from BB to the unvisited vertices are BD=45BD=45,\;BF=46BF=46,\;BC=49BC=49, and the shortest of these is BD=45BD=45.

  11. From DD the nearest unvisited vertex is FF

    DF=91running total=189DF=91\quad\text{running total}=189

    The arcs from DD to the unvisited vertices are DF=91DF=91,\;DC=94DC=94, and the shortest of these is DF=91DF=91.

  12. From FF the nearest unvisited vertex is CC

    FC=56running total=245FC=56\quad\text{running total}=245

    The arcs from FF to the unvisited vertices are FC=56FC=56, and the shortest of these is FC=56FC=56.

  13. Note that all the distances in this network are different

    distinct weights  ⇒  the nearest neighbour is never ambiguous\text{distinct weights}\;\Rightarrow\;\text{the nearest neighbour is never ambiguous}

    With no two arcs of equal length, the nearest unvisited vertex is always unique, so the algorithm has a single well-defined output.

  14. Recall that the nearest-neighbour algorithm gives an UPPER bound

    optimal tour≤any tour found by nearest neighbour\text{optimal tour}\leq\text{any tour found by nearest neighbour}

    The nearest-neighbour algorithm produces a genuine tour, and the optimal tour cannot be longer than a tour we have actually found.

  15. Add the arc lengths to find the length of the tour

    20+33+45+91+56+75=32020+33+45+91+56+75=320

    The nearest-neighbour tour from AA is A\to E\to B\to D\to F\to C\to A, of length 320320; this is an upper bound for the optimal tour.

Answer
320320
Question 5
9 markschallenging
A complete network has vertices AA, BB, CC, DD, EE, FF and GG. The distances between the vertices are AB=83AB=83, AC=36AC=36, AD=75AD=75, AE=20AE=20, AF=26AF=26, AG=81AG=81, BC=33BC=33, BD=62BD=62, BE=88BE=88, BF=71BF=71, BG=29BG=29, CD=51CD=51, CE=54CE=54, CF=59CF=59, CG=44CG=44, DE=91DE=91, DF=61DF=61, DG=84DG=84, EF=14EF=14, EG=11EG=11, FG=12FG=12. In the classical travelling salesman problem each vertex must be visited exactly once and the tour finishes where it started. The nearest-neighbour algorithm is applied, starting at BB. Which of the following is the tour that it produces?
Show worked solution

Worked solution

  1. Start the tour at BB

    visited={B}\text{visited}=\left\{B\right\}

    The nearest-neighbour algorithm must be given a starting vertex; a different start can give a different tour.

  2. From BB the nearest unvisited vertex is GG

    BG=29running total=29BG=29\quad\text{running total}=29

    The arcs from BB to the unvisited vertices are BG=29BG=29,\;BC=33BC=33,\;BD=62BD=62,\;BF=71BF=71,\;BA=83BA=83,\;BE=88BE=88, and the shortest of these is BG=29BG=29.

  3. From GG the nearest unvisited vertex is EE

    GE=11running total=40GE=11\quad\text{running total}=40

    The arcs from GG to the unvisited vertices are GE=11GE=11,\;GF=12GF=12,\;GC=44GC=44,\;GA=81GA=81,\;GD=84GD=84, and the shortest of these is GE=11GE=11.

  4. From EE the nearest unvisited vertex is FF

    EF=14running total=54EF=14\quad\text{running total}=54

    The arcs from EE to the unvisited vertices are EF=14EF=14,\;EA=20EA=20,\;EC=54EC=54,\;ED=91ED=91, and the shortest of these is EF=14EF=14.

  5. From FF the nearest unvisited vertex is AA

    FA=26running total=80FA=26\quad\text{running total}=80

    The arcs from FF to the unvisited vertices are FA=26FA=26,\;FC=59FC=59,\;FD=61FD=61, and the shortest of these is FA=26FA=26.

  6. From AA the nearest unvisited vertex is CC

    AC=36running total=116AC=36\quad\text{running total}=116

    The arcs from AA to the unvisited vertices are AC=36AC=36,\;AD=75AD=75, and the shortest of these is AC=36AC=36.

  7. From CC the nearest unvisited vertex is DD

    CD=51running total=167CD=51\quad\text{running total}=167

    The arcs from CC to the unvisited vertices are CD=51CD=51, and the shortest of these is CD=51CD=51.

  8. Every vertex has now been visited, so return to BB

    DB=62running total=229DB=62\quad\text{running total}=229

    The tour must finish where it started, so the arc DBDB is used to close the tour.

  9. Write down the tour produced

    B→G→E→F→A→C→D→BB\to G\to E\to F\to A\to C\to D\to B

    This is the tour that the nearest-neighbour algorithm produces from BB.

  10. Note that all the distances in this network are different

    distinct weights  ⇒  the nearest neighbour is never ambiguous\text{distinct weights}\;\Rightarrow\;\text{the nearest neighbour is never ambiguous}

    With no two arcs of equal length, the nearest unvisited vertex is always unique, so the algorithm has a single well-defined output.

  11. Recall that the nearest-neighbour algorithm gives an UPPER bound

    optimal tour≤any tour found by nearest neighbour\text{optimal tour}\leq\text{any tour found by nearest neighbour}

    The nearest-neighbour algorithm produces a genuine tour, and the optimal tour cannot be longer than a tour we have actually found.

  12. Recall that deleting a vertex gives a LOWER bound

    residual minimum spanning tree+two shortest arcs≤optimal tour\text{residual minimum spanning tree}+\text{two shortest arcs}\leq\text{optimal tour}

    Removing a vertex from any tour leaves a path through the other vertices, which is a spanning tree of them, so it is at least as long as the minimum spanning tree.

  13. Count the possible tours in a complete network on 77 vertices

    (7−1)!2=360\frac{\left(7-1\right)!}{2}=360

    There are 360360 distinct tours, so checking them all by hand is not practical for larger networks; this is why bounds are used.

  14. Check that the best lower bound does not exceed the best upper bound

    217≤229217\leq 229

    The best lower bound obtainable here is 217217 and the best upper bound is 229229, so the two bounds are consistent.

  15. Select the tour produced by the algorithm

    B→G→E→F→A→C→D→Blength=229B\to G\to E\to F\to A\to C\to D\to B\quad\text{length}=229

    Starting at BB and always moving to the nearest unvisited vertex gives this tour, of length 229229.

Answer
B→G→E→F→A→C→D→BB\to G\to E\to F\to A\to C\to D\to B

Unlock 29 more Travelling salesman problem questions

Create a free account to work through every Further Maths Travelling salesman problem question with instant step-by-step worked solutions, progress tracking and interactive lessons.

  • Full worked solutions for every question
  • Interactive lessons and instant feedback
  • Track your mastery across every topic
Create a Free Account

No card required · Free forever

More Travelling salesman problem practice

Practice QuestionsWorked Solutions

Related Decision Maths topics

AlgorithmsAllocation (assignment)Critical path analysisDecision analysisDynamic programmingFlows in networks