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


Finding the Shortest Hamiltonian Circuit Through n Clusters: A Lagrangean Relaxation Approach

, et

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.

, 13 pages