A TRAVELING SALESMAN ALGORITHM.
Abstract
The study developed an algorithm to solve the traveling salesman problem. Although the program solves problems of forty cities or less, it has a significant limitation. Execution is terminated on a problem if a solution is not found early enough in the trial-and-error process of the algorithm. The solution procedure developed formulates the salesman's problem as an assignment problem, obtains an optimal assignment solution, and then manipulates vectors in the final simplex tableau until an assignment solution is obtained that also satisfies the additional traveling-salesman constraints. Background to the problem is given, the algorithm is developed and stated, the computer program is described and critiqued, highlights of computational expericnce with the program are presented, and, finally, some conclusions and recommendations are made. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1969
- Accession Number
- AD0705498
Entities
People
- William Willerson White
Organizations
- Naval Postgraduate School