Рассказываем про разработку Airline CRM: учебного проекта студентов Computer Science Center под менторством ВКонтакте.
Автор статьи Андрей Шубин, бывший бэкенд-разработчик в команде электронной коммерции ВКонтакте. Эта история — от первого лица.
«Talk is cheap. Show me the code», — сказал когда-то Линус Торвальдс. Но так ли это актуально сегодня?
Многие разработчики занимаются менторством — потому что это помогает классно работать в команде, подниматься по карьерной лестнице, развиваться и вообще быть хорошим специалистом. Можно выступать наставником для новых сотрудников, стажёров или погружать коллег из других команд в особенности именно вашего проекта. А лучший способ этому научиться — конечно, практика.
Современное IT-образование невозможно представить без практических проектов, соединяющих университеты и индустрию. Например, в Санкт-Петербурге благодаря Computer Science Center активные студенты могут поработать вместе с сотрудниками IT-компаний. Что классно: можно основываться на рабочих кейсах или развивать идею pet-проекта. Главное — познакомить ребят с реальными задачами и современными технологиями.
Команда ВКонтакте уже несколько лет предлагает идеи проектов для учащихся Computer Science Center — и мы очень рекомендуем этот формат. Если у вас в компании есть идеи проектов и менторы, готовые выделить несколько часов в неделю на работу со студентами, — предложите ребятам из вашего города попробовать себя на такой практике.
В этой статье мы расскажем о проекте 2021 года, который делали вместе с двумя студентами Computer Science Center, из СПбГУ и ИТМО. Наставником выступил я — Андрей Шубин. К программе менторства решил присоединиться потому, что мне самому в своё время очень не хватало наставника из числа практикующих специалистов. Такого, который бы рассказал, как всё устроено на самом деле, а не в сферическо-вакуумном мире из учебников и методичек.
Какую задачу мы взяли для практики с ребятами и как вместе решали её — рассказываем по порядку.
Краткий экскурс в историю
В интернете легко найти статьи о том, что в СССР экипажи гражданской авиации летали всегда одним составом, знакомы были чуть ли не с лётного училища, дружили семьями, вместе отдыхали… Но по словам действующего пилота, который успел полетать в те славные годы, эта информация не совсем соответствует действительности. Да, к такому положению вещей стремились, но жизнь, как всегда, вносила коррективы: кто-то заболел, кто-то перепил накануне и не получил допуск на рейс, кто-то просто опоздал на явку — и вот в уже слетавшийся экипаж приходит человек из резерва.
В устоявшемся коллективе всегда есть негласная иерархия, и истории известны случаи, когда твёрдое слово лидера приводило к опасному инциденту, а иногда и катастрофе. Вот лишь пара примеров:
- 27 марта 1977 г., Тенерифе. Оба пилота проигнорировали сомнение бортинженера насчёт того, что полоса свободна, и начали разбег. В итоге произошло столкновение с другим самолётом и крупнейшая авиакатастрофа в истории. (Трагедию, конечно, определила целая череда событий, но ошибка экипажа была одним из решающих факторов.)
- 20 октября 1986 г., Куйбышев. Командир поспорил со вторым пилотом, что сможет посадить самолёт вслепую, исключительно по показаниям приборов — и это при идеальной видимости. В кабине находились ещё трое человек, и никто не сказал командиру, что он творит лютую дичь. Результат: досадная ошибка в расчётах, крушение и 64 погибших.
И это только самые громкие события — вообще их намного больше. Если посмотреть «Расследование авиакатастроф», то в каждом втором выпуске кэп давит авторитетом остальных членов экипажа, и кончается всё печально.
Начиная с 90-х годов прошлого века, авиакомпании по всему миру стали внедрять концепцию Crew Resource Management (CRM). Она подразумевает в том числе подход осознанного неподчинения для предотвращения катастрофы. Указать на ошибку малознакомому человеку психологически проще, чем давнему другу и начальнику. Поэтому сегодня в крупных авиакомпаниях вполне нормально, когда экипаж, которому предстоит выполнить рейс, знакомится за несколько часов до вылета, на брифинге.
Так у перевозчиков появилась новая вакансия — планировщик. В его обязанности входит формирование экипажей на все предстоящие рейсы. При этом он должен учитывать трудовое законодательство, которое запрещает переработки, устанавливает минимальное время между рейсами и ещё сотней способов регламентирует обеспечение безопасности полётов.
И вот примерно десять лет назад на эту сцену вышли информационные технологии. Вычислительные мощности развились достаточно, чтобы оперировать большими объёмами данных. И решать задачи комбинаторики стало значительно проще и эффективнее с помощью компьютера: его не надо содержать, как сотрудника, он не заболеет и не уйдёт в отпуск, да и человеческий фактор практически исключается (не считая багов, занесённых разработчиком системы).
Ставим задачу
Итак, мы хотим разработать систему, которая умеет:
- Управлять парком авиакомпании. Для этого нужна справочная информация обо всех регламентных работах, которые требует или рекомендует производитель. Также важно всегда держать под контролем состояние отдельных агрегатов каждого воздушного судна: двигателей, вспомогательных силовых установок, аварийно-спасательного оборудования, авионики и других, — и вести logbook. Чтобы упростить разработку, допустим, что наша компания владеет воздушными судами одного типа.
- Управлять человеческими ресурсами. Здесь говорим о членах экипажа — пилотах и бортпроводниках (административный и технический персонал в этом задании не рассматриваем). Обязательно учитываем, что человек может уйти в отпуск, на больничный или отсутствовать на рейсе по другой причине.
- Управлять расписанием рейсов. Рейсы могут быть как регулярными, то есть выполняться в определённые дни и время, так и чартерными или техническими — для разового перемещения самолёта с экипажем.
- Ставить самолёты и собирать экипажи на каждый рейс. Важно, чтобы суда как можно меньше стояли на земле, а экипажи по возможности каждый раз выходили на рейс в новом составе.
С первыми тремя пунктами вопросов не возникает — это стандартная функциональность практически любой CRM-системы для предприятия, немного усложнённая интеграциями с IoT-модулями самолётов (если таковые имеются). А вот планировщик рейсов — довольно сложный комплекс, который должен заполнить сетку так, чтобы каждый рейс выполнялся:
— на технически исправном воздушном судне,
— с отдохнувшим экипажем,
— и желательно с не летавшими ранее вместе пилотами и бортпроводниками.
При этом все самолёты нужно максимально задействовать в полётах, без простоев в аэропортах. А членам экипажа — обеспечить примерно одинаковое количество часов в небе. Также возможны дополнительные условия: например, некоторые авиакомпании стараются ставить семейные пары из экипажей на один рейс, а другие — наоборот (и у обоих принципов есть логичное обоснование). Иными словами, у нас есть множество ограничений, которые обязательно надо учитывать при планировании.
Распределяем самолёты
Рассмотрим постановку задачи более подробно, введём несколько вспомогательных определений.
Полёт (Flight) — структура, описывающая единственное перемещение конкретного воздушного судна из точки A в точку B с установленным временем вылета и прилёта.
Шаблон генерации, или план, полётов (Route) — это правила, задающие информацию для создания полётов. Шаблон определяет время и аэропорт вылета и прилёта; дни недели, когда должны состояться полёты; ожидаемое количество пассажиров; а также диапазон дат, в который рейс будет выполняться.
Нам необходимо разработать подсистему генерации полётов по расписанию и назначения самолётов. При этом шаблоны генерации расписания задаются персоналом, а на систему ложится ответственность по выбору подходящих судов, которые будут доступны в пунктах вылета в установленное время. Мы решили задавать расписание так, потому что большинство рейсов на практике планируются именно таким образом. Кроме того, данные в таком виде часто можно встретить на сайтах авиакомпаний и аэропортов.
Выдвинем следующие требования:
- Время «оборота» (время, которое самолёт должен провести на земле для обслуживания) не должно быть меньше установленного в конфигурации значения. Среднестатистическая авиакомпания способна «обернуть» самолёт за 40 минут (лоукостеры не считаем — у них там своя атмосфера).
- Расписание должно генерироваться последовательными фрагментами, которые всегда осуществимы и укладываются в установленный график.
- Если фрагменты пересекаются на каком-то участке, отрезок нового фрагмента должен вставать на место отрезка старого.
- Отменённые рейсы не должны генерироваться вновь, а выделенные под них ресурсы — должны освобождаться.
Проанализировав эти требования, в качестве основы для более эффективных решений мы решили реализовать жадный рандомизированный алгоритм. Будем последовательно, по возрастанию времени вылета, для каждого неотменённого полёта определять, какие самолёты доступны в аэропорту вылета в установленное время. И уже среди них выбирать любой, который удовлетворяет требованиям по вместимости и максимальной дальности полёта.
Но мы столкнулись с проблемой: как понять, какие самолёты будут в аэропорту в указанное время? Сначала мы думали хранить в базе данных актуальную информацию о местоположении каждого самолёта и о том, где он будет находиться. Но такое решение создаёт лишние зависимости: как указать, в каком аэропорту самолёт, когда он в воздухе? Как обозначить самолёт, который стоит в пункте отправления, но ещё не готов к полёту? Кроме того, при таком подходе регулярно приходилось бы редактировать расписание вручную. Например, при нештатных ситуациях во время полёта: когда самолёт прибыл на запасной аэродром из-за погоды или ЧП на борту. Тогда операторам приходится самим вводить данные фактического местоположения судна. Это трудоёмко и не очень безопасно с точки зрения согласованности данных: приходится всё полётное расписание пропускать через голову. А поскольку решать такие кейсы требуется оперативно, добавляются стресс и человеческий фактор — лучшие друзья инцидентов.
Так что мы решили определять местоположение самолёта на ходу. Он находится в аэропорту, если прибыл туда меньше 40 минут назад и после этого никуда не улетел. Приблизительно так и выглядит запрос к базе данных. Такой подход фактически гарантирует актуальность данных и не вызывает вопросов, где самолёт, если он в полёте.
Но это решение отвечает только на вопрос о том, где находится самолёт прямо сейчас. А нас в процессе генерации практически всегда интересует, где самолёт будет в нужное время. Для решения такой задачи мы решили попросту моделировать расписание, отталкиваясь от текущего расположения самолётов.
Так как нам необходимо знать расположение судов последовательно во времени, достаточно перемещать их, как сказано в расписании. При этом перед каждым вылетом необходимо возвращать прилетевшие самолёты из состояния «В полёте» на землю — в соответствующий аэропорт. Этот подход гарантирует, что расписание корректно, то есть что нет таких случаев, когда самолёт пытается вылететь из аэропорта, в котором его нет (такое может произойти, когда расписание редактируют вручную). Если ошибка всё же допущена, то генерация будет остановлена, а оператор получит уведомление о том, что расписание некорректно. Кроме того, в этом подходе для одной попытки генерации требуется всего один раз пройти по списку запланированных полётов.
Жадный рандомизированный алгоритм не всегда находит решение. Например, это может произойти в такой ситуации:
Алгоритм отправил в аэропорт B более вместительный самолёт. Это привело к тому, что по маршруту A-C-D направилось судно с меньшим количеством мест — и оно не сможет перевезти всех пассажиров на последнем этапе. Но такая ситуация на практике должна возникать редко, ведь авиакомпании строят маршруты с учётом максимизации прибыли и пытаются заполнять суда полностью. Так что практически всегда самолёты определяются однозначно, а выбор у алгоритма есть только среди судов с одинаковой вместимостью. В крайнем случае можно сослаться на овербукинг и предложить некоторым пассажирам улететь следующим рейсом.
Бороться с подобной проблемой, если она возникнет, мы решили брутфорсом. Будем запускать генерацию некоторое число раз (оно задаётся в настройках системы) — и если расписание не будет построено, система об этом уведомит. Тогда можно либо запустить процесс ещё раз, либо смириться с фактом, что расписание построить невозможно. Все запросы на его генерацию выполняются асинхронно, а результаты отображаются на странице шаблонов полётов.
Формируем экипажи
Когда суда назначены на рейсы, похожим образом формируются экипажи. Здесь тоже есть ограничения. Например, законодательство РФ запрещает членам экипажа летать более 12 часов подряд: после половины суток в небе положен 12-часовой отдых. Также нельзя летать более 80 часов в месяц (в исключительных случаях допускается до 90 часов, но по повышенной ставке). Ещё пример: запрещено перелетать океан больше трёх раз в календарный месяц. Все ограничения по каждому сотруднику должен учитывать планировщик — и корректно комплектовать экипаж или оповещать о том, что это невозможно.
Не забываем и об обязательной ротации экипажей: чтобы обеспечить более высокий уровень безопасности, желательно подбирать команду, которая ранее не работала таким составом. Но это условие практически невыполнимо по двум причинам.
Во-первых, количество специалистов конечно и довольно ограничено — так или иначе на рейсе будут два-три человека, которые уже знакомы.
Во-вторых, сравнение возможных комбинаций становится нетривиальной задачей. Например, имея флот в 10 самолётов, нам необходимо 50 укомплектованных экипажей в штате — по пять на каждое воздушное судно. Для Airbus A320 или Boeing 737 (самых распространённых типов самолётов в мире) это командир (p1), второй пилот (p2) и четыре бортпроводника (a), из которых один старший (af). Суммарное количество всех возможных комбинаций будет почти 69 млрд. Если учесть факт, что пилот, имеющий статус командира, может исполнять обязанности второго пилота, а старший бортпроводник может работать в роли рядового, то это число увеличивается ещё на несколько порядков. В общем случае формула будет выглядеть так:
Перефразируя великого Конфуция: «Видишь факториалы — прячься, глупец!». Получается, мы физически никак не можем проверить, был ли такой состав экипажа когда-либо. Во всяком случае, за более-менее адекватное время. Шутка ли — сравнить текущее значение с 70 миллиардами других, и это только в рамках анализа одного рейса!
Очевидно, что решение в лоб не подходит. Надо искать алгоритм, который будет давать достаточно хороший результат, но при этом не требовать бесконечного времени на исполнение. Здесь мы вернулись к жадным алгоритмам, которые просто незаменимы при решении подобных задач. После мозгового штурма выработали такую последовательность:
- При планировании первого числа месяца формируем пул для каждой роли в экипаже (командир, второй пилот, бригадир, бортпроводник). С каждым пулом будем работать по принципу очереди.
- Проходим по временной шкале от начала к концу месяца. Как только встречаем рейс, который надо запланировать, берём сверху каждого пула необходимое количество человек. Проверяем для каждого, может ли он быть на рейсе: достаточно ли времени прошло с его прошлого полёта, не находится ли он в отпуске или на больничном, смотрим на прочие ограничения. Если все условия соблюдены, записываем человека в полётное задание, если нет — ставим его в конец очереди и берём следующего.
- Как только экипаж сформирован, нам надо получить хеш, который складывается из последовательности id.
- Берём такие же хеши для N предыдущих рейсов (например, за прошедший месяц) и для каждого находим расстояние Левенштейна до текущего хеша.
- Если на этой выборке не нашлось хеша, до которого расстояние меньше 3, значит, текущий экипаж как минимум на 50% не повторялся в последнее время и его можно записывать в таком виде. В противном случае возвращаемся к п. 2 и продолжаем жонглировать очередями.
Важно также учитывать, что большинство рейсов разворотные, — значит, на обратный рейс нужно ставить тот же борт и экипаж. Это сокращает количество вычислений примерно в два раза.
Такой алгоритм может надолго зациклиться, поэтому есть смысл жёстко ограничить максимальное количество итераций, чтобы сформировался хотя бы какой-то экипаж.
Что может пойти не так
В реальности деятельность авиакомпании редко полностью соответствует планируемому расписанию. Причин этому много: например, у воздушного судна может возникнуть неисправность — и выполнять на нём рейсы будет просто опасно для жизни. Или один из членов экипажа берёт больничный или попадает в пробку по пути в аэропорт. Также часто наземные службы не успевают вовремя подготовить самолёт к вылету. Всё это приводит к задержкам рейсов, а иногда даже к их отмене. Так что создаём систему выявления несоответствий в исполнении расписания.
Система способна распознавать ошибки и показывать предупреждения там, где могут возникнуть проблемы.
Есть такие предупреждения и статусы:
- SCHEDULED — полёт запланирован по расписанию;
- DEPARTED — самолёт отправился из аэропорта вылета;
- DEPARTURE_DELAY — самолёт не вылетает из аэропорта слишком долго;
- ARRIVED — самолёт приземлился в аэропорту назначения;
- ARRIVAL_DELAY — самолёт не приземляется слишком долго;
- ARRIVAL_SHIFTED — самолёт приземлился позже планируемого.
Выделенные предупреждения могут вызвать задержку или даже отмену последующих рейсов.
В нашей системе распознаются следующие проблемы, не позволяющие осуществить рейс:
- PREVIOUS_ARRIVED_TO_LATE — самолёт приземлился поздно, и перед следующим вылетом не выдерживается время оборота;
- PREVIOUS_CAN_ARRIVE_TO_LATE — исходя из планируемого времени полёта судно не сможет приземлиться вовремя, так что возникнет предыдущая ошибка:
- PREVIOUS_NOT_DEPARTURE_TOO_LONG — даже если самолёт с предыдущего рейса вылетит прямо сейчас, он всё равно не будет подготовлен к текущему рейсу;
- AIRCRAFT_WILL_BE_IN_ANOTHER_AIRPORT — по какой-то причине (ЧП, ручное изменение расписания) судно будет находиться в другом аэропорту;
- AIRCRAFT_IN_ANOTHER_AIRPORT — то же, что и в предыдущей ошибке, но как случившийся факт: самолёт уже в другом аэропорту;
- EMPLOYEE_NOT_AVAILABLE — сотрудник, назначенный на рейс, будет недоступен;
- AIRCRAFT_DEVICE_PROBLEM — одно из устройств самолёта технически неисправно и не позволяет выполнить рейс.
Для отслеживания последних двух ошибок мы добавили личные страницы судов и экипажа. Там можно посмотреть предстоящие рейсы, события (дневник), ближайшие отпуска, выходные и больничные экипажа, а также список устройств самолёта (двигатели, шасси).
Для каждого из упомянутых устройств также есть страница, где можно указать ограничения по параметрам: при каких значениях устройство приходит в негодность или требует техобслуживания. Например, максимальное количество часов и циклов или допустимое значение по часам и циклам соответственно.
В итоге мы разработали прототип CRM-системы авиакомпании, охватывающий наиболее важные функциональные требования. Осталась самая малость: закупить воздушные суда, нанять экипажи, получить сертификат эксплуатанта, выкупить слоты в аэропортах — и можно выполнять регулярные рейсы.
Хочу сказать больше спасибо Илье Сокову и Диме Цыкунову — именно они работали над проектом весь семестр. А также Лиде Перовской за приглашение поучаствовать в программе менторства — это был бесценный опыт, который я планирую повторить. Эту статью можно считать результатом нашего общего интеллектуального труда — всех четверых. Ребята, вы крутые!
P. S. Надо понимать, что реализованные нами алгоритмы далеки от идеала, — и, скорее всего, серьёзно уступают существующим enterprise-решениям. Но свою миссию они выполнили: студенты получили практические навыки и попробовали решить задачу из реальной жизни. В этом и заключается конечная цель образовательного процесса.
P. P. S. Ни у кого из участников этого проекта нет профильного образования и опыта работы в авиации — поэтому мы запросто могли что-то напутать. Если среди читателей найдутся эксперты в этой области, будем рады получить обратную связь в комментариях.
Источник: Блог компании VK на Хабре