A multi-tour heuristic for the traveling salesman problem

Graduation date: 1981This paper demonstrates the effectiveness of a heuristic for\ud the Traveling Salesman Problem based purely on the efficient\ud storage of multiple partial sub-tours. The heuristic is among the\ud best available for the solution of large scale geometric Traveling\ud Salesman Problems. Additionally, a version of the heuristic can be\ud used to prove optimality of modest size problems (about 30 cities).\ud The heuristic gives an alternative to the standard technique\ud of backtracking and starting over, by using main memory for alternate\ud paths. It gives insight into the magnitudes of sub-tour sizes in a\ud tour generation process, and gives a potential "assist" heuristic,\ud to be used along with a more standard method in reaching very large\ud scale Traveling Salesman Problems