LK – subsequent 5-opt move

proc LK_Subsequent5Move(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, c7, c8, c9, c10: City_Number
    c2_pred, c2_succ, c3_pred, c3_succ: City_Number
    c4_pred, c4_succ, c5_pred, c5_succ: City_Number
    c6_pred, c6_succ, c7_pred, c7_succ: City_Number
    c8_pred, c8_succ, c9_pred, c9_succ: City_Number
    fwd: bool
    c4_A, c4_B:  City_Number
    G1, Ga, G2a, G2, G3a, G3, G4a, G4, G5a: Length_Gain
    gainFromCloseUp: Length_Gain
    tried_c3, tried_c5, tried_c7, tried_c9: int
    tourOrder_2, tourOrder_3, tourOrder_4, tourOrder_5: int
    Ga_G: Length_Gain
    tourOrder_G: int
    c3_G, c4_G, c5_G, c6_G: City_Number
    c7_G, c8_G, c9_G, c10_G: City_Number
    moveType: int

  improved = false
  fwd = (c2 == t_succ(c1))

  block find_promising_moves:
    Ga_G = 0
    c2_succ = t_succ(c2)
    c2_pred = t_pred(c2)
    tried_c3 = 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 = c3_pred
        c4_B = c3_succ
      else:
        c4_A = c3_succ
        c4_B = c3_pred
      for c4 in [c4_A, c4_B]:
        if isLinkAdded(c4, c1):
          continue
        tried_c3 = tried_c3 + 1
        G2a = G1 + distance(c3, c4)
        if fwd and (c4 == c3_succ)  or
           not fwd and (c4 == c3_pred):
          tourOrder_2 = TO_1234
        else:
          tourOrder_2 = 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 isLinkAdded(c6, c1):
              continue
            tourOrder_3 = Which_TO_3of5(tourOrder_2,
                                        c1, c2, c3, c4, c5, c6,
                                        fwd)
            case tourOrder_3
            of TO_00:
              continue
            of TO_125634, TO_126534, TO_125643, TO_124365:
              moveType = move_type_3  # pure 3-opt move
            else:
              moveType = move_type_0
            tried_c5 = tried_c5 + 1
            G3a = G2 + distance(c5, c6)
            if moveType != move_type_0:
              gainFromCloseUp = G3a - distance(c6, c1)              
              if gainFromCloseUp > 0:  # improving move found
                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

            # 4-opt
            c6_succ = t_succ(c6)
            c6_pred = t_pred(c6)
            tried_c7 = 0
            for c7 in neighbors(c6):
              if tried_c7 >= Max_Breadth_S:
                break
              if (c7 == c6_succ) or (c7 == c6_pred):
                continue
              if (c6 == c2) and (c7 == c3) or
                 (c6 == c3) and (c7 == c2):
                continue
              if isLinkAdded(c6, c7):
                continue
              G3 = G3a - distance(c6, c7)
              if G3  <= 0:
                break
              c7_succ = t_succ(c7)
              c7_pred = t_pred(c7)
              for c8 in [c7_succ, c7_pred]:
                if (c7 == c1) and (c8 == c2) or
                   (c7 == c2) and (c8 == c1):
                  continue
                if (c7 == c3) and (c8 == c4) or
                   (c7 == c4) and (c8 == c3):
                  continue
                if isLinkAdded(c8, c1):
                  continue
                tourOrder_4 = Which_TO_4of5(tourOrder_3,
                                            c1, c2, c3, c4,
                                            c5, c6, c7, c8,
                                            fwd)
                if tourOrder_4 == TO_00:
                  continue
                if (c8 == c1):
                  # c8 should not be c1 when we close the tour
                  moveType = move_type_0
                else:
                  case tourOrder_4
                  of TO_12786534, TO_12657834, TO_12653487, TO_12875634,
                     TO_12568734, TO_12563487, TO_12785643, TO_12568743,
                     TO_12564387, TO_12874365, TO_12437865, TO_12436587,
                     TO_12783465, TO_12873465, TO_12658743, TO_12657843,
                     TO_12874356, TO_12784356, TO_12437856, TO_12438756:
                      moveType = move_type_4
                  else:
                      moveType = move_type_0
                #end_if ... set moveType
                tried_c7 = tried_c7 + 1
                G4a = G3 + distance(c7, c8)
                if moveType != move_type_0: # connecting move
                  gainFromCloseUp = G4a - distance(c8, c1)                  
                  if gainFromCloseUp > 0:  # improving move found
                    improved = true
                    Make_4opt_Move(c1, c2, c3, c4, c5, c6, c7, c8,
                                   tourOrder4)
                    tourLen = tourLen - gainFromCloseUp
                    G1a = G4a
                    cLast = c8
                    Set_DLB_off(DontLook, [c3, c4, c5, c6, c7, c8])
                    break find_promising_moves

                # 5-opt
                c8_succ = t_succ(c8)
                c8_pred = t_pred(c8)
                tried_c9 = 0
                for c9 in neighbors(c8):
                  if tried_c9 >= Max_Breadth_S:
                    break
                  if (c9 == c8_succ) or (c9 == c8_pred):
                    continue
                  if (c8 == c2) and (c9 == c3) or
                     (c8 == c3) and (c9 == c2):
                    continue
                  if (c8 == c4) and (c9 == c5) or
                     (c8 == c5) and (c9 == c4):
                    continue
                  if (c9 == c1):
                    continue
                  if isLinkAdded(c8, c9):
                    continue
                  G4 = G4a - distance(c8, c9)
                  if G4  <= 0:
                    break
                  c9_succ = t_succ(c9)
                  c9_pred = t_pred(c9)
                  for c10 in [c9_succ, c9_pred]:
                    if (c9 == c3) and (c10 == c4) or
                       (c9 == c4) and (c10 == c3):
                      continue
                    if (c9 == c5) and (c10 == c6) or
                       (c9 == c6) and (c10 == c5):
                      continue
                    if (c10 == c1):
                      continue
                    if isLinkAdded(c10, c1):
                      continue
                    tourOrder_5 = Which_TO_5of5(tourOrder_4,
                                                c1, c2, c3, c4,
                                                c5, c6, c7, c8,
                                                c9, c10,
                                                fwd)
                    case tourOrder_5
                    of TO_00:
                      #moveType = move_type_0
                      continue
                    else:
                      moveType = move_type_5
                    #end_case ... set moveType
                    # if moveType != move_type_0:
                    tried_c9 = tried_c9 + 1
                    G5a = G4 + distance(c9, c10)
                    gainFromCloseUp = G5a - distance(c10, c1)
                    if gainFromCloseUp > 0:  # improving move found
                      improved = true
                      Make_5opt_Move(c1, c2, c3, c4, c5,
                                     c6, c7, c8, c9, c10,
                                     tourOrder5)
                      tourLen = tourLen - gainFromCloseUp
                      G1a = G5a
                      cLast = c10
                      Set_DLB_off(DontLook,
                                  [c3, c4, c5, c6, c7, c8, c9, c10])
                      break find_promising_moves

                    if G5a > Ga_G:
                      Ga_G = G5a
                      (c3_G, c4_G, c5_G, c6_G, c7_G, c8_G, c9_G, c10_G) =
                          (c3, c4, c5, c6, c7, c8, c9, c10)
                      tourOrder_G = tourOrder_5
                    #end_if G3a > Ga_G:
                  #end loop for c10
                #end loop for c9
              #end loop for c8
            #end loop for c7
          #end loop for c6
        #end loop for c5
      #end loop for c4
    #end loop for c3
  #end block find_promising_moves

  block make_best_gain_move:
    if improved:
      break make_best_gain_move
    if Ga_G <= 0:
      break make_best_gain_move
    Make_5opt_Move(c1, c2,
                   c3_G, c4_G, c5_G, c6_G,
                   c7_G, c8_G, c9_G, c10_G,
                   tourOrder_G)
    G1a = Ga_G
    cLast = c10_G
    AddtoLinksAdded(c3_G, c4_G)
    AddtoLinksAdded(c5_G, c6_G)
    AddtoLinksAdded(c7_G, c8_G)
    AddtoLinksAdded(c9_G, c10_G)
    Set_DLB_off(DontLook, [c3_G, c4_G, c5_G, c6_G,
                           c7_G, c8_G, c9_G, c10_G])
  #end block make_best_gain_move

  result = improved

Auxiliary procs to make the code more clear:

proc Which_TO_3of5(tourOrder_2: int;
                   c1, c2, c3, c4, c5, c6: City_Number;
                   fwd: bool): int =
  var
    tourOrder: int

  tourOrder  = TO_00  # means not valid move
  case tourOrder_2

  of TO_1234:
    if inOrder(c2, c5, c3, fwd):  # 12-(5,6)-34
       if (c6 == c1):
          # c2!=c3, so c5==c2 and (c6,c5)==(c1,c2)
          discard
       else:
          if inOrder(c2, c6, c5, fwd):
             tourOrder = TO_126534
          else:
             tourOrder = TO_125634
    else:                         # 12-34-(5,6)
       if (c6 == c2):
          # c2!=c3, so c5==c1 and (c5,c6)==(c1,c2)
          discard
       else:
          if inOrder(c4, c5, c6, fwd):
             tourOrder = TO_123456 # disconnecting, but starts 5-opt
          else:
             tourOrder = TO_123465 # disconnecting, but starts 4-opt

  of TO_1243:
    if inOrder(c2, c5, c4, fwd):  # 12-(5,6)-43
       if inOrder(c2, c6, c5, fwd):
          # c1 < c2 <= c6 < c5 < c4
          # therefore (c6,c5)!=(c1,c2)
          tourOrder = TO_126543    # disconnecting, but starts 4-opt
       else:
          if (c5 == c1) and (c6 == c2) or
             (c5 == c2) and (c6 == c1):
             # (c5,c6) == (c1,c2)
             discard
          else:
             tourOrder = TO_125643
    else:                         # 12-43-(5,6)
       if inOrder(c3, c6, c5, fwd):
          # c3 <= c6 < c5 <= c1 < c2
          # therefore (c6,c5)!=(c1,c2)
          tourOrder = TO_124365
       else:
          if (c5 == c1) and (c6 == c2) or
             (c5 == c2) and (c6 == c1):
             # (c5,c6) == (c1,c2)
             discard
          else:
             tourOrder = TO_124356 # disconnecting, but starts 4-opt

  else: # of tourOrder_2
    tourOrder  = TO_00
  #end of testing variants

  result = tourOrder

proc Which_TO_4of5(tourOrder_3: int;
                   c1, c2, c3, c4, c5, c6, c7, c8: City_Number;
                   fwd: bool): int =
  var
    tourOrder: int

  tourOrder  = TO_00  # means not valid move
  case tourOrder_3

  of TO_126534:
    if inOrder(c4, c7, c1, fwd):
       if inOrder(c4, c7, c8, fwd):
          tourOrder = TO_12653478 # disconnecting, starts 5-opt
       else:
          tourOrder = TO_12653487
    elif inOrder(c5, c7, c3, fwd):
       if inOrder(c5, c7, c8, fwd):
          tourOrder = TO_12657834
       else:
          tourOrder = TO_12658734 # disconnecting, starts 5-opt
    else: #  inOrder(c2, c7, c6, fwd):
       if inOrder(c2, c7, c8, fwd):
          tourOrder = TO_12786534
       else:
          tourOrder = TO_12876534 # disconnecting, starts 5-opt

  of TO_125634:
    if inOrder(c4, c7, c1, fwd):
       if inOrder(c4, c7, c8, fwd):
          tourOrder = TO_12563478 # disconnecting, starts 5-opt
       else:
          tourOrder = TO_12563487
    elif inOrder(c6, c7, c3, fwd):
       if inOrder(c6, c7, c8, fwd):
          tourOrder = TO_12567834 # disconnecting, starts 5-opt
       else:
          tourOrder = TO_12568734
    else: #  inOrder(c2, c7, c5, fwd):
       if inOrder(c2, c7, c8, fwd):
          tourOrder = TO_12785634 # disconnecting, starts 5-opt
       else:
          tourOrder = TO_12875634

  of TO_123456:
    if inOrder(c6, c7, c1, fwd):
      # TO_12345678 and TO_12345687 are not valid 4-opt moves
      # and they do not lead to valid 5-opt moves
      discard
    elif inOrder(c4, c7, c5, fwd):
       if inOrder(c4, c7, c8, fwd):
          tourOrder = TO_12347856 # disconnecting, starts 5-opt
       else:
          tourOrder = TO_12348756 # disconnecting, starts 5-opt
    else: #  inOrder(c2, c7, c3, fwd):
       if inOrder(c2, c7, c8, fwd):
          tourOrder = TO_12783456 # disconnecting, starts 5-opt
       else:
          tourOrder = TO_12873456 # disconnecting, starts 5-opt

  of TO_125643:
    if inOrder(c3, c7, c1, fwd):
       if inOrder(c3, c7, c8, fwd):
          tourOrder = TO_12564378 # disconnecting, starts 5-opt
       else:
          tourOrder = TO_12564387
    elif inOrder(c6, c7, c4, fwd):
       if inOrder(c6, c7, c8, fwd):
          tourOrder = TO_12567843 # disconnecting, starts 5-opt
       else:
          tourOrder = TO_12568743
    else: #  inOrder(c2, c7, c5, fwd):
       if inOrder(c2, c7, c8, fwd):
          tourOrder = TO_12785643
       else:
          tourOrder = TO_12875643 # disconnecting, starts 5-opt

  of TO_124365:
    if inOrder(c5, c7, c1, fwd):
       if inOrder(c5, c7, c8, fwd):
          tourOrder = TO_12436578 # disconnecting, starts 5-opt
       else:
          tourOrder = TO_12436587
    elif inOrder(c3, c7, c6, fwd):
       if inOrder(c3, c7, c8, fwd):
          tourOrder = TO_12437865
       else:
          tourOrder = TO_12438765 # disconnecting, starts 5-opt
    else: #  inOrder(c2, c7, c4, fwd):
       if inOrder(c2, c7, c8, fwd):
          tourOrder = TO_12784365 # disconnecting, starts 5-opt
       else:
          tourOrder = TO_12874365

  of TO_123465:
    if inOrder(c5, c7, c1, fwd):
       if inOrder(c6, c7, c8, fwd):
          # TO_12346578 is not valid 4-opt move
          # and it does not lead to valid 5-opt move
          discard
       else:
          tourOrder = TO_12346587 # disconnecting, starts 5-opt
    elif inOrder(c4, c7, c6, fwd):
       if inOrder(c4, c7, c8, fwd):
          tourOrder = TO_12347865 # disconnecting, starts 5-opt
       else:
          tourOrder = TO_12348765 # disconnecting, starts 5-opt
    else: #  inOrder(c2, c7, c3, fwd):
       if inOrder(c2, c7, c8, fwd):
          tourOrder = TO_12783465
       else:
          tourOrder = TO_12873465

  of TO_126543:
    if inOrder(c3, c7, c1, fwd):
       if inOrder(c3, c7, c8, fwd):
          # TO_12654378 is not valid 4-opt move
          # and it does not lead to valid 5-opt move
          discard
       else:
          tourOrder = TO_12654387 # disconnecting, starts 5-opt
    elif inOrder(c5, c7, c4, fwd):
       if inOrder(c5, c7, c8, fwd):
          tourOrder = TO_12657843
       else:
          tourOrder = TO_12658743
    else: #  inOrder(c2, c7, c6, fwd):
       if inOrder(c2, c7, c8, fwd):
          tourOrder = TO_12786543 # disconnecting, starts 5-opt
       else:
          tourOrder = TO_12876543 # disconnecting, starts 5-opt

  of TO_124356:
    if inOrder(c6, c7, c1, fwd):
       if inOrder(c6, c7, c8, fwd):
          # TO_12435678 is not valid 4-opt move
          # and it does not lead to valid 5-opt move
          discard
       else:
          tourOrder = TO_12435687 # disconnecting, starts 5-opt
    elif inOrder(c3, c7, c5, fwd):
       if inOrder(c3, c7, c8, fwd):
          tourOrder = TO_12437856
       else:
          tourOrder = TO_12438756
    else: #  inOrder(c2, c7, c4, fwd):
       if inOrder(c2, c7, c8, fwd):
          tourOrder = TO_12784356
       else:
          tourOrder = TO_12874356

  else: # of tourOrder_3
    tourOrder  = TO_00
  #end of testing variants

  result = tourOrder

proc Which_TO_5of5(tourOrder_4: int;
                   c1, c2, c3, c4, c5, c6, c7, c8, c9, c10: City_Number;
                   fwd: bool): int =
  var
    tourOrder: int

  tourOrder  = TO_00  # means not valid move
  case tourOrder_4

  of TO_12347856:
    if inOrder(c2, c9, c3, fwd):
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A347856
       else:
          tourOrder = TO_12A9347856

  of TO_12348756:
    if inOrder(c2, c9, c3, fwd):
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A348756
       else:
          tourOrder = TO_12A9348756

  of TO_12783456:
    if inOrder(c4, c9, c5, fwd):
       if inOrder(c4, c9, c10, fwd):
          tourOrder = TO_1278349A56
       else:
          tourOrder = TO_127834A956

  of TO_12873456:
    if inOrder(c4, c9, c5, fwd):
       if inOrder(c4, c9, c10, fwd):
          tourOrder = TO_1287349A56
       else:
          tourOrder = TO_128734A956

  of TO_12346587:
    if inOrder(c2, c9, c3, fwd):
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A346587
       else:
          tourOrder = TO_12A9346587

  of TO_12347865:
    if inOrder(c2, c9, c3, fwd):
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A347865
       else:
          tourOrder = TO_12A9347865

  of TO_12783465:
    if inOrder(c5, c9, c1, fwd):
       if inOrder(c5, c10, c9, fwd):
          tourOrder = TO_12783465A9
    elif inOrder(c4, c9, c6, fwd):
       if inOrder(c4, c9, c10, fwd):
          tourOrder = TO_1278349A65
    elif inOrder(c8, c9, c3, fwd):
       if inOrder(c8, c10, c9, fwd):
          tourOrder = TO_1278A93465
    else: #  inOrder(c2, c9, c7, fwd)
       if inOrder(c2, c10, c9, fwd):
          tourOrder = TO_12A9783465

  of TO_12873465:
    if inOrder(c5, c9, c1, fwd):
       if inOrder(c5, c10, c9, fwd):
          tourOrder = TO_12873465A9
    elif inOrder(c4, c9, c6, fwd):
       if inOrder(c4, c9, c10, fwd):
          tourOrder = TO_1287349A65
    elif inOrder(c7, c9, c3, fwd):
       if inOrder(c7, c9, c10, fwd):
          tourOrder = TO_12879A3465
    else: #  inOrder(c2, c9, c8, fwd)
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A873465

  of TO_12563478:
    if inOrder(c4, c9, c7, fwd):
       if inOrder(c4, c9, c10, fwd):
          tourOrder = TO_1256349A78
       else:
          tourOrder = TO_125634A978
    elif inOrder(c6, c9, c3, fwd):
       if inOrder(c6, c9, c10, fwd):
          tourOrder = TO_12569A3478
       else:
          tourOrder = TO_1256A93478
    elif inOrder(c2, c9, c5, fwd):
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A563478
       else:
          tourOrder = TO_12A9563478

  of TO_12563487:
    if inOrder(c7, c9, c1, fwd):
       if inOrder(c7, c10, c9, fwd):
          tourOrder = TO_12563487A9
    elif inOrder(c4, c9, c8, fwd):
       if inOrder(c4, c9, c10, fwd):
          tourOrder = TO_1256349A87
    elif inOrder(c6, c9, c3, fwd):
       if inOrder(c6, c9, c10, fwd):
          tourOrder = TO_12569A3487
    else: #  inOrder(c2, c9, c5, fwd)
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A563487

  of TO_12785634:
    if inOrder(c6, c9, c3, fwd):
       if inOrder(c6, c9, c10, fwd):
          tourOrder = TO_1278569A34
       else:
          tourOrder = TO_127856A934
    elif inOrder(c2, c9, c7, fwd):
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A785634
       else:
          tourOrder = TO_12A9785634

  of TO_12875634:
    if inOrder(c4, c9, c1, fwd):
       if inOrder(c4, c10, c9, fwd):
          tourOrder = TO_12875634A9
    elif inOrder(c6, c9, c3, fwd):
       if inOrder(c6, c9, c10, fwd):
          tourOrder = TO_1287569A34
    elif inOrder(c7, c9, c5, fwd):
       if inOrder(c7, c10, c9, fwd):
          tourOrder = TO_1287A95634
    else: #  inOrder(c2, c9, c8, fwd)
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A875634

  of TO_12567834:
    if inOrder(c6, c9, c7, fwd):
       if inOrder(c6, c9, c10, fwd):
          tourOrder = TO_12569A7834
       else:
          tourOrder = TO_1256A97834

  of TO_12568734:
    if inOrder(c4, c9, c1, fwd):
       if inOrder(c4, c10, c9, fwd):
          tourOrder = TO_12568734A9
    elif inOrder(c7, c9, c3, fwd):
       if inOrder(c7, c10, c9, fwd):
          tourOrder = TO_125687A934
    elif inOrder(c6, c9, c8, fwd):
       if inOrder(c6, c9, c10, fwd):
          tourOrder = TO_12569A8734
    else: #  inOrder(c2, c9, c5, fwd)
       if inOrder(c2, c10, c9, fwd):
          tourOrder = TO_12A9568734

  of TO_12653478:
    if inOrder(c4, c9, c7, fwd):
       if inOrder(c4, c9, c10, fwd):
          tourOrder = TO_1265349A78
       else:
          tourOrder = TO_126534A978
    elif inOrder(c5, c9, c3, fwd):
       if inOrder(c5, c9, c10, fwd):
          tourOrder = TO_12659A3478
       else:
          tourOrder = TO_1265A93478
    elif inOrder(c2, c9, c6, fwd):
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A653478
       else:
          tourOrder = TO_12A9653478

  of TO_12653487:
    if inOrder(c7, c9, c1, fwd):
       if inOrder(c7, c10, c9, fwd):
          tourOrder = TO_12653487A9
    elif inOrder(c4, c9, c8, fwd):
       if inOrder(c4, c9, c10, fwd):
          tourOrder = TO_1265349A87
    elif inOrder(c5, c9, c3, fwd):
       if inOrder(c5, c10, c9, fwd):
          tourOrder = TO_1265A93487
    else: #  inOrder(c2, c9, c6, fwd)
       if inOrder(c2, c10, c9, fwd):
          tourOrder = TO_12A9653487

  of TO_12657834:
    if inOrder(c4, c9, c1, fwd):
       if inOrder(c4, c10, c9, fwd):
          tourOrder = TO_12657834A9
    elif inOrder(c8, c9, c3, fwd):
       if inOrder(c8, c10, c9, fwd):
          tourOrder = TO_126578A934
    elif inOrder(c5, c9, c7, fwd):
       if inOrder(c5, c9, c10, fwd):
          tourOrder = TO_12659A7834
    else: #  inOrder(c2, c9, c6, fwd)
       if inOrder(c2, c10, c9, fwd):
          tourOrder = TO_12A9657834

  of TO_12658734:
    if inOrder(c7, c9, c3, fwd):
       if inOrder(c7, c9, c10, fwd):
          tourOrder = TO_1265879A34
       else:
          tourOrder = TO_126587A934
    elif inOrder(c2, c9, c6, fwd):
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A658734
       else:
          tourOrder = TO_12A9658734

  of TO_12786534:
    if inOrder(c4, c9, c1, fwd):
       if inOrder(c4, c10, c9, fwd):
          tourOrder = TO_12786534A9
    elif inOrder(c5, c9, c3, fwd):
       if inOrder(c5, c9, c10, fwd):
          tourOrder = TO_1278659A34
    elif inOrder(c8, c9, c6, fwd):
       if inOrder(c8, c10, c9, fwd):
          tourOrder = TO_1278A96534
    else: #  inOrder(c2, c9, c7, fwd)
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A786534

  of TO_12876534:
    if inOrder(c7, c9, c6, fwd):
       if inOrder(c7, c9, c10, fwd):
          tourOrder = TO_12879A6534
       else:
          tourOrder = TO_1287A96534

  of TO_12435687:
    if inOrder(c3, c9, c5, fwd):
       if inOrder(c3, c9, c10, fwd):
          tourOrder = TO_12439A5687
       else:
          tourOrder = TO_1243A95687
    elif inOrder(c2, c9, c4, fwd):
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A435687
       else:
          tourOrder = TO_12A9435687

  of TO_12437856:
    if inOrder(c6, c9, c1, fwd):
       if inOrder(c6, c10, c9, fwd):
          tourOrder = TO_12437856A9
    elif inOrder(c8, c9, c5, fwd):
       if inOrder(c8, c10, c9, fwd):
          tourOrder = TO_124378A956
    elif inOrder(c3, c9, c7, fwd):
       if inOrder(c3, c10, c9, fwd):
          tourOrder = TO_1243A97856
    else: #  inOrder(c2, c9, c4, fwd)
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A437856

  of TO_12438756:
    if inOrder(c6, c9, c1, fwd):
       if inOrder(c6, c10, c9, fwd):
          tourOrder = TO_12438756A9
    elif inOrder(c7, c9, c5, fwd):
       if inOrder(c7, c9, c10, fwd):
          tourOrder = TO_1243879A56
    elif inOrder(c3, c9, c8, fwd):
       if inOrder(c3, c9, c10, fwd):
          tourOrder = TO_12439A8756
    else: #  inOrder(c2, c9, c4, fwd)
       if inOrder(c2, c10, c9, fwd):
          tourOrder = TO_12A9438756

  of TO_12784356:
    if inOrder(c6, c9, c1, fwd):
       if inOrder(c6, c10, c9, fwd):
          tourOrder = TO_12784356A9
    elif inOrder(c3, c9, c5, fwd):
       if inOrder(c3, c9, c10, fwd):
          tourOrder = TO_1278439A56
    elif inOrder(c8, c9, c4, fwd):
       if inOrder(c8, c10, c9, fwd):
          tourOrder = TO_1278A94356
    else: #  inOrder(c2, c9, c7, fwd)
       if inOrder(c2, c10, c9, fwd):
          tourOrder = TO_12A9784356

  of TO_12874356:
    if inOrder(c6, c9, c1, fwd):
       if inOrder(c6, c10, c9, fwd):
          tourOrder = TO_12874356A9
    elif inOrder(c3, c9, c5, fwd):
       if inOrder(c3, c10, c9, fwd):
          tourOrder = TO_128743A956
    elif inOrder(c7, c9, c4, fwd):
       if inOrder(c7, c9, c10, fwd):
          tourOrder = TO_12879A4356
    else: #  inOrder(c2, c9, c8, fwd)
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A874356

  of TO_12436578:
    if inOrder(c5, c9, c7, fwd):
       if inOrder(c5, c9, c10, fwd):
          tourOrder = TO_1243659A78
       else:
          tourOrder = TO_124365A978
    elif inOrder(c3, c9, c6, fwd):
       if inOrder(c3, c9, c10, fwd):
          tourOrder = TO_12439A6578
       else:
          tourOrder = TO_1243A96578
    elif inOrder(c2, c9, c4, fwd):
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A436578
       else:
          tourOrder = TO_12A9436578

  of TO_12436587:
    if inOrder(c7, c9, c1, fwd):
       if inOrder(c7, c10, c9, fwd):
          tourOrder = TO_12436587A9
    elif inOrder(c5, c9, c8, fwd):
       if inOrder(c5, c9, c10, fwd):
          tourOrder = TO_1243659A87
    elif inOrder(c3, c9, c6, fwd):
       if inOrder(c3, c10, c9, fwd):
          tourOrder = TO_1243A96587
    else: #  inOrder(c2, c9, c4, fwd)
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A436587

  of TO_12437865:
    if inOrder(c5, c9, c1, fwd):
       if inOrder(c5, c10, c9, fwd):
          tourOrder = TO_12437865A9
    elif inOrder(c8, c9, c6, fwd):
       if inOrder(c8, c10, c9, fwd):
          tourOrder = TO_124378A965
    elif inOrder(c3, c9, c7, fwd):
       if inOrder(c3, c9, c10, fwd):
          tourOrder = TO_12439A7865
    else: #  inOrder(c2, c9, c4, fwd)
       if inOrder(c2, c10, c9, fwd):
          tourOrder = TO_12A9437865

  of TO_12438765:
    if inOrder(c7, c9, c6, fwd):
       if inOrder(c7, c9, c10, fwd):
          tourOrder = TO_1243879A65
       else:
          tourOrder = TO_124387A965

  of TO_12784365:
    if inOrder(c3, c9, c6, fwd):
       if inOrder(c3, c9, c10, fwd):
          tourOrder = TO_1278439A65
       else:
          tourOrder = TO_127843A965
    elif inOrder(c2, c9, c7, fwd):
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A784365
       else:
          tourOrder = TO_12A9784365

  of TO_12874365:
    if inOrder(c5, c9, c1, fwd):
       if inOrder(c5, c10, c9, fwd):
          tourOrder = TO_12874365A9
    elif inOrder(c3, c9, c6, fwd):
       if inOrder(c3, c10, c9, fwd):
          tourOrder = TO_128743A965
    elif inOrder(c7, c9, c4, fwd):
       if inOrder(c7, c10, c9, fwd):
          tourOrder = TO_1287A94365
    else: #  inOrder(c2, c9, c8, fwd)
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A874365

  of TO_12564378:
    if inOrder(c3, c9, c7, fwd):
       if inOrder(c3, c9, c10, fwd):
          tourOrder = TO_1256439A78
       else:
          tourOrder = TO_125643A978
    elif inOrder(c6, c9, c4, fwd):
       if inOrder(c6, c9, c10, fwd):
          tourOrder = TO_12569A4378
       else:
          tourOrder = TO_1256A94378
    elif inOrder(c2, c9, c5, fwd):
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A564378
       else:
          tourOrder = TO_12A9564378

  of TO_12564387:
    if inOrder(c7, c9, c1, fwd):
       if inOrder(c7, c10, c9, fwd):
          tourOrder = TO_12564387A9
    elif inOrder(c3, c9, c8, fwd):
       if inOrder(c3, c9, c10, fwd):
          tourOrder = TO_1256439A87
    elif inOrder(c6, c9, c4, fwd):
       if inOrder(c6, c9, c10, fwd):
          tourOrder = TO_12569A4387
    else: #  inOrder(c2, c9, c5, fwd)
       if inOrder(c2, c10, c9, fwd):
          tourOrder = TO_12A9564387

  of TO_12567843:
    if inOrder(c6, c9, c7, fwd):
       if inOrder(c6, c9, c10, fwd):
          tourOrder = TO_12569A7843
       else:
          tourOrder = TO_1256A97843

  of TO_12568743:
    if inOrder(c3, c9, c1, fwd):
       if inOrder(c3, c10, c9, fwd):
          tourOrder = TO_12568743A9
    elif inOrder(c7, c9, c4, fwd):
       if inOrder(c7, c10, c9, fwd):
          tourOrder = TO_125687A943
    elif inOrder(c6, c9, c8, fwd):
       if inOrder(c6, c9, c10, fwd):
          tourOrder = TO_12569A8743
    else: #  inOrder(c2, c9, c5, fwd)
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A568743

  of TO_12785643:
    if inOrder(c3, c9, c1, fwd):
       if inOrder(c3, c10, c9, fwd):
          tourOrder = TO_12785643A9
    elif inOrder(c6, c9, c4, fwd):
       if inOrder(c6, c9, c10, fwd):
          tourOrder = TO_1278569A43
    elif inOrder(c8, c9, c5, fwd):
       if inOrder(c8, c10, c9, fwd):
          tourOrder = TO_1278A95643
    else: #  inOrder(c2, c9, c7, fwd)
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A785643

  of TO_12875643:
    if inOrder(c6, c9, c4, fwd):
       if inOrder(c6, c9, c10, fwd):
          tourOrder = TO_1287569A43
       else:
          tourOrder = TO_128756A943
    elif inOrder(c7, c9, c5, fwd):
       if inOrder(c7, c9, c10, fwd):
          tourOrder = TO_12879A5643
       else:
          tourOrder = TO_1287A95643

  of TO_12654387:
    if inOrder(c5, c9, c4, fwd):
       if inOrder(c5, c9, c10, fwd):
          tourOrder = TO_12659A4387
       else:
          tourOrder = TO_1265A94387

  of TO_12657843:
    if inOrder(c3, c9, c1, fwd):
       if inOrder(c3, c10, c9, fwd):
          tourOrder = TO_12657843A9
    elif inOrder(c8, c9, c4, fwd):
       if inOrder(c8, c10, c9, fwd):
          tourOrder = TO_126578A943
    elif inOrder(c5, c9, c7, fwd):
       if inOrder(c5, c10, c9, fwd):
          tourOrder = TO_1265A97843
    else: #  inOrder(c2, c9, c6, fwd)
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A657843

  of TO_12658743:
    if inOrder(c3, c9, c1, fwd):
       if inOrder(c3, c10, c9, fwd):
          tourOrder = TO_12658743A9
    elif inOrder(c7, c9, c4, fwd):
       if inOrder(c7, c9, c10, fwd):
          tourOrder = TO_1265879A43
    elif inOrder(c5, c9, c8, fwd):
       if inOrder(c5, c9, c10, fwd):
          tourOrder = TO_12659A8743
    else: #  inOrder(c2, c9, c6, fwd)
       if inOrder(c2, c9, c10, fwd):
          tourOrder = TO_129A658743

  of TO_12786543:
    if inOrder(c5, c9, c4, fwd):
       if inOrder(c5, c9, c10, fwd):
          tourOrder = TO_1278659A43
       else:
          tourOrder = TO_127865A943

  else: # of tourOrder_4
    tourOrder  = TO_00
  #end of testing variants

  result = tourOrder

Some simple statistics

Relative time, best length, average length and worst length for all tours created by NN heuristic and improved by 3-opt and simple two Lin-Kernighan algorithm implementations with sequential 5-opt starting move. Neighbor lists size=24, LK breadth=(24, 24, 24, 3, 24), LK depth=100.
Random planar problems, N=100.

Problem #	Method	Time	Best	Avg	Worst
1	NN	100	100.00	109.29	118.74
	3opt-ND(24)	4687	86.67	90.72	92.56
	LK 5+3 + 4-non-seq	5856	85.75	85.91	88.43
	LK 5+5 + 4-non-seq	12306	85.75	85.75	85.75
2	NN	100	100.00	111.34	127.45
	3opt-ND(24)	6249	85.94	87.31	90.96
	LK 5+3 + 4-non-seq	7156	85.94	85.99	86.44
	LK 5+5 + 4-non-seq	23437	85.94	85.96	85.98
3	NN	100	100.00	109.39	119.32
	3opt-ND(24)	5762	86.69	88.36	90.97
	LK 5+3 + 4-non-seq	7712	86.20	86.44	87.37
	LK 5+5 + 4-non-seq	19531	86.20	86.34	87.26
4	NN	100	100.00	107.89	116.04
	3opt-ND(24)	4487	89.43	91.90	93.78
	LK 5+3 + 4-non-seq	5468	88.71	88.91	90.44
	LK 5+5 + 4-non-seq	11818	88.71	88.71	88.71
5	NN	100	100.00	106.52	116.44
	3opt-ND(24)	4756	87.14	88.58	91.10
	LK 5+3 + 4-non-seq	3325	86.46	86.46	86.46
	LK 5+5 + 4-non-seq	7812	86.46	86.46	86.46
6	NN	100	100.00	108.44	119.89
	3opt-ND(24)	4687	81.81	85.37	89.72
	LK 5+3 + 4-non-seq	3806	81.81	81.93	82.96
	LK 5+5 + 4-non-seq	11818	81.81	81.92	82.78
7	NN	100	100.00	105.61	113.40
	3opt-ND(24)	5000	85.08	87.51	90.20
	LK 5+3 + 4-non-seq	10206	85.08	85.17	86.16
	LK 5+5 + 4-non-seq	43960	85.08	85.08	85.08
8	NN	100	100.00	109.38	120.46
	3opt-ND(24)	4587	87.36	89.15	91.61
	LK 5+3 + 4-non-seq	6350	87.04	87.17	88.14
	LK 5+5 + 4-non-seq	19918	87.04	87.12	87.35
9	NN	100	100.00	107.73	118.39
	3opt-ND(24)	4781	85.53	86.70	89.53
	LK 5+3 + 4-non-seq	5274	84.55	84.90	85.42
	LK 5+5 + 4-non-seq	25193	84.55	84.60	85.15
10	NN	100	100.00	108.83	123.73
	3opt-ND(24)	4199	91.63	92.67	95.74
	LK 5+3 + 4-non-seq	8687	91.63	92.00	92.61
	LK 5+5 + 4-non-seq	31156	91.63	91.86	92.41

Results show that "LK 5+5 + 4-non-seq" algorithm for N=100 quite often finds exact, optimal solution regardless of initial tour it starts from.

Scheme of LK with non-sequential moves

proc LK_scheme() =
  var
    locallyOptimal: bool = false
    improved: bool
    baseCity: City_Number

  position = Create_Position_In_Tour(tour)
  Set_DLB_off(DontLook, tour)  
  # calculate initial length of tour
  tourLen = distance(tour[N-1], tour[0])
  for pos in 0 .. N-2:
    tourLen = tourLen + distance(tour[pos], tour[pos+1])

  while not locallyOptimal:
    locallyOptimal = true
    for baseCity in 0 .. N-1:
      if isDLB_on(DontLook, baseCity):
         continue 

      ClearPromisingMoves()
      # first move:
      improved = LK_1Move(baseCity)
      # subsequent moves:
      if not improved:
        improved = LK_1SubsequentMoves()
      # non-sequential moves:
      if not improved:
        improved = LK_1NS_Move(baseCity)

      if improved:
        locallyOptimal = false
      else:
        Set_DLB_on(DontLook, baseCity)
      tourLenArr[baseCity] = tourLen

    #end_loop for baseCity
  #end_while not locallyOptimal

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.

LK – alternative calling subsequent moves

Used with bigger values for breadths (eg. 24, 24, 24, 24, 24, Max_Breadth_K=3) gives similar results, but is up to two times faster than the code showed previously. Some people find this approach also simpler and more convincing.

type
  PromisingMove = object
    c1, c2, c3, c4, c5, c6, c7, c8, c9, c10: City_Number
    Ga: Length_Gain
    moveType: int
    tourOrder: int

const
  HalfListSize = 20
var
  promisingMoves: array[0..2*HalfListSize, PromisingMove]
  emptyListPos: int

proc ClearPromisingMoves() =
  for i in 0 .. len(promisingMoves)-1:
    promisingMoves[i].Ga = 0
  emptyListPos = 0

proc SortPromisingMoves() =
  sort(promisingMoves) do (x,y: PromisingMove) -> int:
       result = cmp(y.Ga, x.Ga)

proc AddToPromisingMoves(move: PromisingMove) =
  promisingMoves[emptyListPos] = move
  emptyListPos = emptyListPos + 1
  if emptyListPos > 2*HalfListSize:
    # sort list by gain, then treat worse half as not filled
    SortPromisingMoves()
    emptyListPos = HalfListSize + 1

proc GetAllPromisigMoves(): seq[PromisingMove] =
  var
    allMoves: seq[PromisingMove]
  allMoves = @[]  # empty list (sequence)
  SortPromisingMoves()
  for i in 0 .. min(emptyListPos, HalfListSize)-1:
    allMoves.add(promisingMoves[i])
  result = allMoves

proc LK_5Move(c1, c2, c3, c4, c5, c6, c7, c8: City_Number;
              G4a: Length_Gain;
              tourOrderPrev: int): bool =
  var
    ...
    move: PromisingMove
...    
  move.c1 = c1
  move.c2 = c2
  move.c3 = c3
  move.c4 = c4
  move.c5 = c5
  move.c6 = c6
  move.c7 = c7
  move.c8 = c8
...
  block find_promising_moves:
    ...
  #end_block find_promising_moves
    
  block evaluate_promising_moves:
    ...
      if moveType != move_type_0: # connecting move
        gainFromCloseUp = Ga - distance(c10, c1)
        if gainFromCloseUp > 0:
          # improving move found
          improved = true
          Make_5opt_Move(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10,
                         tourOrder)
          tourLen = tourLen - gainFromCloseUp
          Set_DLB_off(DontLook,
                      [c1, c2, c3, c4, c5, c6, c7, c8, c9, c10])
          break evaluate_promising_moves
          
      when true: # not OPT_6_IMPLEMENTED
        move.c9  = c9 
        move.c10 = c10
        move.Ga  = Ga
        move.moveType  = moveType
        move.tourOrder = tourOrder
        AddToPromisingMoves(move)
    #end_loop for mve
  #end_block evaluate_promising_moves
  result = improved

proc LK_1SubsequentMoves():bool =
  var
    improved: bool
    promisingMovesList: seq[PromisingMove]
    breadth: int
    c1, c2, c3, c4, c5, c6, c7, c8, c9, c10:  City_Number
    Ga: Length_Gain
    tourOrder: int
    moveType: int
    searching: bool
    c2subseq, cLast:  City_Number

  improved = false
  block evaluate_promising_moves:
    # here we should try to use general subsequent move
    # after temporary applying 5-opt move
    promisingMovesList = GetAllPromisigMoves()
    breadth = min(len(promisingMovesList), Max_Breadth_K)  ## NOTE
    if breadth == 0:
      break evaluate_promising_moves

    Save_Tour()
    Save_DLB()
    for mve in 0 .. breadth-1:
      c1  = promisingMovesList[mve].c1
      c2  = promisingMovesList[mve].c2
      c3  = promisingMovesList[mve].c3
      c4  = promisingMovesList[mve].c4
      c5  = promisingMovesList[mve].c5
      c6  = promisingMovesList[mve].c6
      c7  = promisingMovesList[mve].c7
      c8  = promisingMovesList[mve].c8
      c9  = promisingMovesList[mve].c9
      c10 = promisingMovesList[mve].c10
      Ga  = promisingMovesList[mve].Ga
      #moveType = promisingMovesList[mve].moveType
      tourOrder = promisingMovesList[mve].tourOrder

      c2subseq = c10
      cLast = c10
      LinksAddedClear()
      AddtoLinksAdded(c2, c3)
      AddtoLinksAdded(c4, c5)
      AddtoLinksAdded(c6, c7)
      AddtoLinksAdded(c8, c9)
      Make_5opt_Move(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10,
                     tourOrder)
      Set_DLB_off(DontLook,
                  [c1, c2, c3, c4, c5, c6, c7, c8, c9, c10])
      searching = true
      SubseqLvl = 0
      while searching:
        improved = LK_Subsequent3Move(c1, c2subseq, Ga, cLast)
        if improved:
          break evaluate_promising_moves
        else:
          if c2subseq == cLast: # end of promising moves
            Restore_Tour()
            Restore_DLB()
            searching = false
          else:
            c2subseq = cLast
        if SubseqLvl >= Max_Depth:
          searching = false
          Restore_Tour()
          Restore_DLB()
    #end_loop log mve
  #end_block evaluate_promising_moves
  result = improved

proc LK_scheme() =
  var
    locallyOptimal: bool = false
    improved: bool
    baseCity: City_Number

  position = Create_Position_In_Tour(tour)
  Set_DLB_off(DontLook, tour)

  while not locallyOptimal:
    locallyOptimal = true
    for baseCity in 0 .. N-1:
      if isDLB_on(DontLook, baseCity):
        continue 

      ClearPromisingMoves()
      # first move:
      improved = LK_1Move(baseCity)
      # subsequent moves:
      if not improved:
        improved = LK_1SubsequentMoves()

      if improved:
        locallyOptimal = false
      else:
        Set_DLB_on(DontLook, baseCity)

    #end_loop for baseCity
  #end_while not locallyOptimal

Extending LK: 5-opt move, part 3/3

const
  # descendants of TO_12345678
  TO_123456789A = 59
  TO_12345678A9 = 60
  TO_1234569A78 = 61
  TO_123456A978 = 62
  TO_12349A5678 = 63
  TO_1234A95678 = 64
  TO_129A345678 = 65
  TO_12A9345678 = 66
  # descendants of TO_12345687
  TO_123456879A = 67
  TO_12345687A9 = 68
  TO_1234569A87 = 69
  TO_123456A987 = 70
  TO_12349A5687 = 71
  TO_1234A95687 = 72
  TO_129A345687 = 73
  TO_12A9345687 = 74
  # descendants of TO_12347856
  TO_123478569A = 75
  TO_12347856A9 = 76
  TO_1234789A56 = 77
  TO_123478A956 = 78
  TO_12349A7856 = 79
  TO_1234A97856 = 80
  TO_129A347856 = 81  # 5-opt
  TO_12A9347856 = 82  # 5-opt
  # descendants of TO_12348756
  TO_123487569A = 83
  TO_12348756A9 = 84
  TO_1234879A56 = 85
  TO_123487A956 = 86
  TO_12349A8756 = 87
  TO_1234A98756 = 88
  TO_129A348756 = 89  # 5-opt
  TO_12A9348756 = 90  # 5-opt
  # descendants of TO_12783456
  TO_127834569A = 91
  TO_12783456A9 = 92
  TO_1278349A56 = 93  # 5-opt
  TO_127834A956 = 94  # 5-opt
  TO_12789A3456 = 95
  TO_1278A93456 = 96
  TO_129A783456 = 97
  TO_12A9783456 = 98
  # descendants of TO_12873456
  TO_128734569A = 99
  TO_12873456A9 = 100
  TO_1287349A56 = 101  # 5-opt
  TO_128734A956 = 102  # 5-opt
  TO_12879A3456 = 103
  TO_1287A93456 = 104
  TO_129A873456 = 105
  TO_12A9873456 = 106
  # descendants of TO_12346578
  TO_123465789A = 107
  TO_12346578A9 = 108
  TO_1234659A78 = 109
  TO_123465A978 = 110
  TO_12349A6578 = 111
  TO_1234A96578 = 112
  TO_129A346578 = 113
  TO_12A9346578 = 114
  # descendants of TO_12346587
  TO_123465879A = 115
  TO_12346587A9 = 116
  TO_1234659A87 = 117
  TO_123465A987 = 118
  TO_12349A6587 = 119
  TO_1234A96587 = 120
  TO_129A346587 = 121  # 5-opt
  TO_12A9346587 = 122  # 5-opt
  # descendants of TO_12347865
  TO_123478659A = 123
  TO_12347865A9 = 124
  TO_1234789A65 = 125
  TO_123478A965 = 126
  TO_12349A7865 = 127
  TO_1234A97865 = 128
  TO_129A347865 = 129  # 5-opt
  TO_12A9347865 = 130  # 5-opt
  # descendants of TO_12348765
  TO_123487659A = 131
  TO_12348765A9 = 132
  TO_1234879A65 = 133
  TO_123487A965 = 134
  TO_12349A8765 = 135
  TO_1234A98765 = 136
  TO_129A348765 = 137
  TO_12A9348765 = 138
  # descendants of TO_12783465
  TO_127834659A = 139
  TO_12783465A9 = 140  # 5-opt
  TO_1278349A65 = 141  # 5-opt
  TO_127834A965 = 142
  TO_12789A3465 = 143
  TO_1278A93465 = 144  # 5-opt
  TO_129A783465 = 145
  TO_12A9783465 = 146  # 5-opt
  # descendants of TO_12873465
  TO_128734659A = 147
  TO_12873465A9 = 148  # 5-opt
  TO_1287349A65 = 149  # 5-opt
  TO_128734A965 = 150
  TO_12879A3465 = 151  # 5-opt
  TO_1287A93465 = 152
  TO_129A873465 = 153  # 5-opt
  TO_12A9873465 = 154
  # descendants of TO_12563478
  TO_125634789A = 155
  TO_12563478A9 = 156
  TO_1256349A78 = 157  # 5-opt
  TO_125634A978 = 158  # 5-opt
  TO_12569A3478 = 159  # 5-opt
  TO_1256A93478 = 160  # 5-opt
  TO_129A563478 = 161  # 5-opt
  TO_12A9563478 = 162  # 5-opt
  # descendants of TO_12563487
  TO_125634879A = 163
  TO_12563487A9 = 164  # 5-opt
  TO_1256349A87 = 165  # 5-opt
  TO_125634A987 = 166
  TO_12569A3487 = 167  # 5-opt
  TO_1256A93487 = 168
  TO_129A563487 = 169  # 5-opt
  TO_12A9563487 = 170
  # descendants of TO_12785634
  TO_127856349A = 171
  TO_12785634A9 = 172
  TO_1278569A34 = 173  # 5-opt
  TO_127856A934 = 174  # 5-opt
  TO_12789A5634 = 175
  TO_1278A95634 = 176
  TO_129A785634 = 177  # 5-opt
  TO_12A9785634 = 178  # 5-opt
  # descendants of TO_12875634
  TO_128756349A = 179
  TO_12875634A9 = 180  # 5-opt
  TO_1287569A34 = 181  # 5-opt
  TO_128756A934 = 182
  TO_12879A5634 = 183
  TO_1287A95634 = 184  # 5-opt
  TO_129A875634 = 185  # 5-opt
  TO_12A9875634 = 186
  # descendants of TO_12567834
  TO_125678349A = 187
  TO_12567834A9 = 188
  TO_1256789A34 = 189
  TO_125678A934 = 190
  TO_12569A7834 = 191  # 5-opt
  TO_1256A97834 = 192  # 5-opt
  TO_129A567834 = 193
  TO_12A9567834 = 194
  # descendants of TO_12568734
  TO_125687349A = 195
  TO_12568734A9 = 196  # 5-opt
  TO_1256879A34 = 197
  TO_125687A934 = 198  # 5-opt
  TO_12569A8734 = 199  # 5-opt
  TO_1256A98734 = 200
  TO_129A568734 = 201
  TO_12A9568734 = 202  # 5-opt
  # descendants of TO_12653478
  TO_126534789A = 203
  TO_12653478A9 = 204
  TO_1265349A78 = 205  # 5-opt
  TO_126534A978 = 206  # 5-opt
  TO_12659A3478 = 207  # 5-opt
  TO_1265A93478 = 208  # 5-opt
  TO_129A653478 = 209  # 5-opt
  TO_12A9653478 = 210  # 5-opt
  # descendants of TO_12653487
  TO_126534879A = 211
  TO_12653487A9 = 212  # 5-opt
  TO_1265349A87 = 213  # 5-opt
  TO_126534A987 = 214
  TO_12659A3487 = 215
  TO_1265A93487 = 216  # 5-opt
  TO_129A653487 = 217
  TO_12A9653487 = 218  # 5-opt
  # descendants of TO_12657834
  TO_126578349A = 219
  TO_12657834A9 = 220  # 5-opt
  TO_1265789A34 = 221
  TO_126578A934 = 222  # 5-opt
  TO_12659A7834 = 223  # 5-opt
  TO_1265A97834 = 224
  TO_129A657834 = 225
  TO_12A9657834 = 226  # 5-opt
  # descendants of TO_12658734
  TO_126587349A = 227
  TO_12658734A9 = 228
  TO_1265879A34 = 229  # 5-opt
  TO_126587A934 = 230  # 5-opt
  TO_12659A8734 = 231
  TO_1265A98734 = 232
  TO_129A658734 = 233  # 5-opt
  TO_12A9658734 = 234  # 5-opt
  # descendants of TO_12786534
  TO_127865349A = 235
  TO_12786534A9 = 236  # 5-opt
  TO_1278659A34 = 237  # 5-opt
  TO_127865A934 = 238
  TO_12789A6534 = 239
  TO_1278A96534 = 240  # 5-opt
  TO_129A786534 = 241  # 5-opt
  TO_12A9786534 = 242
  # descendants of TO_12876534
  TO_128765349A = 243
  TO_12876534A9 = 244
  TO_1287659A34 = 245
  TO_128765A934 = 246
  TO_12879A6534 = 247  # 5-opt
  TO_1287A96534 = 248  # 5-opt
  TO_129A876534 = 249
  TO_12A9876534 = 250
  # descendants of TO_12435678
  TO_124356789A = 251
  TO_12435678A9 = 252
  TO_1243569A78 = 253
  TO_124356A978 = 254
  TO_12439A5678 = 255
  TO_1243A95678 = 256
  TO_129A435678 = 257
  TO_12A9435678 = 258
  # descendants of TO_12435687
  TO_124356879A = 259
  TO_12435687A9 = 260
  TO_1243569A87 = 261
  TO_124356A987 = 262
  TO_12439A5687 = 263  # 5-opt
  TO_1243A95687 = 264  # 5-opt
  TO_129A435687 = 265  # 5-opt
  TO_12A9435687 = 266  # 5-opt
  # descendants of TO_12437856
  TO_124378569A = 267
  TO_12437856A9 = 268  # 5-opt
  TO_1243789A56 = 269
  TO_124378A956 = 270  # 5-opt
  TO_12439A7856 = 271
  TO_1243A97856 = 272  # 5-opt
  TO_129A437856 = 273  # 5-opt
  TO_12A9437856 = 274
  # descendants of TO_12438756
  TO_124387569A = 275
  TO_12438756A9 = 276  # 5-opt
  TO_1243879A56 = 277  # 5-opt
  TO_124387A956 = 278
  TO_12439A8756 = 279  # 5-opt
  TO_1243A98756 = 280
  TO_129A438756 = 281
  TO_12A9438756 = 282  # 5-opt
  # descendants of TO_12784356
  TO_127843569A = 283
  TO_12784356A9 = 284  # 5-opt
  TO_1278439A56 = 285  # 5-opt
  TO_127843A956 = 286
  TO_12789A4356 = 287
  TO_1278A94356 = 288  # 5-opt
  TO_129A784356 = 289
  TO_12A9784356 = 290  # 5-opt
  # descendants of TO_12874356
  TO_128743569A = 291
  TO_12874356A9 = 292  # 5-opt
  TO_1287439A56 = 293
  TO_128743A956 = 294  # 5-opt
  TO_12879A4356 = 295  # 5-opt
  TO_1287A94356 = 296
  TO_129A874356 = 297  # 5-opt
  TO_12A9874356 = 298
  # descendants of TO_12436578
  TO_124365789A = 299
  TO_12436578A9 = 300
  TO_1243659A78 = 301  # 5-opt
  TO_124365A978 = 302  # 5-opt
  TO_12439A6578 = 303  # 5-opt
  TO_1243A96578 = 304  # 5-opt
  TO_129A436578 = 305  # 5-opt
  TO_12A9436578 = 306  # 5-opt
  # descendants of TO_12436587
  TO_124365879A = 307
  TO_12436587A9 = 308  # 5-opt
  TO_1243659A87 = 309  # 5-opt
  TO_124365A987 = 310
  TO_12439A6587 = 311
  TO_1243A96587 = 312  # 5-opt
  TO_129A436587 = 313  # 5-opt
  TO_12A9436587 = 314
  # descendants of TO_12437865
  TO_124378659A = 315
  TO_12437865A9 = 316  # 5-opt
  TO_1243789A65 = 317
  TO_124378A965 = 318  # 5-opt
  TO_12439A7865 = 319  # 5-opt
  TO_1243A97865 = 320
  TO_129A437865 = 321
  TO_12A9437865 = 322  # 5-opt
  # descendants of TO_12438765
  TO_124387659A = 323
  TO_12438765A9 = 324
  TO_1243879A65 = 325  # 5-opt
  TO_124387A965 = 326  # 5-opt
  TO_12439A8765 = 327
  TO_1243A98765 = 328
  TO_129A438765 = 329
  TO_12A9438765 = 330
  # descendants of TO_12784365
  TO_127843659A = 331
  TO_12784365A9 = 332
  TO_1278439A65 = 333  # 5-opt
  TO_127843A965 = 334  # 5-opt
  TO_12789A4365 = 335
  TO_1278A94365 = 336
  TO_129A784365 = 337  # 5-opt
  TO_12A9784365 = 338  # 5-opt
  # descendants of TO_12874365
  TO_128743659A = 339
  TO_12874365A9 = 340  # 5-opt
  TO_1287439A65 = 341
  TO_128743A965 = 342  # 5-opt
  TO_12879A4365 = 343
  TO_1287A94365 = 344  # 5-opt
  TO_129A874365 = 345  # 5-opt
  TO_12A9874365 = 346
  # descendants of TO_12564378
  TO_125643789A = 347
  TO_12564378A9 = 348
  TO_1256439A78 = 349  # 5-opt
  TO_125643A978 = 350  # 5-opt
  TO_12569A4378 = 351  # 5-opt
  TO_1256A94378 = 352  # 5-opt
  TO_129A564378 = 353  # 5-opt
  TO_12A9564378 = 354  # 5-opt
  # descendants of TO_12564387
  TO_125643879A = 355
  TO_12564387A9 = 356  # 5-opt
  TO_1256439A87 = 357  # 5-opt
  TO_125643A987 = 358
  TO_12569A4387 = 359  # 5-opt
  TO_1256A94387 = 360
  TO_129A564387 = 361
  TO_12A9564387 = 362  # 5-opt
  # descendants of TO_12567843
  TO_125678439A = 363
  TO_12567843A9 = 364
  TO_1256789A43 = 365
  TO_125678A943 = 366
  TO_12569A7843 = 367  # 5-opt
  TO_1256A97843 = 368  # 5-opt
  TO_129A567843 = 369
  TO_12A9567843 = 370
  # descendants of TO_12568743
  TO_125687439A = 371
  TO_12568743A9 = 372  # 5-opt
  TO_1256879A43 = 373
  TO_125687A943 = 374  # 5-opt
  TO_12569A8743 = 375  # 5-opt
  TO_1256A98743 = 376
  TO_129A568743 = 377  # 5-opt
  TO_12A9568743 = 378
  # descendants of TO_12785643
  TO_127856439A = 379
  TO_12785643A9 = 380  # 5-opt
  TO_1278569A43 = 381  # 5-opt
  TO_127856A943 = 382
  TO_12789A5643 = 383
  TO_1278A95643 = 384  # 5-opt
  TO_129A785643 = 385  # 5-opt
  TO_12A9785643 = 386
  # descendants of TO_12875643
  TO_128756439A = 387
  TO_12875643A9 = 388
  TO_1287569A43 = 389  # 5-opt
  TO_128756A943 = 390  # 5-opt
  TO_12879A5643 = 391  # 5-opt
  TO_1287A95643 = 392  # 5-opt
  TO_129A875643 = 393
  TO_12A9875643 = 394
  # descendants of TO_12654378
  TO_126543789A = 395
  TO_12654378A9 = 396
  TO_1265439A78 = 397
  TO_126543A978 = 398
  TO_12659A4378 = 399
  TO_1265A94378 = 400
  TO_129A654378 = 401
  TO_12A9654378 = 402
  # descendants of TO_12654387
  TO_126543879A = 403
  TO_12654387A9 = 404
  TO_1265439A87 = 405
  TO_126543A987 = 406
  TO_12659A4387 = 407  # 5-opt
  TO_1265A94387 = 408  # 5-opt
  TO_129A654387 = 409
  TO_12A9654387 = 410
  # descendants of TO_12657843
  TO_126578439A = 411
  TO_12657843A9 = 412  # 5-opt
  TO_1265789A43 = 413
  TO_126578A943 = 414  # 5-opt
  TO_12659A7843 = 415
  TO_1265A97843 = 416  # 5-opt
  TO_129A657843 = 417  # 5-opt
  TO_12A9657843 = 418
  # descendants of TO_12658743
  TO_126587439A = 419
  TO_12658743A9 = 420  # 5-opt
  TO_1265879A43 = 421  # 5-opt
  TO_126587A943 = 422
  TO_12659A8743 = 423  # 5-opt
  TO_1265A98743 = 424
  TO_129A658743 = 425  # 5-opt
  TO_12A9658743 = 426
  # descendants of TO_12786543
  TO_127865439A = 427
  TO_12786543A9 = 428
  TO_1278659A43 = 429  # 5-opt
  TO_127865A943 = 430  # 5-opt
  TO_12789A6543 = 431
  TO_1278A96543 = 432
  TO_129A786543 = 433
  TO_12A9786543 = 434
  # descendants of TO_12876543
  TO_128765439A = 435
  TO_12876543A9 = 436
  TO_1287659A43 = 437
  TO_128765A943 = 438
  TO_12879A6543 = 439
  TO_1287A96543 = 440
  TO_129A876543 = 441
  TO_12A9876543 = 442

Extending LK: 5-opt move, part 2/3

proc Make_5opt_Move(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10: City_Number;
                    tourOrder: int) =

  case tourOrder  # all 148 cases of sequential 5-opt move

  of TO_129A347856, TO_12569A3478, TO_129A785634, TO_12569A7834:
    ExchangeLinks(c1, c2, c9, c10)
    ExchangeLinks(c1, c9, c7, c8)
    ExchangeLinks(c1, c7, c5, c6)
    ExchangeLinks(c1, c5, c3, c4)
    ExchangeLinks(c1, c3, c10, c2)

  of TO_12A9347856, TO_129A563487, TO_12A9784356, TO_129A874356:
    ExchangeLinks(c8, c7, c9, c10)
    ExchangeLinks(c1, c2, c10, c7)
    ExchangeLinks(c2, c7, c5, c6)
    ExchangeLinks(c2, c5, c3, c4)

  of TO_129A348756, TO_129A346587, TO_129A873465, TO_129A875634,
     TO_1243A97856, TO_12439A8756, TO_1256439A87:
    ExchangeLinks(c8, c7, c9, c10)
    ExchangeLinks(c1, c2, c10, c7)
    ExchangeLinks(c2, c7, c3, c4)
    ExchangeLinks(c4, c7, c5, c6)

  of TO_12A9348756, TO_12A9346587, TO_1278A93465, TO_12A9783465,
     TO_12A9657834, TO_1243A96578:
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c2, c9, c3, c4)
    ExchangeLinks(c4, c9, c7, c8)
    ExchangeLinks(c4, c7, c5, c6)

  of TO_1278349A56:
    ExchangeLinks(c1, c2, c9, c10)
    ExchangeLinks(c3, c4, c6, c5)
    ExchangeLinks(c1, c9, c7, c8)
    ExchangeLinks(c1, c7, c3, c6)
    ExchangeLinks(c1, c3, c10, c2)

  of TO_127834A956, TO_12A9784365:
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c6, c5, c7, c8)
    ExchangeLinks(c2, c9, c3, c4)
    ExchangeLinks(c4, c9, c5, c8)

  of TO_1287349A56:
    ExchangeLinks(c7, c8, c10, c9)
    ExchangeLinks(c3, c4, c6, c5)
    ExchangeLinks(c1, c2, c10, c7)
    ExchangeLinks(c2, c7, c3, c6)

  of TO_128734A956, TO_12657834A9:
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c3, c4, c6, c5)
    ExchangeLinks(c2, c9, c7, c8)
    ExchangeLinks(c2, c7, c3, c6)

  of TO_129A347865:
    ExchangeLinks(c3, c4, c6, c5)
    ExchangeLinks(c8, c7, c9, c10)
    ExchangeLinks(c1, c2, c10, c7)
    ExchangeLinks(c2, c7, c3, c6)

  of TO_12A9347865, TO_12A9785634, TO_125643A978, TO_12568743A9:
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c2, c9, c3, c4)
    ExchangeLinks(c4, c9, c5, c6)
    ExchangeLinks(c6, c9, c7, c8)

  of TO_12783465A9, TO_12438756A9:
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c5, c6, c8, c7)
    ExchangeLinks(c2, c9, c5, c8)
    ExchangeLinks(c2, c5, c3, c4)

  of TO_1278349A65:
    ExchangeLinks(c6, c5, c7, c8)
    ExchangeLinks(c1, c2, c4, c3)
    ExchangeLinks(c1, c4, c8, c5)
    ExchangeLinks(c1, c8, c10, c9)

  of TO_12873465A9, TO_127856A934, TO_12437856A9:
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c4, c3, c5, c6)
    ExchangeLinks(c3, c6, c8, c7)
    ExchangeLinks(c2, c9, c3, c8)

  of TO_1287349A65:
    ExchangeLinks(c7, c8, c10, c9)
    ExchangeLinks(c1, c2, c4, c3)
    ExchangeLinks(c1, c4, c6, c5)
    ExchangeLinks(c1, c6, c10, c7)

  of TO_12879A3465, TO_12879A6534:
    ExchangeLinks(c7, c8, c10, c9)
    ExchangeLinks(c6, c5, c7, c10)
    ExchangeLinks(c1, c2, c10, c5)
    ExchangeLinks(c2, c5, c3, c4)

  of TO_1256349A78:
    ExchangeLinks(c1, c2, c9, c10)
    ExchangeLinks(c5, c6, c8, c7)
    ExchangeLinks(c1, c9, c5, c8)
    ExchangeLinks(c1, c5, c3, c4)
    ExchangeLinks(c1, c3, c10, c2)

  of TO_125634A978, TO_1256A93478, TO_12875634A9, TO_12874356A9:
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c5, c6, c8, c7)
    ExchangeLinks(c3, c4, c8, c5)
    ExchangeLinks(c2, c9, c3, c8)

  of TO_129A563478:
    ExchangeLinks(c1, c2, c9, c10)
    ExchangeLinks(c2, c10, c3, c4)
    ExchangeLinks(c1, c9, c7, c8)
    ExchangeLinks(c1, c7, c5, c6)
    ExchangeLinks(c1, c5, c10, c4)

  of TO_12A9563478, TO_12A9653487, TO_12784356A9:
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c2, c9, c3, c4)
    ExchangeLinks(c5, c6, c8, c7)
    ExchangeLinks(c4, c9, c5, c8)

  of TO_12563487A9, TO_12569A3487, TO_12659A3478, TO_12659A7834,
     TO_1243A95687, TO_1243659A78, TO_12657843A9:
    ExchangeLinks(c5, c6, c8, c7)
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c2, c9, c3, c4)
    ExchangeLinks(c4, c9, c5, c8)

  of TO_1256349A87, TO_125687A943, TO_126578A943:
    ExchangeLinks(c5, c6, c8, c7)
    ExchangeLinks(c1, c2, c4, c3)
    ExchangeLinks(c1, c4, c8, c5)
    ExchangeLinks(c1, c8, c10, c9)

  of TO_1278569A34:
    ExchangeLinks(c1, c2, c9, c10)
    ExchangeLinks(c4, c3, c5, c6)
    ExchangeLinks(c1, c9, c7, c8)
    ExchangeLinks(c1, c7, c3, c6)
    ExchangeLinks(c1, c3, c10, c2)

  of TO_1287569A34:
    ExchangeLinks(c7, c8, c10, c9)
    ExchangeLinks(c4, c3, c5, c6)
    ExchangeLinks(c1, c2, c10, c7)
    ExchangeLinks(c2, c7, c3, c6)

  of TO_1287A95634, TO_12A9568734, TO_128743A956, TO_127843A965:
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c2, c9, c3, c4)
    ExchangeLinks(c6, c5, c7, c8)
    ExchangeLinks(c4, c9, c5, c8)

  of TO_1256A97834, TO_127865A943:
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c4, c3, c5, c6)
    ExchangeLinks(c2, c9, c3, c6)
    ExchangeLinks(c6, c9, c7, c8)

  of TO_12568734A9, TO_12658743A9:
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c2, c9, c7, c8)
    ExchangeLinks(c3, c4, c6, c5)
    ExchangeLinks(c2, c7, c3, c6)

  of TO_125687A934, TO_126578A934:
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c6, c5, c7, c8)
    ExchangeLinks(c4, c3, c5, c8)
    ExchangeLinks(c2, c9, c3, c8)

  of TO_12569A8734:
    ExchangeLinks(c5, c6, c8, c7)
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c4, c3, c5, c8)
    ExchangeLinks(c2, c9, c3, c8)

  of TO_1265349A78, TO_12A9435687, TO_12A9436578:
    ExchangeLinks(c5, c6, c8, c7)
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c2, c9, c5, c8)
    ExchangeLinks(c2, c5, c3, c4)

  of TO_126534A978, TO_1265879A34, TO_12786534A9, TO_1278659A34,
     TO_12785643A9:
    ExchangeLinks(c4, c3, c5, c6)
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c2, c9, c3, c6)
    ExchangeLinks(c6, c9, c7, c8)

  of TO_1265A93478, TO_1256A94378:
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c2, c9, c7, c8)
    ExchangeLinks(c4, c3, c5, c6)
    ExchangeLinks(c2, c7, c3, c6)

  of TO_129A653478:
    ExchangeLinks(c5, c6, c8, c7)
    ExchangeLinks(c1, c2, c4, c3)
    ExchangeLinks(c1, c4, c10, c9)
    ExchangeLinks(c4, c9, c5, c8)

  of TO_12A9653478, TO_12653487A9, TO_126587A934, TO_12436587A9:
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c2, c9, c7, c8)
    ExchangeLinks(c2, c7, c5, c6)
    ExchangeLinks(c2, c5, c3, c4)

  of TO_1265349A87, TO_1278A96534, TO_1278569A43, TO_1278A95643:
    ExchangeLinks(c4, c3, c5, c6)
    ExchangeLinks(c1, c2, c6, c3)
    ExchangeLinks(c1, c6, c8, c7)
    ExchangeLinks(c1, c8, c10, c9)

  of TO_1265A93487, TO_128756A943:
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c5, c6, c8, c7)
    ExchangeLinks(c4, c3, c5, c8)
    ExchangeLinks(c2, c9, c3, c8)

  of TO_129A658734:
    ExchangeLinks(c8, c7, c9, c10)
    ExchangeLinks(c1, c2, c10, c7)
    ExchangeLinks(c4, c3, c5, c6)
    ExchangeLinks(c2, c7, c3, c6)

  of TO_12A9658734, TO_12A9564378:
    ExchangeLinks(c4, c3, c5, c6)
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c2, c9, c7, c8)
    ExchangeLinks(c2, c7, c3, c6)

  of TO_129A786534:
    ExchangeLinks(c6, c5, c7, c8)
    ExchangeLinks(c8, c5, c9, c10)
    ExchangeLinks(c1, c2, c10, c5)
    ExchangeLinks(c2, c5, c3, c4)

  of TO_1287A96534, TO_124378A956, TO_1278A94356, TO_124387A965:
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c6, c5, c7, c8)
    ExchangeLinks(c2, c9, c5, c8)
    ExchangeLinks(c2, c5, c3, c4)

  of TO_12439A5687:
    ExchangeLinks(c1, c2, c4, c3)
    ExchangeLinks(c8, c7, c9, c10)
    ExchangeLinks(c1, c4, c10, c7)
    ExchangeLinks(c4, c7, c5, c6)

  of TO_129A435687, TO_129A437856, TO_12879A4356, TO_124365A978,
     TO_12437865A9, TO_12874365A9, TO_129A564378, TO_129A568743,
     TO_12879A5643, TO_12659A4387, TO_1265879A43, TO_1278659A43:
    ExchangeLinks(c1, c2, c4, c3)
    ExchangeLinks(c1, c4, c10, c9)
    ExchangeLinks(c4, c9, c5, c6)
    ExchangeLinks(c6, c9, c7, c8)

  of TO_1243879A56, TO_1278439A56:
    ExchangeLinks(c1, c2, c4, c3)
    ExchangeLinks(c6, c5, c7, c8)
    ExchangeLinks(c1, c4, c10, c9)
    ExchangeLinks(c4, c9, c5, c8)

  of TO_12A9438756:
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c3, c4, c6, c5)
    ExchangeLinks(c2, c9, c3, c6)
    ExchangeLinks(c6, c9, c7, c8)

  of TO_12439A6578, TO_12439A7865, TO_1243879A65, TO_1278439A65:
    ExchangeLinks(c1, c2, c4, c3)
    ExchangeLinks(c1, c4, c6, c5)
    ExchangeLinks(c1, c6, c10, c9)
    ExchangeLinks(c6, c9, c7, c8)

  of TO_129A436578, TO_12569A4378, TO_129A785643, TO_1287569A43:
    ExchangeLinks(c1, c2, c4, c3)
    ExchangeLinks(c1, c4, c10, c9)
    ExchangeLinks(c4, c9, c7, c8)
    ExchangeLinks(c4, c7, c5, c6)

  of TO_1243659A87, TO_129A436587, TO_124378A965, TO_129A874365,
     TO_12569A4387, TO_12569A8743:
    ExchangeLinks(c1, c2, c4, c3)
    ExchangeLinks(c1, c4, c6, c5)
    ExchangeLinks(c1, c6, c8, c7)
    ExchangeLinks(c1, c8, c10, c9)

  of TO_1243A96587, TO_128743A965:
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c3, c4, c6, c5)
    ExchangeLinks(c3, c6, c8, c7)
    ExchangeLinks(c2, c9, c3, c8)

  of TO_12A9437865, TO_12564387A9, TO_1287A95643:
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c2, c9, c7, c8)
    ExchangeLinks(c2, c7, c3, c4)
    ExchangeLinks(c4, c7, c5, c6)

  of TO_129A784365, TO_12569A7843, TO_12659A8743:
    ExchangeLinks(c1, c2, c4, c3)
    ExchangeLinks(c1, c4, c10, c9)
    ExchangeLinks(c6, c5, c7, c8)
    ExchangeLinks(c4, c9, c5, c8)

  of TO_1287A94365:
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c6, c5, c7, c8)
    ExchangeLinks(c3, c4, c8, c5)
    ExchangeLinks(c2, c9, c3, c8)

  of TO_1256439A78:
    ExchangeLinks(c1, c2, c4, c3)
    ExchangeLinks(c5, c6, c8, c7)
    ExchangeLinks(c1, c4, c10, c9)
    ExchangeLinks(c4, c9, c5, c8)

  of TO_12A9564387:
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c5, c6, c8, c7)
    ExchangeLinks(c2, c9, c3, c4)
    ExchangeLinks(c4, c9, c5, c8)

  of TO_1256A97843, TO_129A658743:
    ExchangeLinks(c8, c7, c9, c10)
    ExchangeLinks(c1, c2, c4, c3)
    ExchangeLinks(c1, c4, c6, c5)
    ExchangeLinks(c1, c6, c10, c7)

  of TO_1265A94387, TO_1265A97843:
    ExchangeLinks(c1, c2, c10, c9)
    ExchangeLinks(c4, c3, c5, c6)
    ExchangeLinks(c2, c9, c7, c8)
    ExchangeLinks(c2, c7, c3, c6)

  of TO_129A657843:
    ExchangeLinks(c1, c2, c4, c3)
    ExchangeLinks(c1, c4, c10, c9)
    ExchangeLinks(c5, c6, c8, c7)
    ExchangeLinks(c4, c9, c5, c8)

  else:    
    echo "Unknown 5-opt move: ", tourOrder
    quit 1

