An efficient heuristic algorithm for the bottleneck traveling salesman problem

This paper describes a new heuristic algorithm for the bottleneck traveling salesman problem (BTSP) which exploits the formulation of BTSP as a traveling salesman problem (TSP). Computational tests show that our algorithm is quite effective. It found optimal solutions for many problems from the standard TSPLIB problems. We also consider BTSP with an additional constraint and show that our BTSP heuristic can be modified to obtain a heuristic to solve this problem. Relationships between symmetric and asymmetric versions of BTSP are also discussed.