Here is a short description of an augmented version of the LK-algorithm. Instead of making changes at one point, changes are made at two different points at each step of the recursive algorithm. This improves the quality of the resulting tours considerably, although the price is much longer running times.
For each fixed point T (town) you do the following: try a possible neighbour N (as explained below), connect this point to T and cut the subtour between T and N. Now you have a closed subtour and an open subtour and you can start with the recursion. Do this for all neighbours and all point, until after one improvement you check all possible points and neighbours.
At each step you have a closed subtour and an open subtour. You glue this open subtour to the closed subtour. To get a closed subtour again and an open subtour, you have to cut another open subtour from the resulting figure, which geometrically resembles a "B". While doing this, you control that the whole length of the new open subtour and the new closed subtour; in addition, the length of one of the deleted edges is shorter than the length of the best known tour before. If you thereby obtain a shorter tour than the currently shortest tour, you take the new tour as the shortest.
At each step you also try to close the open subtour under the condition that the whole lenght must still be shorter than the best tour. Now you glue these two circles together by connecting one part of a closed subtour to the other subtour to obtain an closed subtour and an open subtour. Using this method you can build "double bridges". This additional option can be implemented in conventional LK-implementations with little effort.
Additionally, you can try to connect one endpoint of the open subtour to one point in the open subtour, with the usual length restriction. By doing this you get a "O6". By deleting one edge you again have a closed subtour, which did not change in this step, and a new open subtour.
First, you should restrict the depth of the recursion.
Second, as in the LK-algorithm you should never delete a formerly added connection.
Third, never try a pair of a closed subtour and an open subtour which have been previously examined
Fourth, for higher recursion levels, the "distance" of the starting and the ending point should be checked. "Distance" means the minimum amount of points to be travelled to from one point to the other with connections provided by neighbour lists described below. Doing the second, the third and the fourth restriction in a clever way is extremely difficult.
Fifth, be aware of never-ending calculations, that means, that you should abort your backtracking for one starting, if you have examined a real high number of situations. The other restrictions should be improved so that this restriction is not needed anymore, because this restriction clearly reduces the quality of the resulting tour.
The list for each point is based on the Delaunay triangulation of the whole configuration, but there is a kind of reengineering of these neighbour lists.
Assume that you have a perfect neighbour list, that means that you can be sure that all connections of the optimal tour are on this list. Furthermore assume, that there is a connection from P1 to P2 on a neighbour lists, and you have a third point P3 so, that for all neighbour point pairs P4 and P5 of P3 you have: Length of P1 to P2 + Length of P4 to P3 + Length of P3 to P5 >= Length of P1 to P3 + Length of P3 to P2 + Length of P4 to P5 , then it should be clear that you can delete the connection between P1 and P2 from the neighbour lists. Unfortunately the Delaunay triangulation as a source of neighbour lists is not perfect, but with some refinements like insertions of certain edges it is applicable to Delaunay triangulations.