Автоматика и телемеханика, № 3, 2022

Оптимизация, системный анализ

и исследование операций

(Институт проблем управления им. В.А. Трапезникова РАН, Москва)

ГЕНЕТИЧЕСКИЙ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ

ОПТИМИЗАЦИИ ПОСЛЕДОВАТЕЛЬНОСТИ

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

Рассматривается NP-трудная задача оптимизации последовательности

и времен посадок воздушных судов с соблюдением необходимых огра-

ничений. В режиме реального времени получить точное решение задачи

не представляется возможным из-за большого объема вычислений. Для

получения приближенного решения предлагается комплексный подход:

на первом этапе применяется генетический алгоритм для получения на-

чального решения, которое затем улучшается на основе эвристического

алгоритма. Предлагаемый подход позволяет получить оптимальные или

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

разработанных алгоритмов использовалось программное средство имита-

ционного моделирования. Обширные вычислительные эксперименты под-

твердили эффективность предлагаемого подхода.

Ключевые слова: управление воздушным движением, последовательность

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

ческий алгоритм.

DOI: 10.31857/S0005231022030114

1. Введение

В настоящее время управление воздушными судами (ВС) в районе аэро-

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

разрабатывают расписания движения ВС в аэропортах, основываясь на своем

опыте, интуиции и некоторых правилах планирования. Однако в последнее

время по мере развития научно-исследовательской программы модернизации

Европейской системы организации воздушного движения SESAR (Single Eu-

ropean Sky ATM Research Programme) возникает необходимость автоматиза-

ции систем для обеспечения координации принятия решений в аэропортах [1].

Из-за высокой интенсивности движения в зоне аэропорта и ограниченной

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

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

минимальное время [2]. В [3] рассматривается задача планирования траекто-

156

рий в зоне аэропорта с учетом жестких ограничений по разделению ВС и их

бесконфликтному сближению вблизи взлетно-посадочной полосы. Поскольку

взлетно-посадочные полосы являются одними из самых жестких узких мест в

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

аэропортов является построение оптимальных очередей ВС на посадку с це-

лью минимизации задержек рейсов, максимизации пропускной способности

аэропорта и минимизации выбросов загрязняющих веществ [4].

В [5] задача формирования оптимальных очередей ВС на посадку бы-

ла формализована в виде задачи смешанного целочисленного линейного

или квадратичного программирования (в зависимости от выбранной целевой

функции) с использованием ∼ P² целочисленных переменных, принимающих

значения 0 или 1, для учета необходимых ограничений на минимальное вре-

мя разделения между ВС, где P - количество ВС. Применение стандартных

методов оптимизации для получения точного решения приводит к экспонен-

циальному росту времени счета с ростом P . Для решения задачи в режиме

реального времени, когда решение необходимо пересчитывать постоянно и

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

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

об особенностях данной задачи.

В обзоре [6] рассматриваются различные методы приближенного решения

задачи оптимизации очередей ВС на посадку: метод рассеивания и биониче-

ский метод, метод искусственных иммунных систем, табу-поиск, меметиче-

ские алгоритмы и др. Для решения задачи предпринимались попытки раз-

работать эффективные генетические алгоритмы на основе перестановок [7].

Особенность заключается в том, что для перестановок стандартные опера-

торы скрещивания неприменимы. В [8] предложен генетический алгоритм, в

котором хромосома из перестановки номеров ВС преобразуется в двоичную

матрицу, которая позволяет использовать равномерный оператор скрещива-

ния. Однако этот оператор включает матричные операции, требующие значи-

тельных вычислительных затрат, при этом оператор скрещивания в процессе

генетического алгоритма выполняется многократно.

В настоящей статье предлагаются генетический алгоритм, требующий

меньших вычислительных затрат, с оригинальным оператором скрещивания

на основе векторов времен посадок ВС и гибридный алгоритм решения зада-

