Heuristic — local search (stochastic)

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.

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