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

Question 1

Skill question

This question requires the formulation of an integer linear programming (ILP) model for the Traveling Salesperson Problem (TSP) on four cities using the Miller-Tucker-Zemlin (MTZ) subtour elimination constraints.

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).

[7]

Question 2

Skill question

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

[4]

Question 3

Skill question

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

$- 37456 3 - 4287 74 - 593 425 - 64 5896 - 5 67345 -$

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.

[5]

Question 4

Skill question

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

$0101520100352515350302025300$

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

[4]

Question 5

Skill question

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

$0476540386730246820356430$

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.

[6]

Question 6

Skill question

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

$- 29107 2 - 643 96 - 85 1048 - 4 7354 -$

Give the resulting approximate tour and its total length.

[7]

Question 7

Skill question

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

$- 34276 3 - 4635 44 - 584 265 - 67 7386 - 5 65475 -$

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

[11]

Question 8

Skill question

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

$A B C D A - 101520 B 10 - 3525 C 1535 - 30 D 202530 -$

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

[4]

Question 9

Skill question

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

$- 261 3 - 35 87 - 2 549 -$

Find the shortest directed Hamiltonian circuit and its total time.

[5]

Question 10

Skill question

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).

[4]

Question 11

Skill question

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.

$\infty 29107 2 \infty 643 96 \infty 85 1048 \infty 4 7354 \infty$

[8]

IB Mathematics Applications & Interpretation Question Type 9: Applying the Traveling Salesman Problem in Real World Contexts Exercises