Решение задачи равномерного разбиения рейсов летного расписания авиакомпании: точная математическая постановка

В задачах планирования авиаперелетов можно выделить четыре основных раздела: создание полетного расписания, назначение типов воздушных судов (ВС) на рейсы полетного расписания, маршрутизация ВС и, наконец, построение графика работы летного состава [1, 4]. Данные задачи последовательны (результат решения предыдущей служит исходной информацией для следующей) и могут решаться независимо. С математической точки зрения, эти проблемы являются сложными и трудоемкими, прежде всего, в плане объема вычислений. Каждая из них представляет собой оптимизационную задачу, для которой необходимо получить оптимальное или субоптимальное решение.

Построение графика работы летного состава является заключительным этапом задач планирования в авиакомпании, когда уже построено полетное расписание авиакомпании, и на все его рейсы назначены определенные ВС. Заработная плата летного состава является одной из существенных статей

ГРНТИ 28.17.19

Сергей Викторович Уният – начальник департамента обслуживания на борту АО «Авиакомпания «Россия».

расходов авиакомпании, которая зависит не только от налета, но и от количества посадок, ночных вылетов, общего рабочего времени вне базы, минимальной гарантированной оплаты труда и т.д. [1].

Отметим, что планирование летного расписания для бортпроводников (БП) и для летчиков часто проводится по отдельности. Задача планирования работы БП состоит в определении летных заданий таким образом, чтобы каждый рейс был обеспечен обслуживающим персоналом с наименьшими затратами для авиакомпании. При этом должны быть соблюдены все правила планирования работы члена экипажа ВС (например, максимально допустимое число последовательных рабочих дней за период, максимально разрешённая санитарная норма налёта за месяц и т.п.). Сложность задачи с вычислительной точки зрения связана с большим количеством рейсов в расписании, значительным числом задействованных в работе бортпроводников, количеством мероприятий по поддержанию лётной годности, а также с существованием разнообразных правил государственного [3] и внутреннего регулирования, определяющих планирование экипажа.

В мировой практике задача назначения БП разбивается на два последовательных этапа, Airline Crew Pairing Problem (ACPP) и Airline Crew Rostering Problem (ACRP) [5, 6]. На первом определяется минимальный набор летных заданий для БП, требуемый для того, чтобы обслужить все рейсы полетного расписания на горизонт планирования с учетом всех требований. На втором каждому БП, в соответствии с его параметрами (допуски, время отдыха, класс обслуживания и др.), назначается индивидуальное летное задание. Решение этих оптимизационных задач чрезвычайно трудоемко и требует значительных вычислительных ресурсов, однако обеспечивает устойчивое и эффективное расписание работы БП.

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

При решении данной задачи не применяется аппарат математического моделирования, а вместо этого используются принятые методики и технологии по составлению графика, выработанные экспертами с многолетним опытом. Каждый эксперт занят планированием определенного подмножества БП, каждое такое подмножество носит название «книга». Книги создаются так, что в каждой содержится примерно равное количество БП с примерно равными характеристиками (должность, класс, пол, знание иностранных языков, допуск на типы ВС). Изменения в книгах могут происходить только при приеме в штат авиакомпании новых БП или в случае увольнения значительного количества БП в книге. Тем не менее, в любой момент времени количество БП, доступных для планирования в книгах, различается вследствие их отпусков, больничных и т.д.

С периодичностью раз в месяц производится разделение всех связок (оборотных рейсов) полетного расписания на несколько групп, число которых равно числу книг. Книга и соответствующее ей подмножество связок образуют «рабочий стол», с которым работает один из экспертов. Для того, чтобы каждым экспертом могли применяться одинаковые методики и технологии при составлении расписания, связки также должны быть равномерно распределены по рабочим столам по некоторому набору заранее выбранных критериев. Под термином «равномерное распределение связок по рабочим столам» понимается следующее:

• •    каждому рабочему столу сопоставляется некоторое подмножество связок из общего списка;

• •    каждое такое подмножество характеризуется заранее определенным, общим для всех рабочих столов, набором параметров-критериев (например, количеством связок по типу сообщения, количеством ночных связок, числом связок для каждого дня, количеством связок по направлениям, средним налетом на БП, средним ночным налетом на БП, средним рабочим временем БП и т.д.). Этот набор выбирается экспертами заранее;

• •    каждый параметр-критерий из такого набора для одного рабочего стола должен быть либо приблизительно равен, либо пропорционален – в соответствии с количеством БП, доступных для данного рабочего стола на заданный горизонт планирования (обычно, месяц) – аналогичному параметру другого рабочего стола.

