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

[摘要] Two instances of the traveling salesman problem, on the same node set{1,2,…,n}but with different cost matricesCandC′, are equivalent iff there exist{ai,bi: i=1,…, n}suchthat for any1≤i,j≤n,i≠j,C′(i,j)=C(i,j)+ai+bj[7]. One of the well-solved special casesof the traveling salesman problem (TSP) is the convex-hull-and-line TSP. We extend the solutionscheme for this class of TSP given in [9] to a more general class which is closed with respect tothe above equivalence relation. The cost matrix in our general class is a certain composition ofKalmanson matrices. This gives a new, non-trivial solvable case of TSP.

[学科分类] 自然科学（综合）