A computational study of smoothing heuristics for the traveling salesman problem

Over the last five years or so, data smoothing has been used to improve the performance of heuristics that solve combinatorial optimization problems. Data smoothing allows a local search heuristic to escape from a poor, local optimum. In practice, data smoothing has worked well when applied to the traveling salesman problem. In this paper, we conduct an extensive computational study to test the performance of eight smoothing heuristics for the traveling salesman problem. In particular, we apply eight smoothing heuristics and standard versions of two-opt and three-opt to 40 randomly generated Euclidean problems and 30 problems taken from a well-known library of test problems. We compare the solutions generated by the heuristics and provide insight into the behavior of the smoothing heuristics.