This paper deals with a generalized version of the Travelling Salesman Problem which consists of finding the shortest Hamiltonian circuit through n clusters, in the case where the distance matrix is asymmetrical. The problem is formulated as an integer linear program. A relaxation of this program possessing a network structure is then considered. The relaxed problem is solved by embedding a network flow routine into a branch and bound algorithm. Some versions of the algorithm make use of Lagrangean relaxation. Computational results are reported.
Paru en janvier 1985 , 13 pages