A Method for Solving Traveling-Salesman Problems

The traveling-salesman problem is a generalized form of the simple problem to find the smallest closed loop that connects a number of points in a plane. Efforts in the past to find an efficient method for solving it have met with only partial success. The present paper describes a method of solution that has the following properties (a) It is applicable to both symmetric and asymmetric problems with random elements (b) It does not use subjective decisions, so that it can be completely mechanized (c) It is appreciably faster than any other method proposed (d) It can be terminated at any point where the solution obtained so far is deemed sufficiently accurate.