The traveling salesman problem (TSP) is one of the most studied problems in combinatorial optimization. We are given a complete undirected graph G = (V,E), and a distance matrix. We assume that the distances are symmetric and satisfy the triangle inequality, i.e., for any vertices u,v,w ϵ V, d(u,v)=d(v,u) and d(u,w) ≤ d(u,v)+d(v,w). The objective is to find atour –a cycle C that visits each vertex in V exactly once (i.e., C is aHamilton cycle in G) – whose total length is minimized. This problem is NP-hard, even with Euclidean distances in the plane.
One of the most common techniques for approaching TSP is the k-opt heuristic: it repeatedly tries to perform an improving k-change – a replacement of up to k tour edges with non-tour edges. k-opt heuristics are used either directly or as subroutines in more sophisticated heuristics, such as the celebrated Lin-Kernighan heuristic. The value of k is typically 2 or 3. In this paper, we focus on the 2-opt heuristic, and we modify it to be based on a function f of the distances rather than the distances solely. This may be viewed as modifying the local search with the 2-change neighborhood to be non-oblivious. We denote the corresponding heuristic by (2,f)-opt. We provide theoretical performance guarantees for it: both lower and upper bounds based on the ones given by Chandra, Karloff, and Tovey (1999), obtained originally for the standard 2-opt heuristic; the upper bound is improved by a factor of √2 with respect to the known upper bound of the standard 2-opt. We then provide experimental evidence based on TSPLIB benchmark problems, showing that (2,f)-opt with f(x) = xr for various values of r < 1 significantly outperforms 2-opt.
