Travelling salesman: constructive heuristics and 2-opt

A technician has to visit twenty customers in a day and return to base. In what order should they go to drive the fewest kilometres? This is the travelling salesman problem (TSP), probably the most studied combinatorial optimisation problem of all.

Stating it is easy: given a set of cities and the distances between every pair, find the shortest tour that visits each of them exactly once and returns to the starting point. Solving it to optimality is another matter.

Why it is hard

With n cities, once the starting one is fixed, there are (n − 1)!/2 possible tours if distances are symmetric. With 10 cities there are 181,440, which is manageable. With 20 there are about 6 · 10^16. With 50 the number far exceeds any possibility of enumeration.

The TSP is NP-hard: no exact algorithm is known that solves it in polynomial time. Held and Karp's dynamic programming brings the cost down to about n² · 2^n, enormously better than enumeration but still exponential. For large instances, exact solvers based on integer programming and cutting planes achieve remarkable results, but in everyday practice heuristics are used above all: fast algorithms that give good tours without a guarantee of optimality.

Constructive heuristics

They build a tour from scratch.

Nearest neighbour

Start from a city and always go to the nearest city not yet visited. At the end, return to the start. It is very simple and fast, but it tends to leave some distant, isolated cities until last, forcing long final moves. On typical instances it produces tours noticeably longer than the optimum.

Insertion

Start from a small tour, for example between two cities, and insert the others one at a time in the position that lengthens the tour the least. The variants differ in how the next city to insert is chosen:

• nearest insertion: the city closest to the current tour;
• farthest insertion: the city farthest from the tour; it seems counterintuitive, but it builds the «skeleton» of the route early and often gives better results;
• cheapest insertion: the city whose insertion costs the least.

The spanning-tree approximation

If distances respect the triangle inequality (going directly from A to C costs no more than going through B), there is a method with a guarantee:

1. build the minimum spanning tree of the cities;
2. traverse the tree depth-first, noting the cities in the order you first meet them;
3. connect the cities in that order and close the tour.

The resulting tour is at most twice the optimum. The reason: the tree costs less than the optimal tour (removing one edge from the tour gives a spanning tree), the full traversal walks each tree edge twice, and the shortcuts, thanks to the triangle inequality, do not lengthen it. Christofides' algorithm improves the guarantee to 1.5 by adding a minimum-cost matching between the odd-degree cities of the tree.

Improvement: the 2-opt move

Constructive heuristics produce tours with obvious flaws, such as routes that cross themselves. In the plane, a self-crossing tour is never optimal with Euclidean distances: it can always be shortened.

The 2-opt move removes two edges (A, B) and (C, D) from the tour and replaces them with (A, C) and (B, D), reversing the stretch in between. If the new length is shorter, the move is accepted.

def two_opt(tour, d):
    improved = True
    while improved:
        improved = False
        for i in range(1, len(tour) - 2):
            for j in range(i + 1, len(tour) - 1):
                a, b = tour[i - 1], tour[i]
                c, e = tour[j], tour[j + 1]
                if d[a][c] + d[b][e] < d[a][b] + d[c][e]:
                    tour[i:j + 1] = reversed(tour[i:j + 1])
                    improved = True
    return tour

Here the tour is a list that begins and ends with the same city. Moves are repeated until none improves: the result is a local optimum with respect to 2-opt.

There are more powerful moves: 3-opt replaces three edges, and the Lin-Kernighan heuristic adaptively combines moves of variable depth. Its modern implementations are among the most effective methods known for the TSP.

Knowing how far you are from the optimum

A heuristic gives a tour, but how good is it? You need lower bounds:

• the cost of the minimum spanning tree is always less than the optimal tour;
• the Held-Karp bound, based on 1-trees with penalties on the vertices, is much tighter and often very close to the optimum;
• the linear relaxation of an integer formulation of the TSP provides a similar bound.

Real-world variants

In practice the pure TSP is rare. There are customer time windows, several vehicles with limited capacity, one-way streets that make distances asymmetric, service times, mandatory breaks. These vehicle routing problems are tackled with the same ideas: construction, local improvement moves and metaheuristics that make it possible to escape local optima.

In short

• The TSP looks for the shortest tour visiting each city once; the combinations grow factorially.
• Nearest neighbour and insertion build tours quickly, with different quality.
• With the triangle inequality, the spanning tree gives a tour at most twice the optimum.
• The 2-opt move removes crossings and greatly improves constructive solutions.
• Lower bounds such as Held-Karp show how far a tour is from the optimum.