Here I discuss how to do a single 2-opt move.

First, for a general description of 2-opt moves, see wikipedia:
   http://en.wikipedia.org/wiki/2-opt

In our particular situation, we have a cyclic tour on all V vertices,
and e is an edge from G.  We want to try adding e to create a 2-opt
move.  Here we sketch out the steps.

Let v and w be the two endpoints of e.  These vertex ids are also
indices into the points array, i.e. they correspond to points[v] and
points[w].

I suppose your current tour is stored in an array of size V, so the
vertex ids around the tour are tour[0], tour[1], ..., tour[V-1].  So
the first tour edge goes from points[tour[0]] to points[tour[1]], and
so on.  The tour is cyclic, so the last edge wraps around from
points[tour[V-1]] to points[tour[0]].

Find indices i and j, positions in the tour, so that tour[i]==v and
tour[j]==w.  (This step is fast if you also keep track of the
"inverse" map, from vertex ids to their positions in the tour.)

Find v'=tour[i+1] and w'=tour[j+1] (the vertices right after v and w,
in the tour order).  If v'==w, or w'==v, then we can give up now (we
are trying to add an edge that is already in the tour!).  You should
take both i+1 and j+1 modulo V, in case they wrap around.  They define
an edge e'=(v',w') (it is OK if e' is not in G, the tour does not have
to contain only edges from G).  The current tour has edges (v,v') and
(w,w'), we are considering a 2-opt move which would remove those two
edges, and add edges e and e' in their place.

The proposed 2-opt move makes the following net change in tour weight:

   Add weights of e and e', subtract weights of (v,v') and (w,w').

You should compute this net change in tour weight.  If it is not an
improvement (the net change is >= 0), then you do not want to do this
2-opt move.  Otherwise, you do want to do the 2-opt move.

OK: in order to actually DO the 2-opt move, you simply need to
"reverse" half the tour array.  You reverse all the vertex ids
(cyclically) from tour[i+1] to tour[j] (or instead you could reverse
from tour[j+1] to tour[i], if that would be faster).


REMARK1: an second 2-opt move can also be defined by e.  That is, you
consider the move defined by v''=tour[i-1], w''=tour[j-1], adding
edges e and e''=(v'',w''), and removing edges (v,v''), (w,w'').

REMARK2: instead of comparing "net change < 0", it might be safer to
compare "net change < -0.000001" (or some such small number), to avoid
any potential issues involving floating-point round-off error.