О подходе к решению задачи составления расписания использования летного состава в авиакомпании
Приводится анализ требований, предъявляемых к алгоритмам составления расписаний на данном этапе развития информационных технологий, а также ряд решений, применяемых в системе планирования летной деятельности авиакомпании „Международные авиалинии Украины”....
Збережено в:
| Дата: | 2010 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем математичних машин і систем НАН України
2010
|
| Назва видання: | Математичні машини і системи |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/47430 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О подходе к решению задачи составления расписания использования летного состава в авиакомпании / А.В. Мирошниченко // Мат. машини і системи. — 2010. — № 1. — С. 193-197. — Бібліогр.: 3 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-47430 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-474302013-07-15T03:07:08Z О подходе к решению задачи составления расписания использования летного состава в авиакомпании Мирошниченко, А.В. Моделювання і управління великими системами Приводится анализ требований, предъявляемых к алгоритмам составления расписаний на данном этапе развития информационных технологий, а также ряд решений, применяемых в системе планирования летной деятельности авиакомпании „Международные авиалинии Украины”. Наводиться аналіз вимог, що пред’являються до алгоритмів створення розкладів на даному етапі розвитку інформаційних технологій. Також запропоновано ряд рішень, що були використані в системі планування льотної діяльності авіакомпанії „Міжнародні авіалінії України”. Аnalysis of requirements, applied to the scheduling algorithms on the current stage of informational technologies, was done. Also the set of scheduling solutions was described. These solutions were applied for „Ukrainian International Airlines”. 2010 Article О подходе к решению задачи составления расписания использования летного состава в авиакомпании / А.В. Мирошниченко // Мат. машини і системи. — 2010. — № 1. — С. 193-197. — Бібліогр.: 3 назв. — рос. 1028-9763 http://dspace.nbuv.gov.ua/handle/123456789/47430 681.3 ru Математичні машини і системи Інститут проблем математичних машин і систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Моделювання і управління великими системами Моделювання і управління великими системами |
| spellingShingle |
Моделювання і управління великими системами Моделювання і управління великими системами Мирошниченко, А.В. О подходе к решению задачи составления расписания использования летного состава в авиакомпании Математичні машини і системи |
| description |
Приводится анализ требований, предъявляемых к алгоритмам составления расписаний на данном этапе развития информационных технологий, а также ряд решений, применяемых в системе планирования летной деятельности авиакомпании „Международные авиалинии Украины”. |
| format |
Article |
| author |
Мирошниченко, А.В. |
| author_facet |
Мирошниченко, А.В. |
| author_sort |
Мирошниченко, А.В. |
| title |
О подходе к решению задачи составления расписания использования летного состава в авиакомпании |
| title_short |
О подходе к решению задачи составления расписания использования летного состава в авиакомпании |
| title_full |
О подходе к решению задачи составления расписания использования летного состава в авиакомпании |
| title_fullStr |
О подходе к решению задачи составления расписания использования летного состава в авиакомпании |
| title_full_unstemmed |
О подходе к решению задачи составления расписания использования летного состава в авиакомпании |
| title_sort |
о подходе к решению задачи составления расписания использования летного состава в авиакомпании |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| publishDate |
2010 |
| topic_facet |
Моделювання і управління великими системами |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/47430 |
| citation_txt |
О подходе к решению задачи составления расписания использования летного состава в авиакомпании / А.В. Мирошниченко // Мат. машини і системи. — 2010. — № 1. — С. 193-197. — Бібліогр.: 3 назв. — рос. |
| series |
Математичні машини і системи |
| work_keys_str_mv |
AT mirošničenkoav opodhodekrešeniûzadačisostavleniâraspisaniâispolʹzovaniâletnogosostavavaviakompanii |
| first_indexed |
2025-07-04T07:18:30Z |
| last_indexed |
2025-07-04T07:18:30Z |
| _version_ |
1836699889233297408 |
| fulltext |
© Мирошниченко А.В., 2010 193
ISSN 1028-9763. Математичні машини і системи, 2010, № 1
УДК 681.3
А.В. МИРОШНИЧЕНКО
О ПОДХОДЕ К РЕШЕНИЮ ЗАДАЧИ СОСТАВЛЕНИЯ РАСПИСАНИЯ
ИСПОЛЬЗОВАНИЯ ЛЕТНОГО СОСТАВА В АВИАКОМПАНИИ
Abstract. Аnalysis of requirements, applied to the scheduling algorithms on the current stage of informational
technologies, was done. Also the set of scheduling solutions was described. These solutions were applied for
„Ukrainian International Airlines”.
Key words: plan, scheduling, algorithm.
Анотація. Наводиться аналіз вимог, що пред’являються до алгоритмів створення розкладів на даному
етапі розвитку інформаційних технологій. Також запропоновано ряд рішень, що були використані в системі
планування льотної діяльності авіакомпанії „Міжнародні авіалінії України”.
Ключові слова: розклад, планування, алгоритм.
Аннотация. Приводится анализ требований, предъявляемых к алгоритмам составления расписаний на
данном этапе развития информационных технологий, а также ряд решений, применяемых в системе
планирования летной деятельности авиакомпании „Международные авиалинии Украины”.
Ключевые слова: расписание, планирование, алгоритм.
1. Введение
В данной статье представлены алгоритмы составления расписаний для пилотов и
бортпроводников. Под расписанием понимается совокупность индивидуальных планов летного
состава. Каждый индивидуальный план представляет собой чередующуюся последовательность
дежурств и отдыха. Дежурства могут включать в себя набор полетов или выполнение других
обязанностей (на земле).
Сначала следует рассмотреть особенности предметной области, для которой строятся
алгоритмы составления расписаний. Необходимо сразу отметить, что сейчас мы имеем дело с
очень динамичной системой. Динамика данной системы обусловливается следующими факторами:
• изменение расписания полетов. Это касается как маркетингового расписания (постоянно
выполняемые рейсы), так и расписания чартерных рейсов (разовые полеты);
• изменение в планах использования самолетов. Смена самолета может привести к
невозможности выполнения данного рейса пилотами, которые не имеют лицензии для полетов на
данном классе воздушных судов;
• изменение в правилах использования экипажей. При планировании летной деятельности
применяются правила, определенные Министерством транспорта Украины, а также внутренние
правила авиакомпании. Списки этих правил периодически меняются, что ведет к невозможности их
внесения в исходный код программ;
• большая размерность задачи. Задача решается для нескольких сотен человек, каждый из
которых должен будет выполнить пятнадцать–двадцать рейсов в месяц.
Остановимся на требованиях, предъявляемых как к алгоритмам планирования, так и к
системе в целом:
• возможность изменять правила. Система должна допускать возможность редактирования
списка правил;
• время, затрачиваемое на планирование. Процесс планирования должен укладываться в
30 минут;
ISSN 1028-9763. Математичні машини і системи, 2010, № 1 194
• критерии оптимизации. Равномерность распределения летных часов, равномерность
распределения денежного содержания;
• ограничения. Построенные планы должны соответствовать всем правилам.
2. Описание предложенного решения
Учитывая большую комбинаторную сложность данной задачи, следует задуматься о декомпозиции
[1, 2]. Очевидно, что задача допускает декомпозицию на уровне создания планов для различных
типов членов экипажа. Таким образом, задача может быть разбита на следующие подзадачи:
• планирование командиров воздушных судов;
• планирование вторых пилотов;
• планирование инструкторов пилотов;
• планирование бригадиров бортпроводников;
• планирование бортпроводников;
• планирование инструкторов бортпроводников.
Каждая из вышеперечисленных задач имеет меньшую размерность. Задачи по назначению
пилотов и бортпроводников могут решаться параллельно разными диспетчерами, что, в общем, и
соответствует устоявшейся в авиакомпании практике.
Начало
Список рейсов АК за
плановый период,
Тип членов экипажа
Создать упорядоченный по времени
отправления список полетов
Список
дежурств
Список полетов
пустой?
КонецДа
Взять первый
полет из списка
Нет
Можно взять
следующее
дежурство?
Создать новое дежурство и
поместить в него текущий полет
Нет
Поместить дежурство в список
дежурств
Удалить полет из списка полетов
Взять дежурствоДа
Добавление полета в
дежурство приводит к
нарушениям?
Добавить полет в дежурство
Нет
Да
Здесь производится
контроль дежурства на
соответствие структурным
ограничениям, а также на
соответствие правилам
Рис. 1. Алгоритм построения дежурств
Еще одним шагом, призванным уменьшить размерность задачи планирования, есть
переход от планирования рейсов к планированию дежурств. Это подразумевает, что элементами
ISSN 1028-9763. Математичні машини і системи, 2010, № 1 195
планирования у нас станут последовательности рейсов (дежурства), а не отдельные рейсы. Блок-
схема, приведенная на рис. 1, демонстрирует данный шаг декомпозиции.
Теперь необходимо создать первое допустимое расписание для определенного типа
членов экипажа. Блок-схема данного рекуррентного алгоритма приведена на рис. 2 [3].
Рис. 2. Алгоритм построения допустимого расписания (плана)
Этот алгоритм имеет следующие отличительные особенности:
• построенное решение является допустимым. Оно соответствует всем правилам,
определенным в системе;
• построенное решение не является оптимальным. Наблюдается серьезный дисбаланс
относительно критериев, приведенных выше.
Дисбаланс легко объясним тем фактом, что мы пытаемся вставить каждое новое
дежурство, обходя людей по одному и тому же заранее определенному списку. В результате
«голова» списка будет перегружена дежурствами, в то время как «хвост» будет испытывать явный
«недогруз» в летных часах, что, в свою очередь, напрямую отразится на зарплатах людей.
ISSN 1028-9763. Математичні машини і системи, 2010, № 1 196
Учитывая все вышесказанное, следующий этап планирования выглядит весьма очевидным
– усреднение часов налета для людей без нарушения правил. Блок-схема данного алгоритма
приведена на рис. 3.
Рис. 3. Алгоритм усреднения летных часов в планах
Как видно из блок-схемы, алгоритм заключается в пошаговом улучшении общей картины за
счет совместной пересборки пары решений с максимальной и минимальной оценками. Алгоритм
может завершиться сам в случае, если решение нельзя более улучшить или же он может быть
остановлен диспетчером, если он считает, что текущий разброс между минимальным и
максимальным налетом в плане удовлетворителен.
Следует отметить следующие особенности данного алгоритма:
• построенное решение является допустимым. Оно соответствует всем правилам,
определенным в системе;
• построенное решение является оптимальным. Оптимальным в достаточной степени с
точки зрения критерия равенства летных часов;
ISSN 1028-9763. Математичні машини і системи, 2010, № 1 197
• данное решение не является оптимальным с точки зрения критерия равенства денежного
содержания.
Дисбаланс по денежному содержанию вызывается тем, что для различных рейсов данное
содержание является разным (в зависимости от страны назначения). Так, за полет в Симферополь
пилот получит командировочные в размере 18 гривен, а за полет в Лондон – 50 долларов. Таким
образом, зарплаты пилотов при относительной близости летных часов за плановый период могут
отличаться почти в 2 раза.
Возникает вопрос: как бороться с данным дисбалансом? Частично этот вопрос может быть
решен при помощи правил, которые ограничивают количество «дорогих» и «дешевых» дежурств в
плане. Однако эксперименты показали, что данное решение не очень эффективно. В связи с этим
был предложен алгоритм усреднения планов с точки зрения денежного содержания. Суть данного
алгоритма аналогична алгоритму усреднения летных часов, различаются лишь целевые функции.
Результат работы данного алгоритма имеет следующие особенности:
• предложенное решение является допустимым, оно соответствует всем правилам,
определенным в системе;
• предложенное решение является оптимальным в достаточной степени с точки зрения
критерия равенства денежного содержания;
• данное решение не является оптимальным с точки зрения критерия равенства часов
налета.
Становится очевидным, что мы имеем дело с двумя противоположными критериями:
улучшение одного ведет к нарушению другого.
Поэтому были предложены еще два алгоритма:
• усреднение летных часов с заданным допустимым ухудшением по критерию суточного
содержания;
• усреднение летного содержания с заданным допустимым ухудшением по критерию летных
часов.
Эти алгоритмы аналогичны алгоритму усреднения летных часов и отличаются лишь
целевыми функциями и дополнительным ограничением на ухудшаемый критерий.
3. Выводы
В данной статье был разработан инструментарий, позволяющий диспетчеру строить допустимые
планы использования летного состава и проводить итерации по их улучшению. Предложенный
человеко-машинный метод показал свою эффективность и нашел применение в реальной жизни.
СПИСОК ЛИТЕРАТУРЫ
1. Юдин Д.Б. Линейное программирование. Теория и конечные методы / Д.Б. Юдин, Е.Г. Гольдштейн. – М.:
Изд-во физ.-мат. литературы, 1963. – 775 с.
2. Winston W. Operations Research: Applications and Algorithms / Winston W. – Duxbury Press; 4th. Edition, 2003. –
1262 р.
3. Хемди А. Таха Введение в исследование операций = Operations Research: An Introduction / Хемди А. Таха. –
М.: Вильямс, 2007. – 912 с.
Стаття надійшла до редакції 05.02.2010
|