1. SOLUTION OF A LARGE-SCALE TRAVELING-SALESMAN PROBLEM.
- Author
-
Dantzig, G., Fulkerson, R., and Johnson, S.
- Subjects
TRAVELING salesman problem ,MATHEMATICAL programming ,ALGORITHMS ,MATHEMATICAL optimization ,OPERATIONS research ,LINEAR programming ,CITIES & towns ,ITERATIVE methods (Mathematics) - Abstract
The article presents a solution to a large-scale traveling-salesman problem which shows that a certain tour of 49 cities, one in each of the 48 states and Washington, D.C., has the shortest road distance. A brief history of the problem is provided. A city in each state including the District of Columbia was selected to try the optimal path method on a large problem. The devices in obtaining solutions include the use of undirected tours, the imposition of linear conditions to characterize the tours, the speeding up of the iterative process and the use of a combinatorial approach.
- Published
- 1954
- Full Text
- View/download PDF