Traveling Salesperson Problem (TSP)

The Simplest Explanation

You have a list of cities and distances between every pair. Visit each city exactly once and return home. Find the shortest possible tour.

That's the entire problem. It's trivial to state, brutally hard to solve optimally for large instances, and shows up everywhere — logistics, circuit board drilling, DNA sequencing.

The Problem Formally

Given: A complete graph with $n$ vertices, edge weights $d(i,j)$ representing distance/cost between cities $i$ and $j$.

Find: A Hamiltonian cycle (tour visiting every vertex exactly once) with minimum total cost.

$\min_{\pi \in \text{permutations}} \sum_{i=1}^{n-1} d(\pi_i, \pi_{i+1}) + d(\pi_n, \pi_1)$

Distance Matrix

The input to TSP is a distance matrix (also called cost matrix). For 5 cities:

• The matrix is symmetric ($d(A,B) = d(B,A)$) for standard TSP
• Diagonal is meaningless (distance from a city to itself)
• Read: "From A to B costs 3, from A to C costs 7, from D to E costs 2"

Symmetric vs Asymmetric TSP

• Symmetric TSP: $d(i,j) = d(j,i)$ for all pairs. Road networks are symmetric.
• Asymmetric TSP (ATSP): $d(i,j) \neq d(j,i)$ in general. Airfares, one-way streets, shipping costs are asymmetric.

The Scale of the Problem

This is why exact methods (brute force, BnB, dynamic programming) only work for small instances. For real-world problems with hundreds or thousands of cities, heuristic methods are essential.

Nearest Neighbor Heuristic

The simplest constructive heuristic: always go to the closest unvisited city.

1. Start at any city
2. Go to the nearest unvisited city
3. Repeat until all cities visited
4. Return to start

Nearest Neighbor Result

Starting from A: A→B→C→E→D→A = 3+4+7+2+10 = 26

But the optimal tour is: A→E→D→C→B→A = 5+2+8+4+3 = 22

Nearest neighbor missed the optimal by 4 (18% over optimal). This is typical — nearest neighbor can produce tours up to 50% longer than optimal in the worst case.

Properties of Nearest Neighbor

2-Opt Improvement

Nearest neighbor gives an initial tour. 2-opt improves it by swapping edges.

The Idea

Remove two edges from the tour, reconnect the two resulting paths in the other possible way. If the new tour is shorter, keep it.

Before: ...→ A → B → ... → C → D →...
Swap edges A-B and C-D:
After:  ...→ A → C → ... → B → D →...

2-Opt on Our Example

Starting tour: A→B→C→E→D→A (cost 26)

1. Try swapping edges (B,C) and (E,D): A→B→E→C→D→A = 3+6+7+8+10 = 34. Worse.
2. Try swapping edges (A,B) and (D,A): This creates A→D→E→C→B→A = 10+2+7+4+3 = 26. Same.
3. Try swapping edges (C,E) and (D,A): A→B→C→D→E→A = 3+4+8+2+5 = 22. Better! Found the optimal.

2-opt is a local search — it finds a locally optimal tour where no 2-edge swap improves it. The result depends on the starting tour.

Other TSP Heuristics

Christofiles Algorithm (Guaranteed Bound)

For metric TSP (triangle inequality holds), Christofides guarantees a tour within 1.5× optimal:

1. Build a minimum spanning tree (MST)
2. Find a minimum weight perfect matching on the odd-degree vertices
3. Combine them into a tour

This is the best known polynomial-time approximation ratio for metric TSP.

Properties Summary