TSP EJECTION CHAINS

We identify ejection chain methods for the traveling salesman problem based on a special reference structure for generating constructions re lated to alternating paths. Computational tests show that the method p erforms very effectively, obtaining generally better solutions than im proved versions of the Lin-Kernighan method within the same time frame . Our approach, which currently has a simple tabu search guidance comp onent at a local level, also has the potential to be combined in more advanced ways with metaheuristics such as genetic algorithms, simulate d annealing and tabu search.