Heuristic — local search

Or-opt
Aliasor_opt, or-opt
TypeHeuristic — local search
Auto-seeds fromnn (nearest neighbor)

Description

Local search algorithm that relocates segments of 1, 2, or 3 consecutive cities to a better position elsewhere in the tour. This is a relocation move, as opposed to the reversal move used by 2-opt and 3-opt — the two strategies find different local optima and are complementary.

Each pass scans all possible relocations across all three segment sizes (Or-1, Or-2, Or-3), applies the single best improving move found, and repeats until no relocation improves the tour (best-improvement strategy). Reversed insertion is also attempted for Or-2 and Or-3 moves.

Or-opt is a restricted form of 3-opt where one of the three segments is always inserted intact (or reversed) without any further reconnection.

Auto-expands to pipeline(nn, or_opt).

Move structure

Or-1 — relocate a single city:
  Before: ... A → [B] → C ... X → Y ...
  After:  ... A → C ... X → [B] → Y ...

Or-2 — relocate an adjacent pair:
  Before: ... A → [B → C] → D ... X → Y ...
  After:  ... A → D ... X → [B → C] → Y ...

Or-3 — relocate a triple:
  Before: ... A → [B → C → D] → E ... X → Y ...
  After:  ... A → E ... X → [B → C → D] → Y ...

When to use

Or-opt works well as a post-processing step after any constructive or metaheuristic solver. Because it catches improvements that 2-opt misses (and vice versa), combining them via the pipeline is more effective than either alone:

teeline pipeline --steps=nn,2opt,or_opt -i ./data/tsplib/berlin52.tsp
procedure OrOpt(tour):
    improved ← true
    while improved:
        improved ← false
        for segment_len in {1, 2, 3}:
            for each segment S of length segment_len in tour:
                for each insertion position p not adjacent to S:
                    new_tour ← remove_and_insert(tour, S, p)
                    if length(new_tour) < length(tour):
                        tour ← new_tour
                        improved ← true
    return tour

Options

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

Usage

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

# explicit alias
teeline solve or-opt -i ./data/tsplib/berlin52.tsp

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

# combine with 2-opt for deeper local search
teeline pipeline --steps=nn,2opt,or_opt -i ./data/tsplib/berlin52.tsp

References