Scholarship at UWindsor

Title

Generalization of the convex-hull-and-line traveling salesman problem

Authors

Fazle Baki, University of WindsorFollow
S. N. Kabadi

Document Type

Article

Publication Date

1998

Publication Title

Journal of Applied Mathematics and Decision Sciences

Volume

2

Issue

2

First Page

177

Keywords

Traveling salesman problem, Kalmanson matrix, polynomial algorithm.

Last Page

191

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 {a, hi: -1, n} such that for any 1 _i, j _n, j, C(i, j) C(i,j) q-a -t-bj [7]. One ofthe 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.

Comments

This article was originally published in the Journal of Applied Mathematics and Decision Sciences, Hindawi Publishing Corporation.

Recommended Citation

Baki, Fazle and Kabadi, S. N.. (1998). Generalization of the convex-hull-and-line traveling salesman problem. Journal of Applied Mathematics and Decision Sciences, 2 (2), 177-191.
https://scholar.uwindsor.ca/odettepub/10