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

• Автор: Ляликов, Вадим Николаевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Ульяновск
• Количество страниц: 123 с. : ил.

Оглавление
Оглавление
Введение

Глава 1. Современные методы решения задачи о коммивояжере

1.1. Формулировки ЗКВ.

.1 i 1 I ч i

1,2.1 Алгоритмы и методы решения ЗКВ.

1.3. Средства решения ЗКВ.

1.4. Замечания о проведении вычислительных экспериментов

Глава 2. Методы приближенного решения ЗКВ

. 2.1. Стабильная аппроксимация АЗКВ.

2.1.1 Формальное описание алгоритма РМСА
2.1.2. Экспериментальное исследование алгоритма РМСА
2.1.3. Результаты вычислительных экспериментов
2.1.4. Заключение.
2.2. Задача о назначениях для решения ЗКВ.
2.2.1. Формальное описание алгоритма 1.
2.2.2. Экспериментальное исследование алгоритма 1
2.2.3. Заключение.
2.3. Решение близких к симметричным асимметричных ЗКВ необратимым преобразованием их к симметричным ЗКВ равного размера
2.3.1. Алгоритм с неэквивалентным преобразованием.
2.3.2. Вычислительные эксперименты
2.3.3. Заключение.
2.4. Локальный поиск для асимметричной ЗКВ
2.4.1. Алгоритм .
2.4.2. Способы решения асимметричной ЗКВ
2.4.3. Вычислительные эксперименты
2.4.4. Заключение.
Заключение.
Глава 3. Методы точного решения ЗКВ
3.1. Распределенный Метод Ветвей и Границ.
3.1.1. Описание среды.
3.1.2. Алгоритмы синхронизации распределенных решателей.
3.1.3. Результаты вычислительных экспериментов
3.1.4. Заключение.
3.2. Исследование оптимизации использования локальных отсечений .
3.2.1. Методика оптимизации
3.2.2. Вычислительные эксперименты.
3.2.3. Основные результаты.
3.2.4. Заключение
3.3. ЗКВ как модель задачи дискретной оптимизации на примере задачи о маршрутизации V
3.3.1. Решатель V.
3.3.2. Отсечения ЗКВ для V. Схема экспериментов
3.3.3. Заключение
3.4. Комплекс программ
Заключение
Заключение
Список литературы


Для разных исследуемых методов решения ЗКВ задачи и цели исследования отличаются: для некоторых это построение нового алгоритма, для других - модификация существующих программных средств, для третьих — поиск способов повышения эффективности использования программ. В §2. А-ЗКВ РМСА. Алгоритм РМСЛ разработал Ю. Громкович и соавторы. РМСА интересен по нескольким причинам. Во-первых, стабильная аппроксимация ЫР-сложных задач является довольно новой областью исследований и активно развивается. Во-вторых, несмотря на то, что авторы схем аппроксимации уделяют основное внимание разработке максимально близких к точным алгоритмов, практические оценки в публикациях приводятся редко. РМСА, проведению вычислительных экспериментов и анализу полученных результатов. В выводах приводится оценка теоретической значимости и практической применимости алгоритма. ЗН (задачи о назначениях) для решения асимметричной ЗКВ. Задача о назначениях [8] может использоваться как для точного, так и для приближенного решения ЗКВ. Решением ЗН является множество непересекающихся подтуров. Наложив дополнительные ограничения, можно преобразовать это множество подтуров и получить единственный тур — решение ЗКВ. Преимущество использования задачи о назначениях в том, что для нее существуют быстрые полиномиальные алгоритмы. В §2. ЗН - усеченный метод ветвей и границ по Жангу [,]. Открытых реализаций такого алгоритма найдено не было. С реализованным алгоритмом па различных классах ЗКВ задач проводятся вычислительные эксперименты. По результатам анализа формулируются рекомендации по наиболее эффективному использованию ЗН, алгоритма усеченного МВГ и модификации алгоритма. В §2. ЗКВ. Его можно также назвать схемой алгоритмов, потому что, модифицируя некоторые подалгоритмы, можно существенно изменять и время работы и качество получаемого тура. Новым в алгоритме является использование неэквивалентного преобразования асимметричной ЗКВ в симметричную ЗКВ, сохраняющего размер матрицы. После преобразования для решения полученной матрицы используется решатель СЗКВ и на выходном туре рассчитывается стоимость по исходной матрице весов. Результаты вычислительных экспериментов показали, что разработанный алгоритм на некоторых классах АЗКВ задач может успешно конкурировать с лучшими эвристиками локальной оптимизации, как по качеству тура, так и по скорости решения. В §2. ЗКВ - ЕКН (Ьіп-Кеп^Ьаіь ГІе^аип — алгоритм Лина-Кернигана, модифицированный Хелсгауном) []. Цель исследования — повысить качество решения и уменьшить время решения асимметричных ЗКВ. Поводом для рассмотрения послужило то, что в публикациях по ЬКН Хелсгаун не приводит аргументов, поясняющих выбор эквивалентного преобразователя АЗКВ в СЗКВ, реализованного в ЬКН. Как показано в §3. АЗКВ в СЗКВ и последующего решения с помощью конкорда. З-node преобразователь. Для LKH подобных исследований в литературе не встречалось. После описания особенностей различных преобразователей, изменений внесённых в код программы для сбора необходимой информации, и разработанной для LKJ-I схемы эксперимента приводятся результаты и их анализ, свидетельствующий об успешности подхода - использования- разных эквивалентных преобразователей для разных классов задач и размерностей, позволяющего уменьшать время работы программы и улучшать получаемый тур. В §3. На основе алгоритма из [6] создается распределенный вариант метода ветвей и границ, использующий эквивалентные преобразования матриц с уменьшением размерности при ветвлении. Создается эвристика, позволяющая синхронизировать оценки сверху между узлами распределенного алгоритма. Реализуются несколько (новых) распределенных решателей, и сравнивается скорость их работы при: решении на оптимальность матриц небольшой размерности. Алгоритм представляет в основном теоретический интерес, но может быть при доработке использован в специальных приложениях []. Результаты вычислительных экспериментов показывают эффективность предложенной схемы распараллеливания алгоритма. В §3. ЗКВ. В исследовании известных специалистов по ЗКВ. ЗКВ. Задачей в §3.