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 K-Opt moves.
A K-Opt 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 K-opt Moves for the Lin-Kernighan TSP Heuristic"
.
The paper changes the problem of performing a K-Opt to the problem of transforming a signed permutation that consists of a single K-cycle 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 4-Opt 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 K-Opt to the problem of transforming a signed permutation that consists of a single K-cycle 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_(i-1)
- 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 K-Opt move been applied)
- sign(P[i]) = +1 if s[i] has the same orientation in the tour after the K-Opt 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 4-Opt 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)
- 2-opt(t2, t1, t8, t7)
- 2-opt(t4, t3, t2, t7)
- 2-opt(t7, t4, t5, t6)