СОСТАВЛЕНИЕ РАСПИСАНИЯ ИСПОЛЬЗОВАНИЯ ЛЕТНОГО СОСТАВА В АВИАКОМПАНИИ
Автор: А.В. Мирошниченко
Источник: http://www.aticmd.md/...
А.В. МИРОШНИЧЕНКО Институт проблем математических машин и систем НАН Украины, Киев, Украина, andriy.miroshnychenko@gmail.com
Аннотация: приводится анализ требований предъявляемых к алгоритмам составления расписаний на данном этапе развития информационных технологий. А так же приводится ряд решений примененных в системе планирования летной деятельности авиакомпании Международные Авиалинии Украины.
Ключевые слова: расписание, планирование, алгоритм.
Abstract: analysis 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 минут;
- критерии оптимизации. Равномерность распределения летных часов, равномерность распределения денежного содержания;
- ограничения. Построенные планы должны соответствовать всем правилам.
2. Описание предложенного решения
Учитывая большую комбинаторную сложность данной задачи, следует задуматься о декомпозиции [1,2]. Очевидно, что задача допускает декомпозицию на уровне создания планов для различных типов членов экипажа. Таким образом, задача может быть разбита на следующие подзадачи:
· Планирование командиров воздушных судов;
· Планирование вторых пилотов;
· Планирование инструкторов пилотов;
· Планирование бригадиров бортпроводников;
· Планирование бортпроводников;
- Планирование инструкторов бортпроводников.
Каждая из выше перечисленных задач имеет меньшую размерность. Задачи по назначению пилотов и бортпроводников могут решаться параллельно разными диспетчерами, что, в общем, и соответствует устоявшейся в авиакомпании практике.
Еще одним шагом, призванным уменьшить размерность задачи планирования есть переход от планирования рейсов к планированию дежурств. Это подразумевает, что элементами планирования у нас станут последовательности рейсов (дежурства), а не отдельные рейсы. Блок–схема, приведенная на рис. 1 демонстрирует данный шаг декомпозиции.
Рис. 1. Алгоритм построения дежурств
Теперь необходимо создать первое допустимое расписание для определенного типа членов экипажа. Блок–схема данного рекуррентного алгоритма приведена на рис. 2 [3].
Рис. 2. Алгоритм построения допустимого расписания (плана)
Этот алгоритм имеет следующие отличительные особенности:
- построенное решение является допустимым. Оно соответствует всем правилам, определенным в системе;
- построенное решение не является оптимальным. Наблюдается
серьезный дисбаланс относительно критериев, приведенных выше.
Дисбаланс легко объясним тем фактом, что мы пытаемся вставить каждое новое дежурство, обходя людей по одному и тому же заранее определенному списку. В результате «голова» списка будет перегружена дежурствами, в то время как «хвост» будет испытывать явный «недогруз» в летных часах, что, в свою очередь, напрямую отразится на зарплатах людей.
Учитывая все выше сказанное, следующий этап планирования выглядит весьма очевидным – усреднение часов налета для людей,
Как видно из блок–схемы, алгоритм заключается в пошаговом улучшении общей картины за счет совместной пересборки пары решений с максимальной и минимальной оценками. Алгоритм может завершиться сам в случае если решение нельзя более улучшить или же он может быть остановлен диспетчером, если он считает, что текущий разброс между минимальным и максимальным налетом в плане удовлетворителен.
Следует отметить следующие особенности данного алгоритма:
- Построенное решение является допустимым. Оно соответствует всем правилам, определенным в системе;
- Построенное решение является оптимальным. Оптимальным в достаточной степени с точки зрения критерия равенства летных часов;
- Данное решение не является оптимальным с точки зрения
критерия равенства денежного содержания.
Дисбаланс по денежному содержанию вызывается тем, что для различных рейсов данное содержание является разным (в зависимости от страны назначения). Так за полет в Симферополь пилот получит командировочные в размере 18 гривен, а за полет в Лондон – 50 долларов. Таким образом, зарплаты пилотов при относительной близости летных часов за плановый период могут отличаться почти в 2 раза.
Возникает вопрос: как бороться с данным дисбалансом? Частично этот вопрос может быть решен при помощи правил, которые ограничивают количество «дорогих» и «дешевых» дежурств в плане. Однако эксперименты показали, что данное решение не очень эффективно. В связи с этим был предложен алгоритм усреднения планов с точки зрения денежного содержания. Суть данного алгоритма аналогична алгоритму усреднения летных часов, различаются лишь целевые функции.
Результат работы данного алгоритма имеет следующие особенности:
- предложенное решение является допустимым, оно соответствует всем правилам, определенным в системе;
- предложенное решение является оптимальным в достаточной степени с точки зрения критерия равенства денежного содержания;
- данное решение не является оптимальным с точки зрения
критерия равенства часов налета.
Становится очевидным, что мы имеем дело с двумя противоположными критериями – улучшение одного ведет к нарушению другого.
Поэтому были предложены еще два алгоритма:
- усреднение летных часов с заданным допустимым ухудшением по критерию суточного содержания;
- усреднения летного содержания с заданным допустимым ухудшением по критерию летных часов.
Эти алгоритмы аналогичны алгоритму усреднения летных часов и отличаются лишь целевыми функциями и дополнительным ограничением на ухудшаемый критерий.
Выводы
Был разработан инструментарий, позволяющий диспетчеру строить допустимые планы использования летного состава и проводить итерации по их улучшению. Предложенный человеко–машинный метод показал свою эффективность и нашел применение в реальной жизни.
Литературa
- Юдин Д.Б., Гольдштейн Е.Г. Линейное программирование. Теория и конечные методы. – М.: Изд–во Физ.–мат. литературы, 1963. – 775 с.
- Wayne Winston. Operations Research: Applications and Algorithms. – Duxbury Press; 4th. Edition, 2003. – 1262 с.
- Хемди А. Таха Введение в исследование операций. Operations Research: An Introduction. – М.: Вильямс, 2007. – 912 с.