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

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

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

Using the same distance matrix from Question 1, apply the nearest neighbor heuristic starting at city A. Determine the tour produced and its total length.

Formulate an integer linear programming model for a TSP on four cities 1,2,3,4. Define variables, objective function and constraints (do not solve).

Solve the TSP for five cities 1–5 with symmetric distances given below using branch and bound. Show the branching, bounds and optimal tour.

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

Solve the asymmetric TSP for four cities A,B,C,D with travel times:

Find the shortest directed Hamiltonian circuit and its total time.

Given a TSP tour A→B→C→D→E→A on five cities with distances:

Apply one 2-opt swap to improve the tour and give the new route and its length.

Apply Christofides’ algorithm to the symmetric 5-city TSP with distances:

Give the approximate tour and its length.

Use the nearest insertion heuristic on six cities 1–6 with symmetric distances:

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

For six nodes with distance matrix:

compute a lower bound via the assignment relaxation (1-tree bound) by summing the two smallest distances from each node divided by 2, and compare with a feasible tour length of 23 to find the percentage gap.

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