Some properties of the solution space of the N-city traveling-salesman problem

摘要

For the matrix of variables in the N-city traveling-salesman problem, consider both the N row and the N column vectors. An orthogonality condition involving products of row and column vectors is shown to eliminate subtours. Also, a group representation of the problem is given to observe properties of the solution space. The matrix of variables is subsequently decomposed into a product of elementary transposition matrices. Numerous examples are provided to illustrate the properties of the problem.