An Improved Local Search:Ejection Chain Method And Hybrid Algorithms For The Traveling Salesman Problem

As one of the most well-know NP-hard problems in the domain of combination optimization,the Traveling Salesman Problem(TSP)has many applications in produc-tion,such as logistics planning and circuit board printing.The study of this problem is of great significance not only for practical applications but also for scientific research.The Ejection Chain Method(ECM)for the TSP was introduced in 1992 and shown to be competitive to the famous Lin-Kernighan(LK)heuristic.In this thesis,we inves-tigate the ECM algorithm and its hybrids for the TSP.We improve the original ECM in several ways and conduct large-scale experiments.In contrast to other studies that only focus on the end result of the experiment,we use several different runtime measures and analyze the progress of the algorithm throughout their complete run.We make four main contributions.Firstly,we develop a more efficient ECM-based local search algorithm making improvements compared with the original version,in-cluding the design of a much more efficient data structure particularly suitable for the characteristics of ECMs,change the root node candidate collection size and adjust the termination criterion.The improved ECM can solve 28%more of the 110 benchmark instances than the original ECM in finding the global optima.Secondly,a large-scale experiment is carried out,deeply analyzing the perfor-mance of ECMs throughout the optimization process and compare them with LK heuris-tic local search(LS)algorithms.Thirdly,because local search and combined local search algorithms(LS-LS hy-brids)are prone to fall into local optima,we add a crossover operator to the combined local search algorithms.We obtain a new class of heuristics,the LS-LS-X hybrids,which can solve,respectively,28%and 41%more of the 110 benchmark instances than the original LS-LS and their component algorithms.Finally,we combine the LS-LS and LS-LS-X hybrid algorithms with Evolution-ary Computation(EC)methods,namely Evolutionary Algorithms and Population-based Ant Colony Optimization.The resulting EC-LS-LS-X hybrids are limited to 1 hour to solve the problem with scale of 85900,and the best resulting solution is only 4.85%longer than the global optimal solution.