Найти

Результаты поиска

• ГИБРИДНЫЙ МЕТОД РЕШЕНИЯ МНОГОАГЕНТНОЙ ЗАДАЧИ КОММИВОЯЖЁРА

  В.А. Костюков , Ф.А. Хуссейн

  2025-04-27

  Аннотация ▼

  Рассматривается проблема распределения задач в многоагентной системе, где каждый
  агент представляет собой робота, а каждая задача представляется позицией, которая должна
  быть посещена одним агентом. Эта задача очень похожа на многоагентную задачу коммивояжё-
  ра, которая в отличие от знаменитой задачи коммивояжера, задействует несколько коммивоя-
  жёров, которые посещают заданное количество городов ровно один раз и возвращаются в исход-
  ное положение с минимальными затратами на поездку. Поэтому проводится анализ многоагент-
  ной задачи коммивояжёра как представителя задачи целераспределения. Многоагентная задача
  коммивояжера является важной для области оптимизации маршрутов и распределения задач
  между несколькими агентами. Она включает в себе две различные, однако, взаимосвязанные под задачи: распределение городов между агентами и определение порядка посещения городов каж-
  дым агентом. В литературе существуют три концепции решения этой проблемы относительно
  решения ее двух составляющих подзадач: оптимизационная концепция, где обе подзадачи реша-
  ются одновременно; концепция Cluster-First, Route-Second – где сначала решается вопрос о назна-
  чении задач каждому коммивояжеру, а потом - вопрос о порядке посещений пунктов назначений
  для каждого коммивояжёра; концепция Route-First, Cluster-Second – где сначала решается вопрос
  о порядке посещения пунктов назначения, а затем происходит разделение этого цикла между
  агентами без изменения порядка посещений. В этой работы предлагается гибридный подход к
  решению многоагентной задачи коммивояжера, который объединяет идеи двух известных кон-
  цепций: Cluster-First, Route- econd и Route-First, Cluster- econd чтобы получить их позитивные
  аспекты и избавиться от их негативных сторон. Для оценки эффективности разработанного
  метода было проведено сравнительное исследование. Оценка результатов осуществлялась на
  основе трех ключевых критериев: вычислительного времени получения решения многоагентной
  задачи коммивояжера, суммарной длины пройденных маршрутов коммивояжерами и максималь-
  ной длины маршрута среди них. Анализ экспериментальных данных показал, что при использова-
  нии предложенного метода максимальная длина пути среди пройдённых агентами маршрутов
  (дисбаланс нагрузки) уменьшается в среднем на 26%.