RevisionDojo

Question 1

Consider the following distance matrix for a complete graph with 4 nodes, $A$ , $B$ , $C$ , and $D$ :

\begin{array}{c|cccc} & A & B & C & D \\ \hline A & - & 10 & 15 & 30 \\ B & 10 & - & 20 & 25 \\ C & 15 & 20 & - & 30 \\ D & 30 & 25 & 30 & - \end{array}

Using the distance matrix provided, apply Christofides’ heuristic to approximate a TSP tour. Describe each step of the algorithm and determine the weight of the resulting tour.

[6]

Question 2

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

[5]

Question 3

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

D = \begin{pmatrix} 0 & 3 & 4 & 2 & 7 & 8\\ 3 & 0 & 5 & 6 & 9 & 3\\ 4 & 5 & 0 & 3 & 4 & 5\\ 2 & 6 & 3 & 0 & 5 & 6\\ 7 & 9 & 4 & 5 & 0 & 6\\ 8 & 3 & 5 & 6 & 6 & 0 \end{pmatrix}.

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

[3]

Question 4

The following distance matrix shows the distances, in kilometres, between four cities $A$ , $B$ , $C$ , and $D$ .

$\begin{array}{c|cccc} & A & B & C & D \\ \hline A & - & 10 & 15 & 20 \\ B & 10 & - & 35 & 25 \\ C & 15 & 35 & - & 30 \\ D & 20 & 25 & 30 & - \end{array}$

Apply the nearest neighbour heuristic starting from city $A$ . State the order of visits and calculate the total distance of the tour found.

[4]

Question 5

A salesperson needs to visit four cities $A, B, C$ , and $D$ . The distances between the cities are given in the following distance matrix:

\begin{array}{c|cccc} & A & B & C & D \\ \hline A & - & 10 & 30 & 50 \\ B & 10 & - & 40 & 20 \\ C & 30 & 40 & - & 20 \\ D & 50 & 20 & 20 & - \end{array}

Perform a branch and bound demonstration to find the optimal Traveling Salesperson Problem (TSP) tour for these cities. In your demonstration:

(i) Compute an initial lower bound based on the Minimum Spanning Tree (MST) of all four nodes. (ii) Compute a more refined initial lower bound using the matrix reduction method (sum of row minima). (iii) Explore the branch $A \to B \to D \to C \to A$ and determine its cost. (iv) Explain how a branch could be pruned if an upper bound of $80$ is already known. (v) Identify the optimal tour and its total distance.

[8]

Question 6

A Traveling Salesman Problem involves five locations, $P_1, P_2, P_3, P_4$ , and $P_5$ . The distances between certain pairs of locations are given in the following table:

	$P_1$	$P_2$	$P_3$	$P_4$	$P_5$
$P_1$	-	$3.61$	$6.40$		$3.16$
$P_2$	$3.61$	-	$5.00$	$4.47$
$P_3$	$6.40$	$5.00$	-	$3.16$	$5.39$
$P_4$		$4.47$	$3.16$	-	$3.61$
$P_5$	$3.16$		$5.39$	$3.61$	-

A candidate tour has been identified as $P_1 \to P_5 \to P_4 \to P_3 \to P_2 \to P_1$ .

Perform one 2-opt swap on the given tour to attempt an improvement. Indicate the new route and its length, and state whether the tour length decreased.

[6]

Question 7

Given the complete graph on nodes 1 to 5 with weight matrix $W = \begin{pmatrix} 0 & 2 & 9 & 8 & 7 \\ 2 & 0 & 6 & 5 & 3 \\ 9 & 6 & 0 & 4 & 12 \\ 8 & 5 & 4 & 0 & 10 \\ 7 & 3 & 12 & 10 & 0 \end{pmatrix},$ compute the weight of a minimum spanning tree (MST) and use it to provide a lower bound for the Traveling Salesperson Problem (TSP) tour length.

[6]

Question 8

Discrete Mathematics: Graph Theory – Traveling Salesperson Problem (TSP)

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

D = \begin{pmatrix} 0 & 10 & 15 & 20 \\ 10 & 0 & 35 & 25 \\ 15 & 35 & 0 & 30 \\ 20 & 25 & 30 & 0 \end{pmatrix}

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

[4]

Question 9

A machine must process five tasks A–E with setup times given by the following matrix:

T = \begin{pmatrix} 0 & 4 & 8 & 5 & 7\\ 4 & 0 & 6 & 3 & 10\\ 8 & 6 & 0 & 9 & 2\\ 5 & 3 & 9 & 0 & 4\\ 7 & 10 & 2 & 4 & 0 \end{pmatrix}.

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

[6]

Question 10

Given five points in the plane: $P_1(0,0)$ , $P_2(2,3)$ , $P_3(5,4)$ , $P_4(6,1)$ , $P_5(3,-1)$ .

Apply the nearest neighbour heuristic starting at $P_1$ to find a tour for the travelling salesman problem (TSP).

State the sequence of visits and calculate the total length of the resulting tour.

[6]

Question 11

Consider a Traveling Salesperson Problem (TSP) with four cities: A, B, C, and D. The distances between the cities are given in the following table:

\begin{array}{c|cccc} & \text{A} & \text{B} & \text{C} & \text{D} \\ \hline \text{A} & - & 10 & 15 & 20 \\ \text{B} & 10 & - & 35 & 25 \\ \text{C} & 15 & 35 & - & 30 \\ \text{D} & 20 & 25 & 30 & - \end{array}

Using the Held–Karp dynamic programming algorithm, compute the exact optimal Traveling Salesperson Problem (TSP) cost for a tour starting and ending at city A. Outline the recurrence relations and show the computations for each step.

[6]

Question 12

This question assesses the ability to evaluate the performance of the nearest neighbour heuristic by comparing it with an exact optimal solution using percentage excess in the context of the Traveling Salesman Problem (TSP).

The length of the route obtained by the nearest neighbour heuristic is 80 units and the length of the exact optimal route for the same matrix is 80 units.

Calculate the percentage excess of the heuristic over the optimum and compare the performance of the heuristic with the optimal route.

[3]

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