Computational Performance of Three Subtour Elimination Algorithms for Solving Asymmetric Traveling Salesman Problems.

摘要

In this paper we develop and computationally test three implicit enumeration algorithms for solving the asymmetric traveling salesman problem. All three algorithms use the assignment problem relaxation of the traveling salesman problem with subtour elimination similar to the previous approaches by Eastman, Shapiro and Bellmore and Malone. The present algorithms, however, differ from the previous approaches in two important respects: (1) lower bounds on the objective function for the descendants of a node in the implicit enumeration tree are computed without altering the assignment solution corresponding to the parent node --- this is accomplished using a result based on cost operators and (2) a LIFO (Last In, First Out) branching strategy is used which considerably reduces the storage requirements for the implicit enumeration approach. The three algorithms differ from each other in the details of implementing the implicit enumeration approach and in terms of the type of constraint used for eliminating subtours. Computational experience with randomly generated test problems indicates that the present algorithms are more efficient and can solve larger problems compared to (1) previous subtour elimination algorithms and (2) the 1-arborescence approach of Held and Karp for the asymmetric traveling salesman problem.