Novel method to solve the traveling salesman problem using distance matrix
Loading...
Date
2024-11-01
Authors
Ruwan, S. M. T.
Ekanayake, E. M. U. S. B.
Journal Title
Journal ISSN
Volume Title
Publisher
Postgraduate Institute of Science (PGIS), University of Peradeniya, Sri Lanka
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.
Description
Keywords
Combinatorial optimization , Heuristic optimization , NP-hard problems , Traveling salesman problem
Citation
Proceedings of the Postgraduate Institute of Science Research Congress (RESCON) -2024, University of Peradeniya, P 91