ГЛАВА 3

ТРАНСПОРТНЫЕ СЕТИ

3.1.Моделирование процессов планирования воздушного движения

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

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

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

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

Необходимость рассмотрения указанной задачи как оптимизационной по критерию экономии авиатоплива подтверждается анализом эффективности использования запасных аэродромов, выбранных в соответствии с существующей технологией только по критерию безопасности. Такой анализ показывает, что, как правило, в реальных ситуациях при массовых сбоях воздушного движения из-за прекращения приема ВС на аэродроме назначения имеется возможность его перенацеливания на запасные аэродромы и, соответственно, снижения за счет этого перерасхода топлива на 25–30 % по сравнению с фактическим. В связи с этим представляется целесообразным обоснование методов и разработка алгоритмов решения задачи рационального назначения запасных аэродромов в смысле рассматриваемого показателя эффективности с целью обеспечения информацией как экипажей ВС на этапе предполетной подготовки, так и органов УВД при перенацеливании ВС на запасные аэродромы в процессе текущего планирования.

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

Задачи планирования потока на транспортных сетях

К классу потоковых задач (задач планирования потока на сетях) можно отнести следующую задачу:

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

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

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

Под моделью транспортной сети (сетью) понимается ориентированный граф, в котором выделяются две вершины: s – исток (источник) и t – сток, а дугам присвоен вес, означающий пропускную способность. Пропускную способность дуги u обозначим как (u). Пропускная способность пути, предположим, из s в t Р(s, t) равна наименьшей из пропускных способностей дуг, в него входящих:

[Р(s, t)] = min [ (u1), (u2), (u3), ...].

Интенсивность потока в сети (далее – поток) обозначим (s, t), поток в дуге –(u). На рис. 23 показан пример простой сети. Цифрами обозначена текущая интенсивность потока в дуге, а в скобках указаны пропускные способности дуг(u). Заметим, что на изображенной сети распределен поток с интенсивностью(u) = 2, причем все объекты потока перемещаются по одному пути.

Рис. 23. Пример транспортной сети

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

1) весь поток, поступающий на вход, достигает выхода сети, т. е.

(s, xi) = (xj, t) = 0,

где хj Х+(t), хi Х–(s);

2) интенсивность потока в любой дуге сети удовлетворяет соотношению:

0(u) (u);

3)для любой вершины все объекты, входящие в нее, также выходят, т. е.

(xj, хk) – (xk, хi) = 0,

где хj Х+(xk), хi Х–(xk).

Введем величину d, которая будет характеризовать возможное приращение потока. Для дуги d(u) = (u) – (u), если поток пропускаем в направлении ориентации дуги, и d = (u), если речь идет о встречном потоке (т. е. условно предполагается, что имеющийся поток величиной (u) можно уменьшить для того, чтобы пропустить во встречном направлении некоторое количество единиц потока). Для некоторого пути из s в t Р(s, t) приращение определяется как наименьшее из приращений дуг, в него входящих:

d[Р(s, t)] = min [d(u1), d(u2), d(u3) ...].

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

графа приращений.

Рассмотрим, что такое орграф приращений. Этот граф строится из исходной сети при данном значении потока в сети и обозначается как I(Н, i). Напомним, что символом Н ранее мы обозначали любой орграф, в данном случае это обозначение исходной сети; i – поток в сети на i-м цикле работы алгоритма ( i =(s, t)). Рассмотрим правила построения орграфа приращений.

1.Каждой дуге сети ставятся в соответствие две дуги орграфа приращений – сонаправленная и противонаправленная. Обозначим их w1 и w2 соответственно.

2.Каждой дуге орграфа приращений присваивается вес по следующим правилам:

–(w1) = 0, если в соответствующей дуге сети Н выполняется (u) < (u);

–(w1) = , если (u) (u);

–(w2) = 0, если (u) = 0;

–(w2) = , если (u) = 0.

Таким образом, вес дуги орграфа приращений равен нулю, если в соответствующей дуге сети можно изменить (увеличить или уменьшить) поток. На рис. 24 приведен пример орграфа приращений I(Н, 2) для сети с потоком, равным 2 (см. рис. 23). Цифрами 1 и 2 показаны номера вершин.

Рис. 24. Орграф приращений I(Н, 2) для сети, изображенной на рис. 23

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

1)i = 1, произвольно выбирается и распределяется по дугам в соответствии

стребованиями допустимости начальный поток i(s, t) (он может быть нулевым);

2)строится орграф приращений I(Н, i);

3)на I(Н, i) выбирается путь Р(s, t), длина которого равна 0. Если такого пути нет, – конец работы алгоритма и i – максимальный допустимый поток;

4)на исходной сети определяется последовательность дуг, соответствующая выбранному пути на I(Н, i) и по их приращениям находится d[Р(s, t)] по формуле, приведенной выше;

5)определяется новый поток i+1 = i + d[Р(s, t)], для каждой дуги, соответствующей пути Р(s, t). Дополнительные единицы потока распределяются по этим дугам (здесь целесообразно перерисовать сеть заново с вновь полученным потоком);

6)i = i + 1, далее следует перейти на шаг 2.

Пример. Первый цикл работы алгоритма, i = 1.

Шаг 1. Рассмотрим сеть, изображенную на рис. 25. Выберем путь, это путь Р1(s, t). Начальный поток равен 2.

Шаг 2. Строим орграф приращений I(Н, 2) (см. рис. 25).

Шаг 3. На орграфе приращений выберем путь нулевой длины Р(s, 2, t).

Шаг 4. Находим приращение d[Р(s, 2, t)] = min [5, 4] = 4.

Шаг 5. Новый поток 2 = 1 + 4 = 2 + 4 = 6. Получаем сеть с распределенным новым потоком (см. рис. 24).

Рис. 25. Сеть с полученным потоком (s, t) = 6 после первого цикла работы алгоритма

Второй цикл работы алгоритма, i = 2.

Шаг 2. Строим орграф приращений I(Н, 6) (рис. 26).

Шаг 3. На I(Н, 6) находим единственный путь нулевой длины Р(s, 2, 1, t).

Шаг 4. Находим приращение d[Р(s, 2, 1, t)] = min [1, 2, 4] = 1.

Шаг 5. Новый поток 1 = 2 + 1 = 6 + 1 = 7. Получаем сеть с распределенным новым потоком (рис. 27).