Cluster based branching for the asymmetric traveling salesman problem

This paper presents a new branching scheme for the asymmetric traveling salesman problem (ATSP) based on clusters. A cluster is defined as a node set with the characteristic that there exists an optimal solution in which the nodes in the node set are visited consecutively. The paper considers identification of clusters, implementation of a cluster based branching scheme, and cluster based dominance tests. The new approach is implemented in a branch and bound algorithm using a well-known additive bounding procedure. Considerable savings in computing time are obtained compared to previously published assignment based branch and bound algorithms for the ATSP.