3-Opt Local Search for TSP?

Question

I understand that the 3-Opt Heuristic involves removing three edges from a graph and adding three more to re-complete 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, this paper 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. A 3-opt move can actually be seen as two or three 2-opt moves.

However, I count 8 different ways to reconnect the tour (7 if not counting the order before removing the edges). 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 better but I haven't come across any yet. All resources I find simply say "remove three edges, reconnect them". That's it.

Answer 1

I agree that the footnote reduces it to four ways, not two.

In the following code, you can pass in a permutation p and it will perform a 3-opt, one of the four possibilities. If you also pass broad=False, it will allow any of the 8 (including the identity).

However, I would really welcome a review of this code, or a link to any other implementation online.

Note that this code doesn't enforce that the edges we cut are originally non-contiguous. Should it?

Note also that this just does the move, it doesn't carry out the full routine of trying all moves and choosing the best.

def three_opt(p, broad=False):
    """In the broad sense, 3-opt means choosing any three edges ab, cd
    and ef and chopping them, and then reconnecting (such that the
    result is still a complete tour). There are eight ways of doing
    it. One is the identity, 3 are 2-opt moves (because either ab, cd,
    or ef is reconnected), and 4 are 3-opt moves (in the narrower
    sense)."""
    n = len(p)
    # choose 3 unique edges defined by their first node
    a, c, e = random.sample(range(n+1), 3)
    # without loss of generality, sort
    a, c, e = sorted([a, c, e])
    b, d, f = a+1, c+1, e+1

    if broad == True:
        which = random.randint(0, 7) # allow any of the 8
    else:
        which = random.choice([3, 4, 5, 6]) # allow only strict 3-opt

    # in the following slices, the nodes abcdef are referred to by
    # name. x:y:-1 means step backwards. anything like c+1 or d-1
    # refers to c or d, but to include the item itself, we use the +1
    # or -1 in the slice
    if which == 0:
        sol = p[:a+1] + p[b:c+1]    + p[d:e+1]    + p[f:] # identity
    elif which == 1:
        sol = p[:a+1] + p[b:c+1]    + p[e:d-1:-1] + p[f:] # 2-opt
    elif which == 2:
        sol = p[:a+1] + p[c:b-1:-1] + p[d:e+1]    + p[f:] # 2-opt
    elif which == 3:
        sol = p[:a+1] + p[c:b-1:-1] + p[e:d-1:-1] + p[f:] # 3-opt
    elif which == 4:
        sol = p[:a+1] + p[d:e+1]    + p[b:c+1]    + p[f:] # 3-opt
    elif which == 5:
        sol = p[:a+1] + p[d:e+1]    + p[c:b-1:-1] + p[f:] # 3-opt
    elif which == 6:
        sol = p[:a+1] + p[e:d-1:-1] + p[b:c+1]    + p[f:] # 3-opt
    elif which == 7:
        sol = p[:a+1] + p[e:d-1:-1] + p[c:b-1:-1] + p[f:] # 2-opt

    return sol