Large-step Markov chains for the Traveling Salesman Problem

We introduce a new class of Markov chain Monte Carlo search procedures, leading to more powerful optimization methods than simulated annealing. The main idea is to embed deterministic local search techniques into stochastic algorithms. The Monte Carlo explores only local optima, and it is able to make large, global changes, even at low temperatures, thus overcoming large barriers in configuration space. We test these procedures in the case of the Traveling Salesman Problem. The embedded local searches we use are 3-opt and Lin-Kernighan. The large change or step consists of a special kind of 4-change followed by local-opt minimization. We test this algorithm on a number of instances. The power of the method is illustrated by solving to optimality some large problems such as the LIN318, the AT&T532, and the RAT783 problems. For even larger instances with randomly distributed cities, the Markov chain procedure improves 3-opt by over 1.6%, and Lin-Kernighan by 1.3%, leading to a new best h...