An Algorithm for the Bottleneck Traveling Salesman Problem

Giorgio Carpaneto, Silvano Martello and Paolo Toth
Additional contact information
Giorgio Carpaneto: University of Bologna, Bologna, Italy
Silvano Martello: University of Bologna, Bologna, Italy
Paolo Toth: University of Bologna, Bologna, Italy

Operations Research, 1984, vol. 32, issue 2, 380-389

Abstract: Given a graph with arc costs, the Bottleneck Traveling Salesman Problem is to find a Hamiltonian circuit that minimizes the largest cost of any of its arcs. Lower bounds for the problem (bottleneck assignment problem, bottleneck paths, bottleneck arborescence, cuts) are analyzed and combined to obtain a bounding procedure for a breadth-first branch and bound algorithm. At each node of the branch-decision tree, the algorithm uses a heuristic search to find a Hamiltonian circuit containing only arcs whose cost is not greater than the current lower bound, the aim being to reduce the number of nodes explored. Extensive computational results are discussed. These show that, unlike the classical Traveling Salesman Problem, the same algorithm can be used successfully for large numbers of vertices both in symmetric and in asymmetric cases. Results for Euclidean graphs are also presented.

Keywords: 491 bottleneck traveling salesman problem; 627 breadth-first branch and bound (search for similar items in EconPapers)
Date: 1984
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.32.2.380 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:32:y:1984:i:2:p:380-389

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().