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

Disjoining 3-exchanges as base for 5-opt non-sequential moves, part 1

So far we have considered 5-opt non-sequential moves obtained by extending double bridge or crossed bridge move. Double bridge and crossed bridge themselves are obtained from disjoining 2-exchange submove, that is from 2-exchange starting with 12-34. But they are other disjoining k-exchanges that we can start from to built an 5-opt non-sequential move.

Among eight possible types of 3-exchanges there are four disjoining 3-exchange moves. We have already considered them, though in a different context, namely while examining 3-exchanges during constructing a sequential move. These disjoining 3-exchanges are:

        ... TO_123456 # disconnecting...
        ... TO_123465 # disconnecting...
        ... TO_124356 # disconnecting...
        ... TO_126543 # disconnecting...

12-34-56
12-34-65	12-43-56	12-65-43

The first of these disjoining 3-exchanges, 12-34-56, breaks tour into three separated cycles. It is not possible to join them into feasible tour by any additional single 2-exchange (to have then 5 exchanges in total). So we would skip this case and take a closer look at the remaining three 3-exchanges, each breaking tour into two cycles only.

General idea of construction of 5-opt non-sequential moves from disjoining 3-exchange is similar to the idea of construction of 4-opt non-sequential moves from disjoining 2-exchange and is shown on diagrams for four descentants of 12-34-65 below:

12-34-65	AEcDB	AdCeB
12-34-65	ADeCB	AcEdB

Note that while from one disjoining 2-exchange (12-34) we have obtained two 4-opt non-sequential move types: double bridge (ADBC) and crossed vertical bridge (AcdB), but any of the three disjoining 3-exchanges gives us four 5-opt non-sequential move types. For example 12-34-65 gives: AEcDB, AdCeB, ADeCB, AcEdB.

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

Extending crossed bridge or double bridge 'from d3'

If we take a closer look at diagram for AdebC move type, we can notice that it cannot be made by extending double bridge or crossed bridge from the last city (d4) in move, if the second submove starts from d1-d2:

On the other hand, if we denoted the city we want to extend move from as d3, then there would be no consistency in the numbering:

Note that so far we used only d1-d2 ordering. Instead we can use the first two cities in the reverse order:

proc LK_Bridge_A1(...) =
...
      improved = LK_Bridge_A2(cF1, cF2, cF3, cF4, d1, d2, Ga)
      if not improved:
        improved = LK_Bridge_A2(cF1, cF2, cF3, cF4, d2, d1, Ga) # NOTE

and get

Using the same approach we obtain:

proc LK_Bridge_A3(...) = 
...
  fwd = (d2 == t_succ(d1))
...
      # choose d6
      case tourOrderPrev
      of TO_ADBC:
        if fwd:
          d6 = t_pred(d5)
          if inOrder(d3, d5, c1, true):
            tourOrder = TO_AxdECB_1   # AdECB
          elif inOrder(c4, d5, d4, true):
            tourOrder = TO_AxcxeDB_1  # AceDB
          elif inOrder(d2, d5, c3, true):
            tourOrder = TO_AxbxdxeC_1 # AbdeC
          else:
            tourOrder = TO_AxbEDC_1   # AbEDC
        else:  # not fwd
          d6 = t_succ(d5)
          if inOrder(d3, d5, c1, true):
            tourOrder = TO_ADxcxeB_3  # ADceB
          elif inOrder(c4, d5, d4, true):
            tourOrder = TO_AECxdB_3   # AECdB
          elif inOrder(d1, d5, c3, true):
            tourOrder = TO_AEDxbC_3   # AEDbC
          else:
            tourOrder = TO_AxdxexbC_3 # AdebC
        #end_if fwd
      of TO_AxcxdB:
        if fwd:
          if inOrder(d3, d5, c1, true):
            d6 = t_succ(d5)
            tourOrder = TO_AECxdB_2   # AECdB
          elif inOrder(c4, d5, d4, true):
            d6 = t_succ(d5)
            tourOrder = TO_ADxcxeB_2  # ADceB
          elif inOrder(d2, d5, c3, true):
            d6 = t_pred(d5)
            tourOrder = TO_AxbEDC_2   # AbEDC
          else:
            d6 = t_pred(d5)
            tourOrder = TO_AxbxdxeC_2 # AbdeC
        else:  # not fwd
          if inOrder(d4, d5, c1, true):
            d6 = t_pred(d5)
            tourOrder = TO_AEDxbC_4   # AEDbC
          elif inOrder(c4, d5, d3, true):
            d6 = t_pred(d5)
            tourOrder = TO_AxdxexbC_4 # AdebC
          elif inOrder(d1, d5, c3, true):
            d6 = t_succ(d5)
            tourOrder = TO_AxdECB_4   # AdECB
          else:
            d6 = t_succ(d5)
            tourOrder = TO_AxcxeDB_4  # AceDB
        #end_if fwd
...

and

