Linear time algorithm for Precedence Constrained Asymmetric Generalized Traveling Salesman Problem. Issue 12 (2016)

• Record Type: Journal Article
• Authors: Chentsov, Alexander; Khachay, Michael; Khachay, Daniel
• Is Part Of: IFAC-PapersOnLine. Volume 49:Issue 12(2016)
• Page Start: 651
• Page End: 655
• Publication Date: 2016
• Subjects: Asymmetric Generalized Traveling Salesman Problem (AGTSP) -- NP-hard problem -- dynamic programming; Automatic control -- Periodicals; 629.805
• DOI: 10.1016/j.ifacol.2016.07.767
• Languages: English
• ISSNs: 2405-8963

Abstract

Abstract: We consider the combinatorial optimization problem of visiting clusters of a fixed number of nodes (cities), where, on the set of clusters should be visited according to some kind of partial order defined by additional precedence constraints. This problem is a kind of the Asymmetric Generalized Traveling Salesman Problem (AGTSP). To find an optimal solution of the problem, we propose a dynamic programming based on algorithm extending the well known Held and Karp technique. In terms of special type of precedence constraints, we describe subclasses of the problem, with polynomial (or even linear) in n upper bounds of time complexity.