All issues

In this paper, a comparative analysis of the exact and heuristic algorithms presented by the method of branches and boundaries, genetic and ant algorithms, respectively, is carried out to find the optimal solution to the traveling salesman problem using the example of a courier robot. The purpose of the work is to determine the running time, the length of the obtained route and the amount of memory required for the program to work, using the method of branches and boundaries and evolutionary heuristic algorithms. Also, the most appropriate of the listed methods for use in the specified conditions is determined. This article uses the materials of the conducted research, implemented in the format of a computer program, the program code for which is implemented in Python. In the course of the study, a number of criteria for the applicability of algorithms were selected (the time of the program, the length of the constructed route and the amount of memory necessary for the program to work), the results of the algorithms were obtained under specified conditions and conclusions were drawn about the degree of expediency of using one or another algorithm in various specified conditions of the courier robot. During the study, it turned out that for a small number of points  $\leqslant10$, the method of branches and boundaries is the most preferable, since it finds the optimal solution faster. However, when calculating the route by this method, provided that the points increase by more than 10, the operating time increases exponentially. In this case, more effective results are obtained by a heuristic approach using a genetic and ant algorithm. At the same time, the ant algorithm is distinguished by solutions that are closest to the reference ones and with an increase of more than 16 points. Its relative disadvantage is the greatest resource intensity among the considered algorithms. The genetic algorithm gives similar results, but after increasing the points more than 16, the length of the found route increases relative to the reference one. The advantage of the genetic algorithm is its lower resource intensity compared to other algorithms.

The practical significance of this article lies in the potential possibility of using the results obtained for the optimal solution of logistics problems by an automated system in various fields: warehouse logistics, transport logistics, «last mile» logistics, etc.

Traditional methods for solving the traveling salesman problem are not effective for high-dimensional problems due to their high computational complexity. One of the most effective ways to solve this problem is the decomposition approach, which includes three main stages: clustering vertices, solving subproblems within each cluster and then merging the obtained solutions into a final solution. This article focuses on the third stage — merging cycles of solving subproblems — since this stage is not always given sufficient attention, which leads to less accurate final solutions of the problem. The paper proposes a new modified Sigal algorithm for merging cycles. To evaluate its effectiveness, it is compared with two algorithms for merging cycles — the method of connecting midpoints of edges and an algorithm based on closeness of cluster centroids. The dependence of quality of solving subproblems on algorithms used for merging cycles is investigated. Sigal’s modified algorithm performs pairwise clustering and minimizes total distance. The centroid method focuses on connecting clusters based on closeness of centroids, and an algorithm using mid-points estimates the distance between mid-points of edges. Two types of clustering — k-means and affinity propagation — were also considered. Numerical experiments were performed using the TSPLIB dataset with different numbers of cities and topologies to test effectiveness of proposed algorithm. The study analyzes errors caused by the order in which clusters were merged, the quality of solving subtasks and number of clusters. Experiments show that the modified Sigal algorithm has the smallest median final distance and the most stable results compared to other methods. Results indicate that the quality of the final solution obtained using the modified Sigal algorithm is more stable depending on the sequence of merging clusters. Improving the quality of solving subproblems usually results in linear improvement of the final solution, but the pooling algorithm rarely affects the degree of this improvement.