The simplest sequential move consist of two steps, that is of two link exchanges. Obvious example of such move is 2-opt move. We can describe it using tour order notation:
2-opt move = 12-43
The following question arises: does any combination of numbers 1,2,3,4 describe some sequential move? Let us take for example: 13-24. This cannot be a sequential move, because by definition first pair of cities in sequential move must be a pair of tour neighbors. The same for second and every other pair. This means that each pair of numbers in the record must contain two consecutive numbers, in one or the other order.
Therefore there are only four combinations of numbers 1,2,3,4 that actually describe sequential moves:
First pair
12
21
Second pair
34
12-34
21-34
43
12-43
21-43
The corresponding diagrams are as follows:
Forward
Move 12-34
Move 12-43
Backward
Move 21-34
Move 21-43
As we can see, moves starting with 21- are "backward moves" and their schemes are simply mirror images of their "forward" counterparts. Therefore we will no longer consider features of "backward" moves and we will focus on "forward" moves, that is moves which notation begins with 12-.
So there are only two sequential moves consisting of two steps, that is of two link exchanges: 12-34 and 12-43.
Move 12-43 is 2-opt move; we already know it and it does not require further comments.
Move 12-34is a sequential move, despite the fact that it disconnects tour into two disjoint cycles. It may seem not useful and tempting to change the definition of a sequential move, but moves of this kind, although not producing valid tours, can be a part of connecting sequential move.
If we look closer to these diagrams we can notice that only two pure 3-opt moves: 12-43-65 and 12-56-43 come from 12-43 sequential move, that is from 2-opt move. The other two moves: asymmetric 12-65-34 and symmetric 12-56-34 come from disconnecting 12-34 sequential move. That is why we do not narrow the definition of a sequential move and actually consider disconnecting sequential moves — to have a consistent method of extending 2-exchange moves into full set of 3-moves, 3-moves to 4-moves and so on.
Origins of pure 3-opt moves from shorter sequential moves
12-34
12-65-34
12-56-34
12-43
12-56-43
12-43-65
We can notice that above table does not contain all possibilities of inserting a pair (5,6) or (6,5) into sequences 12-34 and 12-43. Moves 12-34-56, 12-34-65, 12-65-43 and 12-43-56 are missing, because they do not describe valid (connecting) 3-opt moves. Let us take a look at the last of them:
12-43-56
This is a disconnecting sequential move and we would not consider it when we want to narrow our searching to valid 2-opt and 3-opt moves. On the other way it leads to four valid sequential 4-opt moves (12-87-43-56, 12-78-43-56, 12-43-78-56, 12-43-87-56), so if we would like to consider all valid sequential 4-opt moves, then we should not omit it while building a sequential move step by step.
Let us take a look at diagrams of two 3-opt sequential moves:
Move A
Move B
In both cases, A and B, the same set of cities is used to make a move: {c1, c2, c3, c4, c5, c6}, or: the same set of positions in tour. However, schemes for each of these two moves are different, and therefore the results would be different.
How can we distinguish between move of type A and of type B then?
We can use simple and unambiguous notation: by indicating the tour order of cities involved, starting from c1.
Let us take move A: we start from c1 and move along the tour clockwise. The next city from the set is c2 (second city engaged in move), then we encounter c4 (that is: fourth city of move), c3 (third city of move), c6 (sixth city of move) and c5 (fifth city of move). The tour order of cities in this sequential move is: c1, c2, c4, c3, c6, c5, so the move can be described as 12-43-65.
Move A = 12-43-65
Move B = 12-56-43
In move B the tour order of cities is: c1, c2, c5, c6, c4, c3, so this move can be described as 12-56-43.
This notation is simple, unambiguous and natural. Thanks to it we no longer need to use some arbitrary numbers as labels for each type of 3-opt move, not saying anything about scheme of given move. Moreover, this notation can be used to identify a scheme of any other sequential move, for example sequential 4-opt moves, 5-opts and so on.
Let us consider 2-opt move described in the following way:
Step 0:
Start from certain city c1 on tour.
Step 1:
Remove link between c1 and one of its tour neighbors, c2.
Add link between c2 and some other city c3.
Step 2:
Remove link between c3 and its tour neighbor c4.
Add link between c4 and the first city c1, to close the tour.
Note that steps 1 and 2 have the same scheme: remove a link between a city and its tour neighbor and then add link between this neighbor and some other city. Each step exchanges two links.
Example of 3-opt sequential move
We can extend 2-opt move to 3-opt move using the same scheme. Step 1 would be the same as in 2-opt move, so we show the procedure from step 2. Note that the only difference is in part B of this step:
Step 2:
Remove link between c3 and its tour neighbor c4.
Add link between c4 and the some other city c5.
Step 3:
Remove link between c5 and its tour neighbor c6.
Add link between c6 and the first city c1, to close the tour.
Example of 4-opt sequential move
Step 3:
Remove link between c5 and its tour neighbor c6.
Add link between c6 and the some other city c7.
Step 4:
Remove link between c7 and its tour neighbor c8.
Add link between c8 and the first city c1, to close the tour.
General scheme of a sequential move
As we can see the general scheme of sequential move is as follows:
Step 1
Remove link between c1 and its tour neighbor c2.
Add link between c2 and some c3.
Step 2
Remove link between c3 and its tour neighbor c4.
Add link between c4 and some c5.
...
Last step can close the tour this way:
Remove link between c_2k1 and its tour neighbor c_2k.
Add link between c_2k and the first city c1, to close the tour.
The cyclic tour before 3-opt asymmetric move can be described as consisting of three consecutive segments:
A B C = B C A = C A B
The 3-opt asymmetric move showed on the diagram transforms the tour into the form:
A' B' C
where symbol prime (') after a letter means that the segment is reversed.
Reversing whole tour doesn't change it, only its natural orientation is reversed, so:
A' B' C = (A' B' C)' = (C)' (B')' (A')' = C' B A
Tour is cyclic, therefore:
C' B A = A C' B = B A C'
This shows us three methods of obtaining result from 3-opt move:
A B C ==> A' B' C
C A B ==> A C' B
B C A ==> C' B A
In each method different segment remains unchanged in its original place, so we can use this fact to speed up the procedure of making the move.
proc Make_3_Opt_Asym_Move_Fast(tour: var Tour_Array;
p1, p2, p3, p4, p5, p6: Tour_Index;
position: var City_Position_In_Tour) =
var
city: City_Number
left, right: Tour_Index
segment: seq[City_Number] # max. N/2 elements
move_method: int
# the tour consists of three consecutive segments:
# [p6,p1] [p2,p3] [p4,p5] == A B C
# A B C == B C A == C A B
# there are three ways of *performing* the very same
# 3-opt asymmetric move, in each different segment remains
# intact in its original place:
# 1) A B C ==> A' B' C -- doesn't touch C
# 2) C A B ==> A C' B -- doesn't touch B
# 3) B C A ==> C' B A -- doesn't touch A
# Method 1, used so far, is default, but when segment B or A
# has many cities compared to segment C then we choose
# method 2 or 3, to not change the longest segment
let size_A = (N + p1 - p6 + 1) mod N
let size_B = (N + p3 - p2 + 1) mod N
let size_C = (N + p5 - p4 + 1) mod N
let sizeMax = max(size_A, max(size_B, size_C))
move_method = 1
if sizeMax == size_B:
move_method = 2
elif sizeMax == size_A:
move_method = 3
case move_method
of 1: # default method, not changing segment C
...
of 2: # not changing segment B
...
of 3: # not changing segment B
...
else: # we use only 3 methods of performing asym. 3-opt move
discard
The first, traditional method is as follows:
case move_method
of 1: # default method, not changing segment C
# A B C ==> A' B' C
# reverse segment A in place:
left = p6
right = p1
for counter in 1 .. size_A div 2:
city = tour[right]
tour[right] = tour[left]
tour[left] = city
position[tour[left]] = left
position[tour[right]] = right
left = t_succ(left)
right = t_pred(right)
# reverse segment B in place:
left = p2
right = p3
for counter in 1 .. size_B div 2:
city = tour[right]
tour[right] = tour[left]
tour[left] = city
position[tour[left]] = left
position[tour[right]] = right
left = t_succ(left)
right = t_pred(right)
The second method is:
case move_method
...
of 2: # not changing segment B
# C A B ==> A C' B
# make a copy of segment C=[p4,p5]:
segment = newSeq[City_Number](size_C)
left = p4
for pos in 0 .. size_C-1:
segment[pos] = tour[left]
left = t_succ(left)
# move segment A backward, it should end at p4:
left = p6
right = p4
for counter in 1 .. size_A:
tour[right] = tour[left]
position[tour[right]] = right
left = t_succ(left)
right = t_succ(right)
# put copy of reversed C before B in tour:
right = p1
for pos in 0 .. size_C-1:
tour[right] = segment[pos]
position[tour[right]] = right
right = t_pred(right)
The third method is:
case move_method
...
of 3: # not changing segment A
# B C A ==> C' B A
# make a copy of reversed segment C=[p4,p5]:
segment = newSeq[City_Number](size_C)
right = p5
for pos in 0 .. size_C-1:
segment[pos] = tour[right]
right = t_pred(right)
# shift segment B forward, it should end at p5:
left = p3
right = p5
for counter in 1 .. size_B:
tour[right] = tour[left]
position[tour[right]] = right
left = t_pred(left)
right = t_pred(right)
# put the copy of reversed C in its new place in tour:
left = p2
for pos in 0 .. size_C-1:
tour[left] = segment[pos]
position[tour[left]] = left
left = t_succ(left)
Alternative version
Above solution has two disadvantages. Firstly, it is quite complex. Secondly, methods 2 and 3 have to use temporary variable to store whole segment C during shifting segment A or B.
Thanks to properties of inversion operation the second disadvantage can be eliminated:
(C A')' = (A')' C' = A C'
Therefore we can replace method 2 by:
case move_method
...
of 2: # not changing segment B
# C A B ==> ==> C A' B ==> A C' B
# reverse segment A in place:
left = p6
right = p1
for counter in 1 .. size_A div 2:
city = tour[right]
tour[right] = tour[left]
tour[left] = city
left = t_succ(left)
right = t_pred(right)
# reverse segment (A'C) in place:
left = p4
right = p1
for counter in 1 .. (size_A+size_C) div 2:
city = tour[right]
tour[right] = tour[left]
tour[left] = city
left = t_succ(left)
right = t_pred(right)
# update position[] array:
left = p4
for pos in 0 .. size_A+size_C:
position[tour[left]] = left
left = t_succ(left)
and method 3 by:
case move_method
...
of 3: # not changing segment A
# B C A ==> B' C A ==> C' B A
# reverse segment B in place:
left = p2
right = p3
for counter in 1 .. size_B div 2:
city = tour[right]
tour[right] = tour[left]
tour[left] = city
left = t_succ(left)
right = t_pred(right)
# reverse segment (B'C) in place:
left = p2
right = p5
for counter in 1 .. (size_B+size_C) div 2:
city = tour[right]
tour[right] = tour[left]
tour[left] = city
left = t_succ(left)
right = t_pred(right)
# update position[] array:
left = p2
for pos in 0 .. size_B+size_C:
position[tour[left]] = left
left = t_succ(left))
This alternative versions of speedup methods, although does not need additional memory for segment variable, could be somewhat slower than more complex versions shown first, and in fact is not very elegant.
Final version
We can use Swap_Segments() procedure to make the implementation of this speedup both concise and clear, although probably slightly slower than the complex version shown first and still using additional variable to store a segment during swap:
case move_method
of 1: # default method, not changing segment C
Reverse_Segment(tour, p6, p1, position)
Reverse_Segment(tour, p2, p3, position)
of 2: # not changing segment B
Reverse_Segment(tour, p4, p5, position)
Swap_Segments(tour, p4, p5, p6, p1, position)
of 3: # not changing segment A
Reverse_Segment(tour, p4, p5, position)
Swap_Segments(tour, p2, p3, p4, p5, position)
else: # we use only 3 methods of performing asym. 3-opt move
discard
proc Swap_Segments(tour: var Tour_Array;
start_1, end_1, start_2, end_2: Tour_Index;
position: var City_Position_In_Tour) =
## Swaps two consecutive segments of tour:
## [start_1, end_1] and [start_2, end_2]
## NOTE: start_2 should be tour successor of end_1
var
left, right: Tour_Index
segment: seq[City_Number]
let size_1 = (N + end_1 - start_1 + 1) mod N
let size_2 = (N + end_2 - start_2 + 1) mod N
# make a copy of first segment:
segment = newSeq[City_Number](size_1)
right = end_1
for pos in 0 .. size_1-1:
segment[pos] = tour[right]
right = t_pred(right)
# move second segment backward, it should start at start_1:
left = start_2
right = start_1
for counter in 1 .. size_2:
tour[right] = tour[left]
position[tour[right]] = right
left = t_succ(left)
right = t_succ(right)
# put the copy of first segment in its new place in tour:
left = end_2
for pos in 0 .. size_1-1:
tour[left] = segment[pos]
position[tour[left]] = left
left = t_pred(left)
If segment reversing is used as an independent 2-opt move, not as a part of sequence (e.g. to apply 3-opt move), then we can take advantage of the fact that the tour is cyclic. Therefore reversing a segment has the same effect as reversing its complementary segment and changing "natural orientation" of the tour array.
Using array representation of tour causes that reversing a segment is done by swapping elements of array. The number of swaps (thus the amount of time) needed to reverse a segment is proportional to the number of cities the segment consists of. So when the segment to reverse is longer than half of tour, then can we reverse the complementary segment to speed-up the transformation.
proc t_pred(pos: Tour_Index): Tour_Index {.inline.} =
## returns position of tour predecessor for given position
result = (N + pos - 1) mod N
proc t_succ(pos: Tour_Index): Tour_Index {.inline.} =
## returns position of tour successor for given position
result = (pos + 1) mod N
proc Make_2_Opt_Move_Fast(tour: var Tour_Array;
p1, p2, p3, p4: Tour_Index;
position: var City_Position_In_Tour) =
## Reverses order of elements in segment [p2, p3] of tour:
## if the complementary segment is shorter, reverses the complementary
# Assumes: p1==t_pred(p2), p4==t_succ(p3)
var
city: City_Number
left, right: Tour_Index
inversionSize: int
inversionSize = (p3 - p2 + 1)
if inversionSize < 0:
inversionSize = inversionSize + N
if (2 * inversionSize > N): # segment longer than half of tour
left = p4 # t_succ(p3)
right = p1 # t_pred(p2)
inversionSize = N - inversionSize
else:
left = p2
right = p3
inversionSize = inversionSize div 2
for counter in 1 .. inversionSize:
city = tour[right]
tour[right] = tour[left]
tour[left] = city
position[tour[left]] = left
position[tour[right]] = right
left = t_succ(left)
right = t_pred(right)
#end_for counter loop
