So far we have built a set of nested procs for starting move:
LK_1Move() # level 0: c1, c2
LK_2Move() # level 1: c1, c2, c3, c4
LK_3Move() # level 2: c1, c2, c3, c4, c5, c6
LK_4Move() # level 3: c1, c2, c3, c4, c5, c6, c7, c8
While they are sufficient to obtain a solution for sequential 4-opt optimization, the main goal of Lin-Kernighan algorithm is to search beyond k-optimization for some fixed k. When the process of searching reaches level 3 there are two possibilities:
- There is no
c7candidate with positiveG3. Then this is the end of searching for improving sequence. There are no more promising moves for given base city and control returns to previous level, then finally to level 0. - There is some
c7with positiveG3.
When G3 is positive, then it is possible that there would be some promising move also at subsequent level, that is: with positive G4. Regardless whether at level 3 exists such c8 (tour neighbor of c7) that resulting move is improving.
G3 = G2 + distance(c5, c6) - distance(c6, c7)
gainFromCloseUp_atLevel3 = G3 + distance(c7, c8) - distance(c8, c1)
...
G4 = G3 + distance(c7, c8) - distance(c8, c9)
We need a general way to try to extend the sequence by one exchange. Our code for starting move is for maximum 4-opt, we will use general proc for subsequent moves.
Move = StartingMove [+ SubsequentMove [+ SubsequentMove ...]]
The simplest general move for subsequent steps of sequence is 2-opt, and this one is actually used in original Lin-Kernighan algorithm. It differs from the usual 2-opt procedure in that it has to fulfill additional conditions:
- It must continue construction of sequential move.
- It must be designed to be used recursively or in a loop.
What would our LK_SubsequentMove() need to continue any sequence? It must:
- continue given sequence, continue the process of calculating and checking partial sum of gains (that is: it takes value of
Gobtained so far, for given sequence, instead of starting withGequalG0=distance(c1, c2)). - continue given sequence, for the same base city (that is: if starting move starts with
c1, then the first subsequent move must start withc1), - continue given sequence, from the last city used (that is: if starting move ends with
c8, then the first subsequent move must start with breaking the link(c8, c1)as if it was(c2, c1)in starting move). - continue given sequence, with its restrictions on links (that is: it must not remove links added previously, during construction of sequence).
So general idea of using subsequent moves in 4-opt would be (note that we have used don't look bits):
var
SubseqLvl: int # let us make it global for further changes in the code
proc LK_4Move(...) =
...
var
c2subseq, cLast: City_Number
Ga: Length_Gain
...
...
if moveType != move_type_0:
gainFromCloseUp = G4a - distance(c8, c1)
if gainFromCloseUp > 0:
# improving move found
improved = true
Make_4opt_Move(c1, c2, c3, c4, c5, c6, c7, c8,
tourOrder)
tourLen = tourLen - gainFromCloseUp
Set_DLB_off(DontLook, [c1, c2, c3, c4, c5, c6, c7, c8])
break find_promising_moves
when not OPT_5_IMPLEMENTED:
# here we should try to use general subsequent move
# after temporary applying 4-opt move
c2subseq = c8
cLast = c8
Ga = G4a
Save_Tour()
Save_DLB()
LinksAddedClear()
AddtoLinksAdded(c2, c3)
AddtoLinksAdded(c4, c5)
AddtoLinksAdded(c6, c7)
Make_4opt_Move(c1, c2, c3, c4, c5, c6, c7, c8,
tourOrder)
tourLen = tourLen - gainFromCloseUp
Set_DLB_off(DontLook,
[c1, c2, c3, c4, c5, c6, c7, c8])
searching = true
SubseqLvl = 0
while searching:
SubseqLvl = SubseqLvl + 2
# above 2 since each 2-opt subsequent move exchanges 2 links
improved = LK_SubsequentMove(c1, c2subseq,
Ga, cLast)
if improved:
break find_promising_moves
else:
if c2subseq == cLast: # end of promising moves
Restore_Tour()
Restore_DLB()
searching = false
else:
c2subseq = cLast
if SubseqLvl > Max_Depth:
LinksAddedClear()
#end_while searching
#end_when not OPT_5_IMPLEMENTED
...
We need a proc for subsequent moves:
proc LK_SubsequentMove(c1, c2: City_Number;
G1a: var Length_Gain;
cLast: var City_Number): bool =
# cLast is set to c4 when promising move has been found and applied
var
improved: bool
c3, c4: City_Number
c2_pred, c2_succ: City_Number
fwd: bool
G1, Ga: Length_Gain
G2a, gainFromCloseUp: Length_Gain
improved = false
fwd = (c2 == t_succ(c1))
c2_succ = t_succ(c2)
c2_pred = t_pred(c2)
block find_promising_moves:
for c3 in neighbors(c2):
if (c3 == c2_succ) or (c3 == c2_pred):
continue
if isLinkAdded(c2, c3):
continue
G1 = G1a - distance(c2, c3)
if G1 <= 0:
break
# only one choice of c4 gives closed tour
if fwd:
c4 = t_pred(c3)
else:
c4 = t_succ(c3)
if isLinkAdded(c4, c1):
continue
G2a = G1 + distance(c3, c4)
gainFromCloseUp = G2a - distance(c4, c1)
if gainFromCloseUp > 0:
improved = true
# apply promising (or even improving) move
Make_2opt_Move(c1, c2, c3, c4)
tourLen = tourLen - gainFromCloseUp
G1a = G2a
cLast = c4
AddtoLinksAdded(c3, c4)
# don't look bits for c1, c2 should be set at previous level
Set_DLB_off(DontLook, [c3, c4])
# breadth for subsequent general moves is equal 1, so:
break find_promising_moves
#end_loop for neighbor_number
#end_block find_promising_moves
result = improved
