Non-sequential 5-opt moves – part 1 of 7

Extending double bridge, from d4

We already know how to build sequential moves, that is how to extended sequential 3-opt move to sequential 4-opt move or 4-opt move to 5-opt move. We can use the same approach to extend non-sequential 4-opt move, for example double bridge, to built some 5-opt non-sequential move.

The first option is to extend the second submove and can be made as follows:

1. Step 0
   1. Start from tour after considered double bridge move.
2. Step 1
   1. Remove last link added in the second submove of double bridge, that is: from d4 to d1.
   2. Add link between d4 and the some other city d5.
3. Step 2
   1. Remove link between d5 and its tour neighbor d6.
   2. Add link between d6 and the first city of submove, d1, to close the tour.

inOrder(c2, d5, d1, true)

double bridge (AB)EDC	d6 = t_pred(d5)	AbEDC

Note that we should make sure we have chosen this d6, tour neighbor of d5, that linked with d1 closes the tour. For example in the above case we should not use alternative d6, because it disjoins tour into two cycles:

inOrder(c2, d5, d1, true)

double bridge	d6 = t_succ(d5)	disjoining move

The first set of diagrams shows that when d5 is between c2 and d1, then for c6 we can use tour predecessor of c5. The second set of diagrams shows that when d5 is between c2 and d1, then for c6 we should not use tour successor of c5.

But what if d5 happens to be not in the upper-right segment, not between c2 and d1?

Then it can be between d2 and c3, or between c4 and d3, or between d4 and c1. Relevant diagrams for these cases are given below:

inOrder(d2, d5, c3, true)

double bridge AED(BC)	d6 = t_pred(d5)	AbdeC

 

inOrder(c4, d5, d3, true)

double bridge AE(CD)B	d6 = t_pred(d5)	AceDB

 

inOrder(d4, d5, c1, true)

double bridge A(DE)CB	d6 = t_pred(d5)	AdECB

So in this kind of extending double bridge move, for d6 we should always take the tour predecessor of d5. It is easy to check that in each case using tour successor results in disjoining move.

Aditionally, we should check check whether d5 and d6 meet the restrictions: city d5 should not be the same as d1, nor d2, nor a tour neighbor of d4 (one of these neigbors is d3). Link (d5, d6) to remove should not be the same as link (c1, c2) nor (c3, c4), already removed in the first submove.

Then discussed algorithm can be implemented as follows:

proc LK_Bridge_A3(c1, c2, c3, c4,
                  d1, d2, d3, d4: City_Number;
                  G2a: Length_Gain; tourOrderPrev: int): bool =
  ## c1..c4, d1..d4 define valid double bridge move
  ## G2a is partial gain from this double bridge,
  ## without cost of the last, closing link (d4, d1),
  ## that is:
  ##   d(c1,c2) - d(c2,c3) + d(c3,c4) - d(c4,c1) +
  ##   d(d1,d2) - d(d2,d3) + d(d3,d4)
...
  if not (tourOrderPrev == TO_ADBC):
    return false

  d4_succ = t_succ(d4)
  d4_pred = t_pred(d4)
  block find_move:
    for d5 in neighbors(d4):
      if (d5 == d4_succ) or (d5 == d4_pred):
        continue      
      if (d5 == d1) or (d5 == d2):
        continue

      G2 = G2a - distance(d4, d5)
   
      # choose d6 as predecessor of d5:
      d6 = t_pred(d5)
      if (d5 == c1) and (d6 == c2) or
         (d5 == c2) and (d6 == c1):
        continue
      if (d5 == c3) and (d6 == c4) or
         (d5 == c4) and (d6 == c3):
        continue
        
      G3a = G2 + distance(d5, d6)
      gainFromCloseUp = G3a - distance(d6, d1)
      if gainFromCloseUp > 0: # improving move found      
        improved = true
        Make_5opt_NS_Move(c1, c2, c3, c4,
                          d1, d2, d3, d4, d5, d6,
                          TO_AxbEDC) # NOTE this tourOrder is exemplary
        tourLen = tourLen - gainFromCloseUp
        Set_DLB_off(DontLook, [c1, c2, c3, c4,
                               d1, d2, d3, d4, d5, d6])
        break find_move
  #end_block find_move

  result = improved

It may not be obvious, but all four considered move types has one more common feature: all of them can be applied using exactly the same procedure: first we apply initial double bridge move, and then we apply simple 2-opt move, the very same in each case. This 2-opt (segment reversing) is equivalent to link exchange: links (d4, d1) and (d5, d6) are exchanged for (d4, d5) and (d6, d1).

proc Make_5opt_NS_Move(c1, c2, c3, c4,
                       d1, d2, d3, d4, d5, d6: City_Number;
                       tourOrder: int) =
  case tourOrder
  of TO_AxbEDC_1,  TO_AxbxdxeC_1,
     # c12-d65-d12-c34-d34, c12-d12-d65-c34-d34,
     TO_AxcxeDB, TO_AxdECB:
     # c12-d12-c34-d65-d34, c12-d12-c34-d34-d65
    Exchange_Links(d1, d2, d4, d3)
    Exchange_Links(c1, c2, c4, c3)
    Exchange_Links(d1, d3, d4, d2)  
    Exchange_Links(d1, d4, d6, d5)
  of ...:
    ...

For example type AbEDC is obtained from double bridge (AB)EDC by reversing segment B, which in this case is the segment from d5 to d1. Type AbdeC is obtained from double bridge AED(BC) by reversing joined segments EDB, which in the same as reversing joined segments CA, in this case also from d5 to d1. And so on...