Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Комплекс программ для исследования методов решения задачи о коммивояжере Ляликов Вадим Николаевич

Комплекс программ для исследования методов решения задачи о коммивояжере
<
Комплекс программ для исследования методов решения задачи о коммивояжере Комплекс программ для исследования методов решения задачи о коммивояжере Комплекс программ для исследования методов решения задачи о коммивояжере Комплекс программ для исследования методов решения задачи о коммивояжере Комплекс программ для исследования методов решения задачи о коммивояжере
>

Диссертация, - 480 руб., доставка 1-3 часа, с 10-19 (Московское время), кроме воскресенья

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Ляликов Вадим Николаевич. Комплекс программ для исследования методов решения задачи о коммивояжере : диссертация ... кандидата технических наук : 05.13.18 / Ляликов Вадим Николаевич; [Место защиты: Ульян. гос. ун-т]. - Ульяновск, 2008. - 123 с. : ил. РГБ ОД, 61:08-5/284

Введение к работе

Актуальность исследования. Задача о коммивояжёре – traveling salesman problem (TSP, ЗКВ) – является NP-сложной задачей дискретной оптимизации. Для нее не найдено, и возможно, не существует быстрых, полиномиальных алгоритмов. На графах она формулируется следующим образом: требуется найти гамильтонов цикл наименьшей стоимости во взвешенном полном графе. Т.е. выйдя из стартовой вершины, посетить каждую вершину графа ровно один раз и вернуться в начальную по кратчайшему пути.

Поиск точных и приближённых способов решения задачи о коммивояжёре остается актуальным и с теоретической и с практической точек зрения. Результатом теоретических исследований являются такие методы как:

релаксации линейного программирования, релаксация Лагранжа, метод ветвей и отсечений, метод ветвей и границ (МВГ)

распределенный метод ветвей и границ, решатели ЛП (задачи линейного программирования)

эвристические: симулированный отжиг, генетические алгоритмы, цепная локальная оптимизация, поиск с запретами.

В этом смысле задача о коммивояжёре является упрощённой моделью для многих других задач дискретной оптимизации, а также часто является подзадачей, например, в задаче о маршрутизации.

Программные коды, предназначенные для решения на оптимальность задачи о коммивояжёре, за последние 30 лет развились от решения задач размерности 100 до 10 000.

Среди приложений ЗКВ, встречающихся в литературе, можно отметить:

Оптимизацию в сетях

Оптимизацию маршрутов

Приложения в кристаллографии

Управление роботами

Обработку печатных плат

Исследование ДНК

«Городами» в различных задачах могут выступать как физические объекты, так и процессы, и другие сущности.

Основными актуальными вопросами, связанными с решением ЗКВ, являются

Быстрое точное решение асимметричных и симметричных ЗКВ больших размерностей

Быстрое приближённое решение асимметричных и симметричных ЗКВ больших размерностей

Разработка быстрых схем аппроксимации ЗКВ высокой точности

Диссертация посвящена новым подходам к решению этих задач: разработке новых алгоритмов и оптимизации существующих решений.

Цель работы. Целью настоящей работы является

создание новых алгоритмов и программ для точного и приближённого решения асимметричной и симметричной задачи о коммивояжёре

реализация и получение экспериментальных оценок эффективности схем аппроксимации ЗКВ

улучшение качества тура и ускорение существующих программ решения ЗКВ

поиск новых способов эффективного использования существующего программного обеспечения (ПО) по решению ЗКВ

Методы исследования. В исследовании использовались методы комбинаторного анализа, теории графов, дискретной оптимизации, линейного программирования, технологий распределённых вычислений.

Достоверность результатов обеспечивается строгостью постановок задач и использованием оттестированных компонентов программного обеспечения сторонних исследователей и разработчиков.

Научная новизна

Для достижения поставленных целей решены следующие задачи:

  1. Разработан алгоритм решения асимметричной задачи о коммивояжёре (АЗКВ, ATSP) с помощью неэквивалентного преобразования к симметричной задаче о коммивояжёре (СЗКВ, STSP). Выработаны рекомендации по применению.

  2. Реализованы и исследованы на эффективность алгоритмы распределенного метода ветвей и границ (МВГ) и полиномиальной аппроксимации СЗКВ PMCA.

  3. Реализован алгоритм усеченного МВГ ZHANG1 с задачей о назначениях для АЗКВ. Получены оценки времени работы и качества тура. Выработаны рекомендации по применению.

  4. Разработаны схемы экспериментов для исследования эффективности локальных отсечений в методах ветвей и отсечений (МВО, Branch and Cut) и эквивалентных преобразований в приближённых k-opt алгоритмах для АЗКВ. По результатам выработаны рекомендации по оптимизации времени и качества тура.

  5. Экспериментально исследована эффективность отсечений ЗКВ для решения задачи маршрутизации (Vehicle Routing Problem – VRP). Подтверждена эффективность подхода.

Практическая значимость исследования. Все рассмотренные в работе алгоритмы и методы оптимизации обладают практической значимостью. Наиболее интересными с теоретической точки зрения являются алгоритмы решения асимметричной задачи о коммивояжёре путем неэквивалентного преобразования к симметричной задаче о коммивояжёре и методы повышения эффективности локальной оптимизации асимметричной задачи о коммивояжёре с использованием различных типов эквивалентных преобразований. Практически полезными эффектами являются улучшение качества получаемого решения (длина тура ЗКВ) и уменьшение времени решения (увеличение скорости решения).

Основные положения, выносимые на защиту:

  1. Новый алгоритм решения асимметричной задачи о коммивояжёре путем неэквивалентного преобразования к симметричной задаче о коммивояжёре.

  2. Программная реализация и экспериментальная оценка эффективности схемы полиномиальной аппроксимации симметричной задачи о коммивояжёре и распределенного метода ветвей и границ для симметричной задачи о коммивояжёре.

  3. Методика повышения эффективности программ метода ветвей и отсечений, метода ветвей и границ с задачей о назначениях, и локальной оптимизации для асимметричной задачи о коммивояжёре.

Апробация работы.

Основные научные и практические результаты исследований по теме диссертации докладывались на

VI Международной конференции «Математическое моделирование физических, экономических, технических, социальных систем и процессов» (г. Ульяновск, 2005)

«XIII Всероссийской школе-коллоквиуме по стохастическим методам и VII Всероссийском симпозиуме по прикладной математике» (г. Йошкар-Ола, 2006)

девятом международном семинаре «Дискретная математика и ее приложения» (г. Москва, 2007)

Личный вклад. В работе использовались теоретические и практические разработки отечественных и зарубежных авторов. Формулировка новых алгоритмов, построение схем вычислительных экспериментов, программная реализация алгоритмов, анализ полученных результатов и обоснование выводов выполнены соискателем самостоятельно.

Публикации. По теме диссертации опубликовано 10 работ, в том числе 4 в ведущих рецензируемых журналах, рекомендованных ВАК.

Структура и объем диссертации. Общий объем диссертации 123 страницы. Диссертация состоит из введения, трех глав, заключения, списка используемой литературы из 89 наименований и одного приложения.

Похожие диссертации на Комплекс программ для исследования методов решения задачи о коммивояжере