Hybrid Ejection Chain Methods for the Traveling Salesman Problem

Local search such as Ejection Chain Methods (ECMs) based on the stem-and-cycle (S&C) reference structure, Lin-Kernighan (LK) heuristics, as well as the recently proposed Multi-Neighborhood Search (MNS), are among the most competitive algorithms for the Traveling Salesman Problem (TSP). In this paper, we carry out a large-scale experiment with all 110 symmetric instances from the TSPLib to investigate the performances 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, not just their end results. This leads to one of the most comprehensive comparisons of these algorithms to date. We introduce a new, improved S&C-ECM that can outperform LK and MNS. We then develop new hybrid versions of our ECM implementations by combining them with Evolutionary Algorithms and Population-based Ant Colony Optimization (PACO). We compare them to similar hybrids of LK and MNS. Our results show that hybrid PACO-S&C, PACO-LK and PACO-MNS are all very efficient. We also find that the full runtime behavior comparison provides deeper and clearer insights, while focusing on end results only would have led to a misleading conclusion.