A LAGRANGIAN BASED APPROACH FOR THE ASYMMETRIC GENERALIZED TRAVELING SALESMAN PROBLEM
成果类型：
Article
署名作者：
NOON, CE; BEAN, JC
署名单位：
University of Michigan System; University of Michigan
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.39.4.623
发表日期：
1991
页码：
623-632
关键词：
摘要：
This paper presents an optimal approach for the asymmetric Generalized Traveling Salesman Problem (GTSP). The GTSP is defined on a directed graph in which the nodes are grouped into m predefined, mutually exclusive and exhaustive sets with the arc set containing no intraset arcs. The problem is to find a minimum cost m-arc directed cycle which includes exactly one node from each set. Our approach employs a Lagrangian relaxation to compute a lower bound on the total cost of an optimal solution. The lower bound and heuristically determined upper bound are used to identify and remove arcs and nodes which are guaranteed not to be in an optimal solution. Finally, we use an efficient branch-and-bound procedure which exploits the multiple choice structure of the node sets. We present computational results for the optimal approach tested on a series of randomly generated problems. The results show success on a range of problems with up to 104 nodes.