This paper presents an exact algorithm for a generalized version of the Travelling Salesman Problem which consists of finding the shortest Hamiltonian cirnuit through n clusters of nodes, in the case where the distance matrix is asymmetrical. The problem is formulated as an integer linear program. The program is then relaxed and solved by a branch and bound algorithm. Computational results are reported for problems involving up to 100 nodes and 8 clusters.
Published March 1985 , 18 pages
This cahier was revised in May 1986