SOME METHODS OF PRODUCING APPROXIMATE SOLUTIONS TO TRAVELLING SALESMAN PROBLEMS WITH HUNDREDS OR THOUSANDS OF CITIES

Some approximate, sequential methods and the results of applying them to 30 problems of between 20 and 500 cities are described. In addition, the results of applying one method to ten 2500 city problems are are reported; the solutions produced were, on average, 1. 28 times the corresponding lower bound. It appears that satisfactory solutions to some large practical prolems may be obtained by developing suitable sequential methods.