LK – subsequent 3-opt move

Subsequent move in Lin-Kernighan optimization does not need to be 2-opt as in original algorithm. We can use 3-opt as well, or any other sequential type of move:

proc LK_Subsequent3Move(c1, c2: City_Number;
                        G1a: var Length_Gain;
                        cLast: var City_Number): bool =
  # cLast is set to last city in sequential move when promising move
  # has been found and applied
  var
    improved: bool
    c3, c4, c5, c6: City_Number
    c2_pred, c2_succ: City_Number
    c3_pred, c3_succ: City_Number
    c4_pred, c4_succ: City_Number
    c5_pred, c5_succ: City_Number
    fwd: bool
    c4_A, c4_B:  City_Number
    G1, Ga, G2a, G2, G3a, gainFromCloseUp: Length_Gain
    tried_c3, tried_c5: int
    tourOrder2, tourOrder3: int
    c3_BG, c4_BG, c5_BG, c6_BG: City_Number
    Ga_BG: Length_Gain
    tourOrder_BG: int

  improved = false
  fwd = (c2 == t_succ(c1))
  c2_succ = t_succ(c2)
  c2_pred = t_pred(c2)

  block find_promising_moves:
    tried_c3 = 0
    Ga_BG = 0
    for c3 in neighbors(c2):
      if tried_c3 >= Max_Breadth_S:
        break
      if (c3 == c2_succ) or (c3 == c2_pred):
        continue
      if isLinkAdded(c2, c3):
        continue
      G1 = G1a - distance(c2, c3)
      if G1 <= 0:
        break
      c3_succ = t_succ(c3)
      c3_pred = t_pred(c3)
      if fwd:
        c4_A = t_pred(c3)
        c4_B = t_succ(c3)
      else:
        c4_A = t_succ(c3)
        c4_B = t_pred(c3)
      for c4 in [c4_A, c4_B]:
        if isLinkAdded(c4, c1):
          continue
        tried_c3 = tried_c3 + 1
        G2a = G1 + distance(c3, c4)
        if (c4 == c4_B):
          tourOrder2 = TO_1234
        else:
          tourOrder2 = TO_1243
          gainFromCloseUp = G2a - distance(c4, c1)
          if gainFromCloseUp > 0:  # improving move found
            improved = true
            Make_2opt_Move(c1, c2, c3, c4)
            tourLen = tourLen - gainFromCloseUp
            G1a = G2a
            cLast = c4
            # don't look bits for c1, c2 should be set at previous level
            Set_DLB_off(DontLook, [c3, c4])
            break find_promising_moves
        # 3-opt
        c4_succ = t_succ(c4)
        c4_pred = t_pred(c4)
        tried_c5 = 0
        for c5 in neighbors(c4):
          if tried_c5 >= Max_Breadth_S:
            break
          if (c5 == c4_succ) or (c5 == c4_pred):
            continue
          if isLinkAdded(c4, c5):
            continue
          G2 = G2a - distance(c4, c5)
          if G2  <= 0:
            break
          c5_succ = t_succ(c5)
          c5_pred = t_pred(c5)
          for c6 in [c5_succ, c5_pred]:
            if (c6 == c1):
              continue
            if isLinkAdded(c6, c1):
              continue
            tourOrder3 = TO_00
            case tourOrder2
            of TO_1234:
              if inOrder(c2, c5, c3, fwd):
                if inOrder(c2, c6, c5, fwd):
                  tourOrder3 = TO_126534
                else:
                  tourOrder3 = TO_125634
            of TO_1243:
              if inOrder(c2, c5, c4, fwd):
                if inOrder(c2, c6, c5, fwd):
                  continue
                else:
                  tourOrder3 = TO_125643
              else:
                if inOrder(c3, c6, c5, fwd):
                  tourOrder3 = TO_124365
            else:
              continue
            #end_case tourOrder2
            if tourOrder3 == TO_00:
              continue
            tried_c5 = tried_c5 + 1
            G3a = G2 + distance(c5, c6)
            gainFromCloseUp = G3a - distance(c6, c1)
            if gainFromCloseUp > 0:
              improved = true
              Make_3opt_Move(c1, c2, c3, c4, c5, c6, tourOrder3)
              tourLen = tourLen - gainFromCloseUp
              G1a = G3a
              cLast = c6
              Set_DLB_off(DontLook, [c3, c4, c5, c6])
              break find_promising_moves
            if G3a > Ga_BG:
              Ga_BG = G3a
              c3_BG  = c3
              c4_BG  = c4
              c5_BG  = c5
              c6_BG  = c6
              tourOrder_BG = tourOrder3
    #end loop for c3
  #end block find_promising_moves

  block make_best_3move:
    if improved:
      break make_best_3move
    if Ga_BG <= 0:
      break make_best_3move
    Make_3opt_Move(c1, c2,
                   c3_BG, c4_BG, c5_BG, c6_BG, tourOrder_BG)
    G1a = Ga_BG
    cLast = c6_BG
    AddtoLinksAdded(c3_BG, c4_BG)
    AddtoLinksAdded(c5_BG, c6_BG)
    Set_DLB_off(DontLook, [c3_BG, c4_BG, c5_BG, c6_BG])
  #end block make_best_3move

  result = improved

Beware

Note that while 2-opt move is just single exchange of two pairs of links, 3-opt move constists of two or three such exchanges. Therefore we should modify the way we count levels for subsequent moves (needed to restrict their number). Instead of incrementing local SubseqLvl variable inside LK_5Move or LK_scheme, we should make it a global variable and increment it while actually performing the basic tour transformation, that is: inside Exchange_Links.