Найти

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

• АЛГОРИТМ ПОСЛЕДОВАТЕЛЬНОЙ ГИБРИДИЗАЦИИ ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА

  Е. Е. Полупанова, А.А. Рыбалко

  2023-08-14

  Аннотация ▼

  Задача коммивояжера является задачей комбинаторной оптимизации. В статье при-
  водится постановка данной задачи и предлагается графовая математическая модель, в ко-
  торой вершины соответствуют городам, а рёбра – это пути между городами, причем пред-
  полагается, что граф взвешен. Решение задачи коммивояжёра состоит в нахождении га-
  мильтонова цикла минимального веса в полном взвешенном графе. Задача является NP-
  трудной, поэтому для решения данной задачи используется эвристический подход для полу-
  чения решения задачи на больших объёмах входных данных. Эвристика заключается в приме-
  нении для решения задачи коммивояжера гибридизации двух алгоритмов: алгоритма имита-
  ции отжига и алгоритма ближайшего соседа. Для решения задачи коммивояжера использу-
  ется последовательная схема гибридизации. Основная идея заключается в том, что на
  стартовом наборе решений запускается метод ближайшего соседа, а затем лучшее реше-
  ние, полученное на первом этапе, подается на вход алгоритму имитации отжига. В статье
  подробно освещены построение, блок-схемы гибридного алгоритма, алгоритма имитации
  отжига и метода ближайшего соседа. Далее в статье приводится описание пользователь-
  ского интерфейса приложения, написанного на Typescript. Приложение использует реальную
  карту местности для решения задачи коммивояжера. В последней части статьи освещает-
  ся сравнительный анализ эффективности работы алгоритмов: сравнение точности и време-
  ни работы разработанного гибридного алгоритма, алгоритма имитации отжига и метода
  ближайшего соседа на различных входных наборах данных. Удалось установить, что разра-
  ботанный гибридный алгоритм находится на втором месте по скорости работы и на пер-
  вом по качеству решения среди реализованных алгоритмов. Кроме того, разработанное ре-
  шение имеет высокую экономическую и практическую ценность ввиду того, что приложение
  для решения задачи коммивояжера, а следовательно, приложение для навигации по маршру-
  ту может заменить существующие аналоги или же оно может быть использовано в каких-
  либо узконаправленных областях, а также в логистике.