A Method for Solving Traveling-Salesman Problems

Abstract

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.