Tags:NP-hard, permutation matrix and Traveling salesman problem
Abstract:
The article describes the method of local sequencing, addressed to traveling salesman problem (TSP) and its restricted versions in the form of polynomial algorithms of finding satisfactory exact solutions. The proposed method takes into account the features of efficiently solvable generalizations of assignment problem. The considerations that are the basis for the development of algorithms for solving TSP by local optimal sequence building are presented. The algorithm for building the bypass τ^o is presented. The proposed algorithm is characterized by low complexity of building a acceptable solution to τ^o. The time of its operation is estimated. The time complexity of the proposed algorithm is estimated with value O(n^2 ). In practice, the algorithm works faster than the "go to the nearest" heuristics.
Local Sequence Method of Finding Solution to Traveling Salesman Problem