A Lagrangian Based Approach for the Asymmetric Generalized Traveling Salesman Problem

Charles E. Noon and James C. Bean
Additional contact information
Charles E. Noon: University of Tennessee, Knoxville, Tennessee
James C. Bean: University of Michigan, Ann Arbor, Michigan

Operations Research, 1991, vol. 39, issue 4, 623-632

Abstract: 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 a 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.

Keywords: networks/graphs; traveling salesman: generalized TSP model; programming; relaxation/subgradient: efficient relaxation; transportation; vehicle routing: routing with alternatives (search for similar items in EconPapers)
Date: 1991
References: Add references at CitEc
Citations: View citations in EconPapers (19)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.39.4.623 (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:39:y:1991:i:4:p:623-632

Access Statistics for this article

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