A METHOD FOR SOLVING THE MULTI-TRAVELING SALESMAN PROBLEM IN AN ENVIRONMENT WITHOUT OBSTACLES BASED ON REDUCING THE SIZE OF THE SOLUTION SPACE

Abstract

This research paper analyzes the multi traveling salesman problem, which, unlike the famous
traveling salesman problem, involves several traveling salesmen who visit a given number of cities exactly
once and return to their original position with minimal travel costs. The multi-traveling salesman
problem is an important problem in the field of route optimization and task distribution among multiple
agents. The main goal of the study is to develop an effective method for solving this problem, which will
reduce task completion time and optimize the use of resources. During the study, an innovative method
was created based on reducing the dimension of the solution space. This method allows you to more
efficiently manage workload and resources, which in turn helps to minimize the overall execution time of
tasks. A special feature of the method is its versatility and applicability in various scenarios, including
situations with different numbers of tasks and traveling salespeople. This approach provides broader
coverage and allows the applicability of the method to be assessed in different contexts, which is an
important strength of this study. To evaluate the effectiveness of the developed method, a comparative study was conducted using the classical method for solving the multi-traveling salesman problem. The
results were evaluated based on three key criteria: the calculation time for solving the multi-traveling
salesman problem, the total length of the routes traveled by the traveling salesmen, and the maximum
route length among them. Analysis of experimental data showed that the developed method significantly
exceeds the classical approach in all considered criteria in most experiments, since when using the
proposed method, the average time for calculating a solution to the multi-traveling salesman problem is
reduced by 56%, while the average sum of the lengths of routes traveled by traveling salesmen is reduced
by 12%. In addition, the maximum path length among the routes traveled by agents (load imbalance)
is reduced by 8%, which confirms the high efficiency of the proposed method and its promise for
practical application in various fields where optimization of routes and distribution of tasks among
several executors is required