article

A Method for Solving Traveling-Salesman Problems

Operations Research · 1958 · Vol. 6(6) · pp. 791–812

G. A. Croes✉(Shell (United States))

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.

Data Management and AlgorithmsTravelling salesman problemPoint (geometry)Simple (philosophy)Mathematical optimizationCutting-plane methodTraveling purchaser problemPlane (geometry)MathematicsComputer science2-opt

Citations

1,517

FWCI

1.08

field-weighted impact

References

Percentile

72%

vs. same field & year

Citations per year

Cited by

An Algorithm for the Vehicle-dispatching Problem