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
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
0.8894187211990356
0 references
0.8489194512367249
0 references
0.8463541865348816
0 references
0.8206024169921875
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