Н. А. Зенкова - РАССТАНОВКА ПАРКА ВОЗДУШНЫХ СУДОВ С УЧЕТОМ ДАННЫХ СИСТЕМЫ УПРАВЛЕНИЯ ДОХОДАМИ

РАССТАНОВКА ПАРКА ВОЗДУШНЫХ СУДОВ С УЧЕТОМ ДАННЫХ СИСТЕМЫ УПРАВЛЕНИЯ ДОХОДАМИ

КАК ОБОБЩЕНИЕ ЗАДАЧИ ЗАМКНУТОЙ ПЕРЕСТАНОВКИ

Автор: Н. А. Зенкова

Рассмотрены подходы к взаимодействию между управлением доходами и задачей расстановки парка судов. Первый подход, называемый «замкнутая перестановка», харак-теризуется минимальным влиянием на незадействованные рейсы, второй — предполагает принципиально новую формулировку задачи расстановки парка. Каждый подход имеет ряд преимуществ, которые рассматриваются в статье.

Ключевые слова: замкнутая перестановка, ODFAM, управление доходами, расста-новка парка ВС.

FLEET ASSIGNMENT BASED ON REVENUE MANAGEMENT SYSTEM AS A SOLUTION

OF CLOSE-IN REFLEETING PROBLEM

Two approaches of coordination between the fleet assignment problem solution and revenue management effects are presented. The first approach decsribed a close- in refleeting is character-ized by a minimum impact on the unused flights, the second approach is a radically new formula-tion of the Fleet Assignment Model. Each approach has several advantages that are discussed in the article.

Keywords: close-in refleeting, ODFAM, revenue management, fleet assignment.

В настоящее время процессы управления ресурсами авиакомпании стремятся к пол-ной автоматизации, задачи управления весьма многовариантны и включают большое число естественных и политических ограничений, ручными средствами невозможно провести полноценный анализ всей системы. В 1989 г. впервые была опубликована статья, описы-вающая формулировку оптимизационной задачи Fleet Assignment Model (FAM) [2], в даль-нейшем были автоматизированы процессы расстановки экипажей, управления доходами, а также процессы технического обслуживания. Активно развивается исследование влияния этих процессов друг на друга и способы их взаимодействия [1; 3].

Рассмотрим влияние эффектов управления доходами на задачу FAM, один из наибо-лее экономически значимых процессов.

Одним из первых примеров подобного взаимодействия может служить представлен–ная Крайгом Хопперстадом (Craig Hopperstad) и Мэтью Берджем (Мэтью Birge) (1993 г.) модель замкнутой перестановки (Demand Driven Dispatch). Ими было предложено прово–дить перерасчет задачи оптимальной расстановки судов за 14–30 дней до вылета рейса и использовать для более точного прогнозирования данные о текущем бронировании и ста–тистику отказов и неявок (no–show). Важно отметить, что несовершенство методик прогно–зирования и большое число внешних факторов , влияющих на спрос (таких как экономиче–ский кризис, политические отношения стран и др.), приводят к значительной погрешности прогноза, сделанного в начале сезона, тогда как предложенный подход дает принципиально лучшее качество прогнозируемых данных. Решение по замене типов ВС (воздушное судно) для более полного соответствия текущему прогнозируемому спросу в данной модели про–исходит на более низком уровне; рассматриваются некоторые цепочки рейсов, а не все рас–писание. В данном случае цепочка рейсов — это последовательность рейсов, которые

Расстановка парка воздушных судов с учетом данных системы управления доходами…

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

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

Рассмотрим математическую формулировку технических условий замены: Δti ^A — оборотное время (A — аэропорт, i — тип самолета); t_i ^d — время отлета i рейса; t_i ^a — время прилета i рейса; DopTime— максимальное время задержки самолета в аэропорту.

