Local Search and Simulated Annealing

Many of the optimization problems we care about do not have a differentiable objective we can hand to a gradient method. A delivery planner wants to order eight stops into two delivery routes; a compiler wants to schedule instructions to minimize register pressure; a logistics team wants to re-sequence a pick list to shave a few kilometers off the day. In each case the decision variable is a discrete arrangement (a permutation, a schedule, a subset), and the objective is defined on that arrangement. Gradient descent cannot move "a little bit" in a discrete space, so we need a different strategy: propose a small structural change, evaluate the result, and keep it if it helps.

Local search applies that idea to a chosen neighborhood. We start from some feasible solution, examine a curated set of nearby solutions obtained by a small edit called a neighborhood move, and step to a better one. If we only ever accept improvements, the procedure is called hill climbing (or descent, when minimizing). Its strict-improvement rule is easy to trace on a small routing example. Its weakness is that it can get trapped: it stops improving even though some distant solution is far better.

Simulated annealing addresses that trap by occasionally accepting a worse solution, with a probability that shrinks over time as a virtual "temperature" cools. The name draws on physical annealing: temperature controls thermal motion, and cooling affects how a material settles into lower-energy states. In optimization, the random uphill moves early on give the search a chance to escape a basin, and the gradual cooling lets it settle back down at the end.

In this chapter we build both algorithms from primitives on a concrete eight-customer routing instance, watch them in action, and compare them, under an equal evaluation budget and across twenty random seeds, against a deterministic construction heuristic and a random baseline. The instance is new and deliberately small so that we can enumerate every one of the 40,320 permutations and know the true optimum. That reference lets us measure the distance from each reported objective to the enumerated minimum. Reference enumeration, figure diagnostics, and post-run validation are outside the search budgets. Every method also builds the same nearest-neighbor start using 36 candidate-arc lookups; its complete objective score counts as evaluation one.

For the finite combinatorial setting studied here, local search needs a representation, an objective evaluator, and a neighborhood generator. There is no requirement that the objective be differentiable, convex, or even continuous, and no matrix of derivatives to compute or invert. These interfaces can be defined for routing, scheduling, packing, and assignment. Continuous relaxations and specialized exact methods remain alternatives.

For a symmetric Euclidean tour, a within-route segment reversal replaces two boundary edges and preserves the lengths of internal edges. Selected reversals can remove crossings and shorten a route; arbitrary reversals need not improve it. This is the geometric idea behind 2-opt. Restarts provide additional starting points, at the cost of their construction and neighborhood evaluations.

Simulated annealing adds a controlled escape mechanism without much extra code. At a fixed positive temperature, symmetric Metropolis proposals leave the finite-state distribution proportional to $\exp(-f(x)/T)$ invariant. This is a stationary-distribution statement, not a claim that a short run already samples from equilibrium. The search state uses current and incumbent permutations, while our experiment also stores the distance matrix, score histories, and repeated-run traces.

Finally, both methods are trivially parallelizable across seeds. Because each run is independent, running twenty seeds is embarrassingly parallel, and the spread of their final objectives describes seed variation for this fixed instance and algorithm configuration.

Hill climbing's central failure is the local optimum. Because it only accepts strict improvements, it halts the moment every neighbor is at least as bad as the current point, even if a better solution sits one move further away. A local minimum can occur before the global optimum is reached. The fix, restarts, helps, but it spends the budget on independent attempts rather than systematically exploring, and there is no guarantee that the next restart will find a better basin. Perturbations and larger neighborhoods offer other ways to leave a local minimum.

Annealing permits uphill moves instead of stopping solely because no improving neighbor is available; a finite evaluation budget still terminates the run. The choice of initial temperature, cooling schedule, and number of moves at each temperature strongly affects quality. Too hot and the search wanders; too cold and it behaves like a slow hill climber. Classical asymptotic convergence results include sufficiently slow logarithmic schedules under finite-state and energy-barrier conditions. They do not certify a result after our 300-evaluation run; an independent bound or exhaustive reference is needed for that. We must therefore judge quality empirically, not by appeal to the asymptotic theory.

