С 17 марта 2020 г. для образовательных ресурсов Электронной библиотеки СПбПУ установлен особый режим их использования

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

Title: Разработка быстрого алгоритма для составления расписания шлюзованного участка судоходного канала: магистерская диссертация: 01.04.02
Creators: Александров Алексей Дмитриевич
Scientific adviser: Ануфриев Игорь Евгеньевич
Organization: Санкт-Петербургский политехнический университет Петра Великого. Институт прикладной математики и механики
Imprint: Санкт-Петербург, 2017
Collection: Выпускные квалификационные работы; Общая коллекция
Subjects: Судоходные каналы; Шлюзы судоходные; теория расписаний; методы оптимизации; дискретное программирование
UDC: 519.854:626.4(043.3)
Document type: Master graduation qualification work
File type: PDF
Language: Russian
Speciality code (FGOS): 01.04.02
Speciality group (FGOS): 010000 - Математика и механика
DOI: 10.18720/SPBPU/2/v17-3298
Rights: Свободный доступ из сети Интернет (чтение, печать, копирование)

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

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

Группа: Anonymous

Сеть: Internet

Аннотация

В данной магистерской диссертации описана и формализована задача построения оптимального расписания для серии шлюзов. Построенная модель является задачей смешенного целочисленного линейного программирования. Для таких задач не существует эффективного алгоритма решений в общем виде. В основу данной работы лег специализированный алгоритм, учитывающий специфику и физические особенности данной задачи. Алгоритм реализует общую идею ветвей и границ. Благодаря эффективному правилу разбиения множества решений на подмножества и оценки точной нижней границы каждого подмножества удалось значительно повысить вычислительную эффективность. Также разработан алгоритм локального поиска, который выполняется в процессе работы алгоритма, после нахождения текущего наилучшего решения. Алгоритм локального поиска основан на физическом смысле решения, а не на классическом подходе поиска локального экстремума. Объясняется это тем, что в данной задаче крайне трудоемок поиск допустимого решения. Вычислительные тесты показали эффективность данного алгоритма, его преимущества перед алгоритмом ветвей и границ общей задачи бинарного программирования. Так же в данной работе был проведен сравнительный анализ с работой зарубежных авторов, в которой решалась аналогичная задача.

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

Место доступа Группа пользователей Действие
ILC SPbPU Local Network All Прочитать Печать Загрузить
Internet Authorized users Прочитать Печать Загрузить
-> Internet Anonymous

Статистика использования документа

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