Linear time algorithm for Precedence Constrained Asymmetric Generalized Traveling Salesman Problem

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. © 2016