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

Miftakhov Eldar N., Andrey A. Akimov, Yuliya A. Gnatenko

2025 , VOLUME 25, NUMBER 5 ( september-october )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Publications

Editor-in-Chief

Nikiforov
Vladimir O.
D.Sc., Prof.

Partners

doi: 10.17586/2226-1494-2025-25-5-856-865

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

E. N. Miftakhov, A. A. Akimov, Y. A. Gnatenko

Read the full article

Article in Russian

For citation:

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

Abstract

В данной работе представлены разработка и оценка метода решения задачи коммивояжёра (mTSP) с целью минимизации максимальной длины маршрута (минимаксная оптимизация). В исследовании рассматривается комбинаторное пространство маршрутов, возникающее при распределении городов между несколькими агентами, что требует сбалансированного распределения рабочей нагрузки для предотвращения перегрузки отдельных маршрутов. Новизна предлагаемого подхода заключается в создании дискретного аналога классического алгоритма оптимизации роя частиц (PSO), специально адаптированного для представления маршрутов на основе перестановок, и его интеграции с локальными эвристическими процедурами и алгоритмом оптимизации колонии муравьёв (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, что подтверждает эффективность предлагаемого решения. Практическая значимость данного исследования заключается в возможности применения разработанного алгоритма в логистике, транспортном планировании, управлении сетевым трафиком и других областях, где оптимальное распределение ресурсов имеет решающее значение. Предложенный метод будет полезен специалистам по оптимизации, алгоритмическому моделированию и разработчикам систем планирования и управления.

Keywords: particle swarm optimization, multiple traveling salesman problem, minimax optimization, discrete optimization, ant colony optimization, local heuristics

References

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, vol. 175, no. 1, pp. 246–257. https://doi.org/10.1016/j.ejor.2005.04.027

2. Smirnov A.V. Investigation of influence of objective function valley ratio on the determination error of its minimum coordinates. Russian Technological Journal, vol. 11, no. 6, pp. 57–67. (in Russian). 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, vol. 33, no. 10, pp. 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, vol. 90, pp. 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, vol. 25, pp. 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, vol. 124, no. 2, pp. 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, vol. 76, pp. 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, vol. 1447, pp. 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, pp. 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, pp. 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, vol. 3172, pp. 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, vol. 34, no. 10, pp. 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, vol. 1, pp. 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, pp. 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, vol. 12, pp. 966–980.

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

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