How does the 3-opt algorithm for TSP work?

Question Detail: 

I understand that the 3-Opt Heuristic for solving the Traveling Salesman problem involves removing three edges from a graph and adding three more to recomplete the tour. However, I've seen many papers that mention that when three edges are removed, there remain only 2 possible ways to recombine the tour - this doesn't make sense to me.

For example, I found a paper [1] that says:

The 3-opt algorithm works in a similar fashion, but instead of removing two edges we remove three. This means that we have two ways of reconnecting the three paths into a valid tour1 (figure 2 and figure 3). A 3-opt move can actually be seen as two or three 2-opt moves.

However, I count 3 different ways to reconnect the tour. What am I missing here?

Also, can someone link me to an algorithm for 3-opt if possible? I'm just trying to understand it, but I haven't come across any clear algorithms yet: all resources I find simply say "remove three edges, reconnect them". That's it, which is sort of vague.

Here are the 3 tours that seem to me to be 3-opt moves after removing three edges.

---

1. Heuristics for the Traveling Salesman Problem by C. Nilsson

Asked By : ujvl

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19808

Answered By : Yuval Filmus

You missed the footnote — these ways are "not including the connections being identical to a single 2-opt move". Indeed, there are only two permutations in $S_3$ without fixed points (also known as derangements), namely $(123)$ and $(132)$. More generally, for a $k$-opt move it is enough to consider permutations without fixed points, since those with $t$ fixed points are $(k-t)$-moves.

The algorithm for $k$-opt local search is as follows. Start with some initial solution, say the one produced by Christofides's algorithm. Repeatedly try to improve it by performing a $k$-opt: choose $k$ edges and reconnect them in a different way (this time it's OK if the move is also an $\ell$-move for some $\ell < k$) that results in a shorter tour.

The way this is implemented is by going over all sets of $k$ edges and over all ways of reconnecting the edges, perhaps in some intelligent order, and computing the difference in length (there is no need to recompute the length of the entire tour, just the different of length; that takes $O(k)$ instead of $O(n)$); if an improvement is found, we make the switch and repeat from the beginning. We continue like that until we get stuck.

A different variant is to always try all possibilities, and use the one that results in the best improvement. There are also other variants which you can probably find in the literature.