Математическая модель восстановления маршрутов пассажиров после сбойной ситуации в расписании авиакомпании

В работе любой сложной системы могут возникать сбойные ситуации. Не является исключением и авиационный транспорт. Погодные условия, неисправность техники, перегруженность аэропортов — всё это может привести к задержкам и отменам рейсов. В свою очередь, сбойные ситуации приводят к дополнительным расходам на питание и размещение пассажиров в гостиницах, а также к снижению лояльности клиентов [1]. Поэтому авиакомпании стремятся минимизировать потери от сбойных ситуаций и не допускать их распространения.

В широком смысле под сбойной ситуацией будем понимать невозможность выполнения одного или нескольких рейсов по расписанию без внесения управляющего воздействия. Управление такими ситуациями ведётся в центре управления полётами авиакомпании (ЦУП). Диспетчеры стремятся минимизировать влияние на расписание, подбирая меры реагирования под конкретные обстоятельства с учетом эксплуатационных ограничений и доступности ресурсов. В качестве методов восстановления движения используются: размен воздушных судов и экипажей, назначение дополнительных рейсов, задержка рейса [2].

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

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

Особую актуальность задача перераспределения пассажиров имеет для авиакомпаний с хабовой структурой маршрутной сети (hub-and-spoke). В ней определяется ряд ключевых аэропортов (хабов), все рейсы выполняются между хабами и регионами либо между хабами [3]. Для такого типа маршрутной сети характерна высокая доля трансфера в хабах — значительная часть пассажиров делает пересадку в них и летит дальше. В случае сбойной ситуации стыковки пассажиров срываются, и требуется определить новые рейсы для доставки пассажиров. При этом маршруты доставки могут отличаться от изначальных маршрутов пассажиров: более оптимальным может быть вариант пролета через другой хаб. Такую структуру маршрутной сети имеет значительная часть крупных авиакомпаний в России.

Исследованию методов разрешения сбойных ситуаций посвящено множество публикаций. Их обзор приведен в работах [4,5]. Рассмотрим подробнее работы, в которых рассматривается перемещение пассажиров в конечный пункт назначения. В [6] предложена комбинированная модель разрешения сбойной ситуации с учетом ограничений по воздушным судам и экипажам, в которой также учитывается возможность перераспределения пассажиров на другие рейсы. В [7] используется тот же подход к пересадке пассажиров. Важным ограничением этой модели является то, что пересадка возможна только на рейсы, которые следуют непосредственно в аэропорт назначения пассажира, возможность построения новых альтернативных маршрутов отсутствует. Авторы [8] расширили модель, добавив возможность возврата билетов. Работа [9] единственная среди прочих, которая полностью посвящена работе с пассажирами, восстановление движения воздушных судов и экипажей в ней не рассматривается. Авторы используют превентивный подход к изменению маршрутов пассажиров при возникновении неопределенных задержек на пути следования. На первом этапе, как только становится известно о задержке рейса, пассажирам заранее назначаются новые маршруты. На втором этапе дополнительно изменяются маршруты для пассажиров, которые пропустили стыковки после того, как произошла задержка. В [10] разработана комплексная модель, которая учитывает вероятность неявки пассажира на посадку после перебронирования. Авторы принимают во внимание, что пассажир может получить денежную компенсацию от авиакомпании и купить новый билет на рейс другого перевозчика. Их пассажирская модель имеет сходство с работой [7], но дополнена факторами поведенческой экономики, что позволяет более точно прогнозировать реальное поведение пассажиров в условиях сбойной ситуации. В [11] был предложен эвристический алгоритм, допускающий возможность создания hobbix маршрутов для транспортировки пассажиров через альтернативный хаб.

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

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

2.    Постановка задачи

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

• 1)    Оперативное расписание авиакомпании — множество рейсов E fn _g ht данной авиакомпании за рассматриваемый период времени. Оно содержит сведения о каждом рейсе с учетом изменений (i,j) G E fUgh _t. Здесь и далее, если для обозначения рейса используется двойной индекс, то он обозначает место и время вылета (i) и прибытия (j) рейса соответственно. Для рейса известны:

• •    уникальный номер;

• •    аэропорты вылета и прилета;

• •    ETD ij ,ETA {j — estimated time of departure, arrival — ожидаемые времена отправления и прибытия, с учетом задержек на момент расчета;

• •    dij — количество свободных мест на рейсе.

• 2)    Информация о пассажирах, у которых нарушилась стыковка. Для каждого пассажира известны:

