= Asymmetric 2-opt reversal cost
{title2=$\Delta=\Delta_{\rm boundary}+\Delta_{\rm internal}$}
A 2-opt schedule move reverses a consecutive block $v_p,\ldots,v_q$, reconnecting its boundary arcs. With directed costs, its change is
$$
\Delta=c_{v_{p-1},v_q}+c_{v_p,v_{q+1}}
-c_{v_{p-1},v_p}-c_{v_q,v_{q+1}}
+\sum_{r=p}^{q-1}(c_{v_{r+1},v_r}-c_{v_r,v_{r+1}}).
$$
Omitting the internal sum is valid only for symmetric costs. A <simulated annealing> step accepts an increase with probability $\exp(-\Delta/T)$; a strictly positive temperature permits escape from local minima.
Back to article page
