Performance of efficient variants of the 2-Opt heuristic for the traveling salesperson problem

We analyze variants of the 2-opt local search heuristic for the Traveling Salesperson Problem (TSP) with guaranteed polynomial running-time. First we consider X-opt, a heuristic that removes intersecting pairs of edges from two-dimensional Euclidean instances. We show that the longest X-optimal tour may be approximately n/2 times longer than the optimal tour in the worst case. Moreover, even when the instance consists of n points placed uniformly at random in the unit square, the longest tour is Ω(n) times longer than the optimal tour. Next, we propose a new heuristic, which we call Y-opt, that is defined for all TSP instances, not just Euclidean ones. Y-opt has essentially the same approximation guarantees as the well-studied 2-opt. We furthermore evaluate the approximation performance of both X-opt and Y-opt numerically on random instances and compare them to 2-opt. While Y-opt behaves as predicted, we find that X-opt appears to have a constant approximation ratio on these instances in practice.