Minimum and maximum length of link as a speed-up

Any 2-opt or 3-opt move that improves a tour move must fulfill the condition:

addLength < delLength

Sum of length of links added must be less than sum of links removed from tour.

In the case of 2-opt the inquity can be written as:

$$d(X1, Y1) + d(X2, Y2) \lt d(X1, X2) + d(Y1, Y2)$$

We can speed-up the search for improving moves by avoiding considering all elements of this inequity.

One method of doing this is fixed radius search. We search for Y1 (or for Y2) inside a the circle centered at X1 and radius to equal the distance between X1 and X2. Moves with both Y's outside the circle do not improve the tour. Unfortunatelly, this method requires symmetrical searching, which could be inconvenient, especiallly when used with some other speed-ups.

However still: in an improving move one or two longer links are removed and then one or two shorter links are added. Suppose that we know the two distances:

$$d(X1, X2), d(X1, Y1)$$

then the inquity has the form:

distance(X1, Y1) + link_added_len < distance(X1, X2) + link_deleted_len

Situation is the better, the bigger link_deleted_len is and the smaller link_added_len is. The maximum value for link_deleted_len is equal to maxLenInTour, which is the length of the longest link in current tour. The mininum value for link_added_len is equal to minLenInSet, which is the length of the shortest of all possible links beetwen cities in the problem (for simplicity we do not exclude links already in current tour, this way minLenInSet is a constant value for the dataset).

var
  minLenInSet, maxLenInTour: Length

  # 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]))

So if for some Y1 we have got:

distance(X1, Y1) + minLenInSet > distance(X1, X2) + maxLenInTour

then there is no possibility that any 2-opt move with X1, X2 and Y1 could improve the tour, no matter which of the two Y1's tour neighbours we would like to choose for Y2.

Similarilly, we can ommit candidates for 3-opt moves. Consider for example:

distance(X1, Y1) + distance(Y1, Z1) + minLenInSet >
    distance(X1, X2) + distance(Y1, Y2) + maxLenInTour

distance(X1, Y1) + 2 * minLenInSet > 
    distance(X1, X2) + distance(Y1, Y2) + maxLenInTour

distance(X1, Y1) + 2 * minLenInSet >
    distance(X1, X2) + 2 * maxLenInTour