A new heuristic algorithm for the traveling salesman problem

A new algorithm for the traveling salesman problem is presented along with results obtained in using the technique on a set of eight problems. This set of problems includes five problems obtained from the literature having 20, 33, 42, and 57 cities, respectively. In addition, a method is shown for calculating inter-city distances from latitudes and longitudes, thus circumventing a large amount of data preparation. Three problems with 75, 86, and 100 cities are then defined on which the algorithm is further tested. Results indicate that optimal solutions are found for all but the 100 city problem. Average computing times to obtain optimal solutions for all of the problems on a Univac-1108 computer are given along with the times required to solve the first five problems by six other techniques found in the literature.