Задание на бакалаврскую работу 4 (new version)

Тема бакалаврской работы: ¾Оптимизация продаж авиационных билетов

Single leg allocation optimization by Expected Marginal Seat Revenue (EMSRb)¿

1. Немного о терминах и о математической формулировке задачи

Назовем рынком (market) пару городов O è D, между которыми есть хотя бы один маршрут (itinerary). Каждый рынок состоит из двух направленных рынков (directed market): O¡D è D ¡O. Каждый маршрут представляет собой несколько стыкующихся рейсов (leg or flight).

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

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

На каждом направленном рынке пассажир с определенной вероятностью выберет продукты нашей авиакомпании. Эта вероятность называется долей авиакомпании на направленном рынке.

Задачи bid price model определяют оптимальную стратегию продаж при заданном прогнозе спроса на продукты. При этом не принимается во внимание, насколько различаются цены для продуктов. Это может привести к тому, что, например, для двух продуктов, одна и та же стратегия будет выработана и в случае, когда цены соотносятся как 110 è 100, ì â

том случае, когда они 1000 è 100. Это, естественно, не очень логично, потому что, во втором

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

Рассмотрим отдельный рейс и предположим, что он используется только двумя продуктами:

A местный рынок за полную стоимость;

B местный рынок со скидкой.

Нам заданы остаточная вместимость Cap на рейсе, прогноз на остаточный спрос DA è DB для продуктов A è B, а также стоимости TA è TB

ýòîì TA > TB.

В работе следует определить, сколько билетов необходимо зарезервировать для покупателей желающих приобрести продукт A. Очевидно, что, если покупатель просит

продукт A, то мы продаем ему этот продукт. Если же покупатель просит продукт B, òî

перед нами встает выбор продавать ему этот продукт, либо подождать, пока не придет покупатель более дорогого продукта A.

При решении о продаже продукта B нужно учитывать математическое ожидание дохода от принятого решения:

1. если мы продаем продукт B, то получаем его цену TB;

2.если мы не продаем продукт B, то, может быть, потом получим стоимость продукта A, ò.å. TA.

Затем нужно сгенерировать 20 случайных потоков запросов для одного рейса и применить стратегии I IV, проведя сравнение среднего полученного дохода.

Следующим шагом в работе является повторение модельного эксперимента для случая с 5-ю классами бронирования j = 1; : : : ; 5. В этом случае для определения yj количества

зарезервированных для данного j-го класса билетов используем метод EMSRb (Expected Marginal Seat Revenue Version b), предложенный в [2]. Примем, что меньшее значение j обозначает более высокий ценовой класс, т.е. Tj > Tj+1.

Данные для прогноза спроса для модельной задачи с 5-ю ценовыми классами приведены в Табл. 2

Таблица 2. Прогноз спроса на продукты (5 классов).

Метод EMSRb состоит в следующей последовательности шагов.

а) Сначала рассматриваются два верхних класса j = 1 è j = 2, и значение y1 определяется точно так же, как в задаче с классами A è B, причем используются данные только для этих двух классов.

б) затем два верхних класса объединяются в один ¾суперкласс¿, для которого рассчи- тывается мат. ожидание и СКВО по соответствующим данным отдельных классов, а также средневзвешенная (по прогнозу остаточного спроса) цена билета. После этого мы рассматриваем класс j = 3 вместе с этим суперклассом и опять решая задачу

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

в) последний шаг повторяется (образуется суперкласс из первых трех и т.д.) нужное число раз.

В результате мы получим последовательность yj уровней защиты (protection level) для всех классов, т.е. количество зарезервированных мест для классов, начиная с j-ãî è âûøå,

см. следующую часть.

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

3. Вложенные и невложенные классы бронирования

