Heuristic — local search

3-opt
Alias3opt, three_opt
TypeHeuristic — local search
Auto-seeds fromnn (nearest neighbor)

Description

Extension of 2-opt that removes three edges per iteration and reconnects the three segments in the best of the eight possible reconnection configurations. Each pass tries every triple of edges, keeps the single best improvement found, and repeats until no triple yields improvement.

Finds deeper local optima than 2-opt at the cost of O(n³) per pass. Typical tour quality is a few percentage points better than nn → 2opt at the expense of longer runtime.

Auto-expands to pipeline(nn, 3opt).

procedure ThreeOpt(tour):
    improved ← true
    while improved:
        improved ← false
        for each triple of edges (e1, e2, e3):
            best ← best_reconnection(tour, e1, e2, e3)
            if length(best) < length(tour):
                tour ← best
                improved ← true
    return tour

Options

FlagDescriptionDefault
--epochsMaximum passes (0 = until convergence)0

Usage

# auto-expands to pipeline(nn, 3opt)
teeline solve 3opt -i ./data/tsplib/berlin52.tsp

# as part of the thorough preset (nn → 3opt → SA)
teeline solve thorough -i ./data/tsplib/berlin52.tsp

# skip seeding
teeline solve 3opt --no-seed -i ./data/tsplib/berlin52.tsp

References