GENERALIZED TRAVELING SALESMAN PROBLEM THROUGH N-SETS OF NODES - THE ASYMMETRICAL CASE

作     者：LAPORTE, G MERCURE, H NOBERT, Y 

作者机构：UNIV QUEBECDEPT SCI ADMMONTREAL H3C 3P8QUEBECCANADA 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：1987年第18卷第2期

页      面：185-197页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：Luonnontieteiden ja Tekniikan Tutkimuksen Toimikunta  (80EQ0428  A4747  A5486) 

主　　题：MATHEMATICAL PROGRAMMING, LINEAR 

摘      要：This paper presents an exact algorithm for a generalized version of the Travelling Salesman Problem which consists of finding the shortest Hamiltonian circuit 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.