On the refinement of bounds of heuristic algorithms for the traveling salesman problem

A number of heuristics for the traveling salesman problem (TSP) rely on the assumption that the triangle inequality (TI) is satisfied. When TI does not hold, the paper proposes a transformation such that for the transformed problem the TI holds. Consequently, the bounds obtained for heuristics are valid with appropriate modification. Moreover, for a TSP satisfying TI the same transformation strengthens such bounds. The transformation essentially maps the problem into one that is minimal with respect to the property that TI holds. For the symmetric TSP the transformation is particularly simple. For an application of the transformation in the asymmetric case we need the dual solution of an assignment problem.