In his 2009 paper General k-opt submoves for the Lin–Kernighan TSP heuristic, Helsgaun defines the local tour improvements on which the LKH heuristics are based as:
several questions arise from that definition of admissible $k$-Opt moves:
- Where is the proof that the set of exchanged edges must form a cycle?
- Why aren't adjacent tour edges considered as exchange candidates?
Here is a simple counter example to the neessity of the single-cycle conjecture and to the non-adjacent tour edges assumption plus is it a cheaper $3$-Opt move than the ones requiring non-adjacent tour edges:
- One pair of the red tour edges that are exchanged with the solid black edges is adjacent.
- The union of exchanged tour-edges with the replacement edges consists of two vertex-disjoint cycles depicted by the thin ellipses.
- The exchange of the edges resembles a transition between tours.