МЕТОД РЕШЕНИЯ ПРОБЛЕМЫ МУЛЬТИ-КОММИВОЯЖЁРА В СРЕДЕ БЕЗ ПРЕПЯТСТВИЙ НА ОСНОВЕ УМЕНЬШЕНИЯ РАЗМЕРА ПРОСТРАНСТВА РЕШЕНИЙ
Ключевые слова:
Задача мульти коммивояжера, распределение задач, целераспределение, мультиагентные системы, централизованное управление, групповое управлениеАннотация
Проводится анализ проблемы мульти коммивояжера, которая в отличие от знаме-
нитой задачи коммивояжера, задействует несколько коммивояжёров, которые посещают
заданное количество городов ровно один раз и возвращаются в исходное положение с ми-
нимальными затратами на поездку. Задача мульти коммивояжера является важной для
области оптимизации маршрутов и распределения назначений между несколькими аген-
тами. Основной целью исследования является разработка эффективного метода решения
данной проблемы, который позволит сократить время выполнения задач и оптимизиро-
вать использование ресурсов. В ходе исследования был создан инновационный метод, осно-
ванный на уменьшении размерности пространства решений. Этот метод позволяет более
эффективно управлять нагрузкой и ресурсами, что в свою очередь способствует миними-
зации общего времени выполнения задач. Особенностью метода является его универсаль-
ность и применимость в различных сценариях, включая ситуации с разным количеством
задач и коммивояжеров. Такой подход обеспечивает более широкий охват и позволяет
оценить применимость метода в различных контекстах, что является важным преиму-
ществом данного исследования. Для оценки эффективности разработанного метода было
проведено сравнительное исследование с использованием классического метода решения
проблемы мульти коммивояжера. Оценка результатов осуществлялась на основе трех
ключевых критериев: вычислительного времени получения решения задачи мульти комми-
вояжера, суммарной длины пройденных маршрутов коммивояжерами и максимальной дли-
ны маршрута среди них. Анализ экспериментальных данных показал, что разработанный
метод значительно превосходит классический подход по всем рассматриваемым критери-
ям в большинстве экспериментов, так как при использовании предложенного метода сред-
нее время расчета для задачи мульти коммивояжера уменьшается на 56% по сравнению с
наилучшим известным классическим результатом, при этим средняя сумма длины прой-
денных маршрутов коммивояжерами соответственно уменьшается на 12% и максималь-
ная длина пути среди пройдённых агентами маршрутов (дисбаланс нагрузки) уменьшается
на 8%, что подтверждает высокую эффективность предложенного метода и перспек-
тивность для практического применения в различных сферах, где требуется оптимизация
маршрутов и распределения задач между несколькими исполнителями
