SEQUENTIAL HYBRIDIZATION ALGORITHM FOR THE TRAVELING SALESMAN PROBLEM SOLVING

Abstract

The traveling salesman problem is a combinatorial optimization problem. The article presents a statement of this problem and proposes a graph mathematical model in which vertices correspond to cities, and edges are paths between cities, and it is assumed that the graph is weighted. The solution of the traveling salesman problem consists in finding the minimum weight Hamiltonian cycle in a complete weighted graph. The problem is NP-hard, so a heuristic approach is used to solve this problem and speed up the solution of the problem on large volumes of input data. The heuristic consists in applying hybridization of two algorithms to solve the traveling salesman problem: the annealing simulation algorithm and the nearest neighbor algorithm. Sequential hybridization scheme is used to solve the traveling salesman problem. The basic idea is that the nearest neighbor method is launched on the initial set of solutions, and then the best solution of the first stage is fed to the annealing simulation algorithm. The article details the construction, flowcharts of the hybrid algorithm, the annealing simulation algorithm, and the nearest neighbor method. The article goes on to describe the user interface of the application written in Typescript. The application uses an area map as a solution to the traveling salesman problem. In the last part of the article, a comparative analysis of the algorithms' performance is highlighted: a comparison of the accuracy and operating time of the developed hybrid algorithm, the annealing simulation algorithm, and the nearest neighbor method for different input data sets. It was established that the developed hybrid algorithm is in second place in terms of speed and in first place in terms of solution quality among the implemented algorithms. In addition, the developed solution has a high economic and practical value because an application for solving the traveling salesman problem, and therefore an application for route navigation, can replace existing analogues or it can be used in any narrowly focused areas, as well as in logistics.