Two instances of the traveling salesman problem, on the same node set
but with different cost matrices
, are equivalent iff there exist such
that for any . 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 given in  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.