Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP

2-Opt is probably the most basic and widely used local search heuristic for the TSP. This heuristic achieves amazingly good results on "real world" Euclidean instances both with respect to running time and approximation ratio. There are numerous experimental studies on the performance of 2-Opt. However, the theoretical knowledge about this heuristic is still very limited. Not even its worst case running time on Euclidean instances was known so far. In this paper, we clarify this issue by presenting a family of Euclidean instances on which 2-Opt can take an exponential number of steps. Previous probabilistic analyses were restricted to instances in which n points are placed uniformly at random in the unit square [0, 1](2), where it was shown that the expected number of steps is bounded by (O) over tilde (n(10)) for Euclidean instances. We consider a more advanced model of probabilistic instances in which the points can be placed according to general distributions on [0, 1](2). In particular, we allow different distributions for different points. We study the expected running time in terms of the number n of points and the maximal density phi of the probability distributions. We show an upper bound on the expected length of any 2-Opt improvement path of (O) over tilde (n(4+1/3) . phi(8/3)). When starting with an initial tour computed by an insertion heuristic, the upper bound on the expected number of steps improves even to (O) over tilde (n(3+5/6) . phi(8/3)).If the distances are measured according to the Ma:nhattan metric, then the expected number of steps is bounded by (O) over tilde (n(3+1/2) . phi). In addition, we prove an upper bound of O(root phi) on the expected approximation factor with respect to both of these metrics. Let us remark that our probabilistic analysis covers as special cases the uniform input model with phi = 1 and a smoothed analysis with Gaussian perturbations of standard deviation sigma with phi similar to 1/sigma(2). Besides random metric instances, we also consider an alternative random input model in which an adversary specifies a graph and distributions for the edge lengths in this graph. In this model, we achieve even better results on the expected running time of 2-Opt.