чи, который позволяет повысить эффективность генетического алгоритма на

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

гаемый подход позволяет получить оптимальные или близкие к оптимальным

решения за приемлемое время.

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

Задача оптимизации последовательности и времен посадок прибываю-

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

пы ВС, которые находятся в зоне аэропорта с целью совершить посадку, P -

число ВС, ожидающих посадки.

157

Для каждого ВС определено временнóе окно, в течение которого ВС с но-

мером i может совершить посадку в соответствии с его летно-техническими

характеристиками, наличием топлива, длительностью полета и т.д. E_i - самое

раннее возможное время приземления i-го ВС; L_i - самое позднее возможное

время приземления i-го ВС. Для каждого ВС известно также время T_i - опти-

мальное время прибытия i-го ВС при условии свободной взлетно-посадочной

полосы, E_i < T_i < L_i, i = 1, P .

Требуется определить последовательность ВС при посадке и для каждого

ВС назначить x_i - время приземления i-го ВС в течение заданного интервала

времени [T₀, T_k].

В зависимости от решаемой задачи могут формироваться различные це-

левые функции. В настоящей статье рассматривается нелинейная целевая

функция сумма квадратов отклонений от оптимальных времен посадок:

∑

{

}

(1)

F (X) = (T_i - x_i)² , X =

x_i, i = 1,P

i=1

В связи с образованием струйно-вихревого следа необходимо обеспечить

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

щий от типов следующих друг за другом ВС.

Известна матрица S размера P · P , где SCiC_j - минимальный интервал

между посадкой ВС типа c_j после ВС типа c_i, i, j = 1, P , i = j, c_i - тип i-го

ВС.

Решение является допустимым, если для него выполнены два ограниче-

ния.

1. Приземление ВС с номером i происходит внутри временного окна

[E_i, L_i]:

(2)

E_i ≤ x_i ≤ L_i

i = 1,P.

2. Соблюдаются необходимые временные интервалы, зависящие от типов

ВС, при посадке следующих друг за другом ВС:

(3)

x_j ≥ x_i + SCiC_j , i = j, xj > xi,

i, j = 1, P .

3. Описание генетического алгоритма

Для задачи оптимизации последовательности и времен посадок группы

из P ВС, занумерованных от 1 до P , особь в генетическом алгоритме пред-

ставляется в виде двух целочисленных векторов R = {Y, X}.

Вектор Y = {y_i, i = 1, P } представляет собой перестановку номеров ВС и

определяет последовательность посадок ВС. Вектор X = {x_i, i = 1, P } пред-

ставляет собой упорядоченную по возрастанию последовательность смещений

времен посадок ВС в секундах относительно начального времени T₀. Время

посадки ВС с номером i равно T₀ + xyi .

158

3.1. Алгоритм формирования особи случайным образом

Шаг 1. Генерируется вектор Z длины P. Компоненты вектора генериру-

ются при помощи датчика случайных чисел в диапазоне от T₀ до T_K . Этот

вектор используется для формирования последовательности посадок ВС.

Шаг 2. Вектор Y полагается равным упорядоченной по возрастанию но-

меров последовательности от 1 до P : Y = {1, . . . , P }.

Шаг 3. Векторы Z и Y параллельно сортируются в порядке возраста-

ния z_i, при этом формируется новый вектор Y , который является искомой

перестановкой номеров ВС при посадке.

Шаг 4. Полученному вектору Y ставится в соответствие новый вектор X

одним из следующих двух способов.

Способ 1. Сохранив последовательность посадок, определяемую векто-

ром Y , вектор X формируем так:

(

)

(4)

i = 2,P.

xy0 = max (T₀,Ey0 ), max xyi-1 + SCyi,Cyi-1 ,Eyi

В силу такого формирования вектора X, особь R = {Y, X} будет удовле-

творять ограничению (3), при этом ограничение (2) может быть нарушено.

Величина нарушения рассчитывается по формуле:

