Heuristic — local search (stochastic)

▶ Open interactive explainer →

Simulated Annealing
Alias sa, simulated_annealing
Type Heuristic — local search (stochastic)
Auto-seeds from shuffle (random tour)

Description

Probabilistic local search inspired by the annealing process in metallurgy. Each iteration proposes a random tour modification. Improvements are always accepted; worsenings are accepted with probability exp(−Δ/T), where T is the current “temperature”. Temperature decreases each step according to the cooling rate, so the algorithm transitions from broad exploration at high temperature to fine-tuned exploitation at low temperature.

Auto-expands to pipeline(shuffle, sa). The temperature schedule is calibrated for cold starts — seeding SA from a greedy NN tour constrains early exploration and typically worsens the final result. For a warm-started SA run use the classic preset (nn → 2opt → sa): the 2-opt stage removes edge crossings before SA fine-tunes the result.

procedure SimulatedAnnealing(cities, T_start, T_end, cooling):
    tour ← random_tour(cities)
    best ← tour
    T ← T_start
    while T > T_end:
        neighbour ← random_2opt_swap(tour)
        Δ ← length(neighbour) − length(tour)
        if Δ < 0 or random() < exp(−Δ / T):
            tour ← neighbour
        if length(tour) < length(best):
            best ← tour
        T ← T × cooling
    return best

Options

Flag Description Default
--max_temperature Starting temperature 1000.0
--min_temperature Stopping temperature 0.001
--cooling_rate Fractional temperature drop per step —
--epochs Maximum iterations —

Usage

# auto-expands to pipeline(shuffle, sa)
teeline solve sa -i ./data/tsplib/berlin52.tsp
teeline solve sa -i ./data/tsplib/berlin52.tsp --verbose

# run SA from input city order (no shuffle)
teeline solve sa --no-seed -i ./data/tsplib/berlin52.tsp

# warm-start from a 2-opt-refined tour
teeline solve classic -i ./data/tsplib/berlin52.tsp

# custom temperature schedule
teeline solve sa -i ./data/tsplib/berlin52.tsp --cooling_rate=0.003 --max_temperature=500.0

References