УДК 656.7.052:004.4

Алгоритм очередности заходов на посадку

 

 В.Г.Бобряков

 

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

 

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

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

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

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

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

          Такой принцип построения алгоритмов позволяет:

·       Легко перейти к ручному управлению при отказе техники;

·       Осуществлять наращивание алгоритмов с целью дальнейшей автоматизации функций диспетчера;

·       Достаточно просто осуществить сопряжение с существующей технологией УВД.

В общем случае алгоритмы оперативного планирования должны решать две задачи:

1.    Определение оптимальной, с точки зрения экономии, прямых эксплуатационных расходов очередности захода на посадку;

2.    Расчет программных траекторий, обеспечивающих прибытие на ВПП в расчетное время.

В данной статье приведены алгоритмы для решения 1-й задачи оперативного планирования применительно к стандартным траекториям маневрирования при заходе на посадку.

Задача планирования движения воздушных судов при заходе на посадку не нова. Наиболее распространёнными на практике в настоящий момент являются эвристические методы интуитивного характера, приводящие к выбору по правилу: первый пришел в зону – первый обслуживается; либо по приоритету в зависимости от класса воздушных судов. Для получения оптимальных решений предлагаются различные методы, например, метод ветвей и границ, метод двойного ранжирования. Однако эти алгоритмы весьма сложны, что обусловлено большим количеством ограничений, связанных с различной длиной траекторий, разными типами самолетов, условиями обеспечения пространственно-временного разделения и т.д.

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

Упростить решение этой задачи позволит использование траекторий с заранее заданной структурой, что дает возможность исключить точки пересечения в пространстве и стандартизовать скоростные режимы снижения разнотипных самолетов. При этом задача назначения времен посадок формулируется следующим образом: пусть в зоне подхода находится N самолетов. Каждому самолету отнесена некоторая функция стоимости Ci(tki) ( где tki – время посадки i-го самолета), определенная на интервале [tmini,tmaxi]. Требуется определить вектор ={tki}, iϵN, минимизирующий критерий стоимости:

 (1.1)

С учетом обеспечения интервалов безопасности в ТВПП

|tki-tkj|≥∆;   ij;    i,jϵN. (1.2)

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

·       Значения tномiопределяют оптимальную последовательность посадок; ( здесь tномi– номинальное время посадки: tномi= tci+ Tномi),

·       Для Ht = tki- tномi, то есть

C(∆ti) = K(I,sgn∆ti)∆ti, (1.3)

где I – тип самолета, K – коэффициент, зависящий от типа самолета и знака ∆ti.

Критерий стоимости для всех самолётов будет равен

 (1.4)

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

 (1.5)

Поскольку из-за взлетов самолетов, аварийных ситуаций и других случаев ВПП может быть закрыта для прилетающих ВС в определенные отрезки времени [t1зап, t2зап], то добавляется еще один тип ограничений:

t1зап>tki> t2зап (1.6)

               Для всего множества запретных зон jϵαэто ограничений можно записать в общем виде:

 (1.7)

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

 (1.8)

Где i*- номер ВС, которому назначается посадка,

{Ci}* - множество весовых коэффициентов для ВС, претендующих на посадку в данный разрешенный момент времени.

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

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

          Предположим, что выполнены следующие основные условия:

·       Имеется одна ВПП, используемая как для взлетов, так и для посадок ВС;

·       Траектории вылета (прилета) организованы так, что достаточно при определении времени задержки ВС анализировать время пролета одного ориентира (например, порога ВПП);

·       Зоны ожидания расположены на внутренней границе буферной зоны регулирования.

Один из методов решения задачи оперативного планирования воздушного движения – целочисленное программирование. Целевая функция в этом случае – сумма (по числу ВС в зоне регулирования) величин, характеризующих расход топлива за время задержки посадки (взлета) ВС, ограничение по топливу, литер, отклонение от расписания.

Ограничения:

·       ВС могут производить посадки (взлеты) в фиксированные моменты времени через равные интервалы времени;

·       Интервалы между посадками (взлетами) должны быть не меньше интервала безопасности, который одинаков для всех типов ВС.

Задача формулируется как много ранцевая задача целочисленного линейного программирования следующим образом. Минимизировать целевую функцию:

 (1.9)

При ограничениях

  (1.10)

 (1.11)

где индекс iнумерует все ВС в зоне регулирования, индекс jнумерует моменты посадки (взлета),  Xij– булева переменная, которая принимает значение 1, если i-тому ВС назначается j-тый момент посадки, n– количество ВС в зоне регулирования, Cij– стоимость перемещения i-того ВС на j-тое место.

          Ограничение (1.10) имеет тот смысл, что каждому ВС должен быть назначен один и только один момент посадки. Ограничение (1.11) имеет тот смысл, что ВС не может осуществить посадку раньше некоторого минимального момента времени Ki.

          Задача (1.9-1.11) может быть решена известными методами, например, методом ветвей и границ. Однако соответствующие целочисленные алгоритмы имеют низкую вычислительную эффективность.

          Для повышения эффективности вычислений в рассмотренной выше задаче математического программирования большой размерности может быть использовано динамическое программирование (ДП).

          В приведенные выше ограничения включим еще одно:

