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

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.

1. Hassett C. Last-Mile Delivery Statistics: The Complete Data Resource for 2025. SmartRoutes. 2025. URL: https://smartroutes.io/blogs/last-mile-delivery-statistics-the-complete-data-resource.

2. ITF, The Final Frontier of Urban Logistics: Tackling the Last Metres. ITF Mobility Innovation Hub No. 131, OECD Publishing, Paris. 2024. URL: https://www.itf-oecd.org/sites/default/files/docs/final-frontier-urban-logistics.pdf.

3. Holmes J., Brady-Phillips V. Transforming Urban Logistics: Sustainable and Efficient Last-Mile Delivery in Cities. World Economic Forum. 2024. URL: https://reports.weforum.org/docs/WEF_Transforming_Urban_Logistics_2024.pdf.

4. Miftakhov E. N., Akimov A. A., Gnatenko Yu. A. Methods of swarm optimization of particles and local heuristics for solving the multi-agent traveling salesman problem. Scientific and Technical Bulletin of Information Technologies, Mechanics and Optics. 2025;25(5):856–865. (In Russ.). DOI 10.17586/2226-1494-2025-25-5-856-865.

5. Telegin V. A. Ant colony algorithms for solving the traveling salesman problem. International Research Journal. 2024;(145). (In Russ.). URL: https://research-journal.org/archive/7-145-2024-july/10.60797/IRJ.2024.145.64.

6. Mo Y., You X., Liu S. Multi-colony ant optimization with dynamic collaborative mechanism and cooperative game. Complex Intell. 2022. Syst. 8. P. 4679–4696. DOI 10.1007/s40747-022-00716-7.

7. Olivari L., Đukić G. Current State of Dynamic Vehicle Routing Problems Solved by Ant Colony Optimization Algorithm. Tehnički Glasnik. 2021;(15(3)):429–434. DOI 10.31803/tg-20210708131104.

8. Wu H., Gao Y., Wang W. A hybrid ant colony algorithm based on multiple strategies for the vehicle routing problem with time windows. Complex Intell. 2023. Syst. 9. P. 2491–2508. DOI 10.1007/s40747-021-00401-1.

9. Dorigo M., Maniezzo V., Colorni A. Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics. Part B (Cybernetics). 1996;26(1):29–41. doi.org/10.1109/3477.484436.

10. Hermanchuk M.S. Knowledge-oriented models of multi-agent routing. Simferopol: V. I. Vernadsky Crimean Federal University; 2022. (In Russ.). URL: http://www.science.vsu.ru/dissertations/10681/%D0%94%D0%B8%D1%81%D1%81%D0%B5%D1%80%D1%82%D0%B0%D1%86%D0%B8%D1%8F_%D0%93%D0%B5%D1%80%D0%BC%D0%B0%D0%BD%D1%87%D1%83%D0%BA_%D0%9C.%D0%A1.pdf.

11. Khabarov V. I., Kvashnin V. E. Multi-agent routing systems in organizing urban transportation. The Siberian Transport University Bulletin. 2025;(74):94–102. (In Russ.). DOI 10.52170/1815-9265_2025_74_94.