A SUBTOUR ELIMINATION ALGORITHM FOR THE BOTTLENECK TRAVELING SALESMAN PROBLEM

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)

  • Corporate Authors:

    Carnegie Mellon University

    Management Sciences Research Group
    Pittsburgh, PA  USA  15213
  • Authors:
    • Smith, THC
    • Thompson, G L
  • Publication Date: 1975-10

Media Info

  • Pagination: 37 p.

Subject/Index Terms

Filing Info

  • Accession Number: 00136737
  • Record Type: Publication
  • Source Agency: National Technical Information Service
  • Report/Paper Numbers: RR-376 Res. Rpt.
  • Contract Numbers: N00014-75-C-0621
  • Files: TRIS
  • Created Date: Jul 13 1976 12:00AM