Applying Minimum Travel Array on Twenty Traveling Salesman Problems

Overview & Synopsis

The exact solution for the Traveling Salesman Problem (TSP) is a main research topic with high priority and importance. This article gives insight analysis to understand this important problem by studying its Minimum Travel Array characteristic. There are symmetric and asymmetric TSP. This article selected ten problems from each type and computed the Minimum Travel Array for each. Then, the sum of the minimum cost of arriving at the node and the sum of the minimum cost of departing from it were computed and compared to the Best-Known solution of each problem. There is a distinct difference between symmetric and asymmetric TSP. This is clear in the results of this research. The mean of both sums is a reliable lower bound for symmetric graphs, and the greater from these sums is a practical lower bound for asymmetric graphs. In both cases, the Minimum Travel Array provides a deep understanding of each TSP and is a first step towards its solution. The TSPLIB is the source for the twenty problems analyzed in this article. The program used and the associated data are freely available online.