NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
A Simple Algorithm for the Metric Traveling Salesman ProblemAn algorithm was designed for a wire list net sort problem. A branch and bound algorithm for the metric traveling salesman problem is presented for this. The algorithm is a best bound first recursive descent where the bound is based on the triangle inequality. The bounded subsets are defined by the relative order of the first K of the N cities (i.e., a K city subtour). When K equals N, the bound is the length of the tour. The algorithm is implemented as a one page subroutine written in the C programming language for the VAX 11/750. Average execution times for randomly selected planar points using the Euclidean metric are 0.01, 0.05, 0.42, and 3.13 seconds for ten, fifteen, twenty, and twenty-five cities, respectively. Maximum execution times for a hundred cases are less than eleven times the averages. The speed of the algorithms is due to an initial ordering algorithm that is a N squared operation. The algorithm also solves the related problem where the tour does not return to the starting city and the starting and/or ending cities may be specified. It is possible to extend the algorithm to solve a nonsymmetric problem satisfying the triangle inequality.
Document ID
19840024560
Document Type
Reprint (Version printed in journal)
Authors
Grimm, M. J. (Jet Propulsion Lab., California Inst. of Tech. Pasadena, CA, United States)
Date Acquired
August 12, 2013
Publication Date
August 15, 1984
Publication Information
Publication: The Telecommun. and Data Acquisition Rept.
Subject Category
NUMERICAL ANALYSIS
Distribution Limits
Public
Copyright
Work of the US Gov. Public Use Permitted.

Related Records

IDRelationTitle19840024551Analytic PrimaryThe Telecommunications and Data Acquisition Report
Document Inquiry