HYBRID METHOD FOR SOLVING THE MULTI-AGENT TRAVELING SALESMAN PROBLEM

In this research work, the problem of task allocation in a multi-agent system is considered, whereeach 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 travelingsalesman problem, involves several traveling salesmen who visit a given number of cities exactlyonce and return to the starting position with minimal travel costs. Therefore, the multi-agent travelingsalesman problem is analyzed as a representative of the task allocation problem. The multi-travelingsalesman problem is important for the field of route optimization and task allocation between severalagents. It includes two different, but interrelated subproblems: distribute cities among agents and determinethe order in which each agent visits cities. In the literature, there are 3 concepts for solving thisproblem with respect to solving its two constituent subproblems: the optimization concept, where bothsubproblems are solved simultaneously; The Cluster-First, Route-Second concept is where the question ofwhich tasks to assign to which salesman is first decided, and then the question of the order in which eachsalesman solves his tasks is decided; The Route-First, Cluster-Second concept is where the question of theorder in which tasks should be visited is first decided, and then this cycle is divided between agents withoutchanging the order of visits in order to answer the question of which tasks each agent takes on. Thispaper proposes a hybrid approach to solving the multiple traveling salesman problem (mTSP), whichcombines the ideas of two well-known concepts: "First clustering, then routing" and "First routing, thenclustering" in order to obtain their positive aspects and get rid of their weaknesses. To evaluate the effectivenessof the developed method, a comparative study was conducted using the classical method for solvingthe multi-traveling salesman problem. The results were evaluated based on three key criteria: thecomputational time to obtain a solution to the multi-travelling salesman problem, the total length of theroutes travelled by the salesmen, and the maximum route length among them. The analysis of the experimentaldata showed that when using the proposed method, the maximum path length among the routestravelled by the agents (load imbalance) is reduced by an average of 26%.