WSEAS Transactions on Information Science and Applications
Print ISSN: 1790-0832, E-ISSN: 2224-3402
Volume 18, 2021
Generating Cyclic Permutations: Insights to the Traveling Salesman Problem
Author:
Abstract: Some results for the traveling salesman problem (TSP) are known for a prime number of cities. In this paper we extend these results to an odd number of cities. For an odd integer n, we show that there is an algorithm that generates n – 1 cyclic permutations, called tours for the traveling salesman problem, which cover the distance matrix. The algorithm allows construction of a two-dimensional array of all tours for the TSP on an odd number of cities. The array has the following properties: (i) A tour on a vertical line in the array moves the salesman uniquely compared to all other tours on the vertical line. (ii) The sum of the lengths of all tours on a vertical line is equal to the sum of all non-diagonal elements in the distance matrix for the TSP.
Search Articles
Keywords: cyclic permutation, entangled set of permutations, traveling salesman problem, tour for the salesman, distance matrix, odd number of cities
Pages: 68-72
DOI: 10.37394/23209.2021.18.9