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  United States  15213
• Authors:
  • Smith, THC
  • Thompson, G L
• Publication Date: 1975-10

Media Info

• Pagination: 37 p.

Subject/Index Terms

• TRT Terms: Algorithms; Bottlenecks; Computer programming; Computer programs; Digital computers; Integer programming; Network analysis (Planning); Nodes (Networks); Operations research; Problem solving; Scheduling; Symmetry; Traffic measurement; Transportation; Urban transportation
• Uncontrolled Terms: Network flows
• Old TRIS Terms: Hamiltonian; Nodes
• Subject Areas: Administration and Management; Operations and Traffic Management; Transportation (General);

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