Введение к работе
Актуальность исследования. Задача о коммивояжёре – traveling salesman problem (TSP, ЗКВ) – является NP-сложной задачей дискретной оптимизации. Для нее не найдено, и возможно, не существует быстрых, полиномиальных алгоритмов. На графах она формулируется следующим образом: требуется найти гамильтонов цикл наименьшей стоимости во взвешенном полном графе. Т.е. выйдя из стартовой вершины, посетить каждую вершину графа ровно один раз и вернуться в начальную по кратчайшему пути.
Поиск точных и приближённых способов решения задачи о коммивояжёре остается актуальным и с теоретической и с практической точек зрения. Результатом теоретических исследований являются такие методы как:
релаксации линейного программирования, релаксация Лагранжа, метод ветвей и отсечений, метод ветвей и границ (МВГ)
распределенный метод ветвей и границ, решатели ЛП (задачи линейного программирования)
эвристические: симулированный отжиг, генетические алгоритмы, цепная локальная оптимизация, поиск с запретами.
В этом смысле задача о коммивояжёре является упрощённой моделью для многих других задач дискретной оптимизации, а также часто является подзадачей, например, в задаче о маршрутизации.
Программные коды, предназначенные для решения на оптимальность задачи о коммивояжёре, за последние 30 лет развились от решения задач размерности 100 до 10 000.
Среди приложений ЗКВ, встречающихся в литературе, можно отметить:
Оптимизацию в сетях
Оптимизацию маршрутов
Приложения в кристаллографии
Управление роботами
Обработку печатных плат
Исследование ДНК
«Городами» в различных задачах могут выступать как физические объекты, так и процессы, и другие сущности.
Основными актуальными вопросами, связанными с решением ЗКВ, являются
Быстрое точное решение асимметричных и симметричных ЗКВ больших размерностей
Быстрое приближённое решение асимметричных и симметричных ЗКВ больших размерностей
Разработка быстрых схем аппроксимации ЗКВ высокой точности
Диссертация посвящена новым подходам к решению этих задач: разработке новых алгоритмов и оптимизации существующих решений.
Цель работы. Целью настоящей работы является
создание новых алгоритмов и программ для точного и приближённого решения асимметричной и симметричной задачи о коммивояжёре
реализация и получение экспериментальных оценок эффективности схем аппроксимации ЗКВ
улучшение качества тура и ускорение существующих программ решения ЗКВ
поиск новых способов эффективного использования существующего программного обеспечения (ПО) по решению ЗКВ
Методы исследования. В исследовании использовались методы комбинаторного анализа, теории графов, дискретной оптимизации, линейного программирования, технологий распределённых вычислений.
Достоверность результатов обеспечивается строгостью постановок задач и использованием оттестированных компонентов программного обеспечения сторонних исследователей и разработчиков.
Научная новизна
Для достижения поставленных целей решены следующие задачи:
-
Разработан алгоритм решения асимметричной задачи о коммивояжёре (АЗКВ, ATSP) с помощью неэквивалентного преобразования к симметричной задаче о коммивояжёре (СЗКВ, STSP). Выработаны рекомендации по применению.
-
Реализованы и исследованы на эффективность алгоритмы распределенного метода ветвей и границ (МВГ) и полиномиальной аппроксимации СЗКВ PMCA.
-
Реализован алгоритм усеченного МВГ ZHANG1 с задачей о назначениях для АЗКВ. Получены оценки времени работы и качества тура. Выработаны рекомендации по применению.
-
Разработаны схемы экспериментов для исследования эффективности локальных отсечений в методах ветвей и отсечений (МВО, Branch and Cut) и эквивалентных преобразований в приближённых k-opt алгоритмах для АЗКВ. По результатам выработаны рекомендации по оптимизации времени и качества тура.
-
Экспериментально исследована эффективность отсечений ЗКВ для решения задачи маршрутизации (Vehicle Routing Problem – VRP). Подтверждена эффективность подхода.
Практическая значимость исследования. Все рассмотренные в работе алгоритмы и методы оптимизации обладают практической значимостью. Наиболее интересными с теоретической точки зрения являются алгоритмы решения асимметричной задачи о коммивояжёре путем неэквивалентного преобразования к симметричной задаче о коммивояжёре и методы повышения эффективности локальной оптимизации асимметричной задачи о коммивояжёре с использованием различных типов эквивалентных преобразований. Практически полезными эффектами являются улучшение качества получаемого решения (длина тура ЗКВ) и уменьшение времени решения (увеличение скорости решения).
Основные положения, выносимые на защиту:
-
Новый алгоритм решения асимметричной задачи о коммивояжёре путем неэквивалентного преобразования к симметричной задаче о коммивояжёре.
-
Программная реализация и экспериментальная оценка эффективности схемы полиномиальной аппроксимации симметричной задачи о коммивояжёре и распределенного метода ветвей и границ для симметричной задачи о коммивояжёре.
-
Методика повышения эффективности программ метода ветвей и отсечений, метода ветвей и границ с задачей о назначениях, и локальной оптимизации для асимметричной задачи о коммивояжёре.
Апробация работы.
Основные научные и практические результаты исследований по теме диссертации докладывались на
VI Международной конференции «Математическое моделирование физических, экономических, технических, социальных систем и процессов» (г. Ульяновск, 2005)
«XIII Всероссийской школе-коллоквиуме по стохастическим методам и VII Всероссийском симпозиуме по прикладной математике» (г. Йошкар-Ола, 2006)
девятом международном семинаре «Дискретная математика и ее приложения» (г. Москва, 2007)
Личный вклад. В работе использовались теоретические и практические разработки отечественных и зарубежных авторов. Формулировка новых алгоритмов, построение схем вычислительных экспериментов, программная реализация алгоритмов, анализ полученных результатов и обоснование выводов выполнены соискателем самостоятельно.
Публикации. По теме диссертации опубликовано 10 работ, в том числе 4 в ведущих рецензируемых журналах, рекомендованных ВАК.
Структура и объем диссертации. Общий объем диссертации 123 страницы. Диссертация состоит из введения, трех глав, заключения, списка используемой литературы из 89 наименований и одного приложения.
