Детальная информация

Название: Поиск субоптимального решения задачи коммивояжёра при помощи агрегирования транспортного графа: выпускная квалификационная работа бакалавра: направление 15.03.03 «Прикладная механика» ; образовательная программа 15.03.03_03 «Вычислительная механика и компьютерный инжиниринг»
Авторы: Ястребов Никита Кириллович
Научный руководитель: Суханов Александр Алексеевич
Организация: Санкт-Петербургский политехнический университет Петра Великого. Физико-механический институт
Выходные сведения: Санкт-Петербург, 2022
Коллекция: Выпускные квалификационные работы; Общая коллекция
Тематика: задача коммивояжёра; агрегирование; декомпозиция; разбиение графа; travelling salesman problem; aggregation; decomposition; graph partitioning
Тип документа: Выпускная квалификационная работа бакалавра
Тип файла: PDF
Язык: Русский
Уровень высшего образования: Бакалавриат
Код специальности ФГОС: 15.03.03
Группа специальностей ФГОС: 150000 - Машиностроение
DOI: 10.18720/SPBPU/3/2022/vr/vr22-2835
Права доступа: Доступ по паролю из сети Интернет (чтение, печать, копирование)
Дополнительно: Новинка
Ключ записи: ru\spstu\vkr\18865

Разрешенные действия:

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

Группа: Анонимные пользователи

Сеть: Интернет

Аннотация

Тема выпускной квалификационной работы: «Поиск субоптимального решения задачи коммивояжёра методом агрегирования транспортного графа». Данная работа посвящена исследованию нового подхода к приближенному решению задачи коммивояжера посредством декомпозиции и агрегирования транспортного графа. Задачи, которые решались в ходе работы: Обзор некоторых существующих методов решения задачи коммивояжера, оценка их свойств. Формулировка общего подхода к решению задачи коммивояжера посредством декомпозиции и агрегирования транспортного графа. Исследование влияния выбора параметров, определяющих подзадачи метода. Синтез критериев оптимальности для подзадач разбиения и агрегирования. Исследование влияния критериев оптимальности подзадач на качество решения. Особенностью работы является новизна выдвигаемого подхода, а также его перспективность как альтернатива другим методам решения. В финале работы был проведен численный эксперимент, в результате которого сделаны выводы относительно пригодности как подхода в целом, так и синтезированных критериев. Определен класс задач, для которых они могут давать решение, близкое к точному.

The subject of this graduate qualification work is “Search for suboptimal solution to TSP with graph aggregation”. The work is devoted to a new approach for solving the TSP with graph decomposition and aggregation. The tasks, fulfilled while processing the research: A review of some existing methods for solving the TSP and their property evaluationStating a basic approach for solving the TSP with graph decomposition and aggregation. A research of subproblem parameters impact on the process of solving the problem. Generation of optimal criteria for the graph partitioning and aggregation subproblems. A research of subproblem optimal criteria impact on the quality of solution. The work features novelty of the approach proposed and its perspectives as an alternative to existing methods for solving the TSP. In the end of this work there has been conduct a series of tests. The results of them allowed the author to assess not only the usability of the entire method, but also of the criteria proposed. Finally, a problem class, for which best results can be provided was defined.

Права на использование объекта хранения

Место доступа Группа пользователей Действие
Локальная сеть ИБК СПбПУ Все Прочитать Печать Загрузить
Внешние организации №2 Все Прочитать
Внешние организации №1 Все
Интернет Авторизованные пользователи СПбПУ Прочитать Печать Загрузить
Интернет Авторизованные пользователи (не СПбПУ, №2) Прочитать
Интернет Авторизованные пользователи (не СПбПУ, №1)
-> Интернет Анонимные пользователи

Статистика использования

stat Количество обращений: 0
За последние 30 дней: 0
Подробная статистика