A Contribution to the “Travelling-Salesman” Problem

Summary This paper is concerned with finding the shortest closed path joining n points where the distances between all pairs of points are given. For a set of points in a metric space we establish that the shortest path will consist of a single loop circuit that will never cross itself. The problem is formally stated in Linear Programming terms. The difficulty in the Linear Programming formulation is to avoid the appearance of sub-cycles. This has been effected by making the programme dynamic. The computational cost of a complete enumeration of all possible circuits or the cost of solving the Linear Programme being prohibitive for a large number of points, we attempt a practicable computing routine. The method proceeds by writing down the set of distances as a square matrix and selecting from the matrix a set of n links which will form an initial single loop circuit: the circuit is changed by simultaneously removing three links and introducing three new links without destroying the single loop form of the circuit. Related methods and problems are discussed.