An improved ejection chain method and its hybrid versions for solving the traveling salesman problem

Abstract

<p>Local search algorithms such as Ejection Chain Methods (ECMs) based on the stem-and-cycle (S&C) reference structure, Lin-Kernighan (LK) heuristics, Tabu Search (TS) as well as the recently proposed Multi-Neighborhood Search (MNS) have been found to be highly competitive for solving the Traveling Salesman Problem (TSP). In this paper, we carry out a large-scale experimental study with all 110 symmetric instances from the TSPLib to investigate the performance of these algorithms. Our study is different from previous work along this line of research in that we consider the entire runtime behavior of the algorithms rather than just their end results. This leads to one of the most comprehensive comparisons of these algorithms using the TSP instances. We then introduce an improved S&C-ECM (named FSM**) that can outperform LK, TS, and MNS. In order to further boost the performance, we develop new hybrid versions of our ECM implementations by combining them with Evolutionary Algorithms and Population-based Ant Colony Optimization. We compare them to similar hybrids of LK, TS, and MNS. Our results show that hybrid algorithms of S&C-ECM, LK, TS and MNS are all very efficient for solving the TSP. We also find that the full runtime behavior comparison provides deeper and clearer insights, while focusing on end results only could have led to a misleading conclusion.</p>