Question Type 8: Applying different approaches to solve the traveling salesman problem Exercises

Using the same distance matrix as above, apply the nearest neighbour heuristic starting from city A. List the order of visits and compute the total distance.

Given five points in the plane: P₁(0,0), P₂(2,3), P₃(5,4), P₄(6,1), P₅(3,−1), apply the nearest neighbour heuristic starting at P₁. Compute the sequence of visits and the approximate tour length (use Euclidean distances).

Prove that in a complete graph on $n$ labelled vertices, the number of distinct Hamiltonian circuits (up to starting point and direction) is $\dfrac{(n-1)!}{2}$. Then compute this number for $n=8$.

In a logistics network with six stops labelled 1–6, the distance matrix is

Apply the nearest neighbour heuristic starting at stop 3. Give the tour and its total distance.

Compare the route obtained by the nearest neighbour heuristic (from question 2) with the exact optimal route for the same matrix. Compute the percentage excess of the heuristic over the optimum.

Given the complete graph on nodes 1 to 5 with weights

For four cities A, B, C and D with distance matrix

find the shortest Hamiltonian circuit visiting each city exactly once and returning to the start. Provide the tour and its total length.

A machine must process five tasks A–E with setup times given by

Find the sequence of tasks (a Hamiltonian circuit) that minimizes total setup time by complete enumeration.

For the tour found in the previous question, perform one 2-opt swap to attempt an improvement. Indicate the new route and its length if it decreases.

For the same 4-city matrix, use Held–Karp dynamic programming to compute the exact optimal TSP cost. Outline the recurrence and compute the final value.

Using the distance matrix from question 1, apply Christofides’ heuristic to approximate a TSP tour. Describe each step and give the resulting tour weight.

Using the distance matrix from question 1, perform a branch and bound demonstration. Show how you compute a lower bound (using an MST-based bound), explore one branch, and prune another branch. Identify the final optimal tour.