  2-Opt is probably the most basic 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 2-dimensional Euclidean instances was known so far. We clarify
this issue by presenting, for every $p\in\mathbb{N}$, a family of $L_p$
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$. We consider
a more advanced model in which the points can be placed independently according
to general distributions on $[0,1]^d$, for an arbitrary $d\ge 2$. In
particular, we allow different distributions for different points. We study the
expected number of local improvements 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
$\tilde{O}(n^{4+1/3}\cdot\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 $\tilde{O}(n^{4+1/3-1/d}\cdot\phi^{8/3})$. If the
distances are measured according to the Manhattan metric, then the expected
number of steps is bounded by $\tilde{O}(n^{4-1/d}\cdot\phi)$. In addition, we
prove an upper bound of $O(\sqrt[d]{\phi})$ on the expected approximation
factor with respect to all $L_p$ 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\sim1/\sigma^d$.
