Методы решения задачи о планировании рейсов воздушных судов: дипломная работа / Полина Кирилловна Костюкович; БГУ, Факультет прикладной математики и информатики, Кафедра дискретной математики и алгоритмики; науч. рук. Мушко В. В.

Abstract

РЕФЕРАТ Дипломная работа: 60 страниц, 6 иллюстраций, 1 таблица, 18 источников. Ключевые слова: ЗАДАЧА КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ, МАТЕМАТИЧЕСКАЯ МОДЕЛЬ, ЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ, МЕТАЭВРИСТИКА, МЕТОД ИМИТАЦИИ ОТЖИГА, ПРОГРАММИРОВАНИЕ В ОГРАНИЧЕНИЯХ. Объект исследования: задача составления расписаний. Предмет исследования: задача о планировании рейсов воздушных судов. Цель работы: разработать и реализовать практически применимое решение задачи о планировании рейсов воздушных судов. Методы исследования: методы теории алгоритмов, методы и алгоритмы решения задач комбинаторной оптимизации. Полученные результаты и их новизна: построены и программно реализованы три математические модели задачи о планировании рейсов воздушных судов: в терминах целочисленного линейного программирования, в терминах задачи комбинаторной оптимизации и в терминах задачи программирования в ограничениях. Описаны два алгоритма генерации начальных расписаний, сгенерированы тестовые начальные расписания различных размеров. Проведены вычислительные эксперименты, на основании которых выполнен анализ применимости и эффективности предложенных решений. Достоверность материалов и результатов дипломной работы: использованные материалы и результаты дипломной работы являются достоверными. Работа выполнена самостоятельно. Область возможного практического применения: результаты работы могут быть использованы авиакомпаниями для составления расписаний рейсов воздушных судов.