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

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

Введение. Представлены результаты разработки и апробации метода решения мультиагентной задачи коммивояжёра (Multiple Traveling Salesman Problem, mTSP) с целью минимизации максимальной длины маршрутов («минимаксная» оптимизация). Объектом исследования является комбинаторное пространство маршрутов, возникающее при распределении городов между несколькими агентами, что обуславливает необходимость равномерного распределения нагрузки и предотвращения перегрузки отдельных маршрутов. Новизна подхода заключается в создании дискретного аналога классического алгоритма роевой оптимизации частиц (Particle Swarm Optimization, PSO), адаптированного для работы с перестановками, а также в интеграции его с локальными эвристическими процедурами и муравьиным алгоритмом (Ant Colony Optimization, ACO). Метод. Предложенный метод базируется на преобразовании исходной задачи mTSP в классическую задачу коммивояжёра для одного агента (TSP) посредством введения фиктивных депо, что позволяет однозначно разделить общий маршрут на отдельные части для каждого агента. Ключевым элементом является модификация PSO с использованием новых операций для дискретного пространства, таких как вычисление минимальной последовательности обменов (транспозиций) между перестановками, масштабирование скорости и применение ее к маршруту. Данный подход позволяет эффективно исследовать комбинаторное пространство решений и предотвращать преждевременную сходимость алгоритма. Основные результаты. Экспериментальное исследование проведено на тестовых наборах стандартной библиотеки TSPLIB (eil51.tsp, berlin52.tsp, eil76. tsp, rat99.tsp) для задачи TSP, в ходе которого сравнивались два сценария: классический PSO со случайной инициализацией и гибридный метод PSO_ACO, где метод ACO используется для формирования начальной популяции. Результаты эксперимента продемонстрировали существенное улучшение по «минимаксному» критерию по сравнению с методами CPLEX, LKH3, OR-Tools, а также современными подходами DAN, NCE и EA, что подтверждает эффективность предложенного решения. Обсуждение. Разработанный алгоритм может найти применение в логистике, транспортном планировании, распределении потоков в сетях связи и иных областях, где требуется оптимальное распределение ресурсов. Представленный метод будет полезен специалистам в области оптимизации, алгоритмического моделирования и практикам, занимающимся разработкой систем управления и планирования.

1. Carter A.E., Ragsdale C.T. A new approach to solving the multiple traveling salesperson problem using genetic algorithms // European Journal of Operational Research. 2006. V. 175. N 1. P. 246–257. https://doi.org/10.1016/j.ejor.2005.04.027

2. Смирнов А.В. Исследование влияния степени овражности целевой функции на погрешность определения координат ее минимума // Российский технологический журнал. 2023. Т. 11. № 6. С. 57–67. https://doi.org/10.32362/2500-316X-2023-11-6-57-67

3. Boudjelaba K., Ros F., Chikouche D. Potential of particle swarm optimization and genetic algorithms for FIR filter design // Circuits, Systems, and Signal Processing. 2014. V. 33. N 10. P. 3195–3222. https://doi.org/10.1007/s00034-014-9800-y

4. Soylu B. A general variable neighborhood search heuristic for multiple traveling salesmen problem // Computers & Industrial Engineering. 2015. V. 90. P. 390–401. https://doi.org/10.1016/j.cie.2015.10.010

5. Elloumi W., Abeda H.E., Abraham A., Alimi A.M. A comparative study of the improvement of performance using a PSO modified by ACO applied to TSP // Applied Soft Computing. 2014. V. 25. P. 234–241. https://doi.org/10.1016/j.asoc.2014.09.031

6. Tang L., Liu J., Rong A., Yang Z. A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex // European Journal of Operational Research. 2000. V. 124. N 2. P. 267–282. https://doi.org/10.1016/S0377-2217(99)00380-X

7. Lu L.C., Yue T.W. Mission-oriented ant-team ACO for min–max MTSP // Applied Soft Computing. 2019. V. 76. P. 436–444. https://doi.org/10.1016/j.asoc.2018.11.048

8. Eberhart R.C., Shi Y. Comparison between genetic algorithms and particle swarm optimization // Lecture Notes in Computer Science. 1998. V. 1447. P. 611–616. https://doi.org/10.1007/BFb0040812

9. Lupoaie V.-I., Chili I.-A., Breaban M.E., Raschip M. SOM-guided evolutionary search for solving MinMax Multiple-TSP // Proc. of the IEEE Congress on Evolutionary Computation (CEC). 2019. P. 73–80. https://doi.org/10.1109/cec.2019.8790276

10. Kim M., Park J., Park J. Learning to CROSS exchange to solve min-max vehicle routing problems // Proc. of the 11^th International Conference on Learning Representations (ICLR). 2023. P. 1–12.

11. Tasgetiren M.F., Sevkli M., Liang Y.C., Gencyilmaz G. Particle swarm optimization algorithm for permutation flowshop sequencing problem // Lecture Notes in Computer Science. 2004. V. 3172. P. 382–389. https://doi.org/10.1007/978-3-540-28646-2_38

12. Liao C.J., Tseng C.T., Luarn P. A discrete version of particle swarm optimization for flowshop scheduling problems // Computers and Operations Research. 2007. V. 34. N 10. P. 3099–3111. https://doi.org/10.1016/j.cor.2005.11.017

13. Junjie P., Dingwei W. An ant colony optimization algorithm for Multiple Travelling Salesman Problem // Proc. of the First International Conference on Innovative Computing, Information and Control (ICICIC'06). 2006. V. 1. P. 210–213. https://doi.org/10.1109/icicic.2006.40

14. Necula R., Breaban M., Raschip M. Tackling the Bi-criteria facet of Multiple Traveling Salesman Problem with Ant Colony Systems // Proc. of the IEEE 27^th International Conference on Tools with Artificial Intelligence (ICTAI). 2015. P. 873–880. https://doi.org/10.1109/ICTAI.2015.127

15. Helsgaun K. An Extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems // Occasional Paper of the Roskilde University, International Development Studies. 2017. V. 12. P. 966–980.

16. Perron L., Furnon V. OR-Tools v9.6. 2019. URL: https://developers.google.com/optimization/

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License