Premium
Doubly‐rooted stem‐and‐cycle ejection chain algorithm for the asymmetric traveling salesman problem
Author(s) -
Rego César,
Gamboa Dorabela,
Glover Fred
Publication year - 2016
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21676
Subject(s) - travelling salesman problem , algorithm , combinatorial optimization , computer science , metaheuristic , chain (unit) , computation , testbed , mathematical optimization , mathematics , computer network , physics , astronomy
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. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(1), 23–33 2016