```
proc One_City_3_Opt_NDM(tour: var Tour_Array;
basePos: Tour_Index;
neighbor: Neighbor_Matrix;
position: var City_Position_In_Tour;
numberOfNeigbors: int;
DontLook: var DLB_Array;
minLenInSet: Length;
maxLenInTour: var Length): bool =
type
Move3 = object
i, j, k: Tour_Index
optCase: Reconnection_3_optCase
gain: Length_Gain
var
improved: bool
i, j, k: Tour_Index
ii, jj, kk: Tour_Index
X1, X2, Y1, Y2, Z1, Z2: City_Number
A1, A2, B1, B2, C1, C2: City_Number
gainExpected: Length_Gain
goodMove: Move3
d1, d2: Length
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:
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)
else:
continue
d2 = distance(X1, Y1) + minLenInSet
if d2 + minLenInSet > distance(X1, X2) + 2 * maxLenInTour:
break
d1 = distance(X1, X2) + distance(Y1, Y2) + maxLenInTour
if d2 + minLenInSet > d1:
continue
for neighbor_2 in 0 .. numberOfNeigbors-1:
Z2 = neighbor[X1][neighbor_2]
k = (position[Z2] + N - 1) mod N
Z1 = tour[k]
if (Z2 == Y2) or (Z1 == Y2) or
(Z1 == X1) or (Z1 == X2) or
(Y1 == X1) or (Y1 == X2):
continue
if d2 + distance(Y1, Z1) > d1:
break
if Between(i, j, k):
jj = j
kk = k
(A1, A2, B1, B2, C1, C2) = (X1, X2, Y1, Y2, Z1, Z2)
else:
jj = k
kk = j
(A1, A2, B1, B2, C1, C2) = (X1, X2, Z1, Z2, Y1, Y2)
for optCase in opt3_case_4 .. opt3_case_7:
gainExpected = Gain_From_3_Opt(A1, A2, B1, B2, C1, C2,
optCase)
if gainExpected > goodMove.gain:
improved = true
goodMove = Move3(i: i, j: jj, k: kk,
optCase: optCase, gain: gainExpected)
if improved:
A1 = tour[goodMove.i]
A2 = tour[(goodMove.i + 1) mod N]
B1 = tour[goodMove.j]
B2 = tour[(goodMove.j + 1) mod N]
C1 = tour[goodMove.k]
C2 = tour[(goodMove.k + 1) mod N]
Set_DLB_off(DontLook, [A1, A2, B1, B2, C1, C2])
Make_3_Opt_Move(tour,
goodMove.i, goodMove.j, goodMove.k,
goodMove.optCase, position)
case goodMove.optCase
of opt3_case_1:
maxLenInTour = max( maxLenInTour, max(distance(A1,B1),
distance(A2,B2)) )
of opt3_case_4:
maxLenInTour = max( maxLenInTour, max(distance(A1,B1),
max(distance(A2,C1),
distance(B2,C2)) ) )
of opt3_case_5:
maxLenInTour = max( maxLenInTour, max(distance(A1,C1),
max(distance(A2,B2),
distance(B1,C2)) ) )
of opt3_case_6:
maxLenInTour = max( maxLenInTour, max(distance(A1,B2),
max(distance(A2,C2),
distance(B1,C1)) ) )
of opt3_case_7:
maxLenInTour = max( maxLenInTour, max(distance(A1,B2),
max(distance(A2,C1),
distance(B1,C2)) ) )
else:
echo "Should not happen: ", goodMove.optCase
maxLenInTour = distance(tour[0], tour[N-1])
for pos in 0 .. N-2:
maxLenInTour = max(maxLenInTour,
distance(tour[pos], tour[pos+1]))
#end goodMove.optCase
result = improved
```

```
proc LS_3_Opt_NDM(tour: var Tour_Array;
neighbor: Neighbor_Matrix;
neighborListLen: int = N-1) =
## Optimizes the given tour using 3-opt with neighbor lists
## Don't Look Bits (DLB) and min-max Links
var
locallyOptimal: bool = false
improved: bool
DontLook: DLB_Array
baseCity: City_Number
position: City_Position_In_Tour
maxLenInTour: Length
let numberOfNeigbors = min(neighborListLen, len(neighbor[0]))
position = Create_Position_In_Tour(tour)
#[
# NOTE: minLenInSet is constant for the dataset
minLenInSet = high(Length)
for city_A in 0 .. N-1:
for city_B in (city_A+1) .. N-1:
minLenInSet = min(minLenInSet, distance(city_A, city_B))
]#
maxLenInTour = distance(tour[0], tour[N-1])
for pos in 0 .. N-2:
maxLenInTour = max(maxLenInTour, distance(tour[pos], tour[pos+1]))
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_NDM(tour, basePos, neighbor, position,
numberOfNeigbors, DontLook,
minLenInSet, maxLenInTour)
if not improved:
Set_DLB_on(DontLook, baseCity)
else:
locallyOptimal = false
```