Group for Research in Decision Analysis

G-85-07

Generalized Travelling Salesman Problem Through n Sets of Nodes: The Asymmetrical Case

, , and

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.

, 18 pages

This cahier was revised in May 1986