Improved Lin-Kernighan Local Search And Hybrid Algorithms For The Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is one of the most important combinatorial optimization problems, with many applications in science and practice. In this thesis, local search (LS) approaches and Evolutionary Computation (EC) methods are investi-gated in order to solve the TSP more efficiently. We focus on the Lin-Kernighan (LK) heuristic and hybrid algorithms based on it for the TSP.We have made five main contributions. First, we investigated a state-of-art lo-cal search, the LK heuristic. We developed a very competitive implementation of this heuristic by designing a new highly-efficient data structure, randomizing the algorithm, and experimentally finding good parameter settings. Second, we carried out a much larger experimental study than any other research work on the LK heuristic to date and give a balanced and detailed performance report. Third, based on this study, we showed that different LS approaches have different strengths and weaknesses. We then proposed the novel idea of pairwise hybridizing different LS approaches to create new hybrid LS methods combining these strengths. Our new LS-LS hybrid approaches are better than the pure LS approaches which serve as their components. Fourth, we hybridized Evo-lutionary Algorithms (EAs) and Population-Based Ant Colony Optimization (PACO) with both pure and hybrid LS approaches. Our results show that these new hybrid algo-rithms have significantly better performances than any other algorithms in our study and the past works with the TSP Suite framework, which we used for our experiments. Even when dealing with TSP instances with large scales, our hybrid algorithms can quickly find good solutions. Fifth and last, we designed a novel crossover operator for the TSP based on the LK heuristic. Our experiments show that our new crossover operator has a better performance than a state-of-the-art operator for the TSP, Edge crossover, which indicates that our idea of a crossover operator based on an LS approaches is promising.