Journal of Applied Mathematics and Decision Sciences
Volume 2 (1998), Issue 2, Pages 177-191

A generalization of the convex-hull-and-line traveling salesman problem

Md. Fazle Baki1 and S. N. Kabadi2

1Department of Management Sciences, University of Waterloo, Waterloo N2L 3G1, Ontario, Canada
2Faculty of Administration, University of New Brunswick, PO Box 4400, Fredericton E3B 5A3, New Brunswick, Canada

Copyright © 1998 Md. Fazle Baki and S. N. Kabadi. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


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 1i, jn,ij,C(i,j)=C(i,j)+ai+bj [7]. 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 [9] 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.