Stochastic Hill Climbing

Each step draws a random 2-opt candidate — a random segment reversal. The candidate is accepted only if it beats the best tour found so far; otherwise it is rejected and the tour stays. When the search goes stale (too many rejections in a row), it restarts from a fresh random tour — the best tour survives. Random restarts are what rescue the search from mediocre local optima.