proc Make_5opt_NS_Move(...) =
  case tourOrder
  of TO_AxbEDC_1, TO_AxbxdxeC_1, TO_AxcxeDB_1, TO_AxdECB_1:
    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 TO_AxbxdxeC_2, TO_AxbEDC_2, TO_ADxcxeB_2, TO_AECxdB_2:
    Exchange_Links(d1, d2, d4, d3)
    Exchange_Links(c1, c2, c4, c3)
    Exchange_Links(d1, d4, d6, d5)

  of TO_ADxcxeB_3, TO_AECxdB_3, TO_AEDxbC_3, TO_AxdxexbC_3:
    Exchange_Links(d2, d1, d4, d3)
    Exchange_Links(c1, c2, c4, c3)
    Exchange_Links(d2, d3, d4, d1)
    Exchange_Links(d1, d4, d6, d5)
  of TO_AEDxbC_4, TO_AxdxexbC_4, TO_AxdECB_4, TO_AxcxeDB_4:
    Exchange_Links(d2, d1, d4, d3)
    Exchange_Links(c1, c2, c4, c3)
    Exchange_Links(d1, d4, d6, d5)
  ...

Adding these additional types for "backward" second submove requires more code, as can be seen above, slightly changes running times, but makes resulting tours less than 0.1% better, so it may or may be not worth introducing.

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

Extending crossed bridge, from d4

We can use the same approach as in part 1 to extend crossed bridge and build some 5-opt non-sequential move.

inOrder(c2, d5, d1, true)

crossed bridge (AB)deC	d6 = t_pred(d5)	AbdeC

Note that AbdeC is the same type of move that we obtained from double bridge in previous part, with different cities order: some cities have different numbers.

inOrder(d2, d5, c3, true)

crossed bridge	d6 = t_pred(d5)	AbEDC

Note that AbEDC is the very same type of move that we obtained from double bridge in previous part, with different cities order: some cities have different numbers.

 

inOrder(c4, d5, d4, true)

crossed bridge	d6 = t_succ(d5)	ADceB

 

inOrder(d3, d5, c1, true)

crossed bridge	d6 = t_succ(d5)	AECdB

So we have:

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 or crossed bridge move
  ## G2a is partial gain from this 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)
  var
    improved: bool
    d5, d6: City_Number    
    d4_pred, d4_succ: City_Number
    d5_pred, d5_succ: City_Number
    G2, G3a, gainFromCloseUp: Length_Gain
    goodSuffix: Suffix
    goodSufficesList: seq[Suffix]
    tourOrder: int
    tried_d5: int = 0
    breadth: int

  improved = false
  d4_succ = t_succ(d4)
  d4_pred = t_pred(d4)
  block find_promising_moves:
    goodSufficesList = @[]  # empty list (sequence)
    for d5 in neighbors(d4):
      if tried_d5 >= 2*Max_Breadth_1:
        break find_promising_moves
      if (d5 == d4_succ) or (d5 == d4_pred):
        continue      
      if (d5 == d1) or (d5 == d2):
        continue

      G2 = G2a - distance(d4, d5)
   
      # choose d6
      case tourOrderPrev
      of TO_ADBC:
        d6 = t_pred(d5)
        if inOrder(d3, d5, c1, true):
          tourOrder = TO_AxdECB     # AdECB
        elif inOrder(c4, d5, d4, true):
          tourOrder = TO_AxcxeDB    # AceDB
        elif inOrder(d2, d5, c3, true):
          tourOrder = TO_AxbxdxeC_1 # AbdeC
        else:
          tourOrder = TO_AxbEDC_1   # AbEDC
      of TO_AxcxdB:
        if inOrder(d3, d5, c1, true):
          d6 = t_succ(d5)
          tourOrder = TO_AECxdB     # AECdB
        elif inOrder(c4, d5, d4, true):
          d6 = t_succ(d5)
          tourOrder = TO_ADxcxeB    # ADceB
        elif inOrder(d2, d5, c3, true):
          d6 = t_pred(d5)
          tourOrder = TO_AxbEDC_2   # AbEDC
        else:
          d6 = t_pred(d5)
          tourOrder = TO_AxbxdxeC_2 # AbdeC
      else:
        discard
      #endcase
      
      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)

      goodSuffix = Suffix(c2iplus1: d5, c2iplus2: d6,
                          tourOrder: tourOrder, Ga: G3a)
      goodSufficesList.add(goodSuffix)
      tried_d5 = tried_d5 + 1
    #end_loop for d5
  #end_block find_promising_moves  

  block evaluate_promising_moves:
    if len(goodSufficesList) == 0:
      break evaluate_promising_moves
    SortSufficesByGain(goodSufficesList)
    breadth = min(len(goodSufficesList), Max_Breadth_1)
    for mve in 0 .. breadth-1:
      goodSuffix = goodSufficesList[mve]
      d5 = goodSuffix.c2iplus1
      d6 = goodSuffix.c2iplus2
      G3a = goodSuffix.Ga
      tourOrder = goodSuffix.tourOrder
      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,
                          tourOrder)
        tourLen = tourLen - gainFromCloseUp
        Set_DLB_off(DontLook, [c1, c2, c3, c4,
                               d1, d2, d3, d4, d5, d6])
        break evaluate_promising_moves
  #end_block evaluate_promising_moves
  result = improved

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 TO_ADxcxeB, TO_AECxdB,
    # c12-d12-c34-d56-d43, c12-d12-c34-d43-d56
    TO_AxbxdxeC_2, TO_AxbEDC_2:
    # 12-d65-d12-c34d-43, c12-d12-d65-c34d-43
    Exchange_Links(d1, d2, d4, d3)
    Exchange_Links(c1, c2, c4, c3) 
    Exchange_Links(d1, d4, d6, d5)
  else:
    discard
  #end_case