Groupe d’études et de recherche en analyse des décisions

G-85-07

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

, et

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

Ce cahier a été révisé en mai 1986