Advances in Decision Sciences
Volume 2 (1998), Issue 2, Pages 177-191
doi:10.1155/S1173912698000108

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

Abstract

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 [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.