∑

W₁ (R) = max(0,xyi - Lyi) .

i=1

Способ 2. Сохранив последовательность посадок, определяемую векто-

ром Y , вектор X формируем так:

(

)

i =2,P.

xy0 = max(T₀,Ey0 ), xyi = min max xyi-1 +SCyi,Cyi-1 ,Eyi^Lyi

В силу такого формирования вектора X особь R = {Y, X} будет удовле-

творять ограничению (2), при этом ограничение (3) может быть нарушено.

Величина нарушения рассчитывается по формуле:

∑

(

)

W₂ (R) =

max

0, SCiC_j - (xj - xi)

i=1

j=1,

j=i, x_j>x_i

Если W (R) = W₁(R) + W₂(R) = 0, то R является решением задачи.

3.2. Создание начальной популяции

Начальная популяция {R} состоит из N особей, созданных по алгорит-

му формирования особи случайным образом. Размер популяции N является

параметром алгоритма.

Особенностью рассматриваемой задачи является наличие исходного ре-

шения R = {Y, X}, в котором компоненты вектора Y упорядочены в порядке

159

возрастания времен T_i. Такая последовательность называется FCFS -последо-

вательностью (First-Come, First-Served - первым пришел, первым обслужен).

Вектор X исходного решения формируется на основе FCFS -последовательно-

сти по процедуре, описанной в шаге 4 алгоритма формирования особи случай-

ным образом. Для повышения эффективности алгоритма исходное решение

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

3.3. Оценка и упорядочение решений

Особи оцениваются и сравниваются по значениям целевой функции (1) и

величинам нарушения W (R).

Сравнение решений.

Решения R₁ = {Y₁, X₁} и R₂ = {Y₂, X₂} сравниваются следующим обра-

зом.

Если W (R₁) < W (R₂), то R₁ лучше, чем R₂.

Если W (R₁) = W (R₂) и F (X₁) < F (X₂), то R₁ лучше, чем R₂.

Все решения популяции оцениваются и упорядочиваются от лучших к худ-

шим.

3.4. Операторы скрещивания и мутации

Особенностью генетического алгоритма решения задачи оптимизации по-

следовательности и времен посадок прибывающих ВС является нестандарт-

ный оператор скрещивания. Стандартный оператор скрещивания в данном

случае применить нельзя, поскольку полученные в результате векторы мо-

гут не являться перестановками номеров ВС. Рисунок 1 демонстрирует это

на примере одноточечного скрещивания.

Алгоритм модифицированного оператора скрещивания.

Шаг 1. На первом шаге алгоритма для выбранной пары особей-родителей

R₁ = {Y₁,X₁} и R₂ = {Y₂,X₂} выполняется стандартный оператор скрещи-

вания над векторами X₁ и X₂, в результате формируются вспомогательные

векторы Z₁ и Z₂.

Шаг 2. Формируются векторы Y₁ и Y₂, равные упорядоченным по воз-

растанию последовательностям номеров от 1 до P : Y₁ = Y₂ = {1, . . . , P }.

Шаг 3. Векторы Z₁ и Y ₁ параллельно сортируются в порядке возрастания

компонент вектора Z₁, при этом формируется новый вектор Y₁, который яв-

ляется искомой перестановкой номеров ВС первой особи-потомка. Аналогич-

но при помощи векторов Z₂ и Y₂ формируется вектор Y₂, который является

искомой перестановкой номеров ВС второй особи-потомка.

y¹ = {1, 2, 3,

4, 5}

~ ¹ = {1, 2, 3, 2, 1}

~2 = {5, 4, 3, 4, 5}

y² = {5, 4, 3,

2, 1}

Рис. 1. Стандартный оператор одноточечного скрещивания.

160

Шаг 4. Вектору Y ₁ ставится в соответствие вектор X₁ способом, описан-

ным в шаге 4 алгоритма формирования особи случайным образом, приведен-

