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.
