• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

Сравнительный анализ комбинаций метода ветвей и границ с метаэвристическими алгоритмами для решения асимметричной задачи коммивояжёра

Информационные технологии. 2019. Т. 25. № 10. С. 590-595.

Алгоритм, реализующий метод ветвей и границ, для решения задачи коммивояжера - один из востребованных точных алгоритмов ее решения. Метаэвристические алгоритмы решения этой задачи не гарантируют получения точного решения, но работают "быстро". Для сокращения числа вершин порожденного дерева решений в методе ветвей и границ можно использовать решение, полученное метаэвристическим алгоритмом. За счет выбора метаэвристического алгоритма и его комбинации с методом ветвей и границ можно получить выигрышво времени получения точного решения. Такой выбор необходимо подтверждать экспериментальными даннымио временной эффективности программной реализации такого комбинированного алгоритма. В данной статьерассматриваются некоторые метаэвристические алгоритмы и комбинация таких алгоритмов с классической реализацией метода ветвей и границ для решения асимметричной задачи коммивояжера. Приводятся данныеэкспериментального исследования среднего времени получения точного решения для диапазона размерности задачи от 30 до 45 и даются рекомендации по выбору метаэвристического алгоритма.