An Algorithm for the Bottleneck Traveling Salesman Problem

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.