Journal of Applied Mathematics and 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
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.
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.