A branch-and-cut algorithm for the symmetric generalized traveling salesman problem
成果类型：
Article
署名作者：
Fischetti, M; Gonzalez, JJS; Toth, P
署名单位：
Universidad de la Laguna; University of Padua; University of Bologna
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.45.3.378
发表日期：
1997
页码：
378-394
关键词：
摘要：
We consider a variant of the classical symmetric Traveling Salesman Problem in which the nodes are partitioned into clusters and the salesman has to visit at least one node for each cluster. This NP-hard problem is known in the literature as the symmetric Generalized Traveling Salesman Problem (GTSP), and finds practical applications in routing, scheduling and location-routing. In a companion paper (Fischetti et al. 1995) we modeled GTSP as an integer linear program, and studied the facial structure of two polytopes associated with the problem. Here we propose exact and heuristic separation procedures for some classes of facet-defining inequalities, which are used within a branch-and-cut algorithm for the exact solution of GTSP. Heuristic procedures are also described. Extensive computational results for instances taken from the literature and involving up to 442 nodes are reported.