Both methods are also sensitive to the representation and the neighborhood. If the neighborhood is disconnected, a local walk from a fixed start stays in its component. Full-permutation random restarts can enter other components, but each epoch still refines only the component it starts in. If it is too wide, a full scan of the neighborhood becomes expensive. If it is too narrow, progress stalls. A move that changes the split between two vehicles in a routing problem has a very different effect from a move that only re-orders stops within one vehicle, and picking the wrong move set silently restricts local refinement between restarts. Finally, an equal number of objective evaluations does not imply equal runtime: a nearest-neighbor scan examines arcs cheaply, while each objective call here checks ten travel arcs for feasibility and traverses ten arcs again for distance, so two methods with the same nominal budget can take very different wall-clock time.

There are four objects to define, and they fit together in a natural order:

1. A representation says what a candidate solution is.
2. An objective assigns a number to each candidate.
3. A neighborhood says which small edits produce the candidates the search is allowed to see next.
4. An acceptance rule decides whether to move to a proposed neighbor.

The order matters. The representation fixes the universe of possible answers; the objective ranks them; the neighborhood defines the local graph the search can traverse; and the acceptance rule determines whether the walk is greedy or stochastic. Each choice below is made with the same routing instance in mind, so that the formal definitions can be checked immediately against concrete numbers.

We encode a solution as a permutation $\pi = (\pi_1, \pi_2, \dots, \pi_8)$ of the customer identifiers $\{1, \dots, 8\}$. The decoder splits the permutation into two routes of four customers each, because the total demand is eight and each of the two vehicles has capacity four:

where node $0$ is the depot. Because each vehicle carries exactly four customers, every permutation of the eight customers automatically produces two capacity-feasible routes, so capacity alone never rules out a permutation. Time-window and depot-return feasibility are checked separately, and on this instance they are deliberately loose. Each customer has demand one, service takes one time unit, and all customer and depot windows are $[0,80]$. Travel time equals Euclidean distance in the chosen units. The coordinates fit in an 8-by-6 rectangle, so every arc is at most 10 units. Each four-customer route uses five arcs and four service periods, giving a return-time bound of $5(10)+4=54<80$. With window openings at zero, no waiting is needed; every valid permutation therefore satisfies these capacity and time limits. The loose windows isolate search behavior; this example does not test restrictive time-window handling.

The objective sums the Euclidean arc lengths over both closed tours:

where:

• $\pi$: a permutation of the eight customer identifiers
• $\pi_k$: the customer visited at position $k$ in the permutation
• $d(a,b)$: the Euclidean distance $\sqrt{(x_a - x_b)^2 + (y_a - y_b)^2}$ between two coordinates
• the first line traverses the first route's internal arcs (positions $1$ to $4$), and the two depot arcs $d(0, \pi_1)$ and $d(\pi_4, 0)$ close that tour
• the second line traverses the second route's internal arcs (positions $5$ to $8$), and the two depot arcs $d(0, \pi_5)$ and $d(\pi_8, 0)$ close that tour

There is no lateness penalty and no service-time term in the objective; service times only constrain the schedule validation.

A representation by itself is not enough: the search needs a notion of "nearby." That is the neighborhood. Here the neighborhood is the set of all inclusive segment reversals. A move selects indices $0 \le i < j < 8$ and replaces the segment $\pi_{i+1}, \dots, \pi_{j+1}$ with its reverse. This move set is not arbitrary. A within-route reversal preserves the undirected internal-edge lengths and rewires two boundary arc positions. Reversing an entire route can leave its aggregate undirected edge multiset unchanged. A reversal crossing the split changes route assignments and route-labelled depot attachments, even when the aggregate depot-edge multiset is unchanged, so it must be scored through the full decoder here. When the reversed segment crosses the position-$4$ boundary, the move changes how customers are assigned to vehicles. Thus the neighborhood can reassign customers between routes.

