Question Type 9: Applying the traveling salesman problem in real world contexts Exercises

Formulate an integer linear programming model for a Traveling Salesperson Problem (TSP) on four cities $1, 2, 3, 4$. Define the decision variables, the objective function, and all necessary constraints (do not solve).

Formulate a general subtour elimination constraint for a TSP on $n$ cities using set notation, and explain how it prevents subtours.

A traveling salesperson problem with six nodes has the following distance matrix:

Calculate a lower bound for the optimal tour length by summing the two smallest distances from each node and dividing the total by 2. Given a feasible tour length of 23, determine the percentage gap between this lower bound and the feasible tour length.

Given the distance matrix for cities $A$, $B$, $C$, $D$:

Find the shortest Hamiltonian circuit (starting and ending at $A$) and its total length.

Given a TSP tour $A \to B \to C \to D \to E \to A$ on five cities with the following distance matrix:

Perform a 2-opt swap by replacing the edges $(C, D)$ and $(E, A)$ with the edges $(C, E)$ and $(D, A)$. State the new tour, calculate its length, and determine whether this swap improves the original tour.

Apply Christofides’ algorithm to the symmetric 5-city Traveling Salesperson Problem (TSP) with the following distance matrix:

$\begin{pmatrix} - & 2 & 9 & 10 & 7 \\ 2 & - & 6 & 4 & 3 \\ 9 & 6 & - & 8 & 5 \\ 10 & 4 & 8 & - & 4 \\ 7 & 3 & 5 & 4 & - \end{pmatrix}$

Give the resulting approximate tour and its total length.

Use the nearest insertion heuristic on six cities 1–6 with symmetric distances defined by the following matrix:

Start with the edge $(1,4)$. Show each insertion step, the final tour, and its total length.

Apply the nearest neighbor heuristic starting at city $A$. Determine the tour produced and its total length.

Solve the asymmetric traveling salesperson problem (TSP) for four cities A, B, C, and D with travel times given in the following weight matrix:

Find the shortest directed Hamiltonian circuit and its total time.

For six cities with coordinates $A(0,0)$, $B(2,3)$, $C(5,2)$, $D(6,6)$, $E(8,3)$, and $F(7,0)$, compute a lower bound for the Traveling Salesman Problem (TSP) using the weight of the minimum spanning tree (MST).

Solve the Traveling Salesperson Problem (TSP) for five cities 1–5 with symmetric distances given in the matrix below using the branch and bound method. Show the initial lower bound calculation, the branching process, and determine the optimal tour and its total cost.