4-opt* – general idea, part 2

The second crucial part of 4-opt* idea is to examine only a specific cases of potentially improving moves.

Any k-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. It is therefore necessary (though insufficient) that at least one of added links is shorter than one of removed links. Lengths of all four links removed in 4-opt* procedure are (see schemes below):

delLen_1 = distance(tour[i], tour[(i+1) mod N])
delLen_2 = distance(tour[j], tour[(j+1) mod N])
delLen_3 = distance(tour[k], tour[(k+1) mod N])
delLen_4 = distance((k+1) mod N], tour[(k+2) mod N])

We take the length of the longest of them:

delLenMax = max(delLen_1, max (delLen_2, max(delLen_3, delLen_4)))

We determine that to reconnect the cities we always add the link to city in position k+1 either from city in position i+1 or from city in j and that we take the shorter of these two links:

addLen_1 = distance(tour[(i+1) mod N], tour[(k+1) mod N])
addLen_2 = distance(tour[(j) mod N], tour[(k+1) mod N])

addLenMin = min(addLen1, addLen2)

Possible cases of reconnection and gain from them are tested only if:

addLenMin < delLenMax

This test guarantees that at least this added link is shorter than at least one of the links removed. If the condition is not met, then cases of 4-opt* move are not examined. This way we examine only one of two classes of moves:

Fixed links in 4-opt* moves

Class A	Class B

So for given i, j, k we consider only one class of reconnections: A or B. Either class have only 8 cases of reconnection (see below), as opposed to 48 cases in standard 4-opt. Moreover, since the scheme of class B is symmetrical to the scheme of class A, then cases of reconnection for class B will be also symmetrical to cases for class A.

4-opt* move: reconnection cases of class A

2-opt move
3-opt moves
4-opt moves