Local Sequence Method of Finding Solution to Traveling Salesman Problem

EasyChair Preprint 6660

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.

Keyphrases: NP-hard, Traveling Salesman Problem, permutation matrix

@booklet{EasyChair:6660,
  author    = {Igor Gritsuk and Dmytro Plechystyy and Andriy Morozov and Tamara Loktikova and Valentyna Shadura},
  title     = {Local Sequence Method of Finding Solution to Traveling Salesman Problem},
  howpublished = {EasyChair Preprint 6660},
  year      = {EasyChair, 2021}}