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