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.