Ценовые классы, или классы бронирования (fare classes) характеризуют уровень скидок при продаже авиационных билетов в различные кабины (в первый класс, в бизнес-класс, в эконом-класс и т.п.). При этом ценовой класс подразумевает не одну фиксированную цену билета, а целый интервал цен, т.е. в рамках одного и того же ценового класса возможна продажа билетов по различной стоимости. Эти интервалы для разных классов могут пересекаться. Обозначаются ценовые классы специальными кодами, которые выбираются каждой авиакомпанией самостоятельно. Например, коды B, H, Q, M и некоторые другие соответствуют ценовому классу для билета в кабину эконом-класса со скидкой, коды Y и S билет той же кабины без скидки и т.д.

Предел бронирования.

При заданной вместимости самолета Cap уровень, или предел бронирования bj (book- ing limit) для определенного ценового класса j означает максимальное количество мест,

которые мы хотим продать покупателям, желающим приобрести билеты этого класса. Например, если в стратегии продаж указано b3 = 10, то это означает, что для класса 3 отведено

не более 10 билетов. После продажи этого количества билетов класс закрывается для покупателей.

Различают невложенные и вложенные уровни бронирования. При невложенной структуре (partitioned, or non-nested, booking limit) каждому ценовому классу отводится определенный сегмент в общей вместимости, который может быть продан только покупателям этого класса. Например, при общей вместимости Cap = 100 и невложенной структуре цено-

