A probabilistic analysis of the switching algorithm for the Euclidean TSP (Q1122505)

The 2-switching Algorithm for the Euclidean Traveling Salesman problem is studied. A probabilistic analysis is developed. It gives an evaluation of a simulated annealing version of the Lin-Kernigham algorithm. A bound of the number of points (n) and the minimum distance (d*) between a tour \(\sigma\) and that generated by switching points \(\tau_ i\) and \(\sigma_ j\) is defined. For small d*'s the necessary computation can be too time-consuming. In order to prove a lemma, \(A_{\epsilon}(i,j,k)\) is fixed as the set of points x such that the absolute value of a function F(i,j,k,x) is bounded by an arbitrary \(\epsilon >0\). The lemma establishes that this set is bounded and the bound is calculated. The behavior of a strategy for fixing paths is analyzed in a ``claim''. This claim is a corrollary to the lemma. It is proved and two figures illustrate the involved ideas. The probability that the algorithm stops after no more than \(O(n^{18})\) steps is 1-(d(x,i)-d(x,j)). The possibility of developing a k-switching algorithm is sketched.