A short description of our iterative Lin-Kernighan heuristic
and its experiments
H. D. Nguyen, I. Yoshihara, K. Yamamori, and M. Yasunaga
Contact to: ndhung@taurus.cs.miyazaki-u.ac.jp
Here is a short description of our implementations. There are two main
modifications in our implementations.
First, we used some extra data structures together with the two-level
tree to implement the temporary flip operation in a constant time (with
the condition that the depth of the search is bounded) and the permanent
flip operation in O(N**0.5) time. Of course the time complexities of
other operations (next, prev, between) are constant. I think that the
idea of the segment tree may be modified to work with the two-level tree
to gain the same time complexity with our implementation but have not
tested this yet. The original segment tree has designed to work with the
array data structure, thus the time complexity of permanent flip
operation is O(N).
The second modification is that we check for a sequence of moves which
consists of a valid 5-opt move followed by any valid 3-opt move as a
basic move. This follows Helsgaun's idea. However, Helsgaun used 5-opt
move as a basic move, making the running time of his implementation
enormous (although the tour quality is very good). By choosing a valid
3-opt move as a basic move, we try to balance between the tour quality
and the running time. As a result, our implementation can handle the
one-million-city instance (and even bigger if the memory of our
computer allows) in a reasonable CPU time.
Other modifications are minor. We use backtracking for searching the
first 5-opt move. The breadths of the search are (3,3,2,2), i.e. 3 first
best choices for x2, 3 first best choices for x4, 2 first best choices
for x6, and 2 first best choices x8. With a given x0, both candidates
for x1 are checked. The depth of the search is limited to 100.
For speeding up the algorithm, we used the don't look bit concept, a
cache mechanism like the one described by Bentley, and an extra cache
that stores the lengths of all edges of the current tour.