A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem

Matteo Fischetti, Juan José Salazar González and Paolo Toth
Additional contact information
Matteo Fischetti: University of Padova, Italy
Juan José Salazar González: University of La Laguna, Spain
Paolo Toth: University of Bologna, Italy

Operations Research, 1997, vol. 45, issue 3, 378-394

Abstract: 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. [Fischetti, M., J. J. Salazar, P. Toth. 1995. The symmetric generalized traveling salesman polytope. Networks 26 113–123.]) 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.

Keywords: networks/graphs; generalized traveling salesman; programming; integer; cutting plane; branch-and-cut algorithm (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (78)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.45.3.378 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:45:y:1997:i:3:p:378-394

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().