Accession Number : AD0705498

Title :   A TRAVELING SALESMAN ALGORITHM.

Descriptive Note : Master's thesis,

Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CALIF

Personal Author(s) : White,William Willerson

Report Date : OCT 1969

Pagination or Media Count : 62

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)

Descriptors :   (*LINEAR PROGRAMMING, ALGORITHMS), NETWORKS, OPTIMIZATION, COMPUTER PROGRAMS, THESES

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE