Local Search and Simulated Annealing › Summary

Local search and simulated annealing are the entry point to heuristic optimization of discrete, non-differentiable objectives. We defined a solution as a permutation of customers, decoded it into two depot tours, and measured it by total Euclidean arc length. We defined a neighborhood of all inclusive segment reversals, established that this state graph is connected, and used that connectivity to motivate cross-route reassignment. Hill climbing used ordered, tolerance-aware neighborhood scans. Every installed step strictly improved the current state within its epoch; the global incumbent retained the best candidate scored across all epochs. When a completed scan refused to step, a random restart spent the remaining budget on a fresh starting point.

Simulated annealing replaced strict improvement with a probabilistic acceptance rule $P_{\text{accept}} = \exp(-\Delta / T)$ for worsening moves, justified through the Metropolis-Hastings stationary distribution $p_T \propto \exp(-f / T)$, and annealed the temperature geometrically from a hot start to a near-greedy end. Under a common $300$-evaluation budget and $20$ seeds, hill climbing was low-variance and prone to plateaus, annealing had a slightly lower mean and larger descriptive standard deviation on this instance, and NN-seeded random search had a higher mean. Full enumeration of the $40{,}320$ permutations supplied the optimality yardstick and certified runs that matched it. The finite geometric schedule alone supplies no such certificate.

The larger lesson is about how to reason about heuristics: define the representation and neighborhood clearly, count every scored candidate, validate feasibility on every reported final solution, and report a distribution across seeds rather than a single lucky result. Those habits carry directly into the population-based methods that follow, which reuse this instance and budget to ask whether a fundamentally different search dynamic can spend the same evaluations more effectively.