Relaxed tours and path ejections for the traveling salesman problem

We describe an edge based ejection chain method to generate compound neighborhood structures for the Traveling Salesman Problem (TSP). These neighborhood structures enclose a special substructure which is not necessarily a Hamiltonian tour. Instead the neighborhood components are linked together to compose successive levels of an ejection chain, and coordinated by a suitable reference structure to generate compound moves with outstanding properties. More precisely, such a substructure can be viewed as a relaxed tour, which allows solution transformations to be obtained without preserving the Hamiltonian property at each step. Furthermore, in the ejection chain process, the generation of substructures produces a variety of alternating paths for the selection of subsequent ejection moves as well as for the choice of the corresponding trial moves. Finally, we propose two algorithmic variants – a Preliminary and a Full Subpath Ejection Chain Method (P-SEC and F-SEC) – based on this type of compound neighborhood design. Both variants are guided by a simple tabu search mechanism. Computational results on 67 TSPLIB problems show that both the Preliminary and the Full methods find optimal and near-optimal solutions very quickly, frequently outperforming the best heuristic procedures for the TSP. In addition, the Full method generally dominates the best alternative TSP procedures.