Среди всех секторов экономики, пострадавших от Covid19, больше всего пострадало воздушное сообщение. Авиакомпании сильно страдают, а, следовательно, и аэропорты. Теперь, когда большинство стран ЕС вновь открывают свои границы, воздушное движение снова медленно растет.
Очевидно, что нынешнее движение далеко от доковидного уровня, и аэропорту не имеет смысла открывать все свои терминалы.< br /> Ставки высоки: отсрочка открытия терминала даже на несколько месяцев может сэкономить десятки миллионов евро.
Недавно я участвовал в проекте с аэропортом №1 в ЕС, чтобы работать над этой проблемой:< br /> если вы представляете собой аэропорт, учитывая прогнозы авиаперевозок на следующее десятилетие и финансовые данные о ваших терминалах (постоянные/переменные затраты/доходы), как вы можете оптимизировать последовательность повторного открытия для всех терминалов?

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

У меня были прогнозы трафика от каждой авиакомпании за 90-месячный период, поэтому мой тензор трафика имел форму (nb_airlines, nb_months). У меня были финансовые данные терминалов аэропорта, разделенные на 6 метаданных: фиксированные затраты/доход, если они закрыты/открыты, переменные затраты/доход на PAX, поэтому тензор метаданных моего терминала имел форму (nb_terminals, 6).

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

Как и во всех ситуациях оптимизации, вам нужно упростить задачу, смоделировать ее, запустить оптимизацию, и как только вы поймете динамику, вы можете начать добавлять ограничения для повышения реалистичности.
В нашем случае я решил сначала игнорировать назначений авиакомпаний/терминалов и просто сосредоточиться на распределении трафика по терминалам (шенгенским и международным). Конкретно это означает, что я загрузил прогноз трафика авиакомпаний в тензоры Pytorch и суммировал их по измерению авиакомпаний, чтобы получить агрегированные суммы трафика для международного и шенгенского трафика. Тогда у меня было 2 тензора трафика (международный/шенгенский) с формой (1, nb_months).

Вторая проблема, с которой я столкнулся, — это моделирование проблемы. Сначала я хотел иметь в качестве переменных бинарные флаги открытия/закрытия для каждого терминала, месяц за месяцем. Затем я вычислил эффективную доступную пропускную способность, несоответствие прогнозам трафика авиакомпаний и вычислил фиксированные + переменные затраты и доход для каждого терминала.
Проблема в том, что Pytorch Autograd требует, чтобы функция потерь была дифференцируемой, что означает, что она должна быть непрерывным почти везде. Это не очень хорошо работает с бинарными целочисленными флагами для открытых/закрытых терминалов.
Итак, я решил использовать непрерывные переменные. Конкретно, я использовал тензор float32 размера (nb_terminals, nb_months) со значениями от 0 до 1. Затем я мог с помощью нескольких тензорных операций вычислить в функции убытков прибыль с течением времени и несоответствие пропускной способности трафика.

Третья проблема, с которой я столкнулся, касалась ограничения переменных. Очевидно, вы хотите, чтобы коэффициент открытия/закрытия терминала находился в диапазоне от 0 до 1. Если вы не будете осторожны, оптимизатор выдаст отрицательный коэффициент открытия для терминалов с плохой структурой затрат (они большую часть времени теряют деньги, поэтому оптимизатор может назначить отрицательный open rate = отрицательный трафик, чтобы сделать его прибыльным, что, конечно, не имеет смысла).
Как оказалось, ограничить переменную в диапазоне [0,1] с Autograd не так просто, на практике и в теории тоже. На практике Автоград не имеет (по состоянию на июнь 2020 года) встроенного способа указания границ переменных. Это может быть преодолено с использованием torch.min и torch.max в функции потерь (= «мягкий зажим», «мягкая» часть важна, потому что вам нужны градиенты, не используйте torch.clamp).< br /> Но проблема была больше. Сначала я попытался быть умным и включить член в функцию убытков, чтобы гарантировать, что коэффициенты открытия/закрытия были как можно ближе к 0 или 1. Конкретно этот термин касался минимизации квадрата (квадрат (x) — x). 0 и 1 — это единственные числа с плавающей запятой, где «квадрат = идентичность», поэтому я ожидал, что оптимизатор попытается получить в основном числа с плавающей запятой 0/1 в конце процесса. термин функции потерь, чтобы убедиться, что оптимизатор отнесся к этому серьезно. Проблема в том, что это полностью обескуражило исследование: оптимизатор счел слишком дорогим уход от точки инициализации, и это «мягкое бинарное ограничение» сделало невозможным для оптимизатора поиск путей, которые изменили бы состояние открытия/закрытия терминала.
В конце концов мне пришлось убрать это ограничение и принять любое значение от 0 до 1 для состояния открытия/закрытия терминала, чтобы позволить оптимизатору исследовать все возможные состояния.

Четвертая проблема, с которой я столкнулся, — это нормализация. Это было не слишком сложно решить, в основном, если разные члены функции потерь имеют разные порядки величины, градиент будет самым большим для самого большого члена в функции потерь, что означает, что другой член не будет сильно влиять на оптимизацию. Лучшее решение — убедиться, что каждый член функции потерь нормализован. Для несоответствия пропускной способности я предположил, что самое большое несоответствие трафика — это «все терминалы закрыты», поэтому я использовал несоответствие в этой ситуации в качестве знаменателя для нормализации члена несоответствия функции потерь. Что касается прибыли, я предположил, что наибольшая прибыль достигается, когда все терминалы работают на полную мощность, я использовал прибыль в этой ситуации в качестве знаменателя нормализации для члена прибыли функции убытков.

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

Затем встал вопрос о распределении компаний/терминалов. Это очень сложно, потому что, по сути, аэропорт хочет, чтобы все компании могли летать прямо сейчас, хочет открыть как можно меньше терминалов и хочет переместить как можно меньше авиакомпаний (потому что авиакомпании ненавидят переключать терминалы). Эти потребности противоречивы, что само по себе не шокирует, это основа почти всех реальных проблем оптимизации. Если нет противоречащих друг другу факторов, то проблема, как правило, проста.
Принимая во внимание распределение авиакомпаний/терминалов, возникает очень неприятная проблема: операции в аэропортах сопровождаются многими исключениями. Авиакомпании из одной группы (например, StarAlliance, SkyTeam и т. д.) должны быть по возможности сгруппированы вместе. Некоторые авиакомпании не могут перемещаться, некоторые другие могут, но только между терминалами X и Y и т. д.
Когда дело доходит до оптимизации, это не очень хорошая новость, особенно в моей ситуации, когда я использую Pytorch Autograd, для которого нужно решить проблему. дифференцируемый. Все эти ограничения можно было бы реализовать с помощью кода, похожего на «если», но логика ветвления в вашей функции потерь действительно затрудняет дифференцируемость.

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

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

В этом проекте использовались Pytorch и Autograd, но вообще не использовались нейронные сети. Кто-то может сказать, что использование слова ИИ несколько преувеличено, и это правда, что этот проект, вероятно, лучше определить с помощью термина дифференцируемое программирование.
Янн ЛеКун сказал несколько лет назад: Глубокое обучение мертво. Да здравствует дифференцируемое программирование! и Я согласен, что мы будем видеть все больше и больше отличных демонстраций с Pytorch и Autograd без обязательного использования нейронных сетей.

Первоначально опубликовано на http://fruty.io 30 июня 2020 г.