Планирование авиаперелетов - Нахождение потока в сети

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

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

Задача

Допустим, вы отвечаете за управление самолетным парком и хотите построить расписание полетов. Ниже описана очень простая модель. В ходе маркетинговых исследований были определены m рейсовых сегментов, обслуживание которых могло бы принести высокую прибыль; сегмент j определяется четырьмя параметрами: аэропортом отправления, аэропортом прибытия, временем отправления и временем прибытия. На рис. 7.17, а изображен простой пример с шестью сегментами, которые вам хотелось бы обслуживать в течение одного дня:

(1) Бостон (BOS, отправление 6:00) — Вашингтон (DCA, прибытие 7:00)

(2) Филадельфия (PHL, отправление 7:00) — Питтсбург (PIT, прибытие 8:00)

(3) Вашингтон (DCA отправление 8:00) — Лос-Анджелес (LAS, прибытие 11:00)

(4) Филадельфия (PHL, отправление 11:00) — Сан-Франциско (SFO, прибытие 14:00)

(5) Сан-Франциско (SFO, отправление 14:15) — Сиэтл (SEA, прибытие 15:15)

(6) Лас-Вегас (LAX, отправление 17:00) — Сиэтл (SEA, прибытие 18:00)

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

Чтобы один самолет мог использоваться для сегмента i, а затем позднее для сегмента j, если:

(a) аэропорт прибытия i совпадает с аэропортом отправления j, и времени между рейсами достаточно для технического обслуживания самолета; или

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

Рис. 7.17. a — простой экземпляр задачи планирования авиаперелетов; b — расширенный граф, показывающий возможности перехода между рейсами

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

Формулировка задачи

Ситуацию можно смоделировать на очень общем уровне, абстрагируясь от конкретных правил о времени технического обслуживания и промежуточных сегментов: мы просто говорим, что рейс jдоступен из рейса i, если самолет, использовавшийся для рейса i, также может использоваться для полета j. Итак, по приведенным выше правилам (а) и (b) для каждой пары ij можно легко определить, доступен ли рейс j из рейса i. (Конечно, правила доступности могут быть намного более сложными. Например, время технического обслуживания в случае (а) может зависеть от аэропорта, или случай (b) может потребовать, чтобы вставленный сегмент обеспечивал необходимую прибыль.) Здесь важно то, что наше определение позволяет обработать любой набор правил: входные данные задачи включают не только множество сегментов, но и спецификацию пар (i, j), для которых более поздний рейс j достижим из более раннего рейса i. Такие пары могут образовать произвольный ациклический граф.

В этой задаче требуется определить, возможно ли организовать все m рейсов из исходного списка с использованием не более k самолетов. Для этого необходимо найти способ эффективного повторного использования самолетов в разных рейсах. Например, вернемся к экземпляру на рис. 7.17 и предположим, что самолетный парк состоит из k = 2 самолетов. Если использовать один самолет для рейсов (1), (3) и (6), как предполагалось выше, другой самолет не сможет обслужить все остальные полеты (2), (4) и (5) (ему не хватит времени на техническое обслуживание в Сан-Франциско между рейсами (4) и (5)). Однако обслужить все шесть рейсов с двумя самолетами все же возможно, если воспользоваться другим решением: один самолет обслуживает рейсы (1), (3) и (5) (с включением промежуточного рейса LAX-SFO), а другой обслуживает рейсы (2), (4) и (6) (с включением промежуточных рейсов PIT-PHL и SFO-LAS).

Разработка алгоритма

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

Решение основано на следующей идее: единицы потока соответствуют самолетам. Для каждого рейса создается ребро, а верхняя и нижняя границы пропускной способности, равные 1, требуют, чтобы по ребру передавалась ровно одна единица потока. Другими словами, каждый рейс должен обслуживаться одним из самолетов. Если (u_i, v_i) — ребро, представляющее рейс i, а (u_j, v_j) — ребро, представляющее рейсj, и рейсj доступен из рейса i, то из v_i в u_j ведет ребро с пропускной способностью 1; при этом единица потока может переместиться по (u_i, v_i), а затем перейти прямо к (u_j, v_j). Такая конструкция ребер изображена на рис. 7.17, b.

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

♦ Для каждого рейса i граф содержит два узла u_i и v_i.

♦ G также содержит отдельный узел-источник s и узел-сток t.

Множество ребер G определяется следующим образом:

♦ Для всех i существует ребро (u_i, v_i) с нижней границей 1 и пропускной способностью 1. (Каждый рейс в списке должен обслуживаться.)

♦ Для всех i и j, для которых рейс j доступен от рейса i, существует ребро (v_i, u_j) c нижней границей 0 и пропускной способностью 1. (Один самолет может выполнять рейсы i и j.)

♦ Для всех i существует ребро (s, u_i) с нижней границей 0 и пропускной способностью 1. (Любой самолет может начать день с полета i.)

♦ Для всех j существует ребро (v_j, t) с нижней границей 0 и пропускной способностью 1. (Любой самолет может завершить день полетом j.)

♦ Существует ребро (s, t) с нижней границей 0 и пропускной способностью k. (Если имеются дополнительные самолеты, не обязательно использовать их в полетах.)

Наконец, узел s имеет уровень потребления -k, а узел t — уровень потребления k. У всех остальных узлов уровень потребления равен 0.

Наш алгоритм основан на построении сети G и поиска в ней действительной циркуляции. Докажем правильность этого алгоритма.

Анализ алгоритма

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

Доказательство. Сначала предположим, что все рейсы могут быть выполнены с использованием k' ≤ k самолетов.

Множество рейсов, выполняемых каждым отдельным самолетом, определяет путь P в сети G; по каждому такому пути P передается одна единица потока. Чтобы удовлетворить полные требования S и t, мы отправляем по ребру (s, t) k - k' единиц потока. Полученная циркуляция удовлетворяет все ограничения по уровню потребления, пропускной способности и нижним границам.

И наоборот, рассмотрим действительную циркуляцию в сети G. Из (7.52) мы знаем, что в сети существует действительная циркуляция с целочисленными величинами потока. Предположим, что k' единиц потока передаются по ребрам, отличным от (s, t). Так как у каждого ребра пропускная способность ограничена значением 1, а циркуляция является целочисленной, каждое ребро, передающее поток, несет ровно одну единицу потока.

Преобразуем результат в расписание по схеме, похожей на приведенную в доказательстве (7.42), где поток преобразовывался в множество пар. На самом деле в данном случае ситуация проще, потому что граф не содержит циклов. Рассмотрим ребро (s, u_i), по которому передается одна единица потока. Из ограничения сохранения потока следует, что (u_i, v_i) передает одну единицу потока, и из v выходит единственное ребро, несущее одну единицу потока. Продолжая таким образом, мы строим путь P от s к t, в котором каждое ребро передает одну единицу потока. Процесс применяется к каждому ребру в форме (s, u_j), передающему одну единицу потока; таким образом будут получены k' путей от s к t, каждый из которых состоит из ребер, передающих одну единицу потока. С каждым путем P, построенным по этой схеме, связывается один самолет, который может выполнять все рейсы этого пути. ■

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

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

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