Heuristic — local search (stochastic)

▶ Open interactive explainer →

Simulated Annealing
Aliassa, simulated_annealing
TypeHeuristic — local search (stochastic)
Auto-seeds fromshuffle (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

FlagDescriptionDefault
--max_temperatureStarting temperature1000.0
--min_temperatureStopping temperature0.001
--cooling_rateFractional temperature drop per step—
--epochsMaximum 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