Neighborhoods and the 2-opt move

Read first

• Post 9: Construction heuristics. Nearest neighbour builds a tour by always driving to the closest unvisited stop. On our eight stops it gives A-G-E-D-H-C-B-F-A, cost 385, which is 22% above the optimum of 315. On berlin52, starting from city 1, it gives 8,980, which is 19.1% above the optimum of 7,542.

The question this post answers: given any complete tour, how do you make it shorter with small, cheap changes, and how far does that get you?

Intuition

Post 10 ended on a visible flaw: tours that cross themselves. A construction heuristic builds a tour and never looks back. Local search starts from a complete tour and keeps asking: is there a small change that makes it shorter? If so, it makes the change and asks again. When no small change helps, it stops.

What counts as a “small change” is the whole design. The simplest choice for the TSP is the 2-opt move: delete two edges of the tour and reconnect the two pieces the only other way that still gives one closed tour.

Here are the same eight stops as in every post so far. Coordinates are in kilometres, distances in units of 100 m, rounded.

We start from the nearest-neighbour tour of Post 9, A-G-E-D-H-C-B-F-A, cost 385. It has eight edges, and a 2-opt move picks two of them that do not share a stop. That gives 20 possible moves. The table below lists the change in tour length, written Δ, for every one of them. Rows and columns are the two edges removed, in tour order; a dash marks two edges that share a stop, which is not a move. A negative Δ means the tour gets shorter.

Three of the 20 moves improve the tour. The rule I use in this post is best improvement: scan every move, then make the one with the most negative Δ. Here that is −41, which removes G–E and B–F. Notice that it is not the move that undoes the tour’s only crossing. That one, removing A–G and B–F, saves 39. Removing a crossing always helps, but it is not always the best thing to do.

Step through the diagram below to watch best-improvement 2-opt run to the end. The lengths drawn are unrounded kilometres, so they differ from the matrix values by a few tenths.

Each move’s Δ comes from just four numbers: the two edges removed and the two added. Nothing else in the tour changes length. The table below prices the three moves with the distance matrix.

Three moves took the tour from 22% above optimal to optimal. On eight stops that is guaranteed: I checked all 2,520 distinct tours of these stops, and the optimum is the only one no 2-opt move can improve. On real instances, as we will see, 2-opt usually stops short.

The formal idea

Neighborhoods. Let T be a tour and c(T) its length. A neighborhood N(T) is the set of tours you can reach from T with one move. A tour T is a local optimum for that neighborhood if no tour in N(T) is shorter. Local search is this loop:

flowchart TD
  S["Start: any tour T"] --> E["Compute Δ for every move in N(T)"]
  E --> Q{"Best Δ < 0?"}
  Q -- yes --> M["Apply that move to T"]
  M --> E
  Q -- no --> L["Stop: T is a local optimum"]

The 2-opt move. Write the tour as a sequence t₀, t₁, …, tₙ₋₁ of the n cities, and let d(x, y) be the distance between cities x and y. Pick two positions i < j and let a = tᵢ, b = tᵢ₊₁, c = tⱼ and e = tⱼ₊₁ (wrapping around at the end). The move deletes edges (a, b) and (c, e) and adds (a, c) and (b, e). In the sequence, that is the same as reversing the stretch from tᵢ₊₁ to tⱼ:

before:  … a | b  →  …  →  c | e …
after:   … a | c  →  …  →  b | e …    (the middle segment is reversed)

Two edges that share a city cannot be used, because reconnecting them gives back the same tour. That leaves n(n − 3)/2 moves: 20 for our 8 stops and 1,274 for berlin52.

Delta evaluation. The change in length is

Δ(i, j) = d(a, c) + d(b, e) − d(a, b) − d(c, e)

That is four lookups, whatever the size of the tour. Re-scoring the whole new tour would cost n additions per move instead. For berlin52 that is 4 versus 52 for each of the 1,274 moves in every scan. This is called delta evaluation, and every fast local search depends on it.

The formula works because the distances are symmetric: driving the reversed segment backwards costs the same as driving it forwards. With one-way streets, or with time windows where arrival times depend on the order, the reversed stretch changes cost too, and Δ is no longer a four-number formula. We will deal with that when we get to vehicle routing.

Applying the move still costs time, because reversing a segment touches every city in it. Post 13 returns to that.

Why removing a crossing always helps. Suppose edges (a, b) and (c, e) cross at a point X. By the triangle inequality, d(a, c) ≤ d(a, X) + d(X, c) and d(b, e) ≤ d(b, X) + d(X, e). The four pieces on the right add up exactly to d(a, b) + d(c, e), because X lies on both edges. So the new edges are never longer than the old ones, and strictly shorter unless the four points sit on one line. A tour with a crossing is never 2-optimal in the Euclidean plane. Flood (1956) put it this way: “In the euclidean plane it states simply that the minimal tour does not intersect itself.” The general version is the 2-opt test itself: a pair of edges is bad whenever Δ < 0, whether or not the edges cross on a map. Move 2 above is an example: the tour had no crossings and still improved.