Some simple statistics

Relative time, best length, average length and worst length for all tours created by NN heuristic and improved by 3-opt and simple Lin-Kernighan algorithm implementation with sequential 5-opt starting move. Neighbor lists size=24, LK breadth=(5, 5, 5, 5, 3, 3), LK depth=55. Random planar problems, N=100.

Problem #	Method	Time	Best	Avg	Worst
1	NN	100	100.00	104.58	111.49
	3opt-ND(24)	4981	82.10	84.07	87.66
	LK 5+2	4687	81.89	82.51	84.62
2	NN	100	100.00	105.94	113.41
	3opt-ND(24)	5862	88.05	89.30	91.10
	LK 5+2	5268	87.87	88.32	89.12
3	NN	100	100.00	110.21	118.39
	3opt-ND(24)	5862	88.69	89.22	92.23
	LK 5+2	3025	88.69	88.74	90.17
4	NN	100	100.00	110.71	121.43
	3opt-ND(24)	4981	88.49	90.36	94.79
	LK 5+2	5174	88.22	88.94	91.08
5	NN	100	100.00	106.48	112.81
	3opt-ND(24)	6249	83.91	86.88	91.43
	LK 5+2	11518	83.36	83.96	85.16
6	NN	100	100.00	107.73	119.37
	3opt-ND(24)	6637	89.29	90.93	94.26
	LK 5+2	3906	89.29	89.66	91.21
