Revisiting the big valley search space structure in the TSP

Abstract

The solution space of the travelling salesman problem under 2-opt moves has been characterized as having a big-valley structure, in which the evaluation of a tour is positively correlated to the distance of the tour from the global optimum. We examine the big-valley hypothesis more closely and show that while the big-valley structure does appear in much of the solution space, it breaks down around local optima that have solutions whose evaluation is very close to that of the global optimum; multiple funnels appear around local optima with evaluations close to the global optimum. The appearance of multiple funnels explains why certain iterated local search heuristics can quickly find high-quality solutions, but fail to consistently find the global optimum. We then investigate a novel search operator, which is demonstrated to have the ability to escape funnels at evaluations close to the global optimum.

Keywords:

• combinatorial optimization
• local search
• travelling salesman problem

Acknowledgements

This research was sponsored by the Air Force Office of Scientific Research, Air Force Materiel Command, USAF, under grant number FA9550-08-1-0422. The US Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon.

Notes

1 In fact, we found two distinct globally optimal solutions. Because they were close together, we selected one for distance computation.