Алгоритмы для составления расписания полетов экипажей авиакомпании

Затраты на оплату работы экипажей занимают второе место по величине после затрат на топливо в индустрии пассажирских авиаперевозок. Авиакомпании заинтересованы в поиске оптимального графика работ экипажей. В данной работе представлен Branch and Price алгоритм для решения детерминированной задачи составления графика работ для экипажей самолета. Метод состоит из следующих этапов: формулировка основной задачи и подзадачи, их решение и реализация метода ветвей и границ для поиска целочисленного решения для исходной задачи. Для формулировки основной задачи был предложен жадный алгоритм для поиска подмножества переменных. В работе представлен эвристический алгоритм для поиска начального решения, которое в дальнейшем используется для поиска самого нарушенного ограничения в двойственной задаче. Поиск целочисленного решения исходной задачи в методе Branch and Price исполнен посредствам метода ветвей и границ, где ветвление происходит по дробным переменным с фиксированными значениями целых переменных.