×

The symmetric generalized traveling salesman polytope. (English) Zbl 0856.90116

Summary: The symmetric generalized traveling salesman problem (GTSP) is 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. A different version of the problem, called E-GTSP, arises when exactly one node for each cluster has to be visited. Both GTSP and E-GTSP are NP-hard problems and find practical applications in routing, scheduling, and location-routing. In this paper, we model GTSP and E-GTSP as integer linear programs and study the facial structure of the corresponding polytopes. In a companion paper, the results described in this work have been used to design a branch-and-cut algorithm for the exact solution of instances up to 442 nodes.

MSC:

90C35 Programming involving graphs or networks
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
90B06 Transportation, logistics and supply chain management
90B80 Discrete location and assignment
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balas, Networks 19 pp 621– (1989)
[2] The prize collecting traveling salesman problem: II. Polyhedral results. Working paper, Carnegie Mellon University (July 1993).
[3] Balas, Math. Oper. Res. 17 pp 1001– (1992)
[4] Balas, Math. Program. 58 pp 325– (1993)
[5] and , A branch-and-cut algorithm for the symmetric generalized travelling salesman problem. Working paper, University of Bologna (November 1993).
[6] and , An additive approach for the optimal solution of the prize-collecting travelling salesman problem. Vehicle Routing: Methods and Studies (B. L. Golden and A. A. Assad, Eds.). Amsterdam (1988) 319–343.
[7] and , Polyhedral Theory. in , , and (Eds.) The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, New York, 1985. · Zbl 0562.00014
[8] Laporte, Discr. Appl. Math. 18 pp 185– (1987)
[9] Laporte, INFOR 21 pp 61– (1983)
[10] , and , Eds., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, New York (1985).
[11] Naddef, Math. Program. 58 pp 53– (1993)
[12] The generalized traveling salesman problem. Unpublished Dissertation, Department of Industrial and Operations Research. University of Tennessee (1988).
[13] Noon, Oper. Res. 39 pp 623– (1991)
[14] Noon, INFOR 31 pp 39– (1993)
[15] Padberg, Oper. Res. 23 pp 833– (1975)
[16] Algoritmi per il problema del Commesso Viaggiatore Generalizzato. PhD Dissertation, Royal Spanish College in Bologna, Italy (1992).
[17] The symmetric generalized travelling salesman problem. PhD Dissertation, University of Tennessee, Knoxville (1991).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.