Selection of relaxation problems for a class of asymmetric traveling salesman problem instances

It is commonly believed that the use of the assignment problem works well when one selects a relaxation problem within the framework of a branch and bound algorithm to solve an asymmetric traveling salesman problem (TSP) optimally. In this paper, the authors present asymmetric TSP instances found in real-life setting, and show that the above common belief is not necessarily appropriate. Based on the real-life example, a family of asymmetric TSP instances called SLOPE is considered, which are generated by deforming arc lengths of standard two-dimensional TSPs on a plane in a specific manner. For this type of instances they show that the assignment relaxation yields poor performance, and propose a minimum 1-arborescence relaxation similar to the minimum 1-tree relaxation that has been successfully applied to the symmetric TSPs. In order to make the algorithm more efficient, the proper selection of a root node and the determination of Lagrange multipliers to increase the lower bounds are explored. Computational experiments with instances SLOPE and also with the real-life instance show that the proposed algorithm gives better computational performance than the algorithm with the assignment relaxation.