Iterated local search approach using genetic transformation to the traveling salesman problem
Kengo Katayama, Hiroyuki Narihisa · 1999
When giving different approximate solutions that are near the optimal solution for a combinatorial optimization problem, these solutions may share several important or common parts. This empirical conjecture is often employed in developing good algorithms for solving combinatorial optimization problems. In this paper, we propose a new iterated local search (ILS) approach incorporating this conjecture for the symmetric traveling salesman problem. To escape from local optimum found by a local search procedure to another, standard ILS algorithms generally have an useful technique called the double-bridge move. However, in our approach we deal with two approximate solutions, which contain many edges which are not shared parts of these solutions. These edges are cleverly reconnected to create a newly escaped solution. From our experimental results, it was observed that our ILS algorithms could find better solution qualities with fewer iterations than standard ILS algorithms for well-known benchmarks of the TSPLIB. In particular, we showed that one algorithm combined with the Lin-Kernighan heuristic was a very high-performance approach.