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
proc One_City_2_Opt_N_Best_From_City(tour: var Tour_Array;
basePos: Tour_Index;
neighbor: Neighbor_Matrix;
position: var City_Position_In_Tour;
numberOfNeigbors: int): bool =
## Makes the best of improving moves starting from given city
type
Move2 = object
i, j: Tour_Index
gain: Length_Gain
var
improved: bool
pos_Y2, i, j: Tour_Index
X1, X2, Y1, Y2: City_Number
gainExpected: Length_Gain
bestMove: Move2
improved = false
bestMove.gain = 0
block two_loops:
for direction in [forward, backward]:
if direction == forward:
i = basePos
X1 = tour[i]
X2 = tour[(i+1) mod N]
else:
i = (N + basePos - 1) mod N
X2 = tour[i]
X1 = tour[(i+1) mod N] # == tour[basePos]
for neighbor_number in 0 .. numberOfNeigbors-1:
Y1 = neighbor[X1][neighbor_number]
if direction == forward:
j = position[Y1]
Y2 = tour[(j+1) mod N]
else:
j = (N + position[Y1] - 1) mod N # pos[Y1] == j+1
Y2 = tour[j]
if (X2 == Y1) or (Y2 == X1):
continue
gainExpected = Gain_From_2_Opt(X1, X2, Y1, Y2)
if gainExpected > bestMove.gain:
bestMove = Move2(i: i, j: j, gain: gainExpected)
improved = true
if improved:
Make_2_Opt_Move(tour, bestMove.i, bestMove.j, position)
result = improved
proc LS_2_Opt_N_BC(tour: var Tour_Array;
neighbor: Neighbor_Matrix;
neighborListLen: int = N-1) =
## Optimizes tour using 2-opt with neighbor lists and fixed radius,
## for each city makes the best of improving moves that starts from it
var
locallyOptimal: bool = false
improved: bool
position: City_Position_In_Tour
let numberOfNeigbors = min(neighborListLen, len(neighbor[0]))
position = Create_Position_In_Tour(tour)
while not locallyOptimal:
locallyOptimal = true
for basePos in 0 .. N-1:
improved = One_City_2_Opt_N_Best_From_City(tour, basePos,
neighbor, position,
numberOfNeigbors)
if improved:
locallyOptimal = false
Some simple statistics
Relative time, best length, average length and worst length for all tours created by NN heuristic and improved by some 2-opt algorithms. Random planar problems, N=200.
This example of code does not contain any new ideas and can be skipped by a reader.
proc One_City_2_Opt_NDR(tour: var Tour_Array;
basePos: Tour_Index;
neighbor: Neighbor_Matrix;
position: var City_Position_In_Tour;
numberOfNeigbors: int;
DontLook: var DLB_Array;
useDLB: bool;
useFixedRadius: bool): bool =
var
improved: bool
pos_Y2, i, j: Tour_Index
X1, X2, Y1, Y2: City_Number
d_X1_X2, d_X1_Y1: Length
improved = false
block two_loops:
for direction in [forward, backward]:
if direction == forward:
i = basePos
X1 = tour[i]
X2 = tour[(i+1) mod N]
else:
i = (N + basePos - 1) mod N
X2 = tour[i]
X1 = tour[(i+1) mod N] # == tour[basePos]
d_X1_X2 = distance(X1, X2)
for neighbor_number in 0 .. numberOfNeigbors-1:
# after 2-opt move new tour would contain direct link X1-Y1,
# so we look for city Y1 among cities that are close to city X1
Y1 = neighbor[X1][neighbor_number]
if direction == forward:
j = position[Y1]
Y2 = tour[(j+1) mod N]
else:
j = (N + position[Y1] - 1) mod N # pos[Y1] == j+1
Y2 = tour[j]
if (X2 == Y1) or (Y2 == X1):
# 2-opt is for non-adjacent links only
# by constuction X1 != Y1
continue
d_X1_Y1 = distance(X1, Y1)
if useFixedRadius:
if d_X1_Y1 > d_X1_X2:
break
# the same as: Gain_From_2_Opt(X1, X2, Y1, Y2) > 0
if (d_X1_X2 + distance(Y1, Y2)) -
(d_X1_Y1 + distance(X2, Y2)) > 0:
if useDLB:
Set_DLB_off(DontLook, [X1, X2, Y1, Y2])
Make_2_Opt_Move(tour, i, j, position)
improved = true
break two_loops
result = improved
proc LS_2_Opt_NDR(tour: var Tour_Array;
neighbor: Neighbor_Matrix;
neighborListLen: int = N-1;
useDLB: bool = true;
useFixedRadius: bool = true) =
## Optimizes the given tour using 2-opt with neighbor lists
## and with optional Don't Look Bits (DLB) and fixed radis
var
locallyOptimal: bool = false
improved: bool
DontLook: DLB_Array
baseCity: City_Number
position: City_Position_In_Tour
let numberOfNeigbors = min(neighborListLen, len(neighbor[0]))
position = Create_Position_In_Tour(tour)
if useDLB:
Set_DLB_off(DontLook, tour)
while not locallyOptimal:
locallyOptimal = true
for basePos in 0 .. N-1:
baseCity = tour[basePos]
if useDLB and isDLB_on(DontLook, baseCity):
continue
improved = One_City_2_Opt_NDR(tour, basePos, neighbor, position,
numberOfNeigbors, DontLook,
useDLB, useFixedRadius)
if improved:
locallyOptimal = false
else:
if useDLB:
Set_DLB_on(DontLook, baseCity)
proc One_City_2_Opt_ND(tour: var Tour_Array;
basePos: Tour_Index;
neighbor: Neighbor_Matrix;
position: var City_Position_In_Tour;
numberOfNeigbors: int;
DontLook: var DLB_Array): bool =
var
improved: bool
pos_Y2, i, j: Tour_Index
X1, X2, Y1, Y2: City_Number
improved = false
block two_loops:
for direction in [forward, backward]:
if direction == forward:
i = basePos
X1 = tour[i]
X2 = tour[(i+1) mod N]
else:
i = (N + basePos - 1) mod N
X2 = tour[i]
X1 = tour[(i+1) mod N] # == tour[basePos]
for neighbor_number in 0 .. numberOfNeigbors-1:
Y1 = neighbor[X1][neighbor_number]
if direction == forward:
j = position[Y1]
Y2 = tour[(j+1) mod N]
else:
j = (N + position[Y1] - 1) mod N # pos[Y1] == j+1
Y2 = tour[j]
if (X2 == Y1) or (Y2 == X1):
continue
if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
Set_DLB_off(DontLook, [X1, X2, Y1, Y2])
Make_2_Opt_Move(tour, i, j, position)
improved = true
break two_loops
result = improved
proc LS_2_Opt_ND(tour: var Tour_Array;
neighbor: Neighbor_Matrix;
neighborListLen: int = N-1) =
## Optimizes the given tour using 2-opt with neighbor lists
## and dDon't Look Bits (DLB)
var
locallyOptimal: bool = false
improved: bool
DontLook: DLB_Array
baseCity: City_Number
position: City_Position_In_Tour
let numberOfNeigbors = min(neighborListLen, len(neighbor[0]))
position = Create_Position_In_Tour(tour)
Set_DLB_off(DontLook, tour)
while not locallyOptimal:
locallyOptimal = true
for basePos in 0 .. N-1:
baseCity = tour[basePos]
if isDLB_on(DontLook, baseCity):
continue
improved = One_City_2_Opt_ND(tour, basePos, neighbor, position,
numberOfNeigbors, DontLook)
if not improved:
Set_DLB_on(DontLook, baseCity)
else:
locallyOptimal = false
proc One_City_2_Opt_NR(tour: var Tour_Array;
basePos: Tour_Index;
neighbor: Neighbor_Matrix;
position: var City_Position_In_Tour;
numberOfNeigbors: int): bool =
var
improved: bool
pos_Y2, i, j: Tour_Index
X1, X2, Y1, Y2: City_Number
radius: Length
improved = false
block two_loops:
for direction in [forward, backward]:
if direction == forward:
i = basePos
X1 = tour[i]
X2 = tour[(i+1) mod N]
else:
i = (N + basePos - 1) mod N
X2 = tour[i]
X1 = tour[(i+1) mod N] # == tour[basePos]
radius = distance(X1, X2)
for neighbor_number in 0 .. numberOfNeigbors-1:
Y1 = neighbor[X1][neighbor_number]
if direction == forward:
j = position[Y1]
Y2 = tour[(j+1) mod N]
else:
j = (N + position[Y1] - 1) mod N # pos[Y1] == j+1
Y2 = tour[j]
if (X2 == Y1) or (Y2 == X1):
continue
if distance(X1, Y1) > radius:
break
if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
Make_2_Opt_Move(tour, i, j, position)
improved = true
break two_loops
result = improved
proc LS_2_Opt_NR(tour: var Tour_Array;
neighbor: Neighbor_Matrix;
neighborListLen: int = N-1) =
## Optimizes tour using 2-opt with neighbor lists and fixed radius
var
locallyOptimal: bool = false
improved: bool
position: City_Position_In_Tour
let numberOfNeigbors = min(neighborListLen, len(neighbor[0]))
position = Create_Position_In_Tour(tour)
while not locallyOptimal:
locallyOptimal = true
for basePos in 0 .. N-1:
improved = One_City_2_Opt_NR(tour, basePos, neighbor,
position, numberOfNeigbors)
if improved:
locallyOptimal = false
proc One_City_2_Opt_N(tour: var Tour_Array;
basePos: Tour_Index;
neighbor: Neighbor_Matrix;
position: var City_Position_In_Tour;
numberOfNeigbors: int): bool =
## Optimizes the given tour using 2-opt with neighours lists
# For each edge looks for improvement considering neigbours
# in ascending order of their distance
var
improved: bool
pos_Y2, i, j: Tour_Index
X1, X2, Y1, Y2: City_Number
improved = false
block two_loops:
for direction in [forward, backward]:
if direction == forward:
i = basePos
X1 = tour[i]
X2 = tour[(i+1) mod N]
else:
i = (N + basePos - 1) mod N
X2 = tour[i]
X1 = tour[(i+1) mod N] # == tour[basePos]
for neighbor_number in 0 .. numberOfNeigbors-1:
# after 2-opt move new tour would contain direct link X1-Y1,
# so we look for city Y1 among cities that are close to city X1
Y1 = neighbor[X1][neighbor_number]
if direction == forward:
j = position[Y1]
Y2 = tour[(j+1) mod N]
else:
j = (N + position[Y1] - 1) mod N # pos[Y1] == j+1
Y2 = tour[j]
if (X2 == Y1) or (Y2 == X1):
# 2-opt is for non-adjacent links only
# by constuction X1 != Y1
continue
if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
Make_2_Opt_Move(tour, i, j, position)
improved = true
break two_loops
result = improved
proc LS_2_Opt_N(tour: var Tour_Array;
neighbor: Neighbor_Matrix;
neighborListLen: int = N-1) =
## Optimizes the given tour using 2-opt with neighbor lists
var
locallyOptimal: bool = false
improved: bool
position: City_Position_In_Tour
let numberOfNeigbors = min(neighborListLen, len(neighbor[0]))
position = Create_Position_In_Tour(tour)
while not locallyOptimal:
locallyOptimal = true
for basePos in 0 .. N-1:
improved = One_City_2_Opt_N(tour, basePos, neighbor,
position, numberOfNeigbors)
if improved:
locallyOptimal = false
Some simple statistics
Relative time, best length, average length and worst length for all tours created by NN heuristic and improved by 2-opt and 2-opt with neighbor lists (number of neighbors in parentheses). Random planar problems, N=100.
holds if at least one of the two conditions is met:
or
The inequity (a) means that for given (X1, X2) we can search for Y2 among those cities that are closer to X2 than is X1.
But alternatively the inequity between the two sums may be considered as a pair of inequities:
or
The inequity (c) means that for given (X1, X2) we can search for Y1 among those cities that are closer to X1 than is X2.
In fixed radius search we can use either (a) or (c), the radius is the same. When fixed radius searching is used with DLB, then probably searching around X1 for Y1 would be better – because we would rather prefer to not miss a good move for base city (X1) before activating its don’t look bit. When we want to continue searching and moving in given direction, then probably searching for Y2 around X2 could be better idea.
proc One_City_2_Opt_DLBR2(tour: var Tour_Array,
basePos: Tour_Index,
DontLook: var DLB_Array): bool =
var
improved: bool
i, j: Tour_Index
X1, X2, Y1, Y2: City_Number
radius: Length
improved = false
block two_loops:
for direction in [forward, backward]:
if direction == forward:
i = basePos
X1 = tour[i]
X2 = tour[(i+1) mod N]
else:
i = (N + basePos - 1) mod N
X2 = tour[i]
X1 = tour[basePos] # == tour[(i+1) mod N]
radius = distance(X1, X2)
for counter_2 in 0 .. N-1:
j = counter_2
Y1 = tour[j]
Y2 = tour[(j+1) mod N]
if direction == backward:
swap(Y1, Y2)
if (X1 == Y1) or (X2 == Y1) or (Y2 == X1):
continue
if distance(X1, Y1) > radius: # NOTE
continue
if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
Set_DLB_off(DontLook, [X1, X2, Y1, Y2])
Make_2_Opt_Move(tour, i, j)
improved = true
break two_loops
result = improved
This example of code does not contain any new ideas and can be skipped by a reader.
proc One_City_2_Opt_DLBR(tour: var Tour_Array,
basePos: Tour_Index,
DontLook: var DLB_Array): bool =
var
improved: bool
i, j: Tour_Index
X1, X2, Y1, Y2: City_Number
radius: Length
improved = false
block two_loops:
for direction in [forward, backward]:
if direction == forward:
i = basePos
X1 = tour[i]
X2 = tour[(i+1) mod N]
else:
i = (N + basePos - 1) mod N
X2 = tour[i]
X1 = tour[basePos] # == tour[(i+1) mod N]
radius = distance(X1, X2)
for counter_2 in 0 .. N-1:
j = counter_2
Y1 = tour[j]
Y2 = tour[(j+1) mod N]
if direction == backward:
swap(Y1, Y2)
if (X1 == Y1) or (X2 == Y1) or (Y2 == X1):
continue
if distance(X2, Y2) > radius:
continue
if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
Set_DLB_off(DontLook, [X1, X2, Y1, Y2])
Make_2_Opt_Move(tour, i, j)
improved = true
break two_loops
result = improved
proc LS_2_Opt_DLBR(tour: var Tour_Array) =
## Optimizes the given tour using 2-opt with Don't Look Bits (DLB)
## and fixed radius search
var
locallyOptimal: bool = false
improved: bool
DontLook: DLB_Array
baseCity: City_Number
Set_DLB_off(DontLook, tour)
while not locallyOptimal:
locallyOptimal = true
for basePos in 0 .. N-1:
baseCity = tour[basePos]
if isDLB_on(DontLook, baseCity):
continue
improved = One_City_2_Opt_DLBR(tour, basePos, DontLook)
if not improved:
Set_DLB_on(DontLook, baseCity)
else:
locallyOptimal = false
Fixed radius search uses the property of the inequity which a 2-opt move must meet to improve a tour.
We can benefit from this even more, but only when we consider links in the two orientations and the two symmetric forms.
forward (ABCD)
backward (DCBA)
implementation
look forward
look backward
Using this scheme we cannot miss an improving move even if we restrict possible choices to one inequity.
Example implementation:
type
Orientation = enum forward, backward
proc One_City_2_Opt_R(tour: var Tour_Array,
basePos: Tour_Index): bool =
var
improved: bool
i, j: Tour_Index
X1, X2, Y1, Y2: City_Number
radius: Length
improved = false
block two_loops:
for direction in [forward, backward]:
if direction == forward:
i = basePos
X1 = tour[i]
X2 = tour[(i+1) mod N]
else:
i = (N + basePos - 1) mod N
X2 = tour[i]
X1 = tour[basePos] # == tour[(i+1) mod N]
radius = distance(X1, X2)
for counter_2 in 0 .. N-1:
j = counter_2
Y1 = tour[j]
Y2 = tour[(j+1) mod N]
if direction == backward:
swap(Y1, Y2)
if (X1 == Y1) or (X2 == Y1) or (Y2 == X1):
continue
if distance(X2, Y2) > radius:
continue
if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
Make_2_Opt_Move(tour, i, j)
improved = true
break two_loops
result = improved
proc LS_2_Opt_R(tour: var Tour_Array) =
## Optimizes the given tour using 2-opt with fixed radius search
var
locallyOptimal: bool = false
improved: bool
while not locallyOptimal:
locallyOptimal = true
for basePos in 0 .. N-1:
improved = One_City_2_Opt_R(tour, basePos)
if improved:
locallyOptimal = false
holds if at least one of the two conditions is met:
or
Simple radius search with 2-opt
Note that for simplicity of the code below we do not change orientation and instead use both conditions.
proc LS_2_Opt_simpleRadius(tour: var Tour_Array) =
var
locallyOptimal: bool = false
i, j: Tour_Index
X1, X2, Y1, Y2: City_Number
radius: Length
while not locallyOptimal:
locallyOptimal = true
block two_loops:
for counter_1 in 0 .. N-1:
i = counter_1
X1 = tour[i]
X2 = tour[(i+1) mod N]
radius = distance(X1, X2)
for counter_2 in 0 .. N-1:
j = counter_2
Y1 = tour[j]
Y2 = tour[(j+1) mod N]
if (X1 == Y1) or (X2 == Y1) or (Y2 == X1):
continue
if distance(X2, Y2) > radius:
if distance(X1, Y1) > radius:
continue
if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
Make_2_Opt_Move(tour, i, j)
locallyOptimal = false
break two_loops
Some simple statistics
Relative time, best length, average length and worst length for all tours created by NN heuristic and improved by 2-opt and 2-opt with simple radius search algorithms. Random planar problems, N=100.
proc isDLB_on(DontLook: DLB_Array,
city: City_Number): bool =
return DontLook[city]
proc Set_DLB_on(DontLook: var DLB_Array,
city: City_Number) =
DontLook[city] = true
proc Set_DLB_off(DontLook: var DLB_Array,
city: City_Number) =
DontLook[city] = false
proc Set_DLB_off(DontLook: var DLB_Array,
cities: openArray[City_Number]) =
# turns off DLB for given cities
for city in 0 .. len(cities)-1:
DontLook[cities[city]] = false
proc One_City_2_Opt_DLB(tour: var Tour_Array,
basePos: Tour_Index,
DontLook: var DLB_Array): bool =
var
improved: bool
i, j: Tour_Index
X1, X2, Y1, Y2: City_Number
improved = false
block two_loops:
for direction in [forward, backward]: # NOTE: both tour neighbors
# consider link between t[i] and t[i+1],
# then between t[i-1] and t[i]
if direction == forward:
i = basePos
else:
i = (N + basePos - 1) mod N
X1 = tour[i]
X2 = tour[(i+1) mod N]
for counter_2 in 0 .. N-1:
j = counter_2
Y1 = tour[j]
Y2 = tour[(j+1) mod N]
if (X1 == Y1) or (X2 == Y1) or (Y2 == X1):
continue
if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
Set_DLB_off(DontLook, [X1, X2, Y1, Y2])
Make_2_Opt_Move(tour, i, j)
improved = true
break two_loops
result = improved
proc LS_2_Opt_DLB(tour: var Tour_Array) =
## Optimizes the given tour using 2-opt with Don't Look Bits (DLB)
var
locallyOptimal: bool = false
improved: bool
DontLook: DLB_Array
baseCity: City_Number
Set_DLB_off(DontLook, tour)
while not locallyOptimal:
locallyOptimal = true
for basePos in 0 .. N-1:
baseCity = tour[basePos]
if isDLB_on(DontLook, baseCity):
continue
improved = One_City_2_Opt_DLB(tour, basePos, DontLook)
if not improved:
Set_DLB_on(DontLook, baseCity)
else:
locallyOptimal = false
A local improvement algorithm can be made faster when we notice that the running time includes the time to needed perform the move, but also the time needed to examine possible good moves and find an improving move (if there is one).
If for a given city X1 we previously did not find any improving move and it still has the same neighbors (none of the links between this city and its neighbors has been changed), then chances that we will find an improving move for this city in current iteration are small (although non-zero, see below).
The concept based on this observation is known as don’t look bits (DLB). We use special flag for each of the cities. Initially all the flags are turned off, which means that we allow searching for improving moves starting from given city. When a search for improving move starting from city C fails, then the bit for this city is turned on. When a move is performed in which this city is involved as one of the endpoints of the exchanged links, then the bit for this city is turned off. When we consider candidates for X1, the first city of an improving move, we skip all cities which have their don’t-look bits set to on.
Comments
Consider also what happens with DLB when we examine moves “in one direction” only (see 2-opt basic algorithn). In such case we consider only one of the two links of X1, that is the link to its successor, the link between tour[i] and tour[i+1]. If we failed to found any improving move, then we turn the don’t-look bit for X1 on. If then in some subsequent iteration a move is performed in which X1 is one of the endpoints of the exchanged links, then we turn the don’t-look bit off. It works as expected. But what if a move changes the orientation of the segment in which X1 is inside, but is not at one of its ends? The don’t-look bit remains unchanged, although now the previous predecessor of X1 is its current successor, and we examined X1 only with its succcessor to verify that there are no improvements for X1. So now there could be some improving move for X1 in “forward” orientation, but it will not be examined, because the don’t-look bit for this city is still on.
That is why in the code below we consider both tour neighbors of a given city.
For the same reason of not missing improving moves we do not limit searching to the cases where j>i, but cosider all possible pairs of (i, j).
Aside from the above, it may seem impossible that new, improving move for given city could appear when both neighbors of this city remain unchanged, but let us take a closer look:
However we should notice that in this case cities Y1 and Z1 have their don’t-look bits set to off after making the move. Therefore the new, possibly improving move: from X0 and involving the link between Y1 and Z1, will be examined in one of the subsequent iterations, that is as a move from Y1 or as a move from Z1.
Using Dont' Looks Bits with a simple 2-opt
type
DLB_Array = array[City_Number, bool]
Orientation = enum forward, backward
proc LS_2_Opt_DLB_General_Idea(tour: var Tour_Array) =
## Optimizes the given tour using 2-opt with Don't Look Bits (DLB)
var
locallyOptimal: bool = false
i, j: Tour_Index
pos_2_Limit: Tour_Index
X1, X2, Y1, Y2: City_Number
DontLook: DLB_Array
for city in 0 .. N-1:
DontLook[city] = false
while not locallyOptimal:
locallyOptimal = true
block three_loops:
for counter_1 in 0 .. N-1:
if DontLook[tour[counter_1]]:
continue
for direction in [forward, backward]: # NOTE: both tour neighbors
# consider link between t[i] and t[i+1],
# then between t[i-1] and t[i]
if direction == forward:
i = counter_1
else:
i = (N + counter_1 - 1) mod N
X1 = tour[i]
X2 = tour[(i+1) mod N]
for counter_2 in 0 .. N-1:
j = counter_2 # 2nd cut between t[j] and t[j+1]
Y1 = tour[j]
Y2 = tour[(j+1) mod N]
if (X1 == Y1) or (X2 == Y1) or (Y2 == X1):
# the same city or adjacent cities
continue
if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
DontLook[X1] = false
DontLook[X2] = false
DontLook[Y1] = false
DontLook[Y2] = false
Make_2_Opt_Move(tour, i, j)
locallyOptimal = false
break three_loops
# end_for backward loop
DontLook[tour[counter_1]] = true
# end_for counter_1 loop
It is expected that the resulting tours will be different from the ones from 2-opt First Take procedure.
Relative time, best length, average length and worst length for all tours created by NN heuristic and improved by 2-opt and 2-opt with DLBs algorithms. Random planar problems, N=100.
...
for i in 0 .. N-1: # outer loop is for X1-X2 link
X1 = tour[i]
X2 = tour[(i+1) mod N]
for j in 0 .. N-1: # inner loop is for Y1-Y2 link
Y1 = tour[j]
Y2 = tour[(j+1) mod N]
if (Y1 == X1) or (Y1 == X2) or (Y2 == X1): # not 2-opt
continue
if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
# this move will shorten the tour, apply it at once
Make_2_Opt_Move(tour, i, j)
...
We can save half of iterations by taking an advantage from symmetry of STSP. There is no need to check pair (10,5), since it is the same as pair (5,10) already checked before. Therefore we can safely skip all cases where j is greater than i. Or just start j loop from i+2 value, because X1 and Y1 should not be consecutive cities.
Using the first improving 2-opt move
proc LS_2_Opt(tour: var Tour_Array) =
## Iteratively optimizes given tour using 2-opt moves.
# Shortens the tour by repeating 2-opt moves until no improvement
# can by done; in every iteration immediatelly makes permanent
# change from the first move found that gives any length gain.
var
locallyOptimal: bool = false
i, j: Tour_Index
counter_2_Limit: Tour_Index
X1, X2, Y1, Y2: City_Number
while not locallyOptimal:
locallyOptimal = true
block two_loops:
for counter_1 in 0 .. N-3:
i = counter_1
X1 = tour[i]
X2 = tour[(i+1) mod N]
if i == 0:
counter_2_Limit = N-2
else:
counter_2_Limit = N-1
for counter_2 in (i+2) .. counter_2_Limit:
j = counter_2
Y1 = tour[j]
Y2 = tour[(j+1) mod N]
if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
# this move will shorten the tour, apply it at once
Make_2_Opt_Move(tour, i, j)
locallyOptimal = false
break two_loops
Note that this code still could be changed for some more efficiency: for example Gain_From_2_Opt() called many times in inner loop uses distance(X1, X2) to obtain a value which is an invariable in this loop. You may also notice that Make_2_Opt_Move() is a oneliner identical to calling Reverse_Segment() with one parameter incremented...
Using the best improving 2-opt move
Instead of applying the first move shortening the tour in given iteration we can use the move that gives the best improvement in this iteration:
proc LS_2_Opt_Take_Best(tour: var Tour_Array) =
# Shortens the tour by repeating 2-opt moves until no improvement
# can by done; in every iteration looks for and applies the move
# that gives maximal length gain.
type
Move2 = object
i, j: Tour_Index
gain: Length_Gain
var
locallyOptimal: bool = false
i, j: Tour_Index
X1, X2, Y1, Y2: City_Number
counter_2_Limit: Tour_Index
gainExpected: Length_Gain
bestMove: Move2
while not locallyOptimal:
locallyOptimal = true
bestMove.gain = 0
for counter_1 in 0 .. N-3:
i = counter_1
X1 = tour[i]
X2 = tour[(i+1) mod N]
if i == 0:
counter_2_Limit = N-2
else:
counter_2_Limit = N-1
for counter_2 in (i+2) .. counter_2_Limit:
j = counter_2
Y1 = tour[j]
Y2 = tour[(j+1) mod N]
gainExpected = Gain_From_2_Opt(X1, X2, Y1, Y2)
if gainExpected > bestMove.gain:
bestMove = Move2(i: i,
j: j,
gain: gainExpected)
locallyOptimal = false
# end_for counter_1 loop
if not locallyOptimal:
Make_2_Opt_Move(tour, bestMove.i, bestMove.j)
# end_while not locallyOptimal
Note that this method itself does not guarantee that the resulting tour will be shorter than in the first improvement method (see below).
Some simple statistics
Relative time, best length, average length and worst length for all tours created by NN heuristic and improved by the two 2-opt algorithms. Random planar problems, N=100.
Considering a TSP on Euclidean plane we notice that the optimal tour must be “intersectionless”, that is the tour cannot cross over itself.
The tour without intersection must be shorter because of triangle inequities:
Unfortunatelly, not all TSP cases are Euclidean or even metric... but does it change anything important to the idea focused on “crossings” of two links?
The condition for obtaining an improvement
We usually draw the schematic diagram of a tour as a circle with highlighted points:
Note that here we do not use triangle inequity, and still the tour can be shortened by exchanging two links (hence a name: 2-opt) if:
If the above condition is true, then when we remove links X1-X2 and Y1-Y2 and replace them with links X1-Y1 and X2-Y2, then the tour would become shorter.
This means than for any type of symmetric TSP the tour can be shortened if for some cities the following gain is positive:
proc Gain_From_2_Opt(X1, X2, Y1, Y2: City_Number): Length_Gain =
## Gain of tour length that can be obtained by performing
## given 2-opt move
# Assumes: X2==successor(X1); Y2==successor(Y1)
let del_Length = distance(X1, X2) + distance(Y1, Y2)
let add_Length = distance(X1, Y1) + distance(X2, Y2)
result = del_Length - add_Length
Beware
Note that lack of “crossings” is a necessary, but not sufficient condition for tour to be optimal. A tour without “crossings”, that is a tour which is already fully 2-opted may still be not optimal and then it could be shortened by some other types of moves.
The move
Suppose that we want to transform a tour by making the 2-opt move for:
var
i, j: Tour_Index
X1, X2, Y1, Y2: City_Number
X1 = tour[i]
Y1 = tour[j]
X2 = tour[(i+1) mod N] # the successor of X1
Y2 = tour[(j+1) mod N] # the successor of Y1
From the first look at the diagram it's clear that:
pos. ... i i+1 ... j j+1 ...
before ... -X1-X2- ... -Y1-Y2- ...
after ... -X1-Y1- ... -X2-Y2- ...
But swapping only X2 and Y1 on their positions in tour would be an error.
The order of cities between X2 and Y1 also has been changed:
before ... -X1-X2-b-c-d-Y1-Y2- ...
after ... -X1-Y1-d-c-b-X2-Y2- ...
Therefore the proper solution is to reverse all the segment of tour from X2 to Y1 (see: Reversing a segment):
proc Make_2_Opt_Move(tour: var Tour_Array;
i, j: Tour_Index) =
## Performs given 2-opt move on array representation of the tour
# We cut the cyclic tour in 2 places, by removing 2 links:
# L1: from t[i] to t[i+1] and L2: from t[j] to t[j+1]
# and replacing them with
# L1': from t[i] to t[j] and L2': from t[i+1] to t[j+1]
# This is equivalent to reversing order in segment from 'i+1' to 'j'
Reverse_Segment(tour, (i+1) mod N, j)
One of the standard transformations of a tour used in local optimization is reversing a segment. In the new tour all the cities of the segment occur in reverse order.
pos. 0 1 2 3 4 5 6 7 ...
before A-B-C-D-E-F-G-H-...
after A-B-F-E-D-C-G-H-...
We use the following algorithm: swap the first and the last city of the segment, then the second and one before last, and so on, to the middle of the segment. This way number of swaps is equal half of the segment size.
Beware
We should not forget that a tour is cyclic, and therefore after tour[N-1] city (in ascending order of indices) goes tour[0], to close the tour. Therefore segment from tour[N-2] to tour[2] is 5 cities long — it constists of: tour[N-2], tour[N-1], tour[0], tour[1] and tour[2], in this order. Note that reversing the complementary segment, consisting of the cities on positions from 2 to (N-2), is not the exactly same and in some cases may lead to erroneous results. (But see later reversing a segment given by city numbers, not by positions, more complex and using additional structure, but where this problem does not occur).
proc Reverse_Segment(tour: var Tour_Array;
startIndex, endIndex: Tour_Index) =
## Reverses order of elements in segment [startIndex, endIndex]
## of tour.
## NOTE: Final and initial part of tour make one segment.
## NOTE: While the order of arguments can be safely changed when
## reversing segment in 2-optimization, it makes difference for
## 3-opt move - be careful and do not reverse (x,z) instead of (z,x).
var
left, right: Tour_Index
let inversionSize = ((N + endIndex - startIndex + 1) mod N) div 2
left = startIndex
right = endIndex
for counter in 1 .. inversionSize:
swap(tour[left], tour[right])
left = (left + 1) mod N
right = (N + right - 1) mod N
