Doubly-rooted stem-and-cycle ejection chain algorithm for the asymmetric traveling salesman problem

Ejection chain methods, which include the classical Lin–Kernighan (LK) procedure and the Stem‐and‐Cycle (S&C) reference structure, have been the source of the currently leading algorithms for large scale symmetric traveling salesman problems (STSP). Although these methods proved highly effective in generating large neighborhoods for symmetric instances, their potential application to the asymmetric setting of the problem (ATSP) introduces new challenges that require special consideration. This article extends our studies on the single‐rooted S&C to examine the more advanced doubly‐rooted (DR) reference structure. The DR structure, which is allied both to metaheuristics and network optimization, allows more complex network‐related (alternating) paths to transition from one tour to another, and offers special advantages for the ATSP. Computational experiments on an extensive testbed exhibits superior performance for the DR neighborhood over its LK counterpart for the ATSP. We additionally show that a straightforward implementation of a DR ejection chain algorithm outperforms the best local search algorithms and obtains solutions comparable to those obtained by the currently most advanced special‐purpose algorithms for the ATSP, while requiring dramatically reduced computation time.