t_i^A ≤ t ^d_j₂	Δ t_i^a₁ ≤ DopTime	Δ t _j^A ≤ t_i^d₂	Δ t ^a_j₁ ≤ DopTime
Δ t_i^c ≤ t ^d_j₄	Δ t_i^a₃ ≤ DopTime	Δ t ^c_j ≤ t_i^d₄	Δ t_i^a₃ ≤ DopTime
t ^d_j₃ Δ t ^a_j₂ ≥ Δ t_i^D		t_i^d₃ Δ t_i^a₂ ≥ Δ t ^B_j

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

Основные подходы к замкнутой перестановке типов ВС [4; 5]:

Первый подход базируется на уже существующей расстановке типов ВС (например, основанной на решении задачи FAM), для которой оцениваются возможности замены ком–поновки (емкости). Такой подход особенно характерен для авиакомпаний, использующих стратегию сети “hub and spoke”, когда самолеты обычно выполняют парный цикл (рейс ту–да—обратно). Если два таких цикла выполняются почти одновременно и полеты занимают приблизительно равное время, то типы ВС, назначенные на эти парные рейсы, потенци–ально могут быть переставлены. Преимущество такого подхода состоит в сохранении ис–ходного решения задачи FAM и, следовательно, в низкой вероятности нарушения требова–ний обслуживания.

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

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

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

Любой из рассмотренных подходов к замкнутой перестановке предполагает ряд до–пущений, однако основные сложности на практике вызывают следующие предположения:

- в замене должны участвовать не более двух типов ВС;

- один рейс не может принимать участие в нескольких заменах одновременно.

В период с 1996 по 2002 годы американские ученые создают модель ODFAM (Origin-Destination Fleet Assignment Model) [2], позволяющую учесть все эффекты управления до-ходами при решении задачи расстановки парка воздушных судов. Таким образом, ODFAM явилась обобщением задачи замкнутой перестановки, она позволяет оперировать всеми доступными типами ВС и учитывать дифференциацию продуктов авиакомпании (продукт характеризуется уровнем цены и направление перелета).

ODFAM отличается от классической задачи FAM:

как точка приложения спроса рассматривается направленный рынок. Направлен–ный рынок определяется парой городов. Любая пара городов в расписании авиакомпании может служить рынком при условии, что из первого города можно долететь во второй рей–сами этой авиакомпании, пусть и не прямым перелетом;

— рейс рассматривается на уровне продуктов;

результатом является не только расстановка ВС по рейсам, но и определение оп–тимального числа пассажиров для каждого продукта;

модель максимизирует общую прибыль при учете продажи разных продуктов. Рассмотрим математическую формулировку задачи.

Оптимизационная задача состоит в том, чтобы при заданных величинах прогноза

спроса и цен на билеты получить максимальную прибыль от продажи билетов. Множества:

A — множество аэропортов (индекс a); L — множество всех рейсов (индекс l);

P — множество всех продуктов (индекс p); F — множество типов самолетов (индекс f);

T — множество моментов времени отправления и прибытия рейсов расписания (ин-декс t);

CL(f) — множество рейсов, пересекающих «нулевую линию»;

I(f, a, t) — множество прибывающих рейсов в аэропорт a в момент времени t на само-лете типа f;

Расстановка парка воздушных судов с учетом данных системы управления доходами…

O(f, a, t) — множество вылетающих рейсов из аэропорта a в момент времени t на са-молете типа f;

Параметры задачи:

rev_p — доход от продажи билета пассажиру на продукт p ∈ P ;

N _f	— количество имеющихся в распоряжении самолетов типа f ∈ F;
Cap _f — вместимость ВС, назначенного на рейс f ∈F ;
^C f ,i	— затраты на полет по рейсу i ∈ L самолета типа f ∈ F ;
D_p	— спрос на продукт p ∈P ;
Неизвестные:
^xf ,i	1,	если самолет f ∈ F назначен на рейс i ∈L;
	=	если самолет f ∈ F назначен на рейс i ∈L,
	0,

^y f ,a,t + — количество самолетов типа f ∈ F в аэропорту a ∈ A непосредственно после момента времени t ∈T ;

y _f _,a,t _- — количество самолетов типа f ∈ F в аэропорту a ∈ A непосредственно до момента времени t ∈T ;

