This paper discusses the most efficient heuristic algorithms for generating optimum or near-optimum solutions for the symmetric travelling salesman problem. Our intent in this paper is to examine some of these well-known heuristics, to introduce a new heuristic, to combine these heuristics in the best possible way, and to compare these approximate techniques on the basis of efficiency and speed. In building an efficient combined heuristic procedure we emphasize both tour construction and tour-to-tour improvement phases. We show, by the wide experimental tests, why it is quite reasonable to construct a combination if the goal is to find quick solutions within 1 - 2 % of optimality.
heuristic algorithms, travelling salesman problem
All articles published by Studies in Informatics and Control (SIC) are published in accordance with the terms and conditions of the Creative Commons Attribution License (CC BY-NC-SA 4.0).