Мифтахов Эльдар Наилевич — доктор физико-математических наук, профессор
sc 56178153800
Москва, 119454
Eldar N. Miftakhov —
sc 56178153800
Moscow, 119454
Акимов Андрей Анатольевич — кандидат физико-математических наук, доцент, доцент
sc 56428598700
Москва, 119454
Andrey A. Akimov — PhD (Physics & Mathematics), Associate Professor, Associate Professor
sc 56428598700
Moscow, 119454
Гнатенко Юлия Ахнафовна — кандидат физико-математических наук, доцент, доцент
sc 9234055300
Стерлитамак, 453103
Yuliya A. Gnatenko — PhD (Physics & Mathematics), Associate Professor, Associate Professor
sc 9234055300
Sterlitamak, 453103
Введение. Представлены результаты разработки и апробации метода решения мультиагентной задачи коммивояжёра (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, что подтверждает эффективность предложенного решения.
Обсуждение. Разработанный алгоритм может найти применение в логистике, транспортном планировании, распределении потоков в сетях связи и иных областях, где требуется оптимальное распределение ресурсов. Представленный метод будет полезен специалистам в области оптимизации, алгоритмического моделирования и практикам, занимающимся разработкой систем управления и планирования.
This paper presents the development and evaluation of a method for solving the Multiple Traveling Salesman Problem (mTSP), with the objective of minimizing the maximum route length (“minimax” optimization). The study addresses the combinatorial route-space arising from distributing cities among multiple agents, requiring balanced workload distribution to avoid overloading individual routes. The novelty of the proposed approach lies in creating a discrete analogue of the classical Particle Swarm Optimization (PSO) algorithm adapted specifically for permutation-based route representations, and integrating it with local heuristic procedures and the Ant Colony Optimization (ACO) algorithm. The proposed method transforms the original mTSP into a classical single-agent Traveling Salesman Problem (TSP) by introducing artificial (dummy) depots, thus allowing an unambiguous separation of the overall route into individual segments for each agent. A key element of the solution involves adapting the PSO algorithm through novel discrete operations, such as computing the minimal sequence of exchanges (transpositions) between permutations, scaling velocity, and applying this velocity to routes. This approach ensures efficient exploration of the combinatorial solution space and prevents premature convergence of the algorithm. The experimental study was conducted on benchmark instances from the TSPLIB library (eil51.tsp, berlin52.tsp, eil76.tsp, rat99.tsp) for the TSP, comparing two scenarios: a classical PSO with random initialization and a hybrid PSO_ACO method where the ACO algorithm is used to generate the initial population. The results demonstrate a significant improvement in the minimax criterion compared to CPLEX, LKH3, OR-Tools as well as state-of-the-art approaches DAN, NCE, and EA, confirming the effectiveness of the proposed solution. The practical importance of this research lies in potential applications of the developed algorithm in logistics, transport planning, network traffic management, and other domains where optimal resource allocation is crucial. The proposed method is valuable for specialists in optimization, algorithmic modeling, and practitioners developing planning and management systems.
The authors declare that there are no conflicts of interest present.