alloc_p — количество билетов, отведенных продукту p ∈ P .

Функция цели:

∑ p ∈P ^rev p ^— ^alloc p ^* ∑ f ∈F ∑i ∈L ^C f , i ^xf ,i ^> ^{max .}

(1)

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

Необходимо найти x_f,i, alloc_p, при которых функция цели (1) будет максимальна, с уче–том ограничений (2)—(8).

Условие покрытия:

∑ _f _∈_F x_f _,i =1 при этом ∀_i ∈L.

(2)

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

Условие баланса:

^y f , a , t – ⁺ ∑ i ∈I ( f , a , t ) ^x f , i ^— ^y f , a , t + ^— ∑i ∈o ( f , a , t ) ^x f ,i ⁼ ^0, ^при ^∀^f ^, ^a ^, ^t^.

(3)

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

Использовать можно не больше, чем имеешь:

∑ a ∈ A ^y f , a , o – ⁺∑i ∈CL ( f ) ^x f ,i ^≤ ^N f ^, ^при ^f ^∈^F^.

(4)

СОВРЕМЕННЫЕ ТЕХНОЛОГИИ

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

Условие ограниченной вместимости:

∑ p ∈i ^aiioc p ^≤ ∑ f ∈F ^Cap f ^xf ,i ^.

(5)

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

Продавать можешь не больше, чем имеешь:

0 ≤ alloc_p ≤ D_p .

(6)

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

Дополнительные ограничения:

x _f _,_i ∈{0,1}, при ∀f ∈ F, ∀i ∈ L ;	(7)
y _f _,_a_,_t ≥ 0, при ∀f , a, t .	(8)

Поставленная задача является задачей смешанного программирования. Исходными данными для нее являются:

полетное расписание;
имеющийся в наличии авиационный парк f ∈ F (тип самолетов, Cap_p, N_f);
удельные затраты авиакомпании на полеты по каждому рейсу для каждого типа самолета;
цена билета rev_p для каждого продукта;
данные по спросу на все продукты D_p.

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

СПИСОК ЛИТЕРАТУРЫ

1. Виноградов Л. В., Фридман Г. М., Шебалов С. М. Математическое моделирование в оптимиза–ции планирования авиационных перевозок: формулировки и методы решения типовых задач // Научный вестник МГТУГА. 2008. С. 49–57.

2. Зенкова Н. А., Носова Е. В., Фридман Г. М. Оперативная расстановка парка воздушных судов по рейсам, связанная с изменениями данных по спросу // Экономическая кибернетика: Сб. науч. тр. 2009.

Вып. 19. С. 165–168.

3. Barnhart C., Belobaba P. and Odoni R. Application operation research in the air transport industry // Transportation Science. 2003. Vol. 37. № 4. P. 368–391.

О влиянии необязательных рейсов на расстановку парка воздушных судов…

4. Shebalov S. In Unison // Ascenda. 2010. № 1. P. 17–19.

5. Smith B. C. Robust Airline Fleet Assignment. Ph.D. thesis. Georgia Institute of Technology, U.S.A.,

REFERENSES

1. Vinogradov L. V., Fridman G. M., Shebalov S. M. Matematicheskoe modelirovanie v optimizacii planirovanija aviacionnyh perevozok: formulirovki i metody reshenija tipovyh zadach // Nauchnyj Vestnik MGTUGA. 2008. S. 49–57.

2. Zenkova N. A., Nosova E. V., Fridman G. M. Operativnaja rasstanovka parka vozdushnyh sudov po rejsam, svjazannaja s izmenenijami dannyh po sprosu. // Ekonomicheskaja kibernetika: Sb. nauch. tr. 2009. Vyp. 19. S. 165–168.

Barnhart C., Belobaba P., and Odoni R. Application operation research in the air transport industry // Transportation Science. 2003. Vol. 37. № 4. P. 368–391.

4. Shebalov S. In Unison // Ascenda. 2010. № 1. P. 17–19.

Smith B. C. Robust Airline Fleet Assignment. Ph.D. thesis. Georgia Institute of Technology, U.S.A.,