An Algorithm for the Bottleneck Traveling Salesman Problem (Q3328310)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3858879
Language Label Description Also known as
default for all languages
No label defined
    English
    An Algorithm for the Bottleneck Traveling Salesman Problem
    scientific article; zbMATH DE number 3858879

      Statements

      An Algorithm for the Bottleneck Traveling Salesman Problem (English)
      0 references
      0 references
      0 references
      0 references
      1984
      0 references
      bottleneck traveling salesman problem
      0 references
      directed Hamiltonian circuit
      0 references
      lower bounds
      0 references
      Bottleneck Assignment
      0 references
      Bottleneck Arborescence
      0 references
      breadth- first branch and bound algorithm
      0 references
      heuristic search
      0 references
      test problems
      0 references
      computational result
      0 references
      The authors discuss the bottleneck traveling salesman problem (BTSP) to find a directed Hamiltonian circuit that minimizes the maximum cost of any of its arcs. \textit{R. S. Garfinkel} and \textit{K. C. Gilbert} [J. Assoc. Comput. Machin. 25, 435-448 (1978; Zbl 0378.90095)] discussed this problem and proposed two branch and bound methods based on the Bottleneck Assignment Relaxation and the Bottleneck One-Arborescence Relaxation. This paper presents a number of lower bounds for BTSP based on (1) Bottleneck Assignment Problem (BAP), (2) Bottleneck Paths (an extension of Bottleneck Arborescence), (3) Linkage of Vertices, (4) Linkage of Subtours (in the solution of BAP), and a breadth-first branch and bound algorithm combined with a heuristic search for a Hamiltonian circuit proposed by \textit{S. Martello} [ACM Trans. Mat. Software 9, 131-138 (1983; Zbl 0511.05041)]. The algorithm is applied to 50 test problems with randomly generated coefficients ranging from 40 to 200 nodes. The computational result shows that their algorithm is more efficient than the Garfinkel/Gilbert method on the average running time and its growing rate. Furthermore, it is applicable to the symmetric problem as well as the asymmetric one.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references