7	NN	100	100.00	111.26	124.70
	3opt-ND(24)	5275	94.92	97.82	103.58
	LK 5+2	3025	94.92	95.47	98.97
9	NN	100	100.00	106.52	117.51
	3opt-ND(24)	5662	87.42	89.30	91.69
	LK 5+2	6837	87.33	88.43	90.56
9	NN	100	100.00	105.63	112.79
	3opt-ND(24)	5368	85.57	87.72	90.64
	LK 5+2	5374	85.57	86.04	87.80
10	NN	100	100.00	107.49	119.01
	3opt-ND(24)	4687	91.04	92.89	94.33
	LK 5+2	4006	90.79	91.50	93.80

Extending LK: 5-opt move, part 1/3

There are 148 pure 5-opt move types.

Note that the code below is for sequential pure 5-opt moves and it is supposed to be used with the code for pure 4-opt, 3-opt and 2-opt moves.

proc LK_5Move(c1, c2, c3, c4, c5, c6, c7, c8: City_Number;
              G4a: Length_Gain;
              tourOrderPrev: int): bool =
  const
    level = 4
  var
    improved: bool
    searching: bool
    c9, c10: City_Number
    c8_pred, c8_succ: City_Number
    c9_pred, c9_succ: City_Number
    fwd: bool
    G4, G5a, gainFromCloseUp: Length_Gain
    goodSuffix: Suffix
    goodSufficesList: seq[Suffix]
    tried_c9: int = 0
    breadth: int
    tourOrder: int
    moveType: int
    c2subseq, cLast:  City_Number
    Ga: Length_Gain
    SubseqLvl: int

  improved = false
  fwd = (c2 == t_succ(c1))
  c8_succ = t_succ(c8)
  c8_pred = t_pred(c8)

  block find_promising_moves:
    goodSufficesList = @[]  # empty list (sequence)
    for c9 in neighbors(c8):
      if tried_c9 >= 2*Max_Breadth_4:
        break find_promising_moves
      # tests:
      # when c9 is one of tour neighbors of c8,
      # then the link (c6,c7) already exists in tour
      # and we cannot add it to the tour
      if (c9 == c8_succ) or (c9 == c8_pred):
        continue
      # link (c8,c9) should not be the same as (c2,c3)
      if (c8 == c2) and (c9 == c3) or
         (c8 == c3) and (c9 == c2):
        continue
      # link (c8,c9) should not be the same as (c4,c5)
      if (c8 == c4) and (c9 == c5) or
         (c8 == c5) and (c9 == c4):
        continue
      # if c9 is c1, then link (c10,c1) needed to close the tour
      # would be the same as (c10,c9) already in in tour
      if (c9 == c1):
        continue

      G4 = G4a - distance(c8, c9)

      if G4  < 0:  # c9 is too far from c8
        break  # all subsequent candidates for c9 are even worse

      # if G4 > 0:
      c9_succ = t_succ(c9)
      c9_pred = t_pred(c9)

      for c10 in [c9_succ, c9_pred]:
        # tests:
        # c10 should not be c1, when we close a tour.
        # We check condition here, because we are not going to
        # go deeper and pass possibly disconnecting move
        # to *general* 6-opt proc
        # (compare place of similar test in 4opt proc)
        if (c10 == c1):
          continue
        # link (c9,c10) should not be the same as (c3,c4)
        if (c9 == c3) and (c10 == c4) or
           (c9 == c4) and (c10 == c3):
          continue
        # link (c9,c10) should not be the same as (c5,c6)
        if (c9 == c5) and (c10 == c6) or
           (c9 == c6) and (c10 == c5):
          continue

        tourOrder = TO_00 #  do not remove this line!
        case tourOrderPrev

        of TO_12347856:
          if inOrder(c2, c9, c3, fwd):
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A347856
            else:
              tourOrder = TO_12A9347856

        of TO_12348756:
          if inOrder(c2, c9, c3, fwd):
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A348756
            else:
              tourOrder = TO_12A9348756

        of TO_12783456:
          if inOrder(c4, c9, c5, fwd):
            if inOrder(c4, c9, c10, fwd):
              tourOrder = TO_1278349A56
            else:
              tourOrder = TO_127834A956

        of TO_12873456:
          if inOrder(c4, c9, c5, fwd):
            if inOrder(c4, c9, c10, fwd):
              tourOrder = TO_1287349A56
            else:
              tourOrder = TO_128734A956

        of TO_12346587:
          if inOrder(c2, c9, c3, fwd):
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A346587
            else:
              tourOrder = TO_12A9346587

        of TO_12347865:
          if inOrder(c2, c9, c3, fwd):
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A347865
            else:
              tourOrder = TO_12A9347865

        of TO_12783465:
          if inOrder(c5, c9, c1, fwd):
            if inOrder(c5, c10, c9, fwd):
              tourOrder = TO_12783465A9
          elif inOrder(c4, c9, c6, fwd):
            if inOrder(c4, c9, c10, fwd):
              tourOrder = TO_1278349A65
          elif inOrder(c8, c9, c3, fwd):
            if inOrder(c8, c10, c9, fwd):
              tourOrder = TO_1278A93465
          else: #  inOrder(c2, c9, c7, fwd)
            if inOrder(c2, c10, c9, fwd):
              tourOrder = TO_12A9783465

        of TO_12873465:
          if inOrder(c5, c9, c1, fwd):
            if inOrder(c5, c10, c9, fwd):
              tourOrder = TO_12873465A9
          elif inOrder(c4, c9, c6, fwd):
            if inOrder(c4, c9, c10, fwd):
              tourOrder = TO_1287349A65
          elif inOrder(c7, c9, c3, fwd):
            if inOrder(c7, c9, c10, fwd):
              tourOrder = TO_12879A3465
          else: #  inOrder(c2, c9, c8, fwd)
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A873465

        of TO_12563478:
          if inOrder(c4, c9, c7, fwd):
            if inOrder(c4, c9, c10, fwd):
              tourOrder = TO_1256349A78
            else:
              tourOrder = TO_125634A978
          elif inOrder(c6, c9, c3, fwd):
            if inOrder(c6, c9, c10, fwd):
              tourOrder = TO_12569A3478
            else:
              tourOrder = TO_1256A93478
          elif inOrder(c2, c9, c5, fwd):
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A563478
            else:
              tourOrder = TO_12A9563478

        of TO_12563487:
          if inOrder(c7, c9, c1, fwd):
            if inOrder(c7, c10, c9, fwd):
              tourOrder = TO_12563487A9
          elif inOrder(c4, c9, c8, fwd):
            if inOrder(c4, c9, c10, fwd):
              tourOrder = TO_1256349A87
          elif inOrder(c6, c9, c3, fwd):
            if inOrder(c6, c9, c10, fwd):
              tourOrder = TO_12569A3487
          else: #  inOrder(c2, c9, c5, fwd)
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A563487

        of TO_12785634:
          if inOrder(c6, c9, c3, fwd):
            if inOrder(c6, c9, c10, fwd):
              tourOrder = TO_1278569A34
            else:
              tourOrder = TO_127856A934
          elif inOrder(c2, c9, c7, fwd):
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A785634
            else:
              tourOrder = TO_12A9785634

        of TO_12875634:
          if inOrder(c4, c9, c1, fwd):
            if inOrder(c4, c10, c9, fwd):
              tourOrder = TO_12875634A9
          elif inOrder(c6, c9, c3, fwd):
            if inOrder(c6, c9, c10, fwd):
              tourOrder = TO_1287569A34
          elif inOrder(c7, c9, c5, fwd):
            if inOrder(c7, c10, c9, fwd):
              tourOrder = TO_1287A95634
          else: #  inOrder(c2, c9, c8, fwd)
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A875634

        of TO_12567834:
          if inOrder(c6, c9, c7, fwd):
            if inOrder(c6, c9, c10, fwd):
              tourOrder = TO_12569A7834
            else:
              tourOrder = TO_1256A97834

        of TO_12568734:
          if inOrder(c4, c9, c1, fwd):
            if inOrder(c4, c10, c9, fwd):
              tourOrder = TO_12568734A9
          elif inOrder(c7, c9, c3, fwd):
            if inOrder(c7, c10, c9, fwd):
              tourOrder = TO_125687A934
          elif inOrder(c6, c9, c8, fwd):
            if inOrder(c6, c9, c10, fwd):
              tourOrder = TO_12569A8734
          else: #  inOrder(c2, c9, c5, fwd)
            if inOrder(c2, c10, c9, fwd):
              tourOrder = TO_12A9568734

        of TO_12653478:
          if inOrder(c4, c9, c7, fwd):
            if inOrder(c4, c9, c10, fwd):
              tourOrder = TO_1265349A78
            else:
              tourOrder = TO_126534A978
          elif inOrder(c5, c9, c3, fwd):
            if inOrder(c5, c9, c10, fwd):
              tourOrder = TO_12659A3478
            else:
              tourOrder = TO_1265A93478
          elif inOrder(c2, c9, c6, fwd):
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A653478
            else:
              tourOrder = TO_12A9653478

        of TO_12653487:
          if inOrder(c7, c9, c1, fwd):
            if inOrder(c7, c10, c9, fwd):
              tourOrder = TO_12653487A9
          elif inOrder(c4, c9, c8, fwd):
            if inOrder(c4, c9, c10, fwd):
              tourOrder = TO_1265349A87
          elif inOrder(c5, c9, c3, fwd):
            if inOrder(c5, c10, c9, fwd):
              tourOrder = TO_1265A93487
          else: #  inOrder(c2, c9, c6, fwd)
            if inOrder(c2, c10, c9, fwd):
              tourOrder = TO_12A9653487

        of TO_12657834:
          if inOrder(c4, c9, c1, fwd):
            if inOrder(c4, c10, c9, fwd):
              tourOrder = TO_12657834A9
          elif inOrder(c8, c9, c3, fwd):
            if inOrder(c8, c10, c9, fwd):
              tourOrder = TO_126578A934
          elif inOrder(c5, c9, c7, fwd):
            if inOrder(c5, c9, c10, fwd):
              tourOrder = TO_12659A7834
          else: #  inOrder(c2, c9, c6, fwd)
            if inOrder(c2, c10, c9, fwd):
              tourOrder = TO_12A9657834

        of TO_12658734:
          if inOrder(c7, c9, c3, fwd):
            if inOrder(c7, c9, c10, fwd):
              tourOrder = TO_1265879A34
            else:
              tourOrder = TO_126587A934
          elif inOrder(c2, c9, c6, fwd):
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A658734
            else:
              tourOrder = TO_12A9658734

        of TO_12786534:
          if inOrder(c4, c9, c1, fwd):
            if inOrder(c4, c10, c9, fwd):
              tourOrder = TO_12786534A9
          elif inOrder(c5, c9, c3, fwd):
            if inOrder(c5, c9, c10, fwd):
              tourOrder = TO_1278659A34
          elif inOrder(c8, c9, c6, fwd):
            if inOrder(c8, c10, c9, fwd):
              tourOrder = TO_1278A96534
          else: #  inOrder(c2, c9, c7, fwd)
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A786534

        of TO_12876534:
          if inOrder(c7, c9, c6, fwd):
            if inOrder(c7, c9, c10, fwd):
              tourOrder = TO_12879A6534
            else:
              tourOrder = TO_1287A96534

        of TO_12435687:
          if inOrder(c3, c9, c5, fwd):
            if inOrder(c3, c9, c10, fwd):
              tourOrder = TO_12439A5687
            else:
              tourOrder = TO_1243A95687
          elif inOrder(c2, c9, c4, fwd):
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A435687
            else:
              tourOrder = TO_12A9435687

        of TO_12437856:
          if inOrder(c6, c9, c1, fwd):
            if inOrder(c6, c10, c9, fwd):
              tourOrder = TO_12437856A9
          elif inOrder(c8, c9, c5, fwd):
            if inOrder(c8, c10, c9, fwd):
              tourOrder = TO_124378A956
          elif inOrder(c3, c9, c7, fwd):
            if inOrder(c3, c10, c9, fwd):
              tourOrder = TO_1243A97856
          else: #  inOrder(c2, c9, c4, fwd)
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A437856

        of TO_12438756:
          if inOrder(c6, c9, c1, fwd):
            if inOrder(c6, c10, c9, fwd):
              tourOrder = TO_12438756A9
          elif inOrder(c7, c9, c5, fwd):
            if inOrder(c7, c9, c10, fwd):
              tourOrder = TO_1243879A56
          elif inOrder(c3, c9, c8, fwd):
            if inOrder(c3, c9, c10, fwd):
              tourOrder = TO_12439A8756
          else: #  inOrder(c2, c9, c4, fwd)
            if inOrder(c2, c10, c9, fwd):
              tourOrder = TO_12A9438756

        of TO_12784356:
          if inOrder(c6, c9, c1, fwd):
            if inOrder(c6, c10, c9, fwd):
              tourOrder = TO_12784356A9
          elif inOrder(c3, c9, c5, fwd):
            if inOrder(c3, c9, c10, fwd):
              tourOrder = TO_1278439A56
          elif inOrder(c8, c9, c4, fwd):
            if inOrder(c8, c10, c9, fwd):
              tourOrder = TO_1278A94356
          else: #  inOrder(c2, c9, c7, fwd)
            if inOrder(c2, c10, c9, fwd):
              tourOrder = TO_12A9784356

        of TO_12874356:
          if inOrder(c6, c9, c1, fwd):
            if inOrder(c6, c10, c9, fwd):
              tourOrder = TO_12874356A9
          elif inOrder(c3, c9, c5, fwd):
            if inOrder(c3, c10, c9, fwd):
              tourOrder = TO_128743A956
          elif inOrder(c7, c9, c4, fwd):
            if inOrder(c7, c9, c10, fwd):
              tourOrder = TO_12879A4356
          else: #  inOrder(c2, c9, c8, fwd)
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A874356

        of TO_12436578:
          if inOrder(c5, c9, c7, fwd):
            if inOrder(c5, c9, c10, fwd):
              tourOrder = TO_1243659A78
            else:
              tourOrder = TO_124365A978
          elif inOrder(c3, c9, c6, fwd):
            if inOrder(c3, c9, c10, fwd):
              tourOrder = TO_12439A6578
            else:
              tourOrder = TO_1243A96578
          elif inOrder(c2, c9, c4, fwd):
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A436578
            else:
              tourOrder = TO_12A9436578

        of TO_12436587:
          if inOrder(c7, c9, c1, fwd):
            if inOrder(c7, c10, c9, fwd):
              tourOrder = TO_12436587A9
          elif inOrder(c5, c9, c8, fwd):
            if inOrder(c5, c9, c10, fwd):
              tourOrder = TO_1243659A87
          elif inOrder(c3, c9, c6, fwd):
            if inOrder(c3, c10, c9, fwd):
              tourOrder = TO_1243A96587
          else: #  inOrder(c2, c9, c4, fwd)
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A436587

        of TO_12437865:
          if inOrder(c5, c9, c1, fwd):
            if inOrder(c5, c10, c9, fwd):
              tourOrder = TO_12437865A9
          elif inOrder(c8, c9, c6, fwd):
            if inOrder(c8, c10, c9, fwd):
              tourOrder = TO_124378A965
          elif inOrder(c3, c9, c7, fwd):
            if inOrder(c3, c9, c10, fwd):
              tourOrder = TO_12439A7865
          else: #  inOrder(c2, c9, c4, fwd)
            if inOrder(c2, c10, c9, fwd):
              tourOrder = TO_12A9437865

        of TO_12438765:
          if inOrder(c7, c9, c6, fwd):
            if inOrder(c7, c9, c10, fwd):
              tourOrder = TO_1243879A65
            else:
              tourOrder = TO_124387A965

        of TO_12784365:
          if inOrder(c3, c9, c6, fwd):
            if inOrder(c3, c9, c10, fwd):
              tourOrder = TO_1278439A65
            else:
              tourOrder = TO_127843A965
          elif inOrder(c2, c9, c7, fwd):
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A784365
            else:
              tourOrder = TO_12A9784365

        of TO_12874365:
          if inOrder(c5, c9, c1, fwd):
            if inOrder(c5, c10, c9, fwd):
              tourOrder = TO_12874365A9
          elif inOrder(c3, c9, c6, fwd):
            if inOrder(c3, c10, c9, fwd):
              tourOrder = TO_128743A965
          elif inOrder(c7, c9, c4, fwd):
            if inOrder(c7, c10, c9, fwd):
              tourOrder = TO_1287A94365
          else: #  inOrder(c2, c9, c8, fwd)
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A874365

        of TO_12564378:
          if inOrder(c3, c9, c7, fwd):
            if inOrder(c3, c9, c10, fwd):
              tourOrder = TO_1256439A78
            else:
              tourOrder = TO_125643A978
          elif inOrder(c6, c9, c4, fwd):
            if inOrder(c6, c9, c10, fwd):
              tourOrder = TO_12569A4378
            else:
              tourOrder = TO_1256A94378
          elif inOrder(c2, c9, c5, fwd):
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A564378
            else:
              tourOrder = TO_12A9564378

        of TO_12564387:
          if inOrder(c7, c9, c1, fwd):
            if inOrder(c7, c10, c9, fwd):
              tourOrder = TO_12564387A9
          elif inOrder(c3, c9, c8, fwd):
