Lower tolerance-based Branch and Bound algorithms for the ATSP

In this paper, we develop a new tolerance-based Branch and Bound algorithm for solving NP-hard problems. In particular, we consider the asymmetric traveling salesman problem (ATSP), an NP-hard problem with large practical relevance. The main algorithmic contribution is our lower bounding strategy that uses the expected costs of including arcs in the solution to the assignment problem relaxation of the ATSP, the so-called lower tolerance values. The computation of the lower bound requires the calculation of a large set of lower tolerances. We apply and adapt a finding from 1231 that makes it possible to compute all lower tolerance values efficiently. Computational results show that our Branch and Bound algorithm exhibits very good performance in comparison with state-of-the-art algorithms, in particular for difficult clustered ATSP instances. (C) 2011 Elsevier Ltd. All rights reserved.