Some Local Moves

The k-OPT class of moves takes the tour and removes k edges from it, then reglues the pieces in some other way.

• 2-OPT: flips a half tour. Pretty fast, can get badly stuck.
• 3-OPT: shuffles thirds. Slower, less prone to sticking.

Picture...

Theoretically, even in metric TSPs, ratio between $1/4 \; \sqrt{n}$ and $4 \sqrt{n}$ in the worst case.

Furthermore, it can take O(2^n/2) moves to get there!

Good performance in practice, though.