A Lagrangian based approach for the asymmetric Generalized Traveling Salesman Problem

A Lagrangian based approach for the asymmetric Generalized Traveling Salesman Problem

0.00 Avg rating0 Votes
Article ID: iaor19931194
Country: United States
Volume: 39
Issue: 4
Start Page Number: 623
End Page Number: 632
Publication Date: Jul 1991
Journal: Operations Research
Authors: ,
Keywords: vehicle routing & scheduling
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. The present 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, the authors use an efficient branch-and-bound procedure which exploits the multiple choice structure of the node sets. They 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.

Reviews

Required fields are marked *. Your email address will not be published.