An asymmetric analog of van der Veen conditions and the traveling salesman problem

J.A.A. van der Veen proved that for the traveling salesman problem which satisfies some symmetric conditions (called van der Veen conditions), a shortest pyramidal tour is optimal, that is, an optimal tour can be computed in polynomial time. In this paper, we prove that a class satisfying an asymmetric analog of van der Veen conditions is polynomially solvable. An optimal tour of the instance in this class forms a tour which is an extension of pyramidal ones. Moreover, this class properly includes some known polynomially solvable classes.