Local Search and Simulated Annealing › Formula

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:

$$\text{route}_1 = (0, \pi_1, \pi_2, \pi_3, \pi_4, 0), \qquad \text{route}_2 = (0, \pi_5, \pi_6, \pi_7, \pi_8, 0),$$

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:

$$\begin{aligned} f(\pi) &= d(0, \pi_1) + \sum_{k=1}^{3} d(\pi_k, \pi_{k+1}) + d(\pi_4, 0) \\ &\quad + d(0, \pi_5) + \sum_{k=5}^{7} d(\pi_k, \pi_{k+1}) + d(\pi_8, 0), \end{aligned}$$

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

$$\pi_{t+1} = \arg\min_{\pi' \in \mathcal{N}(\pi_t)} f(\pi') \quad \text{provided} \quad \min_{\pi' \in \mathcal{N}(\pi_t)} f(\pi') < f(\pi_t) - \epsilon,$$

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

$$\Delta = f(x') - f(x),$$

and accept the proposal with probability

$$P_{\text{accept}} = \begin{cases} 1 & \Delta < 0, \\ \exp\!\left(-\dfrac{\Delta}{T_k}\right) & \Delta \ge 0, \end{cases}$$

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.