В рамках серии статей по применению математической оптимизации для решения задач в бизнесе мне хотелось бы кратко, но ёмко раскрыть причины и предпосылки возникновения потребности у бизнеса решений задач такого класса, а также привести конкретные примеры кейсов, которые успешно реализованы в крупнейших компаниях мира. В отдельности каждый кейс заслуживает не менее 50 страниц текста для полноценного описания, я же постараюсь изложить главную суть решений и некоторые технические особенности в формате статей на Хабре.

Алгоритмы математической оптимизации относятся к категории Prescriptive – аналитики, наиболее сложного и ценного для бизнеса аналитического сегмента. Данная категория позволяет создавать сложные интеллектуальные системы принятия решения с целью максимизировать экономические, производственные и многие другие KPI в рамках заданных ограничений.  Математическая оптимизация имеет своё применение в каждом из видов бизнеса любого масштаба, включая промышленность, производство, розничную торговлю, транспорт и логистика, телеком, агросектор, энергетика, строительство, финансы, банкинг, спорт, кино, медицина, образование и т.д. В текущей статье пойдет речь о задачах в индустрии пассажирских авиалиний.

Почему начинаем с пассажирских авиалиний? Главная причина: это одна из самых подходящих индустрий для генерации экономического эффекта за счет применения оптимизационных решений. К примеру, компания Lufthansa своим решением NetLine/FleetAssigner для планирования расписаний оценивает эффект от внедрения в 600 000 евро в месяц для средней компании. Также на текущий момент для крупных игроков мирового рынка решение подобных задач является актуальным, о чем может говорить большое количество пресс-релизов и вакансий на позицию Operations Research Scientist.

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

Но зачем компаниям иметь свой собственный штат специалистов узкого профиля? На рынке присутствует некоторое количество коробочных решений, которые решают отдельные задачи с применением оптимизационных алгоритмов, в том числе те, о которых пойдет разговор далее в статье, но несмотря на это спустя некоторое время компании пришли к выводу, что разработка решений специально для компании имеет серьезные преимущества перед готовыми решениями:

• Учет всех особенностей процессов конкретной компании. В каждой из компаний многие процессы выстроены с учетом внутренних особенностей ведения бизнеса, законодательства, рыночной конъюнктуры и готовое решение может быть в полной степени использовано, только если учтены все эти нюансы.

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

• Возможность решений некоторых задач для непредвиденных для системы случаев в максимально короткие сроки. Благодаря наличию экспертов можно в ручном режиме задать условия возникшей задачи и получить её решение.

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

Наиболее важными задачами с точки зрения экономической эффективности в авиалиниях являются 3 задачи с применением математической оптимизации:

• Планирование маршрутов и расписаний для максимизации прибыли и использования флота

• Планирование экипажей на рейсы с учетом нормативных требований и обеспечения квалификации

• Динамическое ценообразование на базе истории с учетом кросс-эффектов альтернативных вариантов

Далее я постараюсь изложить суть каждого из кейсов.

Кейс 1. Планирование маршрутов и расписаний для максимизации прибыли и использования флота

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

При выборе оптимального расписания учитываются следующие факторы:

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

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

• Ограничения по ресурсам: количество и вместимость самолетов, персонал, время обслуживания, обучения и т.д. Важно учитывать, чтобы хватало людей, способных обеспечить выполнение рейсов по квалификационным требованиям. Чтобы было время на выполнение работ по подготовке транспорта и время на обслуживание.

• Ограничения инфраструктуры аэропорта, законодательные, условия договоров на выполнение полетов различных направлениях, нормативы по возможным задержкам и прочие нормативные ограничения.

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

Сама задача при нагромождении большим количеством опций, ограничений и высокой детализации становится комбинаторно сложной. Несмотря на отсутствие необходимости построения плана очень часто для работы с большим количеством сценариев у крупных компаний вопрос времени поиска стоит остро и для решения требуется качественная модель с хорошей линейной релаксацией и топовый коммерческий солвер.

Кейс 2. Планирование экипажей на рейсы с учетом нормативных требований и обеспечения квалификации

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

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

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

• Удовлетворение личных предпочтений и потребностей членов экипажа. В некоторых случаях учитываются предпочтения членов экипажей, как по наличию в них других сотрудников, так и по определенным направлениям.

• Другие бизнес-ограничения и предложения

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

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

Кейс 3. Динамическое ценообразование на билеты

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

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

• Для линейной регрессии (очень упрощенной и не используемой на практике) применяется линейное программирование.

• Для нелинейной регрессии или нейронных сетей: для выпуклой функции - методом выпуклой оптимизации, для невыпуклой - методом внутренней точки с применением мультистарта (или других методов нелинейной оптимизации).

• Для методов машинного обучения без явной формализации (деревья, леса, бустинг, SVM и т. д.) используются методы стохастической оптимизации — генетические алгоритмы, имитация отжига и т. д.

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

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

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

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