DEVELOPMENT AND STUDY OF A CENTRALIZED TASK ALLOCATION METHOD IN MULTI-AGENT SYSTEMS

Abstract

This study provides a comprehensive analysis of the multi-traveling salesman problem, which is an extended version of the classical traveling salesman problem. In contrast to the latter, the multi-traveling salesman problem involves the participation of several traveling salesmen, each of whom must visit a certain number of cities exactly once and return to the starting point, while minimizing travel costs. The multi-traveling salesman problem is of significant interest in the field of route optimization and task distribution among multiple agents. The main goal of the research is to develop an effective method for solving this problem, which will reduce execution time and optimize the use of resources. As part of the study, an innovative method was developed, which is based on reducing the dimension of the solution space. This method allows you to more effectively distribute the load and manage resources, which ultimately helps reduce the overall time to complete tasks. One of the key features of the proposed method is its versatility and adaptability to various scenarios, including situations with varying numbers of tasks and traveling salespeople. A detailed study of the proposed method was also carried out from the point of view of the influence of its hyperparameters (pheromone evaporation coefficient, number of iterations, number of ants) on the quality of the solution and calculation time. To evaluate the effectiveness of the new method, a comparative study was conducted using the classical method for solving the multi-traveling salesman problem. The results were assessed according to three main criteria: the computation time for solving the multi-traveling salesman problem, the total length of the routes traveled, and the maximum route length among all traveling salesmen. Analysis of experimental data showed that the developed method significantly exceeds the classical one in all key indicators. These results confirm the high efficiency of the proposed method and its promise for practical application in various fields that require optimizing routes and distributing tasks among several performers. Thus, the study demonstrates that the developed method has significant potential for improving routing and resource allocation processes. Its application can significantly increase efficiency in various areas where coordination of the work of several agents is necessary, such as logistics, transport systems and other areas related to route optimization.