ного в подразделе 3.1. В процессе формирования над каждым компонентом x_i

особи-потомка с заданной параметром алгоритма вероятностью p_m выполня-

ется оператор мутации. Оператор мутации заключается в замене значения x_i

случайно сгенерированным числом в диапазоне от T₀ до T_K . Таким образом,

{

}

формируется особь-потомок R₁ =

Y₁,X₁

На основе вектора Y₂ аналогично формируется особь-потомок R₂ =

{

}

Y₂,X₂

3.5. Формирование новой популяции

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

функций следующим образом.

{

}

• Из популяции {R} случайным образом выбирается решениеR =

X,Y

• Для выбранного решения рассчитывается величина

retF = 1 - F (X)/ max F (X).

{R}

• Генерируется случайное вещественное число rnd в диапазоне от 0 до 1.

{

}

• Если rnd < retF , то решение R =

X, Y

выбирается в качестве решения-

родителя, в противном случае процедура повторяется.

После выбора двух решений-родителей над ними выполняется оператор

скрещивания и формируются два решения-потомка. Эта процедура повторя-

ется до тех пор, пока не будет сформировано P решений-потомков. Затем все

2P решений оцениваются и упорядочиваются. Из P лучших решений форми-

руется новая популяция.

Процесс формирования новой популяции повторяется циклически. Коли-

чество повторений определяется параметром алгоритма количеством по-

колений M.

3.6. Завершение алгоритма

Работа алгоритма завершается либо после формирования заданного ко-

личества поколений M, либо в случае, если популяция стала однородной.

Популяция считается однородной, если близко к единице отношение:

∕

min F (X)

avg F (X) > 0,98.

X∈{R}

В качестве решения задачи выбирается лучшее решение из последней по-

пуляции.

Поскольку исходное решение добавляется в начальную популяцию, то

достаточным условием существования решения задачи является условие

W (X) = 0 для исходного решения.

161

Отметим, что задача может не иметь решения, если недостаточна про-

пускная способность взлетно-посадочной полосы. Для фиксированной груп-

пы ВС существует минимальное время T_min, которое при посадке этих ВС с

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

какой последовательности посадок. Необходимым условием существования

решения является условие T_k - T₀ ≥ T_min.

4. Организация вычислительных экспериментов

Для исследования зависимости результата от параметров алгоритма раз-

работано программное средство имитационного моделирования.

Программное средство позволяет:

• генерировать тесты с заданными параметрами, главным из которых яв-

ляется интенсивность потока ВС на посадку, зависящая от Р и величины

временного интервала T ime = T_k - T₀,

• выбирать целевую функцию (1) или (2),

• выбирать алгоритм решения и задавать параметры алгоритма,

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

тестов и сохранять ее в файле.

Тесты генерируются следующим образом.

Тип ВС определяется при помощи функции генерации случайного целого

числа из заданного диапазона 1, . . . , K: C_i = rnd.Next (K), i = 1, P .

Времена 0 ≤ E_i ≤ T_i ≤ L_i ≤ T ime, i = 1, P, для всех ВС формируются при

помощи датчика случайных вещественных чисел.

T_i = rnd.Next(T₀,T₀ + Time) - оптимальное время прибытия i-го ВС -

случайное число в диапазоне (T₀, T₀ + T ime), i = 1, P . Интенсивность потока

ВС варьируется параметром Time.

E_i = T₀ - t - rnd.Next(2t) - самое раннее возможное время приземления

i -го ВС, i = 1, P , t - ориентировочная минимальная длительность окна по-

садки, например t = 300 c, rnd.Next(t) - случайный разброс времени окна

посадки в диапазоне 0, 2t.

L_i = T₀ + t + rnd.Next(2t) - самое позднее возможное время приземления

i -го ВС, i = 1, P .

Подробно программное средство моделирования описано в [9].

Для оценки эффективности решения, полученного при помощи генетиче-