s            if inOrder(c3, c9, c10, fwd):
              tourOrder = TO_1256439A87
          elif inOrder(c6, c9, c4, fwd):
            if inOrder(c6, c9, c10, fwd):
              tourOrder = TO_12569A4387
          else: #  inOrder(c2, c9, c5, fwd)
            if inOrder(c2, c10, c9, fwd):
              tourOrder = TO_12A9564387

        of TO_12567843:
          if inOrder(c6, c9, c7, fwd):
            if inOrder(c6, c9, c10, fwd):
              tourOrder = TO_12569A7843
            else:
              tourOrder = TO_1256A97843

        of TO_12568743:
          if inOrder(c3, c9, c1, fwd):
            if inOrder(c3, c10, c9, fwd):
              tourOrder = TO_12568743A9
          elif inOrder(c7, c9, c4, fwd):
            if inOrder(c7, c10, c9, fwd):
              tourOrder = TO_125687A943
          elif inOrder(c6, c9, c8, fwd):
            if inOrder(c6, c9, c10, fwd):
              tourOrder = TO_12569A8743
          else: #  inOrder(c2, c9, c5, fwd)
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A568743

        of TO_12785643:
          if inOrder(c3, c9, c1, fwd):
            if inOrder(c3, c10, c9, fwd):
              tourOrder = TO_12785643A9
          elif inOrder(c6, c9, c4, fwd):
            if inOrder(c6, c9, c10, fwd):
              tourOrder = TO_1278569A43
          elif inOrder(c8, c9, c5, fwd):
            if inOrder(c8, c10, c9, fwd):
              tourOrder = TO_1278A95643
          else: #  inOrder(c2, c9, c7, fwd)
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A785643

        of TO_12875643:
          if inOrder(c6, c9, c4, fwd):
            if inOrder(c6, c9, c10, fwd):
              tourOrder = TO_1287569A43
            else:
              tourOrder = TO_128756A943
          elif inOrder(c7, c9, c5, fwd):
            if inOrder(c7, c9, c10, fwd):
              tourOrder = TO_12879A5643
            else:
              tourOrder = TO_1287A95643

        of TO_12654387:
          if inOrder(c5, c9, c4, fwd):
            if inOrder(c5, c9, c10, fwd):
              tourOrder = TO_12659A4387
            else:
              tourOrder = TO_1265A94387

        of TO_12657843:
          if inOrder(c3, c9, c1, fwd):
            if inOrder(c3, c10, c9, fwd):
              tourOrder = TO_12657843A9
          elif inOrder(c8, c9, c4, fwd):
            if inOrder(c8, c10, c9, fwd):
              tourOrder = TO_126578A943
          elif inOrder(c5, c9, c7, fwd):
            if inOrder(c5, c10, c9, fwd):
              tourOrder = TO_1265A97843
          else: #  inOrder(c2, c9, c6, fwd)
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A657843

        of TO_12658743:
          if inOrder(c3, c9, c1, fwd):
            if inOrder(c3, c10, c9, fwd):
              tourOrder = TO_12658743A9
          elif inOrder(c7, c9, c4, fwd):
            if inOrder(c7, c9, c10, fwd):
              tourOrder = TO_1265879A43
          elif inOrder(c5, c9, c8, fwd):
            if inOrder(c5, c9, c10, fwd):
              tourOrder = TO_12659A8743
          else: #  inOrder(c2, c9, c6, fwd)
            if inOrder(c2, c9, c10, fwd):
              tourOrder = TO_129A658743

        of TO_12786543:
          if inOrder(c5, c9, c4, fwd):
            if inOrder(c5, c9, c10, fwd):
              tourOrder = TO_1278659A43
            else:
              tourOrder = TO_127865A943

        else: # of tourOrderPrev
          continue
        #end of testing variants

        if tourOrder == TO_00:
          moveType = move_type_0
        else:
          moveType = move_type_5

        if moveType != move_type_0:  # 6-opt not implemented
          tried_c9 = tried_c9 + 1
          G5a = G4 + distance(c9, c10)
          goodSuffix = Suffix(c2iplus1: c9, c2iplus2: c10,
                              Ga: G5a,
                              tourOrder: tourOrder, moveType: moveType)
          goodSufficesList.add(goodSuffix)
      #end_loop for c10
    #end_loop for neighbor_number
  #end_block find_promising_moves

  block evaluate_promising_moves:
    if len(goodSufficesList) == 0:
      # no promising moves
      break evaluate_promising_moves

    Save_Tour()
    Save_DLB()
    SortSufficesByGain(goodSufficesList)
    # pass promising moves, one by one, to next level
    # to check them there
    breadth = min(len(goodSufficesList), Max_breadth_4)
    for mve in 0 .. breadth-1:
      goodSuffix = goodSufficesList[mve]
      c9 = goodSuffix.c2iplus1
      c10 = goodSuffix.c2iplus2
      Ga = goodSuffix.Ga
      tourOrder = goodSuffix.tourOrder
      moveType  = goodSuffix.moveType
      if moveType != move_type_0: # connecting move
        gainFromCloseUp = Ga - distance(c10, c1)
        if gainFromCloseUp > 0:
          improved = true
          Make_5opt_Move(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10,
                         tourOrder)
          tourLen = tourLen - gainFromCloseUp
          Set_DLB_off(DontLook,
                     [c1, c2, c3, c4, c5, c6, c7, c8, c9, c10])
          break evaluate_promising_moves

      when true: # not OPT_6_IMPLEMENTED:
        # below we try to use general subsequent move
        # after temporary applying 5-opt move
        c2subseq = c10
        cLast = c10

        LinksAddedClear()
        AddtoLinksAdded(c2, c3)
        AddtoLinksAdded(c4, c5)
        AddtoLinksAdded(c6, c7)
        AddtoLinksAdded(c8, c9)
        Make_5opt_Move(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10,
                       tourOrder)
        Set_DLB_off(DontLook,
                   [c1, c2, c3, c4, c5, c6, c7, c8, c9, c10])
        searching = true
        SubseqLvl = 0
        while searching:
          SubseqLvl = SubseqLvl + 1
          improved = LK_SubsequentMove(c1, c2subseq, Ga, cLast)
          if improved:
            break evaluate_promising_moves
          else: # not improved
            if c2subseq == cLast: # end of promising moves
              Restore_Tour()
              Restore_DLB()
              searching = false
            else:
              c2subseq = cLast
          if SubseqLvl > Max_Depth:
            Restore_Tour()
            Restore_DLB()
            searching = false
    #end_loop for mve
  #end_block evaluate_promising_moves

  result = improved