вых классов bp1 = 20, bp2 = 30 è bp3 = 50 (верхний индекс p означает `partitioned'), первый класс будет закрыт немедленно после продажи в нем 20 билетов, независимо от того, остались ли не проданными места в других классах. Очевидно, если первый класс является высшим по цене, то такая стратегия продаж неудачна.

Следует обязательно подчеркнуть, что конкретные значения пределов бронирования связаны с прогнозомp остаточного спроса на соответствующие ценовые классы. Так, в простейшем случае, b1 = 20 с точки зрения прогноза спроса означает, что мы предполагаем спрос на верхний ценовой класс в 20 человек, и поэтому хотим продавать в нем 20 билетов.

Ïðè вложенной структуре бронирования (nested booking limit) более высокие по цене классы включают все находящиеся ниже, образуя систему иерархически вложенных друг в друга подмножеств. В результате, для класса j открыты билеты, отведенные для классов

j + 1, j + 2 ; : : : .

Например, при той же вместимости Cap = 100 и вложенной структуре ценовых классов

пределы бронирования bn1 = 100, bn2 = 80 è bn3 = 50 (верхний индекс n означает `nested') показывают, что мы хотим продать не более 50-ти билетов третьего класса, не более 80-ти второго и как можно больше билетов самого высокого первого класса, см. рис. 2. Полученные данные так же основаны на прогнозе спроса, как и в случае невложенных классов. Мы спрогнозировали спрос на первый класс в 20 человек. Следовательно это же количество билетов следует зарезервировать только äëÿ j = 1, т.е. сделать эти билеты недоступными

для нижних классов. Поэтому в распоряжении второго класса остается только bn2 = 100¡20 = 80 билетов. Прогноз спроса на второй класс равен 30-ти. Эти билеты, как и предыдущие 20,

должны быть недоступны нижнему классу. Соответственно, ему остается всего 50 билетов,

bn3 = 80 ¡ 30 = 50.

Рис. 2: Соотношение между пределом бронирования bj и уровнем защиты yj для ценовых классов.

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

более высокие классы уже закрыты, а на нижних классах еще есть свободные места.

Уровень защиты.

Еще одним параметром, характеризующим стратегию продаж по ценовым классам, служит уровень защиты (protection level). Уровень защиты yj показывает количество мест,

зарезервированных для продажи данному классу j, либо некоторому множеству классов.

Ïðè невложенной структуре ценовых классов уровень защиты определяется для каждого отдельного класса j и, при этом, он совпадает с пределом бронирования этого класса,

Например, предел бронирования для класса 2, равный 30-ти (b2 = 30) равен уровню защиты

для этого класса, y2 = 30.

Ïðè вложенной структуре уровни защиты ценовых классов, как и пределы бронирования, образуют вложенную иерархическую структуру. Если предположить, что классы расположены по убыванию цены (класс j выше, чем класс j + 1), то каждый уровень защиты yj, â отличие от невложенной структуры, определяется не для одного класса, а для совокупности классов, начиная с j и выше, и обозначает количество мест, зарезервированных для продажи

всем этим классам. Например, y1 = 20, y2 = 50 è y3 = 100 означает, что мы зарезервировали

20 билетов для одного первого класса и 50 билетов для продажи только первому и второму классу (и эти билеты будут недоступны более низкому третьему классу), см. рис. 2. Уровень защиты для самого нижнего класса всегда совпадает с вместимостью Cap, поскольку все

классы в сумме как раз образуют эту вместимость. Предел бронирования и уровень защиты

для вложенных классов связаны соотношением

4. Моделирование работы системы продаж для невложенных и вложенных ценовых классов

В системах продаж (reservations system), которые используются большинством авиакомпаний, динамический контроль количества проданных и доступных билетов для всех ценовых классов j = 1; : : : ; N, входящих в данный рейс вместимости Cap, осуществляется изменени-

ем значений пределов бронирования bj и уровней защиты yj. Эти изменения производятся после каждой покупки билета в любом из классов j.

Отметим еще раз, что начальные значения пределов бронирования как для вложенных, так и для невложенных классов тесно связаны с прогнозом спроса. В данном разделе мы не обсуждаем, методы определения пределов продаж для разных классов. Значения bj

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

Контроль продаж для невложенной структуры ценовых классов.

Ïðè невложенной структуре ценовых классов после покупки билета класса j соответ-

bpj (или, что то же самое, уровня защиты yj) уменьшается на единицу, а все остальные величины bpk, k =6 j не меняются. После того, как какое-либо значение bpj становится равным нулю, данный класс j закрывается независимо от того, есть ли доступные места в более низких ценовых классах.

Рис. 3: Изменение значения для пределов бронирования bpj при невложенной структуре це- новых классов.

На рис. 3 показан процесс изменения величин bpj для невложенной структуры из трех це- новых классов с начальными значениями bp1 = 2, bp2 = 3, bp3 = 5 (общая вместимость Cap = 10) в результате появления десяти случайно сгенерированных запросов. Класс запроса показан единицей, расположенной в соответствующей этому классу строке. Таким образом, видно, что первым был запрос на билет третьего класса, в результате чего пределы бронирования получили значения bp1 = 2, bp2 = 3, bp3 = 4.

По сути, текущее значение bpj равно математическому ожиданию прогноза остаточного спроса для класса j. К сожалению, как обычно, прогноз не во всем совпадает с реальностью.

производится по более гибкой схеме. Заметим, что последовательность bnj является невозрастающей: bnj ¸ bnj+1. Ýòî означает, что в любой момент для более высокого класса открыты места всех вложенных в него нижних классов и, таким образом, невозможна ситуация, когда на нижнем классе доступно больше билетов, чем на более высоком.

Существует несколько способов вложения классов друг в друга, различающихся по алго- ритму изменения bnj при продаже билета в одном из классов. Наибольшее распространение получили два: стандартное вложение (standard, or serial, nesting) è вложение с заимствованием (theft nesting). Чтобы различать текущие значения пределов продаж при разных способах вложения, будем обозначать соответствующие величины через bsnj è btnj .

² Стандартное вложение.

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

Рис. 4: Изменение значения для пределов бронирования при стандартной вложенной структуре ценовых классов.

Итак, первый запрос удовлетворен, потому что исходно мы разрешили продать 5 мест в третьем классе. Это, кстати, произошло потому, что для первого класса мы ждем 2-ух, а для второго 3-ех покупателей, и оставшиеся места отдаем нижнему классу. После продажи в третьем классе остается 4 места. Поскольку мы ждем двух человек в первый класс, и из них пока что никто не пришел, а всего после продажи билета осталось 9 мест, то для второго класса остается 9 ¡ 2 = 7 ìåñò.

Следующий запрос из первого класса. Он также удовлетворен. В результате один из двух ожидаемых покупателей в первом классе уже появился, мы ждем еще одного. Всего остается 8 мест, из них для второго класса предназначено 8 ¡ 1 = 7 ìåñò.

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

И так далее, вплоть до восьмого запроса, который интересен тем, что появился покупатель, которого мы не прогнозировали. Восьмой запрос покупатель из второго класса. Там

мы ждали 3-ех человек, и этот запрос оказывается четвертым. Тем не менее, мы ему продаем билет, потому что в этот момент во втором классе остается 3 места. В первом классе уже пришли 2 покупателя, там мы никого не ждем и, следовательно, не резервируем места. То же самое и для второго класса. Поэтому, в результате продажи билета по восьмому запросу для третьего класса остается также 2 места. Отметим, что нижнему классу всегда отводится столько мест, сколько остается после верхних.

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

В общем, получается следующий алгоритм изменения значений bsnj .

При запросе на покупку билета класса j этот запрос удовлетворяется, если bsnj > 0. Соответственно, как и для невложенных классов, в результате на единицу уменьшается количество билетов, зарезервированных только äëÿ j-го класса, которое, напомним, рав-

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

кому же уменьшению всех значений bsn1 ; : : : ; bsnj потому что bpj = bsnj ¡ bsnj+1.

Åñëè æå bpj = 0, т.е. квота билетов, предназначенных для продажи только классу j, выбрана, то билет берется из числа зарезервированных для следующего по уровню доходности билетов класса j + 1. В случае, когда и они все проданы (bpj+1 = 0), то берутся билеты из резерва для класса j + 2, и так далее. Поэтому, при bpj = 0, на единицу нужно уменьшать значения вложенных пределов бронирования для всех классов, начиная с класса под номером k > j, из которого был взят билет на запрос по классу j, и кончая самым верхним

классом: b1; : : : ; bk, k > j. Отметим, что запрос на покупку билета j-го вложенного класса будет отвергнут, не тогда, когда bpj = 0, как это было для невложенных классов, а только если все bpk = 0, k = j; : : : ; N, что просто означает bsnj = 0.

² Вложение с заимствованием.

Для вложения с заимствованием ситуация несколько меняется, см. рис. 5. Первый запрос, поскольку он из нижнего класса, обрабатывается в точности так, как и для стандартного вложения. Однако второй запрос, на билет из первого ценового класса, удовлетворен за счет резерва, отведенного самому нижнему классу. Действительно, несмотря на то, что исходно мы ждали появления 2-ух покупателей первого класса, после продажи билета одному из них, мы продолжаем по-прежнему ждать в первый класс двоих. Во втором классе пока никто не пришел, мы ждем там, как и сначала, 3-ех человек, всего мест осталось уже 8, а для нижнего класса 8 ¡ 5 = 3 места.

Рис. 5: Изменение значения для пределов бронирования при вложенной структуре ценовых классов с заимствованием.

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

Таким образом, получается, что для вложения с заимствованием при каждой покупке мы всегда вычитаем единицу из âñåõ текущих значений величин btnj

Нулевые значения мы не трогаем, оставляем нулями.

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

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

Рис. 6: Пример для 8-ми вложенных классов. Стандартное вложение.

Рис. 7: Пример для 8-ми вложенных классов. Вложение с заимствованием.

Рисунки 6 и 7 иллюстрируют более сложный пример контроля продаж для 8-ми вложенных классов при стандартном вложении и вложении с заимствованием соответственно. Стартовые значения bnj подобраны таким образом, чтобы подчеркнуть особенности вложенной структуры. p

Первый запрос в примере произведен из класса j = 2, для которого b2 = 0, и поэтому при стандартном вложении билет был продан из резерва класса j = 3, ãäå bp3 = 4. В результате