Package org.optaplanner.core.impl.heuristic.selector.move.generic.list.kopt
package org.optaplanner.core.impl.heuristic.selector.move.generic.list.kopt
Contains classes relevant to KOpt moves.
A KOpt move is a move that removes K edges,
and add K new edges that are composed of the removal edges endpoints.
The classes in this package implement the algorithms described in
"An Effective Implementation of Kopt Moves for the LinKernighan TSP Heuristic"
.
The paper changes the problem of performing a KOpt to the problem of transforming a signed permutation that consists of a single Kcycle to the identity permutation. A signed permutation is a permutation where each element have a sign. Let the removed edges be (t_1, t_2), (t_3, t_4), ..., (t_(2k  1), t_2k). Let s_1, s_2, ..., s_k be segments from the original tour that starts and end at two different endpoints of two different removed edges. Additionally, let s_1, s_2, ..., s_k be sorted such that
[t_2, t_4, t_3, t_8, t_7, t_5, t_6, t_1]
and the 4Opt move changes it to
[t2, t_4, t_5, t_7, t_6, t_1, t_8, t_3]
Then
The paper changes the problem of performing a KOpt to the problem of transforming a signed permutation that consists of a single Kcycle to the identity permutation. A signed permutation is a permutation where each element have a sign. Let the removed edges be (t_1, t_2), (t_3, t_4), ..., (t_(2k  1), t_2k). Let s_1, s_2, ..., s_k be segments from the original tour that starts and end at two different endpoints of two different removed edges. Additionally, let s_1, s_2, ..., s_k be sorted such that
 s_1 starts at t_2
 s_2 starts at the successor of the end of s_1
 in general s_i starts at the successor of s_(i1)
 s_k ends at t_1
 s_1 = t_2...t_4
 s_2 = t_3...t_8
 s_3 = t_7...t_5
 s_4 = t_6...t_1
 abs(P[i]) = starting from t_2, he number of segments needed to be transversed to encounter s[i] + 1 (after the KOpt move been applied)
 sign(P[i]) = +1 if s[i] has the same orientation in the tour after the KOpt move been applied, 1 if it been reversed
[t_2, t_4, t_3, t_8, t_7, t_5, t_6, t_1]
and the 4Opt move changes it to
[t2, t_4, t_5, t_7, t_6, t_1, t_8, t_3]
Then
 s_1 = (t_2...t_4), s_2 = (t_3...t_8), s_3 = (t_7...t_5), s_4 = (t_6...t_1)
 P_1 = +1 (first segment encountered, same orientation as original
 P_2 = 4 ((t_8...t_3) is encountered last in the new tour, and it was reversed from (t_3...t_8))
 P_3 = 2 ((t_5...t_7) is second segment encountered in the new tour, and it was reversed from (t_7...t_5)
 P_4 = +3 ((t_6...t_1) is the third segment encountered in the new tour, and has the same orientation.
 (+1 4 [2 +3])
 (+1 [4 3 +2])
 (+1 [2] +3 +4)
 (+1, +2, +3, +4)
 2opt(t2, t1, t8, t7)
 2opt(t4, t3, t2, t7)
 2opt(t7, t4, t5, t6)

ClassDescriptionKOptListMoveSelectorFactory<Solution_>A list that delegates get and set operations to multiple delegates.