Some Examples of Difficult Traveling Salesman Problems

We construct instances of the symmetric traveling salesman problem with n = 8k cities that have the following property: There is exactly one optimal tour with cost n, and there are 2^k−1(k − 1)! tours that are next-best, have arbitrarily large cost, and cannot be improved by changing fewer than 3k edges. Thus, there are many local optima with arbitrarily high cost. It appears that local search algorithms are ineffective when applied to these problems. Even more catastrophic examples are available in the non-symmetric case.