Lin-Kernighan algorithm basics – part 11

Lin-Kernighan algorithm idea is to try the most promising sequences, therefore we should rather sort candidates by decreasing accumulated gain, not by their distance from the last city used (order of nearest neighbors). So, for example:

type
  Suffix = object
    c2iplus1, c2iplus2: City_Number
    Ga: Length_Gain
    moveType: int
    tourOrder: int

proc SortSufficesByGain(goodSufficesList: var seq[Suffix]) =
  # sort the list to have the most promising at top
  sort(goodSufficesList) do (x,y: Suffix) -> int:
       result = cmp(y.Ga, x.Ga)

proc LK_2Move(c1, c2: City_Number;
              G1a: Length_Gain): bool =
...
  var
    goodSuffix: Suffix
    goodSufficesList: seq[Suffix]
    breadth: int
...
  block find_promising_moves:
    goodSufficesList = @[]  # empty list (sequence)
    for c3 in neighbors(c2):
      if tried_c3 > 2*Max_Breadth_1: # note multiplier
        break find_promising_moves
...
    
      c3_succ = t_succ(c3)
      c3_pred = t_pred(c3)
      for c4 in [c3_pred, c3_succ]:
        if fwd and (c4 == c3_succ)  or
           not fwd and (c4 == c3_pred):
          tourOrder = TO_1234
          moveType  = move_type_0
        else:
          tourOrder = TO_1243
          moveType  = move_type_2
        #end_if fwd...
        tried_c3 = tried_c3 + 1
        G2a = G1 + distance(c3, c4)
        goodSuffix = Suffix(c2iplus1: c3, c2iplus2: c4,
                            Ga: G2a,
                            tourOrder: tourOrder, moveType: moveType)
        goodSufficesList.add(goodSuffix)
      #end_loop for c4
    #end_loop for neighbor_number
  #end_block find_promising_moves

  block evaluate_promising_moves:
    if len(goodSufficesList) == 0:
      # no promising moves
      break evaluate_promising_moves
    SortSufficesByGain(goodSufficesList)
    breadth = min(len(goodSufficesList), Max_Breadth_1)
    for mve in 0 .. breadth-1:
      goodSuffix = goodSufficesList[mve]
      c3 = goodSuffix.c2iplus1
      c4 = goodSuffix.c2iplus2     
      Ga = goodSuffix.Ga
      tourOrder = goodSuffix.tourOrder
      moveType  = goodSuffix.moveType
      if moveType != move_type_0: # connecting move
        gainFromCloseUp = Ga - distance(c4, c1)
        if gainFromCloseUp > 0:
          improved = true
          Make_2opt_Move(c1, c2, c3, c4)
          tourLen = tourLen - gainFromCloseUp
          Set_DLB_off(DontLook, [c1, c2, c3, c4])
          break evaluate_promising_moves
      if LK_3Move(c1, c2, c3, c4,
                  Ga, tourOrder):
        improved = true
        break evaluate_promising_moves
  #end_block evaluate_promising_moves

  result = improved

