Gilmore–Gomory type traveling salesman problems

Gilmore–Gomory type traveling salesman problems

0.00 Avg rating0 Votes
Article ID: iaor20001849
Country: United Kingdom
Volume: 26
Issue: 4
Start Page Number: 329
End Page Number: 351
Publication Date: Apr 1999
Journal: Computers and Operations Research
Authors: ,
Keywords: heuristics
Abstract:

One of the well-known, solvable cases of the traveling salesman problem (TSP) is the Gilmore–Gomory case. A generalization of their algorithm to what we call the GG scheme is known to solve a fairly large subclass of the problem. In this paper, we identify new classes of TSP for which the GG scheme produces an optimal solution and which properly include the class of TSP for which the cost matrix is a permuted distribution matrix. Implementation of the GG scheme is NP-hard for these classes of TSP. However, we identify some subclasses for which the GG scheme can be implemented in polynomial time. Some of these new solvable cases are proper generalizations of some well-known cases.

Reviews

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