53947

Автор(ы): 

Автор(ов): 

2

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

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

DOI: 

10.17587/it.25

Наименование источника: 

  • Информационные технологии

Обозначение и номер тома: 

Т. 25, №10

Город: 

  • Москва

Издательство: 

  • Новые Технологии

Год издания: 

2019

Страницы: 

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

Библиографическая ссылка: 

Ульянов М.В., Фомичев М.И. Сравнительный анализ комбинаций метода ветвей и границ с метаэвристическими алгоритмами для решения асимметричной задачи коммивояжера // Информационные технологии. 2019. Т. 25, №10. С. 590-595.