An alternative for sorting candidates

Instead of sorting we can use simpler solution used in original Lin-Kernighan algorithm that is: each time we consider two links to remove we should try the longer link as the first one. Then for example:

proc LK_2Move(c1, c2: City_Number;
              G1a: Length_Gain): bool =

  var
    c4_A, c4_B:  City_Number
...
  block find_promising_moves:
    for c3 in neighbors(c2):
...
      c3_succ = t_succ(c3)
      c3_pred = t_pred(c3)
      
      if distance(c3, c3_succ) > distance(c3, c3_pred):
        c4_A = c3_succ
        c4_B = c3_pred
      else:        
        c4_A = c3_pred
        c4_B = c3_succ

      for c4 in [c4_A, c4_B]:
        if fwd and (c4 == c3_succ)  or
           not fwd and (c4 == c3_pred):
          tourOrder = TO_1234
          moveType  = move_type_0
        else:
          tourOrder = TO_1243
          moveType  = move_type_2
        #end_if fwd...
        tried_c3 = tried_c3 + 1
        G2a = G1 + distance(c3, c4)
        if moveType != move_type_0: # connecting move
          gainFromCloseUp = G2a - distance(c4, c1)
          if gainFromCloseUp > 0:
            # improving move found
            improved = true
            Make_2opt_Move(c1, c2, c3, c4)
            tourLen = tourLen - gainFromCloseUp
            Set_DLB_off(DontLook, [c1, c2, c3, c4])
            break find_promising_moves

        if LK_3Move(c1, c2, c3, c4,
                    G2a, tourOrder):
          improved = true
          break find_promising_moveses
      #end_loop for c4
    #end_loop for neighbor_number
  #end_block find_promising_moves