Some worst-case results related to the asymmetric traveling salesman problem

In the Asymmetric Traveling Salesman Problem (ATSP), an interesting research question is to evaluate the maximum ratio between the cost of a route and the cost of the same route traversed in the opposite direction. This provides a worst-case measure of the tour length asymmetry. Selecting the best between the two routes can be advantageous not only from a theoretical standpoint but also in practical settings: particularly in the presence of factors such as elevation changes, traffic patterns, or operational constraints. We carry out a worst-case analysis to provide the value of the maximum ratio on all instances of the problem, when the classical, the sharpened, and the relaxed triangle inequalities hold. Computational results on benchmark instances show that the value of the ratio is significantly smaller than the worst case bound, on average. Nonetheless, it is still large enough to justify considering both directions of a tour, as selecting the better of the two can lead to a substantially shorter total tour length.