Динамический мультиагентный подход для решения задачи циклической маршрутизации

Настоящая статья посвящена исследованию мультиагентной задачи коммивояжера с общим депо и динамическим распределением точек обслуживания. В отличие от традиционных подходов, предполагающих предварительную кластеризацию множества и жесткое закрепление точек за агентами, предлагаемый метод обеспечивает адаптивное формирование зон обслуживания непосредственно в ходе конструирования маршрутов. Принцип распределения основан на последовательной минимизации длины циклических маршрутов для каждого агента, выходящего из своей стартовой точки (т. е. депо), что обусловливает образование пространственно обособленных и компактных кластеров. Маршрутизация внутри формируемых подмножеств осуществляется с использованием модифицированного муравьиного алгоритма, в котором переходная вероятность учитывает, наряду с интенсивностью феромонового следа и информацией, обратно пропорциональной расстоянию, дополнительный корректирующий множитель, отражающий близость кандидата к стартовой вершине. Данная архитектура позволяет решать задачи кластеризации и маршрутизации согласованно в рамках единого оптимизационного процесса, исключая необходимость этапа предварительного разбиения. Реализована многопоточная обработка формируемых кластеров, обеспечивающая масштабируемость алгоритма при росте числа агентов. Результаты вычислительных экспериментов на стандартных тестовых наборах различной размерности подтверждают эффективность предложенного подхода по критерию минимизации суммарной длины маршрутов. Установлено, что интеграция фактора близости к начальной позиции в эвристическую функцию способствует формированию более компактных траекторий по сравнению с базовой версией муравьиного алгоритма. При сопоставимых вычислительных издержках динамическая схема распределения обеспечивает улучшение целевой функции в среднем на 6 %, а также повышает адаптивность системы к динамическим изменениям входных параметров.

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 (дата обращения: 17.01.2026).

2. ITF, The Final frontier of urban logistics: tackling the last metres // ITF Mobility Innovation Hub. Paris : OECD Publishing, 2024. No. 131. URL: https://www.itf-oecd.org/sites/default/files/docs/final-frontier-urban-logistics.pdf (дата обращения: 17.01.2026).

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 (дата обращения: 20.01.2026).

4. Мифтахов Э. Н., Акимов А. А., Гнатенко Ю. А. Методы роевой оптимизации частиц и локальных эвристик для решения мультиагентной задачи коммивояжера // Научно-технический вестник информационных технологий, механики и оптики. 2025. Т. 25, № 5. С. 856–865. DOI 10.17586/2226-1494-2025-25-5-856-865.

5. Телегин В. А. Муравьиные алгоритмы для решения задачи коммивояжера // Международный научно-исследовательский журнал. 2024. № 7 (145). URL: https://research-journal.org/archive/7-145-2024-july/10.60797/IRJ.2024.145.64 (дата обращения: 23.01.2026).

6. Mo Y., You X., Liu S. Multi-colony ant optimization with dynamic collaborative mechanism and cooperative game // Complex Intell. 2022. Syst. 8. Р. 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. No. 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. Р. 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. Vol. 26, No. 1. P. 29–41. doi.org/10.1109/3477.484436.

10. Германчук М. С. Знаниеориентированные модели многоагентной маршрутизации. Симферополь : ФГАОУ ВО «КФУ им. В. И. Вернадского», 2022. 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 (дата обращения: 23.01.2026).

11. Хабаров В. И., Квашнин В. Е. Мультиагентные системы маршрутизации при организации городских перевозок // Вестник Сибирского государственного университета путей сообщения. 2025. № 2 (74). С. 94–102. DOI 10.52170/1815-9265_2025_74_94.