Where it came from. This post repeats one of the oldest experiments on the TSP. Flood (1956) took the 49-city instance of Dantzig, Fulkerson and Johnson, built a nearest-neighbour tour, and then repaired every “intersecting pair” of edges, his name for a pair with Δ < 0 in today’s terms, until the tour was “intersectionless”. Croes (1958) described the repair as an inversion, reversing the stretch of the tour between the two edges, and used such tours as the starting point of an exhaustive search. Lin (1965) strengthened the method by also moving segments elsewhere in the tour, which leads to Posts 12 and 14.

What is known about it. The table below collects the main results.

On geometric instances 2-opt usually needs few moves and lands within a few percent of optimal, even though the worst cases are bad on both counts.

Common misconceptions

“2-opt just removes crossings.” Removing a crossing is one kind of improving 2-opt move, but not the only kind. In our example, after move 1 the tour had no crossings left and 2-opt still found two more improvements, worth 29.

“Uncrossing one pair can never create another crossing.” It can: the new edges can cut through other parts of the tour. van Leeuwen and Schoone (1981) needed a careful argument to show that uncrossing one pair at a time still finishes in polynomially many steps.

“A better starting tour gives a better 2-opt result.” Not reliably. On berlin52 the Christofides tour from Post 10 (8,595) is much better than the double-tree tour (10,402), but best-improvement 2-opt takes the double tree down to 7,789 and Christofides only to 7,996. Local search keeps what it is given, and a start that is “almost good” can lock in the wrong structure.

“2-opt is always within about 5% of optimal.” Only on geometric instances like berlin52. On distance matrices with no geometry behind them, Johnson and McGeoch measured 2-opt at 66% to 114% above the lower bound. The triangle-inequality argument above is one reason the plane is friendlier.

Try it in Python

The script below runs 2-opt on berlin52 using only the standard library. It starts from the nearest-neighbour tour of Post 9, runs both best improvement and first improvement (make the first improving move found in the scan, then start the scan again), counts the crossings before and after, and repeats best improvement from all 52 nearest-neighbour starts. You need berlin52.tsp from TSPLIB.

import math
from itertools import combinations

body = open("berlin52.tsp").read().split("NODE_COORD_SECTION")[1].split("EOF")[0]
xy = [tuple(map(float, ln.split()[1:])) for ln in body.strip().splitlines()]
n = len(xy)
d = [[int(math.hypot(p[0] - q[0], p[1] - q[1]) + 0.5) for q in xy] for p in xy]  # EUC_2D
OPTIMAL = 7542

def cost(tour):
    return sum(d[tour[i]][tour[(i + 1) % len(tour)]] for i in range(len(tour)))

def nearest_neighbour(start):
    tour, left = [start], set(range(n)) - {start}
    while left:
        nxt = min(left, key=lambda c: (d[tour[-1]][c], c))  # ties go to the lower city number
        tour.append(nxt)
        left.remove(nxt)
    return tour

def two_opt_moves(size):
    """Every 2-opt move as positions (i, j): remove the edges leaving tour[i] and tour[j]."""
    for i in range(size - 1):
        for j in range(i + 2, size if i > 0 else size - 1):  # skip edges that share a city
            yield i, j

def delta(tour, i, j):
    """Length change from replacing edges (a, b) and (c, e) with (a, c) and (b, e)."""
    a, b = tour[i], tour[i + 1]
    c, e = tour[j], tour[(j + 1) % len(tour)]
    return d[a][c] + d[b][e] - d[a][b] - d[c][e]

def two_opt(tour, first_improvement=False):
    tour, moves, evaluated = tour[:], 0, 0
    while True:
        best_delta, best_move = 0, None
        for i, j in two_opt_moves(len(tour)):
            evaluated += 1
            change = delta(tour, i, j)
            if change < best_delta:
                best_delta, best_move = change, (i, j)
                if first_improvement:
                    break
        if best_move is None:  # no move improves the tour: a local optimum
            return tour, moves, evaluated
        i, j = best_move
        tour[i + 1:j + 1] = reversed(tour[i + 1:j + 1])  # the move itself: reverse the segment
        moves += 1

