Алгоритмы локального поиска для решения задачи коммивояжера: дипломная работа / Фёдор Алексеевич Коробейников; БГУ, Факультет прикладной математики и информатики, Кафедра дискретной математики и алгоритмики; науч. рук. Сарванов В. И.

Abstract

Объект исследования: задача коммивояжера. Цель работы: разработка и анализ алгоритмов локального поиска для решения задачи коммивояжера. Результат: изучены и программно реализованы известные эвристические алгоритмы для решения задачи коммивояжера. Изучен ряд известных окрестностей для локального поиска в задаче коммивояжера. Программно реализован поиск оптимума в различных окрестностях экспоненциальной мощности. Предложена новая окрестность экспоненциальной мощности – k-sets окрестность. Разработан алгоритм поиска оптимума в k-sets окрестности. Предложено обобщение пирамидальной окрестности – k-пирамидальная окрестность. Был проведен вычислительный эксперимент на основе которого был произведен анализ эффективности реализованных алгоритмов. Область применения: комбинаторная оптимизация, теория расписаний.