Creating synthetic graphs for the Traveling Salesman Problem

The study is dedicated to the pressing issue of solving the Traveling Salesman Problem (TSP). The paper focuses on the development of neural network approaches to solving this problem, emphasizing the need for training models on a sufficient volume of data, which is not feasible to obtain in a reasonable time under current conditions. Therefore, the authors propose an algorithm for generating a random graph with a known shortest path or a path close to the optimal one. As a result of the study, an algorithm for augmenting adjacency matrices for the TSP with a known route was created.