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.