Следует отметить, что работа по наполнению рабочих столов связками проводится также одним из экспертов. Продолжительность решения задачи составляет около недели, что, соответственно, сокращает время, остающееся непосредственно для составления расписания БП. Основная часть работы по распределению связок по рабочим столам выполняется «вручную», и при этом, поскольку эксперт останавливается на первом полученном решении, отсутствует возможность анализа результатов, в том числе объективного сравнения нескольких допустимых решений.

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

Это происходит и потому, что перед экспертами фактически не ставится задача поиска наилучшего с экономической точки зрения графика работ БП, а основным показателем качества построенного графика служит равномерность загруженности БП в течение месяца. Предоставляемое авиакомпанией решение содержит ряд очевидных недостатков, связанных, прежде всего, с экспертным подходом:

• •    часто наблюдается превышение норм приказа № 139, в том числе, по налету, что подразумевает дополнительные выплаты БП и штрафные санкции со стороны контролирующего органа;

• •    формулируемые требования «социальной справедливости» расписания (т.е. максимальная равномерность загрузки БП) выполняются недостаточно;

• •    не может идти речи о применении иных требований, например, о построении графика работы БП, обеспечивающего наибольшую прибыль для предприятия, либо о выполнении всех летных заданий минимальным числом БП и т.п.

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

Целью статьи является создание математической модели равномерного разбиения множества связок на заданное число подмножеств (по рабочим столам), позволяющей достичь указанных целей.

Математическая постановка задачи

Исходные данные задачи равномерного распределения множества связок по рабочим столам представляют собой два множества:

• 1)    множество связок F = {F₁,F₂, ...,F_M}, при этом {F ₁ ,F ₂ ,^,F _mF } - множество дневных связок (М ' < М), а (F_M ' ₊₁, F_m / ₊₂, --,F_m} - множество ночных связок (к ночным связкам относятся смены, не менее 50% продолжительности которых приходится на местное время базового аэропорта с 22.00 до 06.00 [3]). Каждая связка F t , i = 1, .„,М, описывается:

• •    временем налета, t t ;

• •    требованиями по количеству БП, обслуживающих ВС, которое назначено на связку, p t ;

• •    типом сообщения V : внутреннее (ВВЛ), международное (МВЛ), по странам СНГ. Обозначим через U₁, U₂, U₃ - множества номеров (идентификаторов) связок, относящихся к одному из типов сообщения, соответственно, ВВЛ, МВЛ и СНГ, а через U ' , U 2 , U 3 - аналогичные множества для идентификаторов ночных связок. Тогда V i = 1, ...,М имеем i е U₁ V U₂ V U₃ и Vi = М ' + 1^„,М выполняется i е U 1 V U 2 V U₃ ;

• •    датой вылета d t е Т, где Т - множество дат, в которые осуществляются вылеты на заданном горизонте планирования. Обозначим через D₁,D₂, ,„,D | _T | - множества идентификаторов связок по дате вылета, тогда V i = 1, .„, М имеем i е D₁ V D₂ V .„ V D | _T | ;

• •    типом ВС, назначенного на связку, а Е L, где L - множество идентификаторов для всех типов ВС, задействованных в расписании полетов. Обозначим через Л_1л Л₂, — , А | _Л | — множества идентификаторов связок, на которые назначен один из типов ВС, тогда Vi = 1, —, М имеем i Е А₁ V А₂ V ... V А^;

• •    направлением связки, S i Е R, где R- множество идентификаторов направлений в расписании полетов. Обозначим через S₁,S₂, — ,S | _R | - множество номеров (идентификаторов) связок, относящихся к одному из направлений, тогда V i = 1, —, М имеем i Е S₁ V S₂ V — V S | _R | .

Следует отметить, что

U1UU2UU3= D1UD2U — UDm = А1 UA2 и — иАщ = S1 U S2 U — US|R| = {1, —,М}, U1 U U2 и У' = {М' + 1, — ,М}

и

u1 n и2 n и3 = U1 n U2 n ид = 0,

D1 n D2 n — П D|T| = A1 П A2 П — П A|L| = S1 П S2 П — n S^ = 0.

• 2)    множество «книг» В = {B₁,B₂, — ,8 ^ }, в каждой из которых указаны величины с_а , _к - количество БП, доступных для планирования на рабочем столе с номером к и имеющих доступ по типу сообщения (ВВЛ, МВЛ и СНГ), при этом, соответственно, а = 1,2,3.