This neighborhood has two properties we rely on. First, adjacent reversals (with $j = i+1$) are simple swaps, and swaps alone connect the entire permutation space; the wider reversals only add shortcuts. Consequently the state graph is connected and every permutation is reachable from every other permutation. Second, the wider reversals are geometrically meaningful: reversing a contiguous piece of a route is the 2-opt move, which can uncross edges and shorten a tour. A neighborhood that only reversed within each vehicle would be disconnected across the route boundary and would forbid exactly the cross-split moves a routing search needs.

Enumerating all $40{,}320$ permutations confirms the optimum is printed above, attained by the permutation printed above. This exhaustive reference search is outside the three budgeted heuristic runs, and we exclude it from every method's evaluation budget.

With the representation and neighborhood fixed, we can define an ideal steepest-descent rule: from the current permutation, choose a minimum-score neighbor and step only if it improves enough. The ideal strict-improvement rule is

where:

• $\pi_t$: the current permutation at iteration $t$
• $\mathcal{N}(\pi_t)$: the set of all segment reversals of $\pi_t$
• $f$: the objective (total tour length) defined above
• $\epsilon > 0$: a small tolerance (here $10^{-12}$) to guard against floating-point noise. The tolerance is not decoration: two mathematically equal tour lengths may differ in their last bits, and without a margin round-off can cause unproductive moves between tours that are equal for all practical purposes. Deterministic strict descent still cannot cycle, because every accepted step lowers the fixed computed score. If no neighbor improves by more than $\epsilon$, the step is undefined: no improvement exceeding that tolerance is available in $\mathcal{N}$. This is a tolerance-based stopping point, which need not be an exact mathematical local minimum.

The code below uses an ordered, tolerance-aware scan rather than an exact argmin. The first scored neighbor becomes the scan candidate; a later neighbor replaces it only when its score is lower by more than $\epsilon$. After a completed scan, the candidate is installed only if it improves the current score by more than $\epsilon$. Differences within $\epsilon$ retain the earlier neighbor. The chosen candidate can therefore differ from the exact minimum; the final guard can even reject a scan when a later neighbor would have passed that guard. A budget-truncated scan returns the global best already scored, without installing a local step.

A local optimum is not a global one: there may exist a $\pi^\ast$ with $f(\pi^\ast) < f(\pi_t)$ that is several reversals away. Restarts handle local stopping by abandoning the current epoch when the tolerance-aware scan refuses to step and beginning a fresh epoch from a new permutation. Within an epoch, every accepted step strictly lowers the current computed score. The scan stopping rule is not an exact local-optimality certificate. The restart initialization is usually a fresh random permutation, and the overall best seen across all epochs is what we report.

Two subtleties matter because they change reported comparisons. First, when we scan the full neighborhood to select a neighbor, every neighbor evaluation consumes budget, including the neighbors we reject and including equal-cost duplicates. When the budget runs out mid-scan, the honest thing to do is return the best permutation already scored, not to spend one extra evaluation to finish the scan. Second, the fixed budget must include the evaluations spent starting the epochs, not only the improvement steps. If restart-initialization evaluations are excluded, the reported count understates the true scoring cost and can make the method appear more efficient than it is.

Simulated annealing uses the same representation, objective, and neighborhood. It proposes one random reversal instead of scanning for the best neighbor, then applies a stochastic acceptance rule. From the current state $x$ with objective $f(x)$, we propose a neighbor $x'$ by sampling uniformly from the reversal neighborhood. We define the change in objective

and accept the proposal with probability

where:

