Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem

Abstract

Many algorithms have been developed for the optimal solution of the asymmetric travelling salesman problem: the most efficient ones are based on the subtour elimination approach. This paper presents a breadth-first branch and bound algorithm which differs from the method of Smith, Srinivasan and Thompson in the selection of the subtour to be split, in the ordering of the arcs in the selected subtour, in the computation of different partial lower bounds and in different data structures to facilitate the updating of the cost matrix. Extensive computational results considering random problems with up to 240 vertices are presented for various ranges of the coefficients of the cost matrix.