Comparative Study of Methods for Solving Task Allocation and Routing Problems for Multi-Agent Robotic Systems

Abstract

This paper considers the multi-traveling salesman problem (MTSP), where traveling salesmen must visit a certain number of cities exactly once and return to the starting point with minimal travel costs. There are three methods for solving this problem: optimization-based, Cluster First-Order Second-based, and Route First-Cluster Second. Although the latter was used to solve the vehicle routing problem, this paper proposes a modification of it for solving the MTSP. The main objective of the study is to develop an effective method for solving this problem that will reduce the task execution time and optimize resource utilization. To evaluate the effectiveness of the developed method, a comparative analysis of the methods for solving the MTSP was conducted. It was revealed that the proposed method based on the Route First-Cluster Second concept allows for more efficient load and resource management, which helps to minimize the overall task execution time. This approach provides a wider coverage and allows us to evaluate the applicability of the method in various contexts, which is an important advantage of this study. The evaluation of the results was based on three key criteria: the computational time for obtaining a solution to the MTSP, the total length of the routes traveled by the traveling salesmen, and the maximum route length. The analysis of the experimental data showed that the developed method outperforms the classical approach based on meta-heuristics, and in all considered criteria in most experiments and in some situations it outperforms the approach based on clustering and meta-heuristics.