Требуется равномерно разбить множество связок на К подмножеств (по числу книг). Критериями равномерности разбиения выбраны:

• •    средний налет на одного БП;

• •    средний ночной налет на одного БП;

• •    среднее количество связок на одного БП по типу сообщения, а = 1,2,3;

• •    общее количество ночных связок на рабочем столе;

• •    общее количество связок в день для рабочего стола, а = 1, —, |Т|;

• •    общее количество связок по типу ВС для рабочего стола, а = 1, —, |L|;

• •    общее количество связок по направлениям для рабочего стола, а = 1, —, |R|.

Равномерность разбиения подразумевает, что соответствующие критериям суммарные характеристики всех подмножеств связок должны быть близки к некоторым усредненным значениям 5>₁, У₂, —, У м , где у - усредненное значение -й характеристики:

Уа = ТмУ---У Piti, а = 1,2,3; Уз+а =     ---У Piti, а = 1,2,3; Уб+а =

':- ■■•'■••-■                                   ':.. .с.^-

|Ua|

, а = 1,2,3;

М

У го =

К

М; У1о+а =^,а = 1, —,П; ;У1о+|т|+а = 4г|’а = 1, —,|L|; К                       К

|Sa|

У10+|т|+|А|+а = ""К",а = 1, —,|R|.

В итоге, для «выравнивания» по семи приведенным выше критериям необходимо рассчитать N = 10 + |Т| + |L| + |R| усредненных характеристик.

Исходные данные задачи позволяют также вычислить характеристики каждой связки, которые при разбиении связок дадут суммарные характеристики подмножеств. Обозначим через A i = [5у , _к}, j = 1, — ,N, к = 1, —.К, матрицу, каждый элемент которой, 5ц , _к , - приращение -й суммарной характеристики подмножества под номером к, которое она получает при распределении i-й связки в это подмножество. Множество матриц А = {А₁, —, А_м} образует тензор приращений для всех связок.

Сформулируем задачу как задачу целочисленного программирования [2]. Для каждой характеристики зададим ее весовой коэффициент w1,w2, — ,ww, где w7 - вес -й характеристики, j = 1, — ,N, в целевой функции, которая представляет собой свертку относительных квадратичных отклонений характеристик к-го подмножества связок от усредненных значений. Таким образом, значение целевой функции - это числовая характеристика полученного решения, показывающая его относительную удаленность от полностью равномерного (зачастую нереального) разбиения связок:

К N

^1     yf)2,

k^i)^i              ⁷

где У/л — значение -й характеристики для k-й группы. Поскольку такая форма представления целевой функции нелинейна по переменным y₇- , _k, то на практике удобно воспользоваться другой сверткой:

К N

ZZ"7-x^—y^^b

k=i)^i              ⁷

тоже нелинейной, но допускающей линеаризацию, что чрезвычайно важно с вычислительной точки зрения.

Введем переменные % i, _k, принимающие значение 1, если -я связка попадает в k-е подмножество, и 0 - в противном случае, а также переменные типа у 'у _k, необходимые для линеаризации исходного выражения целевой функции. Тогда обозначенной цели удовлетворяет следующий вид целевой функции:

К N

L = 11wixy' ik^min , k=ij=i а ограничения задачи целочисленного программирования примут вид:

К

^%i,k = 1, V i = 1.....M

k=i

Z p_it_i

5i,a,k%i,k, где 8i,a,k = — Va = 1,2,3, Vk = 1, -,K ieua                           a,k

y3+a,k = ^ 5

ieu ^

y6+a,k = ^ 5,

ieu_a м

¹ i,3+a,k % i,k , ^{где 5} i,3+a,k = ^c a,k

.                           _ 1

¹ i,6+a,k % i,k , ^{где 5} i,6+a,k = ~ ^c a,k

Va = 1,2,3, V к = 1,-,K

V a = 1,2,3, V k = 1,-,K

^y io,k =

1   5i,io,k%i,k , где 5i,io,k = 1 Vk = 1, — , K

i=M ' +i

yio+a,k = ^ 5i,io+a,k%i,k, где 5i,io+a,k = 1 V a = 1,-, |T|, V k = 1, -, K ie^a

^y io+|T|+a,k = ^ ⁵ i,io+|T|+a,k % i,k , ^{где 5} i,io+|r|+a,k = ^{1 V a} = ¹,-J^L|, ^{V k} = 1,-,^K ie^_a

