Two instances of the traveling salesman problem, on the same node set {1,2, ..., n} but with different cost matrices C and C′, are equivalent iff there exist {ai, bi: i = 1, ..., n} such that for any 1 ≤ i, j ≤ n, i ≠ j, C′(i, j) = C(i, j) + ai + bj. One of the well-solved special cases of the traveling salesman problem (TSP) is the convex-hull-and-line TSP. We extend the solution scheme for this class of TSP to a more general class which is closed with respect to the above equivalence relation. The cost matrix in our general class is a certain composition of Kalmanson matrices. This gives a new, non-trivial solvable case of TSP.
