A New Approach to Provide the Best Feasible Solution to Maximize the Traveling Salesman Problem

Abstract

The traveling salesman problem presents a significant difficulty for scholars in mathematics and computer science. The difficulty is in the solution's nature, which involves determining the shortest path to visit multiple cities a single time and return to the origin. The challenge of solving it grows considerably with the rise in the number of cities. This happens because the quantity of potential solutions increases quickly as the number of cities rises. As a result, attaining the ultimate answer takes a greater amount of time, classifying it as an NP-hard problem. This paper examines the traveling salesman problem to try to formulate an appropriate method for attaining its ultimate solution, considering its considerable relevance in various aspects of life. In this context, this research led to the development of a novel algorithm for addressing the linear traveling salesman problem. Although there is a minor resemblance between the traveling salesman problem and assignment problems regarding the solution's nature, this had a crucial impact on the formulation of the new algorithm. Clearly, the approach of the new algorithm relies on the Hungarian method employed to uncover the best solution for assignment issues. This, consequently, aided in gathering the most practical solutions to all aspects of the traveling salesman problem with the new algorithm. Though challenging and intricate, the new algorithm was noted for its efficiency in addressing the traveling salesman problem in an unprecedented manner in terms of time and effort.