A Subtour Elimination Algorithm for the Bottleneck Traveling Salesman Problem.

reportActive / Technical Report | Accession Number: ADA019547 | Need Help?

Abstract:

In this paper we propose a LIFO implicit enumeration algorithm for the bottleneck traveling salesman problem which uses the bottleneck assignment problem as a relaxation. We also present computational experience on a UNIVAC 1108 with symmetric and asymmetric problems, ranging in size from 30 to 2000 nodes. Our results indicate that for asymmetric problems the time requirement of the proposed algorithm grows slower than the square of the problem size -- i.e. the algorithm is empirically good in the sense of Edmonds. Author

Author(s):
Smith, T. H. C. ; Thompson, G. L.
Author Organization(s):
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Descriptive Note:
Research rept.,
Pagination:
0037

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release

RECORD

Collection: TR
Identifying Numbers
Report Number(s):
RR-376, WP-24-75-76
Contract/Grant Number(s):
N00014-75-C-0621
Project Number(s):
NR-047-048
 Subject Terms
Communities of Interest:
No COI(s) Identified
Descriptor(s):
*Algorithms, *Integer programming, *Operations research, Problem solving, Nodes, Hamiltonian, Transportation, Scheduling, Network flows, Digital computers, Computer programming
Field(s)/Group(s):
Theoretical Mathematics, Operations Research
Keyword(s):
Traveling salesman problem, Bottleneck traveling salesman problem
Report Date:
1975 Oct 01