HYBRID METHOD FOR SOLVING THE MULTI-AGENT TRAVELING SALESMAN PROBLEM

Abstract

In this research work, the problem of task allocation in a multi-agent system is considered, where each agent is a robot, and each task is represented by a position, which should be visited by one agent. This problem is very similar to the multi-agent 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 the starting position with minimal travel costs. Therefore, the multi-agent traveling salesman problem is analyzed as a representative of the task allocation problem. The multi-traveling salesman problem is important for the field of route optimization and task allocation between several agents. It includes two different, but interrelated subproblems: distribute cities among agents and determine the order in which each agent visits cities. In the literature, there are 3 concepts for solving this problem with respect to solving its two constituent subproblems: the optimization concept, where both subproblems are solved simultaneously; The Cluster-First, Route-Second concept is where the question of which tasks to assign to which salesman is first decided, and then the question of the order in which each salesman solves his tasks is decided; The Route-First, Cluster-Second concept is where the question of the order in which tasks should be visited is first decided, and then this cycle is divided between agents without changing the order of visits in order to answer the question of which tasks each agent takes on. This paper proposes a hybrid approach to solving the multiple traveling salesman problem (mTSP), which combines the ideas of two well-known concepts: "First clustering, then routing" and "First routing, then clustering" in order to obtain their positive aspects and get rid of their weaknesses. 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 computational time to obtain a solution to the multi-travelling salesman problem, the total length of the routes travelled by the salesmen, and the maximum route length among them. The analysis of the experimental data showed that when using the proposed method, the maximum path length among the routes travelled by the agents (load imbalance) is reduced by an average of 26%.