A generalization of the convex-hull-and-line traveling salesman problem. Issue 2 (1998)

• Record Type: Journal Article
• Authors: Baki, Md. Fazle; Kabadi, S. N.
• Is Part Of: Journal of applied mathematics & decision sciences. Volume 2:Issue 2(1998)
• Page Start: 177
• Page End: 191
• Publication Date: 1998
• Subjects: Operations research -- Periodicals; Mathematical models -- Periodicals; Statistics -- Periodicals; Quality control -- Periodicals; Mathematical models; Operations research; Quality control; Statistics; Periodicals; 519.05
• DOI: 10.1155/S1173912698000108
• Languages: English
• ISSNs: 1173-9126

Abstract

Abstract : Two instances of the traveling salesman problem, on the same node set{ 1, 2, …, n } but with different cost matricesC andC ′, are equivalent iff there exist{ a i, b i : i = 1, …, n } such that for any1 ≤ i, j ≤ n, i ≠ j, C ′ ( i, j ) = C ( i, j ) + a i + b j [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.