• •    плановый маршрут движения пассажира — набор рейсов, по которым был запланирован перелет;

• •    время и место нарушения запланированного маршрута;

• •    конечный пункт назначения;

• •    ST A — scheduled time of arrival — плановое время прибытия в пункт назначения.

• 3)    Минимальное время стыковки (minimum connection time, МСТ) — минимальный интервал времени, необходимый для обеспечения физической возможности пересадки между рейсами в аэропорту. В рамках эксперимента принимается равным 40 минутам.

• 4)    Максимальное время стыковки — максимальный интервал времени, в течение которого пассажир может ожидать следующий рейс. В рамках эксперимента принимается равным 24 часам.

• 5)    Максимальное время на доставку пассажира — интервал времени, в течение которого пассажира необходимо доставить в пункт назначения. Если это сделать не удается, то пассажиру возвращается стоимость билета.

2.1.    Оценка стоимости задержки

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

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

Расчет затрат авиакомпании на сбойные ситуации подробно рассматривается в работе [1]. Традиционно расходы авиакомпании на сбойные ситуации можно разделить на прямые и косвенные.

С   ^С direct + ^С indirect •

Прямые расходы C di _rect компания несет, когда согласно действующему законодательству при задержке рейса она обязана предоставить питание или проживание в зависимости от длительности ожидания. Также пассажир имеет право на компенсацию, размер которой линейно зависит от длительности задержки в часах [12]. Косвенные или репутационные расходы C_in d _irect ~ это потенциальные потери будущих доходов в результате неудобств, причиненных пассажиру, которые, возможно, заставят его в будущем выбрать другую авиакомпанию. Эти затраты оцениваются приблизительно и могут различаться в зависимости от класса перевозки пассажира или его статуса в программе лояльности авиакомпании. В случае если пассажира доставить невозможно в пункт назначения, то ему будет выполнен возврат средств. Соответственно, выручка авиакомпании снизится и, возможно, прибыль будет недополучена. С точки зрения авиакомпании будем описывать такую ситуацию фиксированным штрафом за возврат билета.

Альтернативный вариант оценки затрат на сбойные ситуации, который в дальнейшем применяется в данной статье, — минимизация суммарного количества минут задержки пассажиров. При таком подходе для каждого пассажира рассчитывается величина опоздания в пункт назначения как разность между плановым временем прилета ( ST А) и ожидаемым, после пересадки на другой рейс ( ЕТД, затем складываются полученные опоздания для N пассажиров, затронутых сбойной ситуацией и доставленных в пункт назначения с опозданием. Если же М пассажиров доставить не удалось, то это учитывается в виде штрафа за возврат c_cancei, выраженном в единицах времени.

N+МN

С = Е c. = ZETA, - ST Д') + М • ccancel.(2)

i=1

3.    Представление расписания и сбойной ситуации в виде графа

Одним из способов отображения расписания является представление его в виде ориентированного графа G = (V, Е ). Такой подход используется, например, в [9]. Приведем алгоритм построения графа расписания и добавления в него элементов сбойной ситуации.

• 1)    Построение рейсовых рёбер Е^м С Е:

Каждый рейс расписания описывается двумя узлами. Каждый узел характеризует время и место отправления и прибытия соответственно. Узел однозначно определяется парой значений: аэропорт и метка времени, например «DME, 04.04.2025 20:15». От узла-отправления к узлу-прибытию проводится направленное ребро, которое будем называть рейсовым. Оно изображено на рис. 1.

DME 21:20   ----3033---► UUD 3:20

Рейс 3033, из DME (Домодедово) в UUD (Улан-Удэ), вылет 21:20, прилет 3:20

Рис. 1. Отображение рейса на графе

• 2)    Построение пересадочных рёбер E_correct С Е:

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

Рис. 2. Отображение пересадок на графе

• 3)    Инициализация узлов-источников V_source С V:

Для каждого случая сорванной стыковки создается отдельный узел-источник, содержащий следующие атрибуты:

• •    фактическое время прибытия пассажиров в аэропорт пересадки;

• •    код аэропорта пересадки;

• •    количество пассажиров.

• 4)    Инициализация узлов-стоков V f _arge t С V:

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

• 5)    Построение стартовых рёбер E_start С Е:

Для каждого узла-источника создаются стартовые рёбра к узлам расписания (начальным точкам рейсов), если выполняются условия:

• •    аэропорт отправления рейса совпадает с аэропортом пересадки;

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

• •    из соответствующего узла расписания исходит хотя бы одно рейсовое ребро.

Пример соединения узла-источника с рейсовыми ребрами с помощью стартовых ребер приведен на рис. 3.

Рис. 3. Отображение узла-источника и стартовых ребер на графе. Пассажиры с сорванными пересадками пересаживаются на два рейса

• 6)    Построение финальных рёбер E fi _na i С Е:

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

Рис. 4. Отображение узла-стока и финальных ребер на графе

Пример соединения узла-стока с рейсовыми ребрами с помощью финальных ребер приведен на рис. 4.

• 7)    Добавление возвратных рёбер E_cancei С Е:

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

Рис. 5. Граф расписания и сбойной ситуации

Таким образом, множество ребер графа Е состоит из рейсовых, пересадочных, старто- bbix, финалвнв1х и возвратнв1х ребер.

^Е — ^Е flight U ^E connect ^{U E} start ^{U Е} final ^{U E} cancel .

Аналогично, V — объединение всех типов вершин.

^ — ^V airport,time ^{U V}source ^{U V} sink ^.

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

4.    Алгоритм доставки пассажиров в пункты назначения

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

Рис. 6. Схема двухшагового алгоритма доставки пассажиров

4.1.    Шаг 1. Распределение пассажиров по рейсам

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

Многопродуктовая задача обобщает классическую однопродуктовую транспортную задачу. В ней рассматривается перевозка разного вида продуктов, причем ограничения на пропускные способности ребер определяются для всех продуктов [13]. Для решения задачи предложены различные методы, обзор которых приведен в [14]. Для решения задачи о распределении пассажиров по рейсам остановимся на рассмотрении многопродуктовой задачи в виде задачи целочисленного линейного программирования.

Введем обозначения:

• •    К — множество групп пассажиров;

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

ребер вычисляется как разность между временем прибытия последнего рейса нового маршрута (ET Ар) и плановым временем прибытия данной группы пассажиров (ST AkY ск = ETAjj - STAk V(i, j) G Efinai Ук G К.                (5)

Для возвратных ребер стоимость принимается равной фиксированному штрафу за возврат билета.

^Cij = ^C cancel ^{У (}А З ) ^{G E} cancel ^{Ук G К},                        (6)

• *    Xp ~ ^тшсл° пассажиров группы к G К. которые будут п<провезены рейсом (i,j):

• •    s^k — число пассажиров группы к G К, перемещение которых начинается или заканчивается в узле i:

Целевая функция — суммарное время задержки всех пассажиров с сорванными стыковками:

min ^ ^ Ck Xkj.( кеК (i,j)EE

Ограничения на сохранение потока пассажиров в узлах:

^ хк - ^Xji = sk Vi GV Ук G К.(S)

jj

Ограничения на пропускную способность ребер:

Для каждого рейсового ребра (i,j) G E fi _ig h _t сумма посаженных на рейс пассажиров из разных групп не превосходит количества свободных мест.

^х^

кек

Ограничения неотрицательности и целочисленности потока:

хк > 0 Ук GК V(i,j) GE,(10)

хк g Z Ук GК V(i,j) GE.(11)

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

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

Q_Var = |E|•|К |.                                      (12)

Число ограничений можно получить как сумму количества рейсов и произведения числа вершин в графе и количества групп пассажиров.

Qc^nstr = |V | • |К | + IE flight I.                                   (13)

Характерные значения размерностей приведены в табл. 9.

4.2.    Шаг 2. Построение маршрутов пассажиров

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

От потока как оптимального размера перевозки по каждому ребру нам нужно перейти к потоку как пути или линейной комбинации путей от источника к стоку. Такой переход всегда возможен [15, с. 18-20], опишем его. Для каждой группы пассажиров выполняются следующие действия:

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

• 2)    Определяются источники и стоки в подграфе;

• 3)    Для каждой пары источник-сток выполняется поиск всех возможных простых путей (проходящих через каждую вершину не более одного раза);

• 1.    Для каждого найденного пути вычисляется минимальная пропускная способность среди всех составляющих его рёбер. Она определяет максимально возможный объём перевозки по данному пути;

• 2.    Если минимальная пропускная способность пути положительна, то этот путь добавляется в ответ, и уменьшается пропускная способность всех рёбер на этом пути на величину сформированного потока;

