Travelling salesman problem Worked Solutions — Further Maths Maths

Fully worked, step-by-step solutions to Further Maths Travelling salesman problem questions. See exactly how to solve problems on travelling-salesman, nearest-neighbour, upper-bound, optimal-tour.

travelling-salesmannearest-neighbourupper-boundoptimal-tournetworkslower-bound
Further Maths70 questionsStep-by-step solutions
Question 1
2 markseasy
A complete network has vertices AA, BB, CC, DD and EE. The distances between the vertices are AB=14AB=14, AC=87AC=87, AD=61AD=61, AE=92AE=92, BC=74BC=74, BD=30BD=30, BE=29BE=29, CD=68CD=68, CE=75CE=75, DE=50DE=50. In the classical travelling salesman problem each vertex must be visited exactly once and the tour finishes where it started. Use the nearest-neighbour algorithm on this network, starting at AA, to find an upper bound for the length of the optimal tour.

Worked solution

  1. Start at AA and repeatedly go to the nearest unvisited vertex

    tour:  A→B→E→D→C→A\text{tour}:\;A\to B\to E\to D\to C\to A

    At each stage the algorithm takes the shortest arc to a vertex that has not yet been visited, and finally returns to AA.

  2. Add the lengths of the arcs used, including the return to AA

    14+29+50+68+87=24814+29+50+68+87=248

    The tour uses the arcs AB,\;BE,\;ED,\;DC,\;CA.

  3. State the upper bound

    upper bound=248\text{upper bound}=248

    The tour A\to B\to E\to D\to C\to A has length 248248, so the optimal tour is no longer than 248248.

Answer
248248
Question 2
2 markseasy
A complete network has vertices AA, BB, CC, DD and EE. The distances between the vertices are AB=37AB=37, AC=38AC=38, AD=82AD=82, AE=53AE=53, BC=89BC=89, BD=85BD=85, BE=67BE=67, CD=93CD=93, CE=77CE=77, DE=79DE=79. In the classical travelling salesman problem each vertex must be visited exactly once and the tour finishes where it started. Use the nearest-neighbour algorithm on this network, starting at AA, to find an upper bound for the length of the optimal tour.

Worked solution

  1. Start at AA and repeatedly go to the nearest unvisited vertex

    tour:  A→B→E→C→D→A\text{tour}:\;A\to B\to E\to C\to D\to A

    At each stage the algorithm takes the shortest arc to a vertex that has not yet been visited, and finally returns to AA.

  2. Add the lengths of the arcs used, including the return to AA

    37+67+77+93+82=35637+67+77+93+82=356

    The tour uses the arcs AB,\;BE,\;EC,\;CD,\;DA.

  3. State the upper bound

    upper bound=356\text{upper bound}=356

    The tour A\to B\to E\to C\to D\to A has length 356356, so the optimal tour is no longer than 356356.

Answer
356356
Question 3
2 markseasy
A complete network has vertices AA, BB, CC, DD and EE. The distances between the vertices are AB=40AB=40, AC=89AC=89, AD=6AD=6, AE=57AE=57, BC=27BC=27, BD=22BD=22, BE=45BE=45, CD=12CD=12, CE=65CE=65, DE=72DE=72. In the classical travelling salesman problem each vertex must be visited exactly once and the tour finishes where it started. Use the nearest-neighbour algorithm on this network, starting at CC, to find an upper bound for the length of the optimal tour.

Worked solution

  1. Start at CC and repeatedly go to the nearest unvisited vertex

    tour:  C→D→A→B→E→C\text{tour}:\;C\to D\to A\to B\to E\to C

    At each stage the algorithm takes the shortest arc to a vertex that has not yet been visited, and finally returns to CC.

  2. Add the lengths of the arcs used, including the return to CC

    12+6+40+45+65=16812+6+40+45+65=168

    The tour uses the arcs CD,\;DA,\;AB,\;BE,\;EC.

  3. State the upper bound

    upper bound=168\text{upper bound}=168

    The tour C\to D\to A\to B\to E\to C has length 168168, so the optimal tour is no longer than 168168.

Answer
168168
Question 4
2 markseasy
The distance matrix of a complete network is (−82277248−8366522283−7044776670−5024524450−)\begin{pmatrix} - & 8 & 22 & 77 & 24 \\ 8 & - & 83 & 66 & 52 \\ 22 & 83 & - & 70 & 44 \\ 77 & 66 & 70 & - & 50 \\ 24 & 52 & 44 & 50 & - \end{pmatrix}, where the rows and columns are taken in the order AA, BB, CC, DD, EE and a dash on the diagonal shows that a vertex is not joined to itself. In the classical travelling salesman problem each vertex must be visited exactly once and the tour finishes where it started. Use the nearest-neighbour algorithm on this distance matrix, starting at BB, to find an upper bound for the length of the optimal tour.

Worked solution

  1. Start at BB and repeatedly go to the nearest unvisited vertex

    tour:  B→A→C→E→D→B\text{tour}:\;B\to A\to C\to E\to D\to B

    At each stage the algorithm takes the shortest arc to a vertex that has not yet been visited, and finally returns to BB.

  2. Add the lengths of the arcs used, including the return to BB

    8+22+44+50+66=1908+22+44+50+66=190

    The tour uses the arcs BA,\;AC,\;CE,\;ED,\;DB.

  3. State the upper bound

    upper bound=190\text{upper bound}=190

    The tour B\to A\to C\to E\to D\to B has length 190190, so the optimal tour is no longer than 190190.

Answer
190190
Question 5
2 markseasy
The distance matrix of a complete network is (−1790477317−3336889033−6672473666−6973887269−)\begin{pmatrix} - & 17 & 90 & 47 & 73 \\ 17 & - & 33 & 36 & 88 \\ 90 & 33 & - & 66 & 72 \\ 47 & 36 & 66 & - & 69 \\ 73 & 88 & 72 & 69 & - \end{pmatrix}, where the rows and columns are taken in the order AA, BB, CC, DD, EE and a dash on the diagonal shows that a vertex is not joined to itself. In the classical travelling salesman problem each vertex must be visited exactly once and the tour finishes where it started. Use the nearest-neighbour algorithm on this distance matrix, starting at EE, to find an upper bound for the length of the optimal tour.

Worked solution

  1. Start at EE and repeatedly go to the nearest unvisited vertex

    tour:  E→D→B→A→C→E\text{tour}:\;E\to D\to B\to A\to C\to E

    At each stage the algorithm takes the shortest arc to a vertex that has not yet been visited, and finally returns to EE.

  2. Add the lengths of the arcs used, including the return to EE

    69+36+17+90+72=28469+36+17+90+72=284

    The tour uses the arcs ED,\;DB,\;BA,\;AC,\;CE.

  3. State the upper bound

    upper bound=284\text{upper bound}=284

    The tour E\to D\to B\to A\to C\to E has length 284284, so the optimal tour is no longer than 284284.

Answer
284284

Unlock 65 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

Hard QuestionsPractice Questions

Related Decision Maths topics

AlgorithmsAllocation (assignment)Critical path analysisDecision analysisDynamic programmingFlows in networks