Novel method to solve the traveling salesman problem using distance matrix

Abstract

The Traveling Salesman Problem (TSP) is a well-known optimization problem. Its objective is to find the shortest path for a salesman to visit each city on a list and then return to the initial city. A number of approaches have been developed to solve the TSP, including dynamic programming, branch and bound, the nearest neighbour algorithm, genetic algorithms, simulated annealing, and ant colony optimization. These techniques have their roots in various mathematical fields, operations research, graph theory, and even fuzzy theory. While branch and bound method provides the exact solution, it is computationally expensive. In contrast, approaches such as genetic algorithms, simulated annealing, and ant colony optimization offer approximate solutions with less computational time. This study proposed a new matrix-based approach to solve TSP, which involves the following key steps: identifying and selecting row minimum values in the distance matrix, getting the maximum of them and highlighting corresponding rows and columns, finding the minimum values of the highlighted rows, and selecting the minimum among them. This algorithm is then repeated iteratively to refine the path selection.