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

Stattenberger, Guenther; Dankesreiter, Markus; Baumgartner, Florian; Schneider, Johannes J.

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

Authors

Stattenberger, Guenther

Dankesreiter, Markus

Baumgartner, Florian

Schneider, Johannes J.

Description

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