Мультиагентные системы маршрутизации при организации городских перевозок

   В данной работе исследуются современные проблемы городской логистики, связанные с необходимостью адаптации маршрутов различных транспортных средств к изменяющимся условиям городской среды. Основное внимание уделяется задаче многих коммивояжеров (MTSP), которая формализована в мультиагентной постановке (MATSP) с обязательным посещением выделенных точек погрузки/разгрузки, поскольку задача в таком контексте позволяет рассматривать сценарии, приближенные к типичным для систем городского распределения. В статье анализируются различные методы решения: эволюционные алгоритмы, алгоритмы роевого интеллекта (пчелиного роя и муравьиной колонии) и алгоритм имитации отжига.
   В рамках проведенного исследования сформулирована математическая модель задачи MATSP, позволяющая определить основные ограничения, а также целевую функцию, подвергаемую оптимизации. Далее проведены сравнительные вычислительные эксперименты для задачи нескольких коммивояжеров с точками вывоза для определения оценки эффективности на тестовых наборах данных с выделенными областями обслуживания. Данные эксперименты позволяют наглядным образом выявить особенности каждого из алгоритмов, что дает основу для определения целевого алгоритма в зависимости от входных данных. Отдельное внимание уделено классификации задачи MATSP, которая содержит в себе следующие классы: базовый, сбалансированный, динамический и с выделенными точками погрузки/разгрузки. Исследуются как статические, так и динамические аспекты задачи, включая онлайн-добавление точек и перерасчет маршрутов в реальном времени. Полученные результаты исследования демонстрируют перспективность использования мультиагентного подхода для решения задач городской маршрутизации, особенно в условиях изменяющихся параметров и необходимости оперативного реагирования на изменения.

1. Xie XF, Liu J. Multiagent optimization system for solving the traveling salesman problem (TSP) // IEEE Trans Syst Man Cybern B Cybern. 2009. 39 (2), Apr. Р. 489–502. DOI 10.1109/TSMCB.2008.2006910.

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. 2017. Vol. 17, No. 5. Р. 221–230.

4. Макаров О. О. Анализ метаэвристик для задач многоагентной маршрутизации // Таврический вестник информатики и математики. 2023. URL: https://cyberleninka.ru/article/n/analiz-metaevristik-dlya-zadach-mnogoagentnoy-marshrutizatsii (дата обращения: 04.05.2025).

5. Германчук М. С. Прикладные задачи многоагентной маршрутизации // Таврический вестник информатики и математики. 2021. URL: https://cyberleninka.ru/article/n/prikladnye-zadachi-mnogoagentnoy-marsh-rutizatsii (дата обращения: 04.05.2025).

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. Р. 1729–1733. DOI 10.1109/CoDIT62066.2024.10708116.

7. Агапова Е. Г., Попова Т. М. Задачи коммивояжера при оптимизации маршрутного пути // IJAS. 2019. № 4. URL: https://cyberleninka.ru/article/n/zadachi-kommivoyazhera-pri-optimizatsii-marshrutnogo-puti (дата обращения: 07.11.2024).

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. Vol. 31. P. 1985–2002.

10. Пешкевич А. А., Кобак В. Г., Жуковский А. Г. Решение задачи коммивояжера с использованием двухэтапного генетического алгоритма // Инженерный вестник Дона. 2018. № 3 (50). URL: https://cyber-leninka.ru/article/n/reshenie-zadachi-kommivoyazhera-s-ispolzovaniem-dvuhetapnogo-geneticheskogo-algoritma (дата обращения: 04.05.2025).

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. Vol. 1. P. 462–466. DOI 10.1109/CCCM.2008.318.

12. Микулик И. И., Благовещенская Е. А. Распараллеливание гибридного алгоритма муравьиной колонии с изменяющимися с помощью генетического алгоритма параметрами // Проблемы информатики. 2023. URL: https://cyberleninka.ru/article/n/rasparallelivanie-gibridnogo-algoritma-muravinoy-kolonii-s-izmenyay-uschimisya-s-pomoschyu-geneticheskogo-algoritma-parametrami (дата обращения: 06.05.2025).

13. Семенкина О. Е., Семенкин Е. С. Исследование эффективности параллельного муравьиного алгоритма на задаче коммивояжера // Актуальные проблемы авиации и космонавтики. 2012. URL: https://cyber-leninka.ru/article/n/issledovanie-effektivnosti-parallelnogo-muravinogo-algoritma-na-zadache-kommivoyazhera (дата обращения: 06.05.2025).

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. Vol. 26, No. 1. P. 29–41. https://doi.org/10.1109/3477.484436.

15. Скиена С. С. Алгоритмы : руководство по разработке : пер. с англ. 3-е изд. Санкт-Петербург : БХВПетербург, 2022. 848 с.

16. Поляков И. В., Чеповский А. А., Чеповский А. М. Алгоритмы поиска путей на графах большого размера // Фундаментальная и прикладная математика. Москва, 2014. С. 165–172.

17. Германчук М. С. Знаниеориентированные модели многоагентной маршрутизации : специальность 05.13.18 «Математическое моделирование, численные методы и комплексы программ» : диссертация на соискание ученой степени кандидата физико-математических наук / Германчук Мария Сергеевна ; ФГАОУ ВО «КФУ им. В. И. Вернадского». Симферополь, 2022. 150 с.

18. Рассел Стюарт, Норвиг Питер. Искусственный интеллект: современный подход : пер. с англ. 2-е изд. Москва : Вильямс, 2007. 1408 с.

19. Zavlanos Michael M., Spesivtsev Leonid and Pappas George J. 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. Vol. 1, Iss. 4. P. 403–408.

21. Cepaя O. B., Дунаевская О. И. Многошаговая кластеризация в задаче коммивояжера высокой размерности // Восточно-Европейский журнал передовых технологий. 2008. URL: https://cyberleninka.ru/arti-cle/n/mnogoshagovaya-klasterizatsiya-v-zadache-kommivoyazhera-vysokoy-razmernosti (дата обращения: 07.11.2024).

22. Антонова Е. С., Вирченко Ю. П. Конечные кластеры на плоских мозаиках. Часть I. Операции склеивания и разрезания графов // Прикладная математика & Физика. 2011. URL: https://cyberleninka.ru/article/n/konechnye-klastery-na-ploskih-mozaikah-chast-i-operatsii-skleivaniya-i-razrezaniya-grafov (дата обращения: 13.11.2024).

23. Ершов К. С., Романова Т. Н. Анализ и классификация алгоритмов кластеризации // Новые информационные технологии в автоматизированных системах. 2016. URL: https://cyberleninka.ru/article/n/analiz-i-klassifikatsiya-algoritmov-klasterizatsii (дата обращения: 13.11.2024).