Multi-agent routing systems in urban transport management
https://doi.org/10.52170/1815-9265_2025_74_94
Abstract
This paper investigates modern urban logistics problems related to the need to adapt the routes of different vehicles to the changing conditions of the urban environment. The main attention is paid to the many-to-many salesman problem (MTSP), which is formalized in a multi-agent setting (MATSP) with mandatory visits to dedicated loading/unloading points, since the problem posed in such a context allows us to consider scenarios close to those typical of urban distribution systems. The paper analyses different solution methods: evolutionary algorithms, swarm intelligence algorithms (bee swarm and ant colony) and simulated annealing algorithm.
As part of the research conducted, a mathematical model of the MATSP problem is formulated to define the main constraints as well as the target function subjected to optimization. Further, comparative computational experiments are conducted for the multiple travelling salesman problem with drop-off points in order to determine the performance evaluation on test datasets with selected service areas. These experiments allow us to clearly identify the features of each algorithm, which provides a basis for determining the target algorithm depending on the input data. Special attention is paid to the classification of MATSP tasks, which contains the following classes: basic, balanced, dynamic and with dedicated loading/unloading points. Both static and dynamic aspects of the task are investigated, including online point addition and real-time route recalculation. The results of the study demonstrate the promise of using a multi-agent approach to solve urban routing problems, especially in the context of changing parameters and the need to respond quickly to changes.
About the Authors
V. I. Khabarov
Siberian Transport University;
Novosibirsk State Technical University
Russian Federation
Russian Federation
Valery I. Khabarov – Doctor of Engineering, Professor, Academician of Russian Academy of Transport, Dean of the Information Technology in Business Faculty, Head of the Information Technologies in Transport Department, Professor of the Theoretical and Applied Information Science Department
Novosibirsk
V. E. Kvashnin
Siberian Transport University
Russian Federation
Russian Federation
Vladislav E. Kvashnin – Postgraduate of the Information Technologies in Transport Department
Novosibirsk
References
1. Xie XF, Liu J. Multiagent optimization system for solving the traveling salesman problem (TSP). IEEE Trans Syst Man Cybern B Cybern. 2009 Apr; 39(2): 489-502. doi: 10.1109/TSMCB.2008.2006910. Epub 2008 Dec 16. PMID: 19095545.
2. Vali M., Salimifard K. A constraint programming approach for solving multiple traveling salesman problem. The Sixteenth International Workshop on Constraint Modelling and Reformulation, 2017
3. Shabanpour M., Yadollahi M., Hasani M. M. A New Method to Solve the Multi Traveling Salesman Problem with the Combination of Genetic Algorithm and Clustering Technique. IJCSNS International Journal of Computer Science and Network Security, Vol. 17, No. 5, 2017.
4. Makarov O. O. Analysis of metaheuristics for multi-agent routing tasks. Taurida Journal of Computer Science Theory and Mathematics. 2023. (In Russ.). URL: https://cyberleninka.ru/article/n/analiz-metaevristik-dlya-zadach-mnogoagentnoy-marshrutizatsii.
5. Hermanchuk M. S. Applied tasks of multi-agent routing. Taurida journal of computer science theory and mathematics. 2021. URL: https://cyberleninka.ru/article/n/prikladnye-zadachi-mnogoagentnoy-marshrutizatsii. (In Russ.).
6. Houssein F. A., Kostyukov V. F., Evdokimov I. D. A method for solving the multi-traveling salesman problem based on reducing the size of the solution space. 10th International Conference on Control, Decision and Information Technologies (CoDIT). 2024. P. 1729–1733. DOI 10.1109/CoDIT62066.2024.10708116.
7. Agapova E. G., Popova T. M. Tasks of the travelling salesman at route path optimization. International Journal of Applied Science, 2019;(4). (In Russ.). URL: https://cyberleninka.ru/article/n/zadachi-kommivoyazhera-pri-optimizatsii-marshrutnogo-puti.
8. Sofge D., Schultz A., De Jong K. Evolutionary computational approaches to solving the multiple traveling salesman problem using a neighborhood attractor schema. Proceedings of the Applications of Evolutionary Computing on EvoWorkshops. 2002. P. 153–162.
9. Prins C. A simple and effective evolutionary algorithm for the vehicle routing problem. Comput. Oper. Res. 2004;31:1985–2002.
10. Peshkevich A. A., Kobak V. G., Zhukovsky A. G. Solution of the travelling salesman problem using a two-stage genetic algorithm. Engineering Journal of Don. 2018;(50). (In Russ.). URL: https://cyberleninka.ru/article/n/reshenie-zadachi-kommivoyazhera-s-ispolzovaniem-dvuhetapnogo-geneticheskogo-algoritma.
11. Xu Z., Li Y., Feng X. Constrained multi-objective task assignment for UUVS using multiple ant colonies system. ISECS International Colloquium on Computing, Communication, Control, and Management. 2008;1:462– 466. DOI 10.1109/CCCM.2008.318.
12. Mikulik I. I., Blagoveschenskaya E. A. Parallelization of the hybrid ant colony algorithm with parameters changing with the help of genetic algorithm. Problems of Informatics. 2023. (In Russ.). URL: https://cyberleninka.ru/article/n/rasparallelivanie-gibridnogo-algoritma-muravinoy-kolonii-s-izmenyayuschimisya-s-pomoschyu-geneticheskogo-algoritma-parametrami.
13. Semenkina O. E., Semenkin E. S. Study of the parallel ant algorithm efficiency on the travelling salesman problem. Actual Problems of Aviation and Cosmonautics. 2012. (In Russ.). URL: https://cyberleninka.ru/article/n/issledovanie-effektivnosti-parallelnogo-muravinogo-algoritma-na-zadache-kommivoyazhera.
14. 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. https://doi.org/10.1109/3477.484436.
15. Skeena S. S. Algorithms. Development Guide. Third edition. Translated from English. Saint-Peterburg; 2022. 848 р. (In Russ.).
16. Polyakov I. V., Chepovskiy A. A., Chepovskiy A. M. Pathfinding algorithms on graphs of large size. Fundamental. and Applied Mathematics, Moscow; 2014. P. 165–172. (In Russ.).
17. Hermanchuk M. S. Knowledge-oriented models of multi-agent routing. Simferopol: V. I. Vernadsky Crimean Federal University; 2022. (In Russ.).
18. Russell Stuart, Norvig Peter. Artificial Intelligence: A Modern Approach. Second edition. Translated from English. Moscow: Williams Publishing House; 2007. 1408 p. (In Russ.).
19. Zavlanos Michael M, Leonid Spesivtsev and George J Pappas. A Distributed Auction Algorithm for the Assignment Problem. Proceedings of IEEE CDC'08, 1212–17, IEEE. 2008. DOI 10.1109/CDC.2008.4739098.
20. Beasley J. E. Route First – Cluster Second Methods for Vehicle Routing. Omega. 1983;1(4):403–408.
21. Seraya O. B., Dunayevskaya O. I. Multi-step clustering in the task of a high dimensional travelling salesman. Eastern European Journal of Advanced Technology. 2008. (In Russ.). URL: https://cyberleninka.ru/article/n/mnogoshagovaya-klasterizatsiya-v-zadache-kommivoyazhera-vysokoy-razmernosti.
22. Antonova E. S., Virchenko Yu. P. Finite clusters on plane mosaics. Part I. Operations of gluing and cutting of graphs. Applied Mathematics and Physics. 2011. (In Russ.). URL: https://cyberleninka.ru/article/n/konechnye-klastery-na-ploskih-mozaikah-chast-i-operatsii-skleivaniya-i-razrezaniya-grafov.
23. Ershov K. S., Romanova T. N. Analysis and classification of clustering algorithms. New Information Technologies in Automated Systems. 2016. (In Russ.). URL: https://cyberleninka.ru/article/n/analiz-i-klassifikatsiya-algoritmov-klasterizatsii.
Review
For citations:
Khabarov V.I., Kvashnin V.E. Multi-agent routing systems in urban transport management. Bulletin of Siberian State University of Transport. 2025;(2):94-102. (In Russ.) https://doi.org/10.52170/1815-9265_2025_74_94
Views:
8
Email this article 