·       Функция Ci(∆t­i), характеризующая стоимость задержки i-го ВС на время ∆ti­, - неотрицательная монотонная возрастающая функция ∆ti.

Определим этапы решения поставленной задачи методом ДП. Выделим nэтапов. Определим этап Kкак распределение (n-K+1) ВС на местах оси времени, соответствующих моментам времени tn,tn-1,…,tk, где tn – момент посадки последнего ВС в группе. Представляя процесс распределения ВС начиная с этапа n(процедура обратной прогонки) в виде сетевой модели, пронумеруем индексом μ все возможные варианты распределения ВС на каждом этапе (узлы сети). Обозначим Kμ – узел μ на этапе K. Алгоритм решения задачи запишем через рекуррентное выражение для стоимости Ckзадержек ВС на этапе K:

  (1.12)

(по допустимым дугам)

Где gμ(Kμ) – стоимость, связанная только с этапом Kпри выборе узла μ.

Определение допустимых дуг в (1.12) эквивалентно ограничению (1.11).

В соответствии с (1.12) получаем следующий алгоритм.

Для группы из nВС обозначим tj– разрешенные моменты посадки, j=1,…,n. Для каждого момента посадки jопределяется μj – число ВС, для которых tjtiн>tj-1 (t0=0), т.е. число ВС, претендующих изначально на j-тый момент посадки. Ввиду перемещения ВС в процессе решения задачи ДП μjбудет зависить от номера этапа K, поэтому будем писать μj

Положим K=n. Для удовлетворения ограничениям выполним следующую процедуру. Введем целочисленную переменную υ=1,…,K. Как только при увеличении υ от 1 имеет место равенство:

Фиксируем υ и определяем υ ВС, претендующих на момент посадки (взлета) tK. Это ВС, для которых tiн>tK-υ(за исключением ВС, которым на этапах с номером большим Kназначено время посадки; для K=nисключаемых ВС нет). Для выбранных ВС вычисляем минимальна, назначается момент посадки tj, j=K. Это i-тое ВС исключается из рассмотрения. Также новое μj(K-1) находится исключением ВС, которому на этапе Kназначено время посадки (взлета). Последним рассматриваемым этапом является первый этап.

Дополнительные требования следующие:

·       Обеспечить распределение ВС в соответствии с их приоритетами;

·       Сократить, по возможности, количество перемещаемых ВС и исключить, по возможности, секундные задержки.

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

Где индекс iнумерует все ВС произвольным образом, n – число ВС в зоне регулирования, tпi – время посадки i-го ВС с учетом задержки, t­нi-номинальное (без задержки) время посадки i-го ВС, Ci-коэффициент, характеризующий потери, связанные с задержкой i-го ВС.

Ограничения задачи:

tпi≥0, i=; (1.15)

tпi-tнi≥0, i=; (1.16)

| tпi-tпj|≥∆, i=, j=, ij; (1.17)

tпi-tнj> tпj-tнi, i=, j=, ij;

Ci<Cj, | tнi-tнj|<TM. (1.18)

Где ∆ - минимальный допустимый интервал времени между двумя посадками ВС.

Ограничение (1.15) очевидно, ограничение (1.16) определяет не отрицательность задержек, ограничение (1.17) устанавливает интервал между посадками, исходя из требований безопасности полетов, ограничение (1.18) обеспечивает последовательность посадок исходя из приоритетности ВС.

Для строгого решения задачи (1.14) при ограничениях (1.15-1.18) методом динамического программирования разделим процесс нахождения времен посадки ВС на этапы. Последним этапом будет назначение какому-либо ВС самого раннего времени посадки. Этапом (n-1) будет назначение какому-либо ВС второго по времени момента посадки и т.д. Представляя аналогично тому, как и выше, процесс распределения ВС начиная с этапа Kв виде сетевой модели, пронумеруем индексом μвсе возможные варианты распределения ВС на каждом этапе (узлы сети). Обозначим Kμ– узел μ на этапе К. Алгоритм решения задачи запишем через рекуррентное выражение для стоимости Pк задержек ВС на этапе К.

(по допустимым дугам)

          Где  – потери, связанные с этапом К при выборе узла μ.

Допустимые дуги здесь определяются исходя из ограничений (1.15-1.18).

Соответствующий алгоритм имеет следующие преимущества:

·       Достаточно высокую вычислительную эффективность;

·       Отсутствие необходимости дискретизации оси времени под разрешенные моменты посадки;

·       Уменьшение косвенным образом числа ВС, которым предписываются секундные задержки;

·       Гибкость в смысле возможности развития.

Цикл регулирования (определения времен задержки) заканчивается, когда просмотрены все ВС, находящиеся в буферной зоне. Каждому ВС становится в соответствие два указателя – индекс ВС, находящегося впереди по времени посадки и индекс ВС, имеющего более поздний момент посадки.