^y 10+|T| + |L|+a,k = ^ 5 i,io+|r|+|L|+a,k % i,k , ^{где 5} i,io+|r|+|L|+a,k = ^{1 V a} = 1, -, №, ^{V k} = 1, -,^{K (11)}

У'м > 1

y'^f

yj,k , 37)

— 1,

^ieS a

V У = 1.....N, V k = 1.....K

V У = 1.....N,

V к = 1,-,K

%i,k e {0,1}, yv,k > 0, y'7,k >

Ограничения (4) гарантируют, подмножество. Ограничения (5) —

0, V t = 1,-,M, Vy = 1,-,N, V k = 1,-,K

что каждая связка должна быть помещена в одно и только одно

(11) позволяют установить значения характеристик по всем кри-

териям равномерности. Ограничения (12) — (13) необходимы для линеаризации условий у 'у _k = |1 — У /,к /у / | по каждой суммарной характеристике подмножества. Ограничения (14) определяют область допустимых значений для переменных типа %, у, у’.

Сформулированная оптимизационная задача (3) — (14) относится к классу задач разбиения множества и является вычислительно NP-сложной.

Числовые расчеты на модельных данных

Вследствие NP-сложности оптимизационной задачи полномасштабный расчет на натурных данных представляется затруднительным. Например, в месячном летном расписании одной из крупнейших российских авиакомпаний около 4000 рейсов, которые следует распределить между 6-ю подмножествами (рабочими столами). Были проведены расчеты для модельной задачи со случайно сгенерированными исходными данными. В модельном недельном летном расписании присутствовало до 32 связок, 3 летных направления и 4 типа ВС. Для решения применялся метод ветвей и границ [2].

Для генерации всех исходных данных и формирования матрицы ограничений и вектора коэффициентов целевой функции использовалась компьютерная математическая среда Wolfram Mathematica 10.3, а поиск решения выполнялся в оптимизаторе Gurobi Optimizer 6.5. В таблице приведены данные по среднему времени счета для разбиения множества связок данной мощности на 2 и 3 подмножества. Для каждого набора данных проводилось 50 повторных расчетов. Полученные данные подтверждают экспоненциальный рост времени счета с ростом числа связок.

Таблица

Среднее время счета для разбиения множества связок данной мощности М на К подмножеств, сек

К	М = 6	М = 12	М = 18	М = 22	М = 26	М = 30	М = 32
2	0.23	0.25	0.27	0.3	0.62	2.02	4.1
3	0.26	0.28	0.38	1.41	3.92	26.86	153.97

Анализ предложенной модели

Постановка задачи (3) — (14) достаточно универсальна. Задавая весовые коэффициенты в целевой функции, можно управлять значимостью той или иной характеристики при равномерном разбиении связок на подмножества. Тем не менее, для того, чтобы приблизить математическую модель к реальному процессу, предложенная постановка может быть обобщена на случай, когда величины у7- (усредненные значения характеристик), к которым должны стремиться суммарные характеристики связок, попавших в то или иное подмножество, различны для разных рабочих столов.

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

Следует еще отметить, что для каждого рабочего стола может потребоваться своя усредненная характеристика рабочего времени в связи с неравномерностью распределения нелетных мероприятий между БП. Ввод параметров равномерности другого вида, а именно равномерность распределения подмножества связок, объединенного по какому-то признаку, осуществляется по аналогии с критерием равномерности по типу ВС (10), также с учетом возможного различия усредненных характеристик по рабочим столам.

Наконец, следует отметить, что сама задача по формированию книг, т.е. списков БП для каждого рабочего стола, может также быть сформулирована как оптимизационная задача равномерного распределения БП на подмножества, которая решается по точно такому же принципу, что и (3) — (14). Параметрами равномерности, по которым необходимо минимизировать отклонение суммарных характеристик подмножеств друг от друга, являются общее количество БП по: должностям; доступу на тип сообщения и ВС; знанию иностранных языков; возрасту, полу и другим личным (необязательно профессиональным) характеристикам; приблизительным срокам отпусков и периодам медицинского освидетельствования и переаттестации.

Заключение

В статье математически описан бизнес-процесс построения графика работы БП в одной из крупнейших российских авиакомпаний. Его начальным этапом является равномерное разбиение множества связок на подмножества, так называемые рабочие столы. Равномерность при этом понимается как наименьшее отклонение суммарных характеристик подмножеств (т.е. входящих в них связок) друг от друга. Поскольку работа над этим этапом ведется экспертом практически «вручную», предложена оптимизационная математическая модель распределения связок по подмножествам.

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