Local Search and Simulated Annealing › Example

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

$$\pi^{\text{NN}} = (1, 7, 8, 3, \mid 6, 5, 4, 2),$$

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

$$f(\pi^{\text{NN}}) = (d_{01} + d_{17} + d_{78} + d_{83} + d_{30}) + (d_{06} + d_{65} + d_{54} + d_{42} + d_{20}).$$

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

$$\pi' = (1, 3, 8, 7, \mid 6, 5, 4, 2).$$

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

$$\Delta=d_{13}+d_{70}-d_{17}-d_{30} =\sqrt{13}+\sqrt{10}-\sqrt{8}-\sqrt{41} \approx-2.4637.$$

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.