Heuristic — local search

2-opt
Alias2opt, two_opt
TypeHeuristic — local search
Auto-seeds fromnn (nearest neighbor)

Description

Local search algorithm that iteratively improves a tour by removing two edges and reconnecting the resulting segments in the only other valid way (reversing the segment between the two removed edges). Repeats until no improving swap exists — a local optimum.

Auto-expands to pipeline(nn, 2opt): the nearest-neighbor tour seeds the search so the local optimizer starts in a good region rather than wasting iterations escaping a random tour.

procedure TwoOpt(tour):
    improved ← true
    while improved:
        improved ← false
        for each pair (i, j) with i < j:
            new_tour ← reverse_segment(tour, i, j)
            if length(new_tour) < length(tour):
                tour ← new_tour
                improved ← true
    return tour

Usage

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

# skip seeding — start from input city order
teeline solve 2opt --no-seed -i ./data/tsplib/berlin52.tsp

References