Nonoptimal Edges for the Symmetric Traveling Salesman Problem

Abstract

For the symmetric traveling salesman problem, we identify a set of (undirected) edges that can be eliminated while still retaining at least one optimal solution of the problem. The simple identification rules are based on the fact that a solution can be optimal only if it is 2-optimal. The rules are less stringent than those formulated for nonoptimal arcs (directed), applied to the symmetric case. So, in general, they identify more nonoptimal edges. Application of the theory in a 1-tree based traveling salesman algorithm roughly halves the average computation time for Euclidean problems. We indicate to what extent the theorems presented here can be adapted for variants of the traveling salesman problem.