The dynamic multi-agent approach to solving the traveling salesman problem

Abstract

This paper investigates the multi-agent traveling salesman problem with a common depot and dynamic distribution of service points. Unlike traditional approaches that require preliminary clustering and rigid assignment of points to agents, the proposed method ensures adaptive formation of service zones directly during route construction. The distribution principle is based on minimizing the distance to the agent's initial position, which leads to the formation of spatially separated and compact clusters. Routing within the formed subsets is performed using a modified ant colony algorithm, in which the transition probability accounts for, in addition to pheromone trail intensity and heuristic information inversely proportional to distance, an additional correcting factor reflecting the candidate's proximity to the starting vertex. This architecture allows solving clustering and routing problems in a coordinated manner within a single optimization process, eliminating the need for a preliminary partitioning stage. To reduce computational complexity, multi-threaded processing of formed clusters is implemented, ensuring algorithm scalability as the number of agents increases. Results of computational experiments on standard test sets of various dimensions confirm the effectiveness of the proposed approach in terms of minimizing the total route length. It has been established that integrating the proximity factor to the initial position into the heuristic function contributes to the formation of more compact trajectories compared to the basic version of the ant colony algorithm. With comparable computational costs, the dynamic distribution scheme provides an improvement in the objective function by an average of 6% and also enhances the system's adaptability to dynamic changes in input parameters.