On the exact number of possibilities for cutting and reconnecting the tour of a traveling salesman with Lin-$k$-Opts

Abstract

When trying to find approximate solutions for the Traveling Salesman Problem with heuristic optimization algorithms, small moves called Lin-$k$-Opts are often used. In our paper, we provide exact formulas for the numbers of possible tours into which a randomly chosen tour can be changed with a Lin-$k$-Opt.

13 pages, 4 figures