• $\Delta$: the change in objective, $f(x') - f(x)$
• $T_k$: the temperature after $k$ evaluations (a positive scale that controls how freely uphill moves are accepted)

An improving move is always accepted; a worsening move is accepted with probability that falls as $T_k$ shrinks. When $T_k$ is large the search behaves like a random walk that pays little attention to the objective; as $T_k$ approaches zero, the probability of accepting any fixed positive increase approaches zero. Equal-cost moves still have acceptance probability one, so this limit differs from strict-improvement hill climbing.

The exponential acceptance rule can be read directly as a family of curves: for a fixed worsening move, higher temperature means more exploration, while lower temperature rapidly suppresses uphill moves.

The nearest-neighbor tour supplies the initial state. The initial temperature $T_0$ controls acceptance of worsening perturbations; it does not bound how far the current tour can deteriorate over several accepted moves. The separate incumbent retains the best tour already scored. A final temperature $T_1$ near zero favors polishing for worsening moves large relative to $T_1$. The temperature scale must be checked against actual objective changes; these two endpoint values are choices for this experiment.

Several properties are worth recording so we do not overclaim what these algorithms achieve. First, the permutation graph under reversals is connected: any permutation can be transformed into any other by a finite sequence of inclusive segment reversals, because swaps (adjacent reversals) alone generate all permutations. This guarantees that with a sufficiently long search simulated annealing can in principle visit any solution, which a disconnected neighborhood would not allow.

Second, for a fixed temperature $T$, the Metropolis chain with symmetric proposals has $p_T$ as its stationary distribution. That gives simulated annealing a probabilistic meaning at a frozen temperature, where sufficiently equilibrated samples can approximate the Boltzmann distribution, but stationarity alone does not establish that a changing-temperature chain tracks those distributions. Decreasing temperature changes the transition rule and target distribution over time.

Third, under Hajek's conditions, a logarithmic cooling schedule that decreases slowly enough relative to the critical depth of the deepest nonglobal minimum makes the probability of being in the global-optimum set tend to one. This is an asymptotic statement under its hypotheses. It does not supply a finite-budget success probability for the schedule used here. In practice we measure quality empirically, across many seeds, and report the spread.

Finally, hill climbing with strict improvement terminates in finitely many steps: the objective strictly decreases by at least $\epsilon$ at every accepted step, and the solution space is finite, so the loop cannot run forever. Hypothetically, independent uniform restart states followed by the same deterministic complete descent produce identically distributed completed-epoch outcomes. Our first epoch has a deterministic nearest-neighbor start, and a fixed budget can truncate the last epoch, so those outcomes do not all share that distribution. The best objective observed cannot increase as more candidates are scored.

The formulas now define a complete search process: a permutation is a solution, the objective ranks it, the reversal neighborhood supplies local moves, hill climbing accepts only strict improvements, and annealing accepts improvements always but worsening moves with a temperature-controlled probability. The next section makes the neighborhood visible, so we can see why these rules behave differently on the same eight-customer instance.

Key ParametersLink Copied

The three algorithms have small parameter surfaces. Hill climbing has just two: the budget and the seed (and an implicit restart rule). Simulated annealing adds the initial and final temperatures $T_0$ and $T_1$, which set the geometric cooling curve. Random search adds nothing beyond a budget and a seed.

In our runs we hold the budget fixed at $300$ evaluations and run all three across the same $20$ seeds. Both hill climbing and annealing start from the nearest-neighbor solution, which costs one evaluation immediately. That common warm start controls initialization: different starts would confound the effect of the search with the choice of starting point.

For annealing, we choose $T_0 = 2.0$ and $T_1 = 0.01$. The initial temperature is chosen so that a typical $+0.5$ worsening move is accepted with $e^{-0.25} \approx 0.78$ probability early, but a $+3$ worsening move (an illustrative increase in these distance units) is only accepted with probability $e^{-1.5} \approx 0.22$. At a final temperature of $T_1=0.01$, a $+0.5$ increase has extremely small acceptance probability, although sufficiently small worsening moves can still be accepted. Finite positive temperature is not a strict-improvement rule.

We can see the mechanism directly on this instance. Before plotting, compute the nearest-neighbor tour and its best single-reversal neighbor, so the figure cells only render precomputed results.

These figures together summarize why each method behaves as it does. Within each epoch, hill climbing accepts only a scan-selected move that lowers the current score by more than $\epsilon$. It can stop with tiny negative bars still present, and the evaluation budget can end before a complete scan establishes even that stopping condition. Annealing occasionally climbs a small positive bar early on, which can drop it into a different basin with a lower floor. Neither strategy guarantees success. Both depend on how many evaluations they get and how good their starting point is.

Let us work one reversal entirely by hand to see how the bookkeeping fits together. Start from the nearest-neighbor permutation

where the vertical bar separates the two vehicles. The current objective is the sum of the arc lengths on the two closed tours:

Substituting the coordinates (with $x$ and $y$ given in the array above) gives:

• $d_{01} = \sqrt{(1-0)^2 + (3-0)^2} = \sqrt{10} \approx 3.1623$
• $d_{17} = \sqrt{(3-1)^2 + (1-3)^2} = \sqrt{4+4} \approx 2.8284$
• $d_{78} = \sqrt{(5-3)^2 + (3-1)^2} = \sqrt{4+4} \approx 2.8284$
• $d_{83} = \sqrt{(4-5)^2 + (5-3)^2} = \sqrt{1+4} \approx 2.2361$
• $d_{30} = \sqrt{(0-4)^2 + (0-5)^2} = \sqrt{16+25} \approx 6.4031$

so the first route contributes $17.4583$. For the second route:

• $d_{06} = \sqrt{(6-0)^2 + (1-0)^2} = \sqrt{36+1} \approx 6.0828$
• $d_{65} = \sqrt{(8-6)^2 + (3-1)^2} = \sqrt{4+4} \approx 2.8284$
• $d_{54} = \sqrt{(7-8)^2 + (6-3)^2} = \sqrt{1+9} \approx 3.1623$
• $d_{42} = \sqrt{(2-7)^2 + (6-6)^2} = 5.0000$
• $d_{20} = \sqrt{(0-2)^2 + (0-6)^2} = \sqrt{40} \approx 6.3246$

Carrying unrounded distances through the sums, the second route contributes $23.3980$ and the total is $f(\pi^{\text{NN}}) \approx 40.8563$. Summing the displayed rounded arc values instead can change the final reported decimal.

Now consider the reversal with $i = 1$ and $j = 3$. Reversing positions $2, 3, 4$ of the permutation (that is, the segment $\{7, 8, 3\}$) produces

The reversal leaves the first customer, 1, fixed but changes the last customer of the first route from 3 to 7. Since distances are symmetric, reversing the internal edges keeps their lengths unchanged. The two changed boundary edges are $1\to7$ replaced by $1\to3$, and $3\to0$ replaced by $7\to0$. Therefore

Here $\Delta$ is the new total distance minus the old total distance, and $d_{ab}$ is the Euclidean distance between nodes $a$ and $b$, including depot node $0$. The negative sign means the reversal improves the tour. The two edges strictly inside the reversed segment retain their total length. The changed entering edge lengthens, while the changed return edge shortens by more, producing the net improvement. Checking every changed boundary edge is essential when a reversed segment ends at a route boundary.

The output confirms that reversing $\{7,8,3\}$ to $\{3,8,7\}$ lowers the length by about 2.4637. Other reversals can worsen it, as the printed positive delta illustrates. Every complete candidate score costs one objective evaluation. A full scan contains 28 such calls; initialization and restarts also consume the 300-call limit. Annealing spends that same limit on its initial score and proposals, while NN-seeded random search uses one nearest-neighbor score followed by 299 random permutations.

For the acceptance rule, take a hypothetical worsening move with $\Delta = +0.5$. At temperature $T = 1.0$ the acceptance probability is $\exp(-0.5) \approx 0.607$, so even a small worsening is accepted most of the time. At temperature $T = 0.1$ it is $\exp(-5) \approx 0.0067$, so this $+0.5$ worsening move is rarely accepted. And at temperature $T = 0.01$ it is $\exp(-50) \approx 2 \times 10^{-22}$, effectively zero. That exponential controls acceptance of worsening proposals; annealing also requires a proposal rule, a temperature schedule, state updates, and a stopping budget. In the mathematical acceptance rule, a larger temperature accepts a fixed worsening move more often, while any finite positive temperature leaves a positive probability. In floating-point code, sufficiently small exponentials can underflow to zero.

The design center is a tiny Budget object that counts every objective evaluation and remembers the best permutation it has scored. This centralizes the accounting, so that hill climbing, annealing, and random search all spend budget by the same rule.

We now package the pieces into runnable algorithms. The search implementation uses NumPy and standard Python; figures use Matplotlib and the shared book style. We implement the acceptance and budgeting rules directly so their behavior is inspectable. The budget accounting, the fact that a scoring call is the currency of comparison, is what we want to control ourselves. It also makes the comparison honest: a method cannot quietly spend extra evaluations on rejected proposals or on restart initialization without those calls showing up in the trace.

The trace method returns the running best-so-far length after every evaluation, which is the incumbent curve we will plot. When we call it at the end of a run, it captures the entire trajectory rather than just the final number. That distinction matters: two methods can end at the same objective while one found it early and the other found it only at the last evaluation.

Hill climbing scans the $28$ reversals in the order shown, retaining a candidate through the tolerance-aware update described above. After a completed scan, it steps to that candidate only if the candidate beats the current length by more than $10^{-12}$; otherwise it restarts from a fresh random permutation if budget remains. Equal-cost neighbors still consume budget and the scan continues; they do not themselves authorize an installed step. If the budget interrupts a partial scan, the function returns the best permutation scored so far without spending another evaluation.

Simulated annealing proposes a uniformly random reversal, accepts it by the Metropolis rule, and updates the running best. Nothing about the acceptance uses the budget structures differently from hill climbing: every accepted and every rejected proposal costs one evaluation. Random search uses the same budget object but proposes uniformly random permutations, which makes it a baseline for how much structure the local moves add.

The implementation also rejects a zero or subnormal ratio $T_1/T_0$ in the quotient's floating-point type. This range check leaves equal positive temperatures valid, even when their absolute values are subnormal. The executable schedule is a floating-point approximation to the ideal geometric sequence.

We now run each method on each of $20$ seeds with the same $300$-evaluation budget, and record both the final incumbent and the full incumbent trace. We also check every reported final solution: its identifiers must form the required permutation, it must pass the feasibility checks, and its recomputed objective must match the reported best score within tolerance. These assertions are part of the experiment, not decoration; they catch accounting mistakes before those mistakes become a figure.

Key takeaways from the implementation:

• The methods receive the same number of complete objective evaluations; this does not equalize runtime, construction work, or memory.
• On these 20seeds, annealing has a slightly lower mean than hill climbing and a larger descriptive standard deviation. This is an observation about one instance and schedule.
• NN-seeded random search has a higher final mean here, while providing a baseline with the same nearest-neighbor initial score.
• Report seed variation and the experimental configuration alongside the mean.

Local search and simulated annealing are appropriate when the decision variable is a discrete arrangement, the objective is cheap to evaluate or can be updated incrementally, and a good feasible solution is more useful than a proof of optimality. Routing, scheduling, packing, and assignment are natural fits because a small structural edit (reversing a segment, swapping two jobs, moving an item) produces a candidate that can be scored directly. If an exact method can handle the instance, include it as a reference, as we do by enumerating these 40,320 permutations. A disconnected neighborhood or a budget too small for a meaningful scan also limits the heuristic. In those settings the heuristic may still produce a useful answer, but the comparison should be framed as baseline improvement under a fixed budget, not as a claim of global optimality.

The representation, decoder, and neighborhood jointly determine which candidate changes the algorithm can explore. In this chapter the permutation, the fixed four-customer split, and inclusive reversals work together because adjacent reversals generate all permutations, so the state graph is connected, while wider reversals can cross the route boundary and reassign customers between vehicles. Restricting moves to within-route reversals would silently forbid that reassignment and could leave the search stuck on a solution that is poor only because a customer is on the wrong vehicle. The practical test is to ask whether the move set can express the changes the objective rewards, and whether repeated application can reach every feasible solution. Symmetric within-route reversals give routing a geometric neighborhood, but arbitrary reversals need not improve a route. Scheduling and packing require moves suited to their own decisions and constraints.

Data requirements are modest but not zero. The instance must supply the coordinates, demands, capacities, time windows, service times, and depot information needed by the decoder, and the distance matrix should be computed once and reused rather than recalculated at every proposal. A feasibility checker is part of the data pipeline, not an afterthought: it should be called on every reported final solution, and in this chapter the experiment checks the required permutation, feasibility, objective equality, and monotone incumbent traces. Unlike feature-based models, local search does not require feature scaling or missing-value imputation in the usual sense, but inconsistent units, asymmetric distances, or an infeasible warm start can dominate the outcome. When several objectives are combined, state their units, scaling, and policy weights before scalarizing; equal numerical scales alone do not determine appropriate priorities.

Check experimental comparisons at the level of scored candidates. Reporting only a successful seed hides run-to-run variation. Counting only accepted moves understates cost, because rejected proposals, restarts, and initialization all consume evaluations. Equal evaluation counts should be accompanied by runtime measurements if computational cost is the comparison target: scoring a permutation traverses every arc in both tours, while a nearest-neighbor scan examines candidate arcs more cheaply. Inspect uphill acceptance separately from ties and improvements. A high total acceptance rate can reflect equal-cost or improving proposals; it does not alone prove that temperature is too high. Very few accepted worsening moves may reflect low temperature or the proposed objective changes. Hill climbing should be paired with restarts or perturbation, and annealing should be monitored rather than tuned by a single final number.

Computational cost is governed by how often the objective is evaluated and how expensive each evaluation is. A full scan here examines 28 reversals, so the 300-evaluation budget supports roughly ten scans, enough to reveal plateaus but not enough to certify optimality. For a symmetric within-route 2-opt reversal, the distance delta uses two removed and two replacement boundary edges and can be computed in $O(1)$ distance lookups. Cross-split moves require the correct decoder-specific depot accounting, and time-window feasibility can still need a route scan. This implementation deliberately uses full $O(n)$ candidate scoring and copies permutations; its distance matrix uses $O(n^2)$ storage, each budget trace uses $O(K)$ storage, and the repeated-run experiment retains all traces. Independent seeds can be run separately. If the neighborhood grows quadratically with the number of customers, candidate lists or first-improvement scans may be necessary to keep each iteration affordable; the general principle is to preserve the evaluation accounting while making each evaluation as light as the problem structure allows.

Performance should be reported as a distribution, not a point. Across 20 seeds with the same 300-evaluation budget, report the mean, standard deviation, minimum, maximum, and incumbent traces for each method, and compare against both a construction heuristic and a random baseline. On small instances, full enumeration supplies an exact reference; on larger ones, use the best known solution or a lower bound. In deployment, log the acceptance rate, the incumbent improvement, and the feasibility rate to help diagnose poor schedule behavior. Inspect uphill acceptance separately from ties and improvements; these logs do not guarantee a unique diagnosis or detection before quality degrades. Re-run the search when the instance changes, keep the seed ensemble as part of the evaluation protocol, and treat the method as a budgeted improvement procedure rather than a source of guaranteed optima. That framing also sets up the next chapter, where population-based methods reuse this instance, decoder, and evaluation accounting to ask whether a different search dynamic can spend the same evaluations more effectively.

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.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about local search and simulated annealing on the eight-customer routing instance.