Instead of don't look bits speedup we can use an array indexed by city numbers, in which each element contains length of tour after improving from given city. The algorithm using has the following scheme:
var
tourLen: tourLen # current length of tour
tourLenArr: array[City_Number, tourLen]
# calculate initial length of tour
tourLen = distance(tour[N-1], tour[0])
for pos in 0 .. N-2:
tourLen = tourLen + distance(tour[pos], tour[pos+1])
# initialise array of tour lengths with some arbitrary
# value different from current value of 'tourLen'
for city in 0 .. N-1:
tourLenArr[city] = 1 #
# main loop
for pos in 0 .. N-1:
baseCity = tour[pos]
if (tourLen == tourLenArr[baseCity]):
continue
improved = Improve(baseCity) # MUST update 'tourLen' value!
tourLenArr[baseCity] = tourLen
#end_for
proc One_City_3_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 =
type
Move3 = object
i, j, k: Tour_Index
optCase: Reconnection_3_optCase
gain: Length_Gain
var
improved: bool
i, j, k: Tour_Index
X1, X2, Y1, Y2, Z1, Z2: City_Number
k_6, k_7: Tour_Index
Z1_6, Z2_6, Z1_7, Z2_7: City_Number
gainExpected: Length_Gain
goodMove: Move3
improved = false
goodMove.gain = 0
block three_loops:
for direction in [forward, backward]:
if direction == forward:
i = basePos
else:
i = (N + basePos - 1) mod N
X1 = tour[i]
X2 = tour[(i+1) mod N]
for neighbor_1 in 0 .. numberOfNeigbors-1:
# new edges in optCase=6: *X1-Y2*, Y1-Z1, X2-Z2
# new edges in optCase=7: *X1-Y2*, X2-Z1, Y1-Z2
Y2 = neighbor[X1][neighbor_1]
j = (position[Y2] + N - 1) mod N
Y1 = tour[j]
if (Y1 != X1) and (Y1 != X2):
gainExpected = Gain_From_2_Opt(X1, X2, Y1, Y2)
if gainExpected > goodMove.gain:
improved = true
goodMove = Move3(i: i, j: j, k: j,
optCase: opt3_case_1, gain: gainExpected)
for neighbor_2 in 0 .. numberOfNeigbors-1:
# new edges in optCase=6: X1-Y2, *Y1-Z1*, X2-Z2
Z1_6 = neighbor[Y1][neighbor_2]
k_6 = position[Z1_6]
Z2_6 = tour[(k_6 + 1) mod N]
# new edges in optCase=7: X1-Y2, X2-Z1, *Y1-Z2*
Z2_7 = neighbor[Y1][neighbor_2]
k_7 = (position[Z2_7] + N - 1) mod N
Z1_7 = tour[k_7]
if Between(i, j, k_6):
gainExpected = Gain_From_3_Opt(X1, X2, Y1, Y2, Z1_6, Z2_6,
opt3_case_6)
if gainExpected > goodMove.gain:
improved = true
goodMove = Move3(i: i, j: j, k: k_6,
optCase: opt3_case_6, gain: gainExpected)
if Between(i, j, k_7):
gainExpected = Gain_From_3_Opt(X1, X2, Y1, Y2, Z1_7, Z2_7,
opt3_case_7)
if gainExpected > goodMove.gain:
improved = true
goodMove = Move3(i: i, j: j, k: k_7,
optCase: opt3_case_7, gain: gainExpected)
if improved:
Set_DLB_off(DontLook,
[ tour[goodMove.i], tour[(goodMove.i + 1) mod N],
tour[goodMove.j], tour[(goodMove.j + 1) mod N],
tour[goodMove.k], tour[(goodMove.k + 1) mod N] ])
Make_3_Opt_Move(tour,
goodMove.i, goodMove.j, goodMove.k,
goodMove.optCase, position)
result = improved
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 and 3-opt algorithms. Random planar problems, N=100.
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
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
Procedures to calculate the gain from 3-opt move and to make 3-opt move assume that their parameters (cities and their indices in tour) are given in the order of ascending indices of tour array (modulo N). Therefore we need a function to recognize whether three indices are in this order, or: whether in this orientation the middle index is between the two boundary indices.
proc Between(a, x, b: Tour_Index): bool =
## Returns true if `x` is between `a` and `b` in cyclic sequence
## with established orientation of nondescending indices
# That is: when one begins a forward traversal of the tour
# at position `a', then position `x` is reached before position `b'.
# Returns true if and only if:
# a < x < b or b < a < x or x < b < a
if (b > a):
result = (x > a) and (x < b)
elif (b < a):
result = (x > a) or (x < b)
else:
result = false
Note the additional speed-up: the link between base city X1 and its tour neighbor X2 is not considered when at least one of these cities has its don’t-look bit set to on.
proc One_City_3_Opt_DLB(tour: var Tour_Array,
basePos: Tour_Index,
DontLook: var DLB_Array): bool =
type
Move3 = object
i, j, k: Tour_Index
optCase: Reconnection_3_optCase
var
improved: bool
i, j, k: Tour_Index
X1, X2, Y1, Y2, Z1, Z2: City_Number
gainExpected: Length_Gain
optCase: Reconnection_3_optCase
goodMove: Move3
improved = false
block three_loops:
for direction in [forward, backward]:
if direction == forward:
i = basePos
else:
i = (N + basePos - 1) mod N
X1 = tour[i]
X2 = tour[(i+1) mod N]
if isDLB_on(DontLook,X1) or isDLB_on(DontLook,X2): # NOTE
continue
for counter_2 in 0 .. N-1:
j = counter_2 # second cut after j
Y1 = tour[j]
Y2 = tour[(j+1) mod N]
if (X1 == Y1) or (X2 == Y1) or (Y2 == X1):
continue
# examine 2-opt move (see: opt3_case_1 .. opt3_case_3)
gainExpected = Gain_From_2_Opt(X1, X2, Y1, Y2)
if gainExpected > 0:
goodMove = Move3(i: i, j: j, k: j,
optCase: opt3_case_1)
improved = true
break three_loops
for counter_3 in 0 .. N-1:
k = counter_3 # third cut after k
Z1 = tour[k]
Z2 = tour[(k+1) mod N]
if (X1 == Z1) or (Y1 == Z1):
continue
if not Between(i, j, k):
continue
# examine pure 3-opt cases
for optCase in [opt3_case_6, opt3_case_7]:
gainExpected = Gain_From_3_Opt(X1, X2, Y1, Y2, Z1, Z2,
optCase)
if gainExpected > 0:
goodMove = Move3(i: i, j: j, k: k,
optCase: optCase)
improved = true
break three_loops
# end_block three_loops
if improved:
Set_DLB_off(DontLook, [X1, X2, Y1, Y2])
if goodMove.optCase > opt3_case_3:
Set_DLB_off(DontLook, [Z1, Z2])
Make_3_Opt_Move(tour,
goodMove.i, goodMove.j, goodMove.k,
goodMove.optCase)
result = improved
proc LS_3_Opt_DLB(tour: var Tour_Array) =
## Optimizes the given tour using 3-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_3_Opt_DLB(tour, basePos, DontLook)
if not improved:
Set_DLB_on(DontLook, baseCity)
else:
locallyOptimal = false
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 3-opt with DLB algorithms. Random planar problems, N=100.
proc One_City_25_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, V0: 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:
Make_2_Opt_Move(tour, i, j)
improved = true
else:
V0 = tour[(i+2) mod N]
if V0 != Y1:
if Gain_From_Node_Shift(X1, X2, V0, Y1, Y2) > 0:
Set_DLB_off(DontLook, V0)
Make_Node_Shift_Move(tour, (i+1) mod N, j)
improved = true
else:
V0 = tour[(N+j-1) mod N]
if V0 != X2:
if Gain_From_Node_Shift(V0, Y1, Y2, X1, X2) > 0:
Set_DLB_off(DontLook, V0)
Make_Node_Shift_Move(tour, j, i)
improved = true
#end_if Gain_From_2_Opt...
if improved:
Set_DLB_off(DontLook, [X1, X2, Y1, Y2])
break two_loops
result = improved
proc LS_25_Opt_DLB(tour: var Tour_Array) =
## Optimizes the given tour using 2.5-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_25_Opt_DLB(tour, basePos, DontLook)
if not improved:
Set_DLB_on(DontLook, baseCity)
else:
locallyOptimal = false
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.
