Dynasearch – the idea of set of independent moves

So far we have been dealing with the simplest methods in which a single optimization step is a single improving move of given type (for example 2-opt, 2.5-opt, 3-opt). In more advanced methods, a single step is an improving set of moves. An example of such algorithms is the dynasearch method.

In the dynasearch approach we use dynamic programming algorithm to look for the best set consisting of independent improving moves. Two moves are called independent when, regardless of the order in which they are applied, the resulting tour is the same. For example two 2-opt moves are independent when they do not overlap (their ranges do not overlap):

independent moves	non-independent moves

This means that none of the endpoints of the second move cannot be between the endpoints of the first move.

So for pairs in which the two positions are in ascending order:

0 <= i1 < ... < j1 <= N-1, where i1+1 != j1 and j1+1 != i1

and

0 <= i2 < ... < j2 <= N-1, where i2+1 != j2 and j2+1 != i2

the two 2-opt moves are independent if:

j1 < i2 or j2 < i1

2-opt dynasearch on average is faster than traditional best improvement approach and gives slightly better results. Unfortunatelly, running times are far longer than those for 3-opt with neighbor lists, which gives better results and is much simpler to implement.

Beware

But what when the endpoints of a move are not in ascending order of indices? Let us consider the following:

If the first move is defined by the pair (3, N-2) then the moves are not independent, because all links involved in second move would be affected by changes made by the first move (case A). But if the first move is defined by the pair (N-2, 3) then the two moves are independent (case B):

case A reversing the segment without the city on position 0	case B reversing the segment with the city on position 0

How is it possible that in one case the moves are independent and in the other they are not, when they seem to produce the same tour, differing only in orientation?

The main difference and the problem with case A is that the first move by reversing a segment simultaneously changes the tour positions (indices) of the cities it contains, so after this move i2, i2+1, j2, j2+1 no longer point at the same cities and links they pointed at before the move. So if we found the second move and set up the values for i2, j2 independently from any other move, not assuming that the move (i1, j1) would be apllied before, then after this first move these values are wrong. This does not happen in case B.

But on the other hand, unfortunatelly in case B we cannot apply the rule:

j1 < i2 or j2 < i1

to check independence of the two moves, because the inequity i1 < j1 is not satisfied.

More general condition for independent 2-opt moves is:

Two moves are independend when every city involved in one move comes before every city involved in second move or vice versa.