АЛГОРИТМ ПОСЛЕДОВАТЕЛЬНОЙ ГИБРИДИЗАЦИИ ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА
Аннотация
Задача коммивояжера является задачей комбинаторной оптимизации. В статье при- водится постановка данной задачи и предлагается графовая математическая модель, в ко- торой вершины соответствуют городам, а рёбра – это пути между городами, причем пред- полагается, что граф взвешен. Решение задачи коммивояжёра состоит в нахождении га- мильтонова цикла минимального веса в полном взвешенном графе. Задача является NP- трудной, поэтому для решения данной задачи используется эвристический подход для полу- чения решения задачи на больших объёмах входных данных. Эвристика заключается в приме- нении для решения задачи коммивояжера гибридизации двух алгоритмов: алгоритма имита- ции отжига и алгоритма ближайшего соседа. Для решения задачи коммивояжера использу- ется последовательная схема гибридизации. Основная идея заключается в том, что на стартовом наборе решений запускается метод ближайшего соседа, а затем лучшее реше- ние, полученное на первом этапе, подается на вход алгоритму имитации отжига. В статье подробно освещены построение, блок-схемы гибридного алгоритма, алгоритма имитации отжига и метода ближайшего соседа. Далее в статье приводится описание пользователь- ского интерфейса приложения, написанного на Typescript. Приложение использует реальную карту местности для решения задачи коммивояжера. В последней части статьи освещает- ся сравнительный анализ эффективности работы алгоритмов: сравнение точности и време- ни работы разработанного гибридного алгоритма, алгоритма имитации отжига и метода ближайшего соседа на различных входных наборах данных. Удалось установить, что разра- ботанный гибридный алгоритм находится на втором месте по скорости работы и на пер- вом по качеству решения среди реализованных алгоритмов. Кроме того, разработанное ре- шение имеет высокую экономическую и практическую ценность ввиду того, что приложение для решения задачи коммивояжера, а следовательно, приложение для навигации по маршру- ту может заменить существующие аналоги или же оно может быть использовано в каких- либо узконаправленных областях, а также в логистике.