def crosses(p, q, r, s):
    """True if segment p-q properly crosses segment r-s."""
    side = lambda a, b, c: (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
    return side(p, q, r) * side(p, q, s) < 0 and side(r, s, p) * side(r, s, q) < 0

def crossings(tour):
    edges = [(tour[i], tour[(i + 1) % n]) for i in range(n)]
    return sum(crosses(xy[a], xy[b], xy[c], xy[e])
               for (a, b), (c, e) in combinations(edges, 2) if len({a, b, c, e}) == 4)

def best_relocation(tour):
    """Best way to move one city elsewhere: three edges change, so no 2-opt move can do it."""
    best = (0, None)
    for k, city in enumerate(tour):
        prev, nxt = tour[k - 1], tour[(k + 1) % n]
        saved = d[prev][city] + d[city][nxt] - d[prev][nxt]
        rest = tour[:k] + tour[k + 1:]
        for i in range(n - 1):
            a, b = rest[i], rest[(i + 1) % (n - 1)]
            change = d[a][city] + d[city][b] - d[a][b] - saved
            if change < best[0]:
                best = (change, (city, a, b))
    return best

gap = lambda c: f"{100 * (c - OPTIMAL) / OPTIMAL:.1f}%"
start = nearest_neighbour(0)
print(f"2-opt moves per scan: {sum(1 for _ in two_opt_moves(n))}")
print(f"nearest neighbour from city 1: {cost(start)} ({gap(cost(start))}), {crossings(start)} crossings")
for name, first in (("best improvement", False), ("first improvement", True)):
    tour, moves, evaluated = two_opt(start, first)
    print(f"2-opt, {name}: {cost(tour)} ({gap(cost(tour))}), {moves} moves, "
          f"{evaluated} deltas, {crossings(tour)} crossings")

results = [cost(two_opt(nearest_neighbour(s))[0]) for s in range(n)]
print(f"best improvement from all 52 starts: best {min(results)} ({gap(min(results))}), "
      f"worst {max(results)} ({gap(max(results))}), mean {sum(results) / n:.1f}")

change, (city, a, b) = best_relocation(two_opt(start)[0])
print(f"left over: move city {city + 1} between {a + 1} and {b + 1}, change {change}")

It prints:

Eleven moves cut the gap from 19.1% to 4.0%. The nearest-neighbour tour had only 4 crossings, so most of those moves were not uncrossings at all. First improvement computes fewer than half as many deltas but makes more moves and ends at a worse local optimum here; Post 12 looks at that trade-off properly. Across all 52 starting tours, 2-opt never reaches 7,542. Each run stops at a different local optimum, between 1.5% and 7.1% above it.

Re-scoring each candidate tour instead of using deltas would have meant 15,288 × 52, about 795,000 additions, for the best-improvement run alone. The last line of output is the subject of the final section.

Exercise

Start from the alphabetical tour A-B-C-D-E-F-G-H-A (cost 415) on the eight stops. Using the distance matrix below, find every improving 2-opt move, make the best one, and repeat until no move improves. How many moves does it take, and where do you end up?

Hint: the tour crosses itself twice, and both crossings involve edge D–E. There are 7 improving moves in the first scan. Compare the size of the improvements in your first and second moves.

What this method can’t do yet

The last line of the script’s output is left over: move city 17 between 18 and 3, change -17. The best-improvement 2-opt tour on berlin52 (7,842) contains the stretch 42 → 17 → 21 → 31 → 18 → 3. City 17 is badly placed: taking it out and putting it three stops further on, between 18 and 3, saves 17. That change is small and obvious, yet 2-opt cannot make it, because it deletes three edges (42–17, 17–21 and 18–3) and adds three new ones. A 2-opt move only ever exchanges two. The tour is 2-optimal and still has a simple improvement in plain sight.

The problem is that 2-opt has only one kind of move. Any improvement that is not a single segment reversal is invisible to it, however simple it looks on the map. Post 12, “More moves”, adds moves that relocate and swap cities, and asks whether to take the first improvement or the best.

References

• Flood, M. M. (1956). “The Traveling-Salesman Problem.” Operations Research 4(1): 61–75.
• Croes, G. A. (1958). “A Method for Solving Traveling-Salesman Problems.” Operations Research 6(6): 791–812.
• Lin, S. (1965). “Computer Solutions of the Traveling Salesman Problem.” Bell System Technical Journal 44(10): 2245–2269.
• van Leeuwen, J., and Schoone, A. A. (1981). “Untangling a Traveling Salesman Tour in the Plane.” Proceedings of the 7th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 1981), 87–98.
• Chandra, B., Karloff, H., and Tovey, C. (1999). “New Results on the Old k-opt Algorithm for the Traveling Salesman Problem.” SIAM Journal on Computing 28(6): 1998–2029.
• Applegate, D., Bixby, R., Chvátal, V., and Cook, W. (c. 1999). “Finding Tours in the TSP.” Preliminary chapter of a planned monograph, Rice University. https://www.math.uwaterloo.ca/tsp/methods/papers/lk_report.pdf
• Johnson, D. S., and McGeoch, L. A. (2002). “Experimental Analysis of Heuristics for the STSP.” In Gutin, G., and Punnen, A. P. (eds.), The Traveling Salesman Problem and Its Variations, Kluwer, 369–443.
• Englert, M., Röglin, H., and Vöcking, B. (2014). “Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP.” Algorithmica 68(1): 190–264.
• Reinelt, G. (1991). “TSPLIB—A Traveling Salesman Problem Library.” ORSA Journal on Computing 3(4): 376–384; berlin52 files and list of optimal solutions.

See the whole series · ← All writing