"The traveling salesman problem may be stated as follows: "A salesman is required to visit each of n given cities once and only once, starting from any city and returning to the original place of departure. What route should be chosen in order to minimize the total distance traveled?" A new algorithm is developed which gives a good approximation to the solution for a large number of cities using reasonable computer time and which will converge to the exact solution if allowed to continue. This algorithm is a branch and bound technique which utilizes the distance between cities in its bounding procedure. The bookkeeping scheme for the algorithm is such that only the partial solution along with those routes currently being checked need be retained in memory. The branching technique requires that only one row of the distance matrix be in memory at any time. The algorithm is demonstrated using a four-city problem and a formal statement is given. Computational results from computer implementation of the algorithm are given, including three realistic problems from the printed circuit industry"--Abstract, page ii.
Rigler, A. K.
Hicks, Troy L.
Gillett, Billy E.
Keith, Harold D. (Harold Dean), 1941-
Winrich, Lonny B.
Mathematics and Statistics
Ph. D. in Mathematics
National Science Foundation (U.S.)
University of Missouri--Rolla
vii, 61 pages, 1 plate
© 1970 Joseph Sidney Greene, Sr., All rights reserved.
Dissertation - Open Access
Library of Congress Subject Headings
Traveling salesman problem
Print OCLC #
Electronic OCLC #
Link to Catalog Recordhttp://laurel.lso.missouri.edu/record=b1066904~S5
Greene, Joseph Sidney, "A coordinate oriented algorithm for the traveling salesman problem" (1970). Doctoral Dissertations. 2100.