Barros, A. I.Bárcia, Paulo2019-10-232019-10-231990-10Barros, A. I. and Bárcia, P., New Bounds for Asymmetric Travelling Salesman Problem (October, 1990). FEUNL Working Paper Series No. 158http://hdl.handle.net/10362/85189Recently new Lagrangean techniques for producing lower bounds have appeared in the literature: bound improvement sequences and Lagrangean decomposition. The combination of these approaches yields the Improved Lagrangean decomposition. In this work we will apply this combined approach to the Asymmetric Travelling Salesman Problem. The results obtained using the Improved Lagrangean decomposition on the r-Arborescence formulation of the (ATSP) show that these new bounds often bridge the duality gap without needing valid inequalities or Branch&Bound techniques. We also present an extended version of the subgradient method developed to speed up the computation of the bounds aforementioned. Computational experience is reported.engInteger programmingDuality gapLagrangean relaxationBound improvement sequencesLagrangean decompositionIntegrality propertyX-ConvexitySubgradient methodworking paper