The bottleneck traveling salesman problem (BTSP) refers to the challenge of finding a Hamiltonian circuit that minimizes the largest cost of any of the arcs in the circuit. This paper describes a hybrid genetic algorithm (HGA) that efficiently produces high-quality solutions for BTSPs. The algorithm has been tested on the TSPLIB benchmarks.

For its initial population, the algorithm uses a mixture of chromosomes selected in part through a sampling procedure that starts with chromosomes considered to be likely candidates for solutions and supplements that selection with randomly generated ones. A simple example of this procedure would help the exposition of the paper, as the explanation given in the paper is somewhat obscure. The author states that starting the algorithm entirely with chromosomes generated by the sampling procedure tends to get the algorithm stuck in local minima. The paper details the algorithm by giving the crossover operation and the mutation operation, which combines insertion, inversion, and reciprocal exchange. In addition, to avoid ending up in a local minimum, ten percent of the population is periodically randomly replaced using a sequential sampling algorithm described in the paper. A useful diagram displays the structure of this algorithm.

The paper gives numerous results from the application of the proposed algorithm to various TSPLIB instances. These are compared with results for the binary search threshold (BST) heuristic and the hybrid sequential constructive sampling (HSCS) algorithm.

On average, the proposed HGA algorithm is substantially faster than BST and somewhat faster than HSCS. Both practitioners and students will find in this work a stimulating example of how to use a number of techniques to enhance a genetic algorithm. The ideas for the creation of an initial population are particularly interesting.