Traveling Salesman Problem (TSP)

Visit every city exactly once, return home, minimize total distance.

Intuition

Why it's hard

There are (N−1)!/2 distinct tours. At 500 000 ops/sec:

• N = 10 → ~1 minute
• N = 11 → ~13 minutes
• N = 13 → ~34 hours
• N = 20 → millions of years

So we use heuristics: methods that get a "good enough" tour fast, without enumerating everything.

Construction heuristics — build a tour from scratch

1. Random tour

Pick a random starting city; mark visited.
while (not all visited):
    Pick a random unvisited city, connect it.

2. Iterated random search

Run random tour MaxTries times, keep the best. Researchers typically cap at ~5 tries.

3. Greedy (nearest-neighbor)

Pick a starting city; mark visited.
while (not done):
    From the current city, jump to the closest unvisited city.

Fast and intuitive, but can get trapped — last few hops are often very long.

4. Random Insertion (RI)

Start with 2 cities forming a tiny tour.
while (cities left):
    Pick a random unvisited city C.
    Insert C at the position causing the smallest increase in tour length.

5. Cheapest Insertion

Start with 2 cities forming a tiny tour.
while (cities left):
    For each unvisited city, compute the cheapest insertion.
    Pick the city whose cheapest insertion is the cheapest of all.

Improvement heuristics — locally optimize a given tour

Greedy swap (Heuristic-1)

while (not stop):
    pick two random cities C1, C2.
    swap them in the tour.
    if (tour shorter) accept else revert.

Stopping criteria can be: a fixed number of iterations, a time limit, or "no improvement for K iterations".

2-opt explained

while (not stop):
    pick random edges (i,j) and (k,l).
    remove these two edges; reconnect as (i,k), (j,l)
    (which reverses the segment between j and k).
    if (tour shorter) accept else revert.

Tiny example from your notes:

Before:  1—2—3—4—5—6—7—8—9—10
Pick edges (3—4) and (8—9). Reconnect:
After:   1—2—3—8—7—6—5—4—9—10   ← segment 4..8 reversed

3-opt

Remove three edges and reconnect. There are several ways to reconnect; the algorithm tries each:

while (not stop):
    pick three random edges (i,j), (k,l), (m,n).
    reconnect as (i,k)(j,l)(m,n)       // pass 1
    or          (i,k)(j,m)(l,n)        // pass 2
    keep the one that improves the tour.

Interactive demo

Click in the canvas to add cities, or press "Random 12". Then try the heuristics.

Exam tips