Doctoral Dissertations

Abstract

"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.

Advisor(s)

Rigler, A. K.

Committee Member(s)

Hicks, Troy L.
Gillett, Billy E.
Keith, Harold D. (Harold Dean), 1941-
Winrich, Lonny B.

Department(s)

Mathematics and Statistics

Degree Name

Ph. D. in Mathematics

Sponsor(s)

National Science Foundation (U.S.)

Publisher

University of Missouri--Rolla

Publication Date

1970

Pagination

vii, 61 pages, 1 plate

Note about bibliography

Includes bibliographical references (pages 59-60).

Rights

© 1970 Joseph Sidney Greene, Sr., All rights reserved.

Document Type

Dissertation - Open Access

File Type

text

Language

English

Subject Headings

Traveling salesman problem
Computational complexity

Thesis Number

T 2414

Print OCLC #

6024093

Electronic OCLC #

854576111

Download

Included in

Mathematics Commons

Share

 
COinS