Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem
提出一种广度优先的分支定界算法，通过改进子环选择、弧排序、部分下界计算和数据结构来求解非对称旅行商问题，并在多达240个顶点的随机问题上展示了计算结果。
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.