How does a 2.5-opt linear search work for the TSP?

Question

I understand the logic behind performing a 2-opt, pairwise exchange to get two edges to uncross:

Simply take two edges out and replace them with two other ones. If you have a list of cities:

A, B, C, D, E, A, and AB and DE are chosen... then just reverse the order of cities between B and D so:

A, E, B, C, D, A

For 3-opt, similarly, I also understand that given A,B,C,D,E,F,A, there are two possible changes. For example, if AB, CD and EF are chosen, then:

A,C,B,E,D,F,A and A,E,D,B,C,F,A are both possibilities of 3-opted tours.

However, what exactly is 2.5 opt and how can it be implemented? I've tried looking for info on it but I don't understand the majority of what I've found...

Answer 1

The document at http://www.staff.uni-mainz.de/schneidj/papers/gestatten.pdf seems reasonably clear.

In section 2.2 it describes node insertion, which cuts a node out from the tour and pastes it back between two other nodes which previously came one after the other (there is also a picture of this).

Section 2.3 describes 2-opt, which I believe you understand.

Section 2.5 describes 3-opt and works out some statistics about it. At the very end of this section it shows that node insertion can be treated as a special case of this, with slightly different statistics and that, for this reason, node insertion is sometimes called 2.5-opt. Like 3-opt it cuts three links, but like 2-opt there are about O(N^2) possible such moves.

In case the link gets broken again, the reference is:

On the Neighborhood Structure of the Traveling Salesman Problem Generated by Local Search Moves Günther Stattenberger · Markus Dankesreiter · Florian Baumgartner · Johannes J. Schneider