Open AccessGenerating Cyclic Permutations: Insights to the Traveling Salesman Problem
Author(s) -
Richard H. Warren
Publication year - 2021
Publication title -
wseas transactions on information science and applications
Language(s) - English
Resource type - Journals
eISSN - 2224-3402
pISSN - 1790-0832
DOI - 10.37394/23209.2021.18.9
Subject(s) - travelling salesman problem , combinatorics , integer (computer science) , diagonal , line (geometry) , mathematics , matrix (chemical analysis) , traveling purchaser problem , bottleneck traveling salesman problem , prime (order theory) , computer science , algorithm , geometry , materials science , composite material , programming language
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.