ского алгоритма, это решение на большом количестве тестов сравнивалось с

исходным решением, а для задач небольшой размерности - до 20 ВС - еще и

с оптимальным решением.

Рассматриваемая задача сводится к задаче смешанного целочисленного

линейного или квадратичного программирования (в зависимости от выбран-

ной целевой функции) при помощи введения дополнительных переменных [5]:

{

1, если ВС i приземляется раньше ВС j,

δ_ij =

i, j = 1, P , i = j.

0 в противном случае,

162

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

поколений.

Для задач большой размерности получить точное решение не удается из-за

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

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

Возможность получения точного решения, его визуализация, анализ и срав-

нение с приближенными решениями задачи принесли большую пользу в про-

цессе разработки и анализа алгоритмов.

Недостатками генетических алгоритмов являются снижение скорости схо-

димости по мере приближения к решению и возможное получение однородной

популяции вблизи локального минимума. На рис. 2 представлены графики

типичного изменения максимального Max, среднего Avg и минимального Min

значений целевой функции для последовательных поколений. На нескольких

первых поколениях целевая функция улучшается стремительно, затем ско-

рость изменения резко снижается. В этой связи предлагается использовать

комплексный подход: на первом этапе использовать генетический алгоритм

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

ческого алгоритма улучшить это решение.

Параметры алгоритма - размер популяции N, количество поколений M -

необходимо корректировать в зависимости от размерности задачи P . В [7]

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

(

(max (0,P - 10)))

N = 30 + 10

round

(

(max(0,P - 10)))

M = 20 + 10

round

163

5. Исследование эффективности комплексного алгоритма

Ранее был разработан и реализован эвристический алгоритм на основе

перестановок для решения поставленной задачи на основе улучшения неко-

торого начального решения [9].

В основе алгоритма лежат сравнение решений с переставленными близко

расположенными в последовательности посадок ВС разных типов и выбор

лучшего решения. Пример представлен на рис. 3 в результате трех пере-

становок значение целевой функции (2) уменьшилось с 589 512 до 306 912.

Первый шаг эвристического алгоритма заключается в итерационном про-

цессе формирования, сравнения и выбора лучшего из двух решений, в кото-

рых переставлены два рядом стоящих компонента вектора Y , если им соот-

ветствуют ВС разных типов:

Y = {y₁,...,y_j,y_j+1,...,y_P},

j = 1,P - 1.

Y = {y₁,...,y_j+1,y_j,...,y_P},

Для векторов Y

Y строятся векторы X и

X описанным выше спосо-

бом (4), полученные решения сравниваются и для дальнейших итераций вы-

бирается лучшее из них.

Второй шаг эвристического алгоритма заключается в итерационном про-

цессе формирования, сравнения и выбора лучшего из трех решений, в кото-

рых переставлены три рядом стоящих компонента вектора Y , если им соот-

ветствуют ВС разных типов:

{y₁,... ,y_j,y_j+1,y_j+2,... ,y_P },

{y₁,... ,y_j+1,y_j+2,y_j,... ,y_P },

j = 1,P - 2.

{y₁,... ,y_j+2,y_j,y_j+1,... ,y_P },

На каждом шаге алгоритма для дальнейших итераций выбирается лучшее

решение.

Этот алгоритм работает тем эффективнее, чем лучше взятое за основу

начальное решение. Подробное описание и результаты исследования эффек-

тивности эвристического алгоритма приводятся в [10].

Значение целевой функции = 589 512

-170

-250

-294

-220 -163

-47

-33

-98

-88

156

205

373

322

Значение целевой функции = 306 912

-110 -190

-234

-223

-100-47

-33

-98

-88

-24

198

205

202

Рис. 3. Пример перестановок в последовательности посадок ВС.

164

Таблица 1. Значения целевой функции для разных решений для 17 ВС

Комплексный

Точное

Исходное Генетический

Тест №

алгоритм,

решение,

решение

алгоритм

1-й шаг

2-й шаг

CPLEX

704400

403068

391788

307564

293100

633057

361836

297801

234696

171687

279885

220277

212469

166424

286196

157848

155688

141035

544427

244942

158362

261039

109815

74370

233146

127655

100882

232913

212217

210177

175292

162332

162565

162485

150013

211737

206756

430268

173584

122384

119752

323899

259419

243954

230094

462540

322080

266424

211584

220370

181586

135566

130446

345061

195525

158253

152916

134212

Таблица 2. Значения целевой функции для разных решений для 50 ВС

Комплексный

Исходное Генетический

Тест №

алгоритм,

решение

алгоритм

1-й шаг

2-й шаг

2 904778

1 745359

1 039215

1 035355

1 887645

999401

426044

2 354880

1 231366

1 024269

940472

1 805502

1 768538

1 126340

955292

3 193848

797364

592548

534562

1 158859

591509

506445

461345

2 571624

2 417078

1 596856

1 364057

2 310212

589444

427588

403588

747182

437120

378117

3 347467

1 150929

878921

775345

2 462607

2 177331

1 619727

1 424103

3 332179

1 353453

648310

629647

1 989415

1 729610

1 070057

961849

1 395464

1 104507

601173

569085

2 848916

2 219743

1 384726

1 375948

Предлагается использовать комплексный алгоритм, состоящий из двух

этапов.

1. Получить начальное решение при помощи предлагаемого генетического

алгоритма.

165

12 000 000

Исходное

Генетич.

Компл. 1

Компл. 2

10 000 000

8 000 000

6 000 000

4 000 000

2 000 000

10 11 12 13 14 15 16 17 18 19 20

21 22 23 24 25

Рис. 4. Сравнение значений целевых функций, полученных на основе разных

алгоритмов.

2. Получить решение при помощи эвристического алгоритма на основе

перестановок, использовав начальное решение, полученное на первом этапе.

В табл. 1 приводится пример сравнения значений целевых функций (2), по-

лученных при помощи разных алгоритмов, для 15 тестовых задач для 17 ВС.

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

Для задач большой размерности получить точное решение не удается из-за

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

сравниваются значения целевой функции для исходного и полученных ре-

шений.

В табл. 2 приводится пример значений целевых функций (2), полученных

при помощи разных алгоритмов, для 15 тестовых задач для 50 ВС.

На рис. 4 значения целевых функций, полученных на основе разных алго-

ритмов для тестов из 100 ВС, представлены в форме диаграммы.

В процессе вычислительных экспериментов выигрыш вычислялся по фор-

муле:

((

(

))

)

F (X) - F

/F (X)

100%,

где X - исходное решение, X - исследуемое решение. В табл. 3 представлены

средние выигрыши, полученные после применения генетического алгоритма,

Таблица 3. Выигрыш в результате применения алгоритмов

Количество ВС

ГА

ГА + ЭА шаг 1 ГА + ЭА шаг 2

≈46,2%

≈54,1%

≈56,4%

≈51,5%

≈67,8%

≈70,1%

100

≈53,5%

≈70,2%

≈72,4%

166

после первого шага эвристического алгоритма и после второго шага эвристи-

ческого алгоритма.

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

ние генетического алгоритма, 1-й шаг эвристического алгоритма позволяет

значительно улучшить полученное решение, уменьшение значения целевой

функции после 2-го шага эвристического алгоритма менее существенно.

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

В Российской Федерации в полном объeме автоматизированное регулиро-

вание потоков воздушного движения не внедрено, поэтому развитие теории,

методов и алгоритмов для поддержки систем планирования и регулирования

потоков воздушного движения в условиях увеличивающейся интенсивности

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

Проведенные исследования подтвердили целесообразность применения в

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

посадок ВС большой размерности (более 20 ВС), методов приближенного

решения, которые позволяют получить за приемлемое время (за несколько

секунд) хорошее, хотя не всегда оптимальное решение.

Представлены три оригинальных алгоритма формирования очередей ВС

на посадку: генетический, эвристический и комплексный, в котором решение,

полученное на основе генетического алгоритма, используется в качестве на-

чального решения для эвристического алгоритма. Разработанные алгоритмы

реализованы в виде библиотеки программ.

Для исследования эффективности и обоснования методов и алгоритмов

построения оптимальных очередей ВС на посадку разработан инструмен-

тальный программный комплекс, который включает средства моделирования

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

ла на основе большого числа экспериментов и анализа результатов.

Описаны вычислительные эксперименты с целью оценки эффективности и

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

мов. Для оценки эффективности использовались оптимальные результаты,

полученные при помощи стандартного пакета CPLEX. Подтверждены эф-

фективность и достаточное быстродействие реализованных программ фор-

мирования очередей ВС на посадку для задач разной размерности при ин-

тенсивном потоке ВС.

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

1. Samà M., D’Ariano A., Corman F., Pacciarellia D. Coordination of Scheduling De-

cisions in the Management of Airport Airspace and Taxiway Operations // Trans-

portation Research. Part A: Policy and Practice. 2018. V. 114. Part B. P. 398-411.

2. Samà M., D’Ariano A., Palagachev K., Gerdts M. Integration Methods for Aircraft

Scheduling and Trajectory Optimization at a Busy Terminal Manoeuvring Area //

OR Spectrum. 2019. V. 41. P. 641-681.

167

Ng K.K.H., Lee C.K.M., Chan F.T.S., Chen C.H., Qin Y. A Two-stage Robust

Optimisation for Terminal Traffic Flow Problem // Applied Soft Computing. 2020.

V. 89. 106048.

Yin J., Ma Y., Hu Y., et al. Delay, Throughput and Emission Tradeoffs in Airport

Runway Scheduling with Uncertainty Considerations // Netw Spat Econ. 2021. 21.

P. 85-122.

Beasley J.E., Krishnamoorthy M., Sharaiha Y.M., Abramson D. Scheduling Aircraft

Landings - the Static Case // Transportation Science. 2000. V. 34. No. 2. P. 180-

197.

Вересников Г.С., Егоров Н.А., Кулида Е.Л., Лебедев В.Г. Методы построения

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

ного решения // Проблемы управления. 2018. № 5. С. 2-13.

Veresnikov G.S., Egorov N.A., Kulida E.L., Lebedev V.G. Methods for Solving of the

Aircraft Landing Problem. II. Approximate Solution Methods // Autom. Remote

Control. 2019. V. 80. No. 8. P. 1502-1518.

Hu X.B., Chen W.H. Genetic Algorithm Based on Receding Horizon Control for

Arrival Sequencing and Scheduling // Eng. Appl. Artif. Intell. 2005. V. 18. No. 5.

P. 633-642.

Hu X.B., Di Paolo E. Binary-representation-based Genetic Algorithm for Aircraft

Arrival Sequencing and Scheduling // IEEE Trans. on Intelligent Transportation

Syst. 2008. V. 9. No. 2. P. 301-310.

Kulida E.L. Analysis of Algorithms for Solving the Aircraft Landing Problem //

Proc. 13th Int. Conf. “Management of Large-Scale System Development” (MLSD).

Moscow: IEEE, 2020. C. https://ieeexplore.ieee.org/document/9247839.

10.

Кулида Е.Л., Лебедев В.Г., Егоров Н.А. Исследование эффективности алгорит-

ма оптимизации потока воздушных судов на посадку // Проблемы управления.

2019. № 6. С. 63-69.

Статья представлена к публикации членом редколлегии А.А. Лазаревым.

Поступила в редакцию 19.04.2021

После доработки 21.10.2021

Принята к публикации 20.11.2021

168