## Friday, March 17, 2017

### The idea

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.

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.

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. This would make implementation simpler, but would require more memory, because of storing numbers (lengths), which are longer than booleans.

### 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 DLBs algorithms. Random planar problems, N=100.
Problem # Method Time Best Avg Worst
1NN100100.00112.31122.36
NN + 2opt114693.0997.73104.89
NN + 2opt-DLB31394.4299.86104.98
2NN100100.00108.83124.17
NN + 2opt146286.1690.2097.26
NN + 2opt-DLB29387.8291.2696.06
3NN100100.00106.21115.53
NN + 2opt156682.1985.7789.56
NN + 2opt-DLB31382.6687.3992.24
4NN100100.00105.83112.36
NN + 2opt114690.0294.7898.19
NN + 2opt-DLB21391.6494.9199.78
5NN100100.00111.19119.81
NN + 2opt78191.9195.4399.81
NN + 2opt-DLB29391.8196.31102.66
6NN100100.00112.89126.03
NN + 2opt136094.3599.05104.02
NN + 2opt-DLB20696.0299.56105.29
7NN100100.00109.35117.75
NN + 2opt114690.4793.2899.21
NN + 2opt-DLB31390.5593.8099.71
8NN100100.00109.02120.22
NN + 2opt125386.5091.8898.31
NN + 2opt-DLB31388.4592.6495.84
9NN100100.00108.79116.77
NN + 2opt94095.4697.58101.63
NN + 2opt-DLB42095.5098.14102.77
10NN100100.00105.40113.11
NN + 2opt126882.1285.6689.87
NN + 2opt-DLB29381.7886.4090.22