• 3.    Выполняется переход к следующему простому пути данной пары источник-сток;

• 4)    Выполняется переход к следующей паре источник-сток.

• 5.    Вычислительные примеры

5.1.    Сценарий 1

в различных сценариях сбойных ситуаций

Рассмотрим пример расчета новых маршрутов для пассажиров. Пусть задерживаются на прилет два рейса в Москву и один в Новосибирск. Из-за этого срываются стыковки у нескольких пассажиров, следующих в разные города — Улан-Удэ и Новосибирск. Данные о них см. в табл. 1.

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

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

Рис. 7. Граф сбойной ситуации

Таблица!

Группы пассажиров с сорванной стыковкой

Аэропорт срыва стыковки	Аэропорт назначения	Время прибытия в аэропорт срыва	Количество пассажиров в группе	Плановый рейс	Плановое время прибытия
Москва (DME)	Улан-Удэ (UUD)	20:40	10	3031	1:20
Москва (DME)	Улан-Удэ (UUD)	22:40	5	3033	3:20
Новосибирск (OVB)	Улан-Удэ (UUD)	8:40	5	5253	5:20
Москва (DME)	Новосибирск (OVB)	22:40	1	2511	1:15

Т а б л и ц а 2

Расписание рейсов

Номер рейса	Аэропорт вылета	Аэропорт прилета	Время вылета, ETD	Время прилета, ЕТА	Число свободных мест
2511	Домодедово (DME)	Новосибирск (OVB)	21:15	1:15	2
3033	Домодедово (DME)	Улан-Удэ (UUD)	21:20	3:20	7
3017	Домодедово (DME)	Иркутск (IKT)	21:30	2:30	5
2513	Домодедово (DME)	Новосибирск (OVB)	23:25	3:30	12
5253	Новосибирск (OVB)	Улан-Удэ (UUD)	2:15	5:20	10
5255	Новосибирск (OVB)	Улан-Удэ (UUD)	9:30	11:35	7
6375	Иркутск (IKT)	Улан-Удэ (UUD)	9:40	10:40	2

Т а б л и ц а 3

Стоимость пролета пассажиров

		Новый рейс	2513	3033	5253	5255	6375
Группа, к	Плановый рейс	Плановое / расчетное время прибытия	3:30	3:20	5:20	11:35	10:40
1	3031	1:20	—	120	240	605	560
2	3033	3:20	—	0	—	495	440
3	5253	5:20	—	—	0	375	320
4	2511	1:15	135	—	—	—	—

Т а б л и ц а 4

Распределение пассажиров по рейсам

Группа, к	Плановый / новый рейс	2511	3033	3017	2513	5253	5255	6375
1	3031	2	7	1	0	2	0	1
2	3033	0	0	0	5	0	5	0
3	5253	0	0	0	0	0	5	0
4	2511	0	0	0	1	0	0	0

Т а б л и ц а 5

Маршруты пересаженных пассажиров

Плановый рейс	Аэропорт назначения	Рейсы, на которые пассажиры пересажены	Количество пассажиров, перевезенных этим маршрутом	Время задержки пассажира по прибытию, в минутах
3031	Улан-Удэ (UUD)	3033	7	120
3031	Улан-Удэ (UUD)	2511, 5253	2	240
3031	Улан-Удэ (UUD)	3017, 6375	1	560
3033	Улан-Удэ (UUD)	2513, 5255	5	495
5253	Улан-Удэ (UUD)	5255	5	375
2511	Новосибирск (OVB)	2513	1	135

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

Т а б л и ц а б

Группы пассажиров с сорванной стыковкой в Сценариях 2, 3

Плановый рейс	Аэропорт срыва	Аэропорт назначения	Время прибытия	Кол-во пассажиров	Плановое время
1011	DME	LED	11:20	10	11:15
1229	DME	ммк	13:00	5	14:15
2141	DME	VOG	9:30	6	7:30
1135	DME	UFA	13:00	2	10:35
2043	DME	AER	10:00	9	10:10
2167	DME	MRV	14:00	7	13:40
2517, 5219	DME	GDX	8:00	12	21:45
5104, 5223	AER	HTA	10:40	4	23:40
5065	OVB	KGD	13:30	3	13:10

Выполним первый шаг алгоритма доставки пассажиров, решив задачу минимизации стоимости потока. Для каждого рейса определим х¹^ - число пассажиров каждой группы, пересаженных на него. Модель реализована на языке Python 3.11 с использованием библиотеки pulp. Полученный с помощью модели план перевозки представлен в табл. 4.

Затем построим маршруты для каждой группы пассажиров. То есть на основе распределения по рейсам для каждого пассажира определим набор рейсов, который приводит в пункт назначения. Решение указано в табл. 5. Часть опоздавших пассажиров на прямой рейс по маршруту Москва — Улан-Удэ была пересажена на следующий прямой в тот же день, остальные направлены с пересадкой через Новосибирск и Иркутск.

Т а б л и ц а 7

Маршруты пересаженных пассажиров в Сценарии 2

Плановый рейс	Аэропорт назначения	Рейсы, на которые пассажиры пересажены	Количестве пассажиров, перевезенных этим маршрутом	Время задержки пассажира по прибытию, в минутах
1011	Санкт-Петербург (LED)	1013	10	132
1229	Мурманск (ММК)	1227	2	590
1229	Мурманск (ММК)	возврат билета	3	-
2141	Волгоград (VOG)	2143	6	299
1135	Уфа (UFA)	1137	2	382
2043	Сочи (AER.)	2045	2	270
2043	Сочи (AER)	2047	2	342
2043	Сочи (AER)	2051	4	375
2043	Сочи (AER)	2053	1	400
2167	Минеральные Воды (MRV)	возврат билета	7	-
2517, 5219	Магадан (GDX)	2505, 5219	10	0
2517, 5219	Магадан (GDX)	3021, 6333	2	10
5104, 5223	Чита (НТА)	2044, 3045	2	10
5104, 5223	Чита (НТА)	2046, 3047	2	115
5065	Калининград (KGD)	возврат билета	3	-

5.2.    Сценарии 2, 3

Помимо иллюстративного примера выше в сценарии 1, были рассмотрены другие сбой-нвш ситуации различных характерных масштабов. В них число сбойных рейсов увеличено до девяти, а время на доставку пассажиров принимается равным 24 часам (Сценарий 2) и 72 часам (Сценарий 3).

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

Результаты расчета новых маршрутов пассажиров для Сценариев 2 и 3 приведены в табл. 7, 8. В них следует отметить несколько особенностей:

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

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

• •    При большем времени на доставку пассажиров больше пассажиров удается доставить в пункты назначения.

Т а б л и ц а 8

Маршруты пересаженных пассажиров в Сценарии 3

Плановый рейс	Аэропорт назначения	Рейсы, на которые пассажиры пересажены	Количестве пассажиров, перевезенных этим маршрутом	Время задержки пассажира по прибытию, в минутах
1011	Санкт-Петербург (LED)	1013	10	132
1229	Мурманск (ММК)	1227	2	590
1229	Мурманск (ММК)	1229 (+1 день)	3	1440
2141	Волгоград (VOG)	2143	6	299
1135	Уфа (UFA)	1137	2	382
2043	Сочи (AER)	2045	2	270
2043	Сочи (AER)	2047	2	342
2043	Сочи (AER)	2051	4	375
2043	Сочи (AER)	2053	1	400
2167	Минеральные воды (MRV)	2169 (+1 день)	7	1070
2517, 5219	Магадан (GDX)	2505, 5219	10	0
2517, 5219	Магадан (GDX)	3021, 6333	2	10
5104, 5223	Чита (НТА)	2044, 3045	2	0
5104, 5223	Чита (НТА)	2046, 3047	2	115
5065	Калининград (KGD)	возврат билета	3	-

Т а б л и ц а 9

Сравнительные характеристики сценариев

	Сценарий 1	Сценарий 2	Сценарий 3
Число сбойных рейсов	4	9	9
Максимальное время на доставку пассажира, ч	24	24	72
Размер графа
Число вершин	785	793	2218
Число рёбер	7110	7281	37276
в т.ч. рейсовых	407	407	1230
в т.ч. трансферных	6559	6559	35486
в т.ч. стартовых	38	246	377
в т.ч. финальных	102	60	174
в т.ч. возвратных	4	9	9
Оптимизация
Общее число ограничений	3547	7544	21192
Общее число переменных	28440	65529	335484
Степень разреженности матрицы	1,19 · 10-4	5,5 · 10-5	1,09 · 10-5
Время расчета, с	3,01	3,16	18,4

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

6.    Заключение

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

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

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

Исследование выполнено за счет гранта Российского научного фонда (проект № 21-71-30005-П),