Mathematical Model and Application of the A-Star Algorithm to Optimize Its Routes in the Area Control Center Ho Chi Minh Airspace

Full Text

Введение

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

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

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

В настоящее время в сфере ОрВД внедряется множество современных методов, направленных на оптимизацию и повышение операционной эффективности. Среди них можно выделить такие решения, как навигация, основанная на характеристиках (Performance based navigation / PBN); организация потоков воздушного движения (Air Traffic Flow Management / ATFM); применение ВП свободной маршрутизации (Free Route Airspace) и временный маршрут (Conditional Route) и т.д. Однако эти меры пока не способны полностью решить проблему ПС ВП, а также полностью устранить перегрузки и задержки рейсов. Таким образом, требуется внедрение новых подходов для решения данной проблемы, и применение достижений в области компьютерных технологий представляется новым и перспективным направлением. В этой статье представлены математическая модель и оптимизационная программа, которые способны сократить общую протяженность маршрутов ОВД, что позволит повысить ПС ВП и снизить эксплуатационные расходы ВС.

Часть ВП Юго-Восточной Азии является ВП Хошимина. В 21 веке Юго-Восточная Азия считается одним из самых быстрорастущих регионов воздушного движения в мире. Одной из ключевых проблем в организации ВП РДЦ Хошимина является его ограниченная способность справляться и адаптироваться к растущему объему воздушного движения в нем. ВП РДЦ Хошимина охватывает обширное географическое пространство, в основном Вьетнама и Восточного моря, и граничит с ВП Лаоса и Камбоджи. Несмотря на большую территорию, исследуемое ВП и имеющиеся ресурсы для управления воздушным движением в нём не масштабируются в соответствии с растущим спросом. Эта диспропорция часто приводит к перегрузкам и задержкам, особенно в периоды пиковых нагрузок или в СМУ. Для решения проблемы авторы провели исследование, нацеленное на разработку программы для оптимизации сети маршрутов ОВД в ВП РДЦ Хошимина. Программа использует алгоритм A-star, который является алгоритмом искусственного интеллекта¹ в теории графов, и язык программирования Python [Van Rossum et al., 2009]. Теория графов широко применяется при проектировании транспортных сетей, включая системы метро, городских автомагистралей и высокоскоростных железных дорог, и зарекомендовала себя как эффективный инструмент для исследования проблем, связанных с деятельностью авиации [Румянцев и др., 2024; Air traffic controller …, 2023; Bombelli et al., 2020; Detecting delay propagation …, 2022]. Данное исследование использует алгоритм A-star, известный своей эффективностью в задачах поиска оптимальных путей, впервые применяемый к ВП РДЦ Хошимина. Отличительной особенностью данной работы является построение целостной модели, которая учитывает специфику воздушного пространства РДЦ Хошимина, таких как запретные зоны, зоны ограничений полетов и уникальные эксплуатационные требования. Предлагаемая модель представляет собой новаторский подход, поскольку она впервые во Вьетнаме учитывает как пространственные ограничения (запретные и опасные зоны), так и эксплуатационные требования, обеспечивая оптимальную длину маршрутов и высокую степень безопасности. Целью является достижение более безопасных и эффективных операций в ВП. Интегрируя передовые вычислительные методы, авторы стремятся создать устойчивую и надежную систему ОВД, которая будет адаптирована к будущим вызовам, тем самым поддерживая прогрессивное развитие авиатранспортных систем.

Математическая модель задачи оптимизации сети маршрутов ОВД

Определение структуры ВП и переменных, используемых в модели

Сеть маршрутов в ОВД в структуре ВП может быть описана двухмерной матрицей, состоящей из двух основных компонентов:

• маршрут ОВД – m, где m ∈ {1, 2, ... M}.
• участки маршрута – u, где u ∈ {1, 2, ... U}.

Каждый маршрут ОВД (m) может состоять из множества участков маршрута, которые определяются координатами навигационных точек (x, y), углами между участками маршрута (γ) и их расстояниями (d). Конкретно:

$m\left(u\right)=\left[(x, y), (\gamma , d)\right]$. (1)

Эти компоненты изначально представлены в виде матрицы, где каждая строка матрицы описывает маршрут, а каждая ячейка строки содержит данные об участке маршрута. Однако матрица как способ описания имеет ограниченную гибкость при решении задач маршрутизации, оптимизации или анализа. Поэтому переход к модели в виде графа G = (N, F), где множество узлов N = {N₀, N₁, N₂, ..., N_z} и множество дуг F = {F₁, F₂, ..., F_k}, становится естественным шагом, позволяющим упростить работу с данной структурой. Граф G описывает эти связи более наглядно: узлы N представляют точки маршрута, а дуги F – прямые связи между этими точками, включая такие характеристики, как угол (γ) и расстояние (d).

В математической модели граф G = (N, F) представляет собой описание всей структуры ВП. Более конкретно, множество узлов представляет все соответствующие аэропорты и точки пути или навигационные точки (VOR, DME) системы маршрутов ОВД. Дуга в множестве F – это прямая, соединяющая любые две точки N_i в множестве N. Дуга может быть описана так: F (N₁, N₂) – дуга между двумя узлами N₁ и N₂. Для количественного описания графа вводится матрица расстояний D [i, j], элементы которой характеризуют длину пути или отсутствие связи между узлами. Она задаётся следующей формулой:

$D[i, j]=\left\{\begin{array}{l}0, \mathrm{для} i=j;\\ d_{i,j}, \mathrm{конечная} \mathrm{величина}, \mathrm{если} \mathrm{есть} \mathrm{дуга} \mathrm{из} \mathrm{узла} i в \mathrm{узел} j;\\ \infty , \mathrm{если} \mathrm{нет} \mathrm{дуги} \mathrm{из} \mathrm{узла} i в \mathrm{узел} j.\end{array}\right.$ (2)

В графе G каждый маршрут ОВД формирует подграф G^m = (N^m, F^m), который содержит узлы и дуги, принадлежащие этому маршруту, где N^m ⊂ N и F^m ⊂ F. Маршрут ОВД представляет собой последовательность прямых линий, соединяющих начальную и конечную точки, а также точки пути (навигационные точки), расположенные между ними. Начальная точка ($N_0^m$) и конечная точка ($N_{last}^m$) могут быть как аэропортами, так и точками передачи управления. Другими словами, маршрут – это конечная последовательность узлов и дуг, в которой две соседние дуги имеют общий узел. На каждом маршруте ОВД точка N ∈ N^m перемещается от $N_0^m$ до $N_{last}^m$. То есть, когда N ≡ $N_0^m$, соответствует начальной точке маршрута ОВД, а N ≡ $N_{last}^m$ соответствует конечной точке маршрута ОВД. Далее используются следующие символы:

• (x_N, y_N): представляет широту и долготу точки N;
• $d_{N,N+1}^m$: длина участка, соединяющая точку N и точку N+1 маршрута ОВД. Значение  можно рассчитать следующим образом:

$d_{N,N+1}^m=\sqrt{{\left(x_{N+1}-x_N\right)}^2+{\left(y_{N+1}-y_N\right)}^2}$. (3)

Примечание: Длина маршрута ОВД в структуре ВП – это сумма длин дуг F (N, N + 1), составляющих данный маршрут, т.е. сумму $d_{N,N+1}^m$ при $N\in \left[N_0^m,N_{last}^m\right]$.

При организации и проектировании ВП будут существовать опасные зоны, зоны ограничения полётов и запретные зоны, в пределах которых запрещаются или ограничиваются полеты ВС. Кроме того, чтобы маршрут ОВД не проходил слишком близко к этим зонам, для обеспечения безопасности при фактическом выполнении полётов (например, в случае отклонения ВС) будет создана буферная зона, размером 0,005 км (рис. 1). Маршрут ОВД будет одобрен только в том случае, если все точки находятся за пределами этой зоны. Далее для простоты запретные зоны, зоны ограничения полётов, опасные зоны и буферные зоны будут именоваться бесполётными зонами. В структуре ВП, содержащей маршрут ОВД, S_k обозначает площадь бесполётной зоны. Этот параметр используется для описания зоны, запрещённой для полётов, в рамках ограничений математической модели, представленной на рисунке 1.

 

Рисунок 1. Создание буферной бесполётной зоны

 

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

• B^m: зона действия навигационных станций в структуре ВП – G;
• ${\theta }_{q,p}^m$: угол, образованный F (q, p), соединяющей точки q и точки p (где q, p ∈ N), расположен между маршрутом ОВД и осью магнитного севера;
• R^m: минимальное боковое расстояние между двумя параллельными маршрутами ОВД;
• переменная решения $O_{N,j}^m$ обозначает дугу от точки N до точки j на маршруте ОВД. Переменная $O_{N,j}^m$ описывается так:

$O_{N,j}^m=\left\{\begin{array}{l}\mathrm{1,} если выбирает F(N, j), при определении маршрута ОВД;\\ \mathrm{0,} другие случаи.\end{array}\right.$ (4)

Целевая функция

В этой модели для повышения эффективности использования маршрутов ОВД в ВП необходимо сократить время полёта между рейсами за счёт уменьшения длины маршрута ОВД, соединяющего точки $N_0^m$ и $N_{last}^m$. Другими словами, это означает поиск кратчайшего (оптимального) пути. Кратчайший (оптимальный) путь D_m – путь между начальным узлом $N_0^m$ и конечным узлом $N_{last}^m$ имеющий минимальную протяженность.

$D_m=\sum _{N=N_0^m}^{N_{last}^m-1}{d}_{N,N+1}^m\to \min$. (5)

Особенности структуры ВП графа G:

• дуга, состоящая из двух узлов N_i и N_{i + 1}, может иметь «встречную» дугу, т.е. может существовать F (N_i, N_i+1) или F (N_i+1, N_i). Если существуют две дуги F (N_i, N_i+1) и F (N_i+1, N_i), маршрут ОВД является двусторонним маршрутом, в противном случае, если существует только одна из двух дуг F (N_i, N_i+1) или F (N_i+1, N_i), то это односторонний маршрут от N_i до N_{i + 1} или наоборот.
• максимальное число дуг графа G = (N, F) с N узлами (без учёта направления движения ВС). Это также максимальное количество дуг, которое можно использовать для проектирования сети маршрутов ОВД. Как упоминалось выше, дуга может использовать два направления или одно направление.

$\max F=\frac{N\times (N-1)}{2}$. (6)

• вокруг точки N_i будет множество узлов, находящихся на заданном расстоянии l от узла N_i. Это множество используется для поиска дуг, выходящих из точки N_i (одна из этих дуг будет выбрана как дуга кратчайшего (оптимального) маршрута ОВД). Это множество может быть выражено уравнением:

$L(N_i, l)\stackrel{def}{=}\left\{N_u\in N\left|d_{N_i,N_u}=l\right.\right\}$. (7)

• когда узел N_i определяется как навигационная станция (VOR, DME), дуги, содержащие точку N_i, должны находиться в зоне действия навигационных станций, чтобы обеспечить безопасность и навигационные сигналы для ВС, т. е.:

$\forall F(N_i,N_{i+1})\subseteq B^m$. (8)

Примечание: Значение зоны действия навигационных станций зависит от многих факторов, таких как мощность навигационной станции, высота (эшелон) полёта ВС, рельеф местности и т.д. Как правило, среднее значение зоны действия VOR составляет 130 миль, NDB – 75 миль, а DME – 200 миль.

• когда узел N_i является точкой пути, используется метод навигации PBN. В этом случае маршруты ОВД вдоль маршрута от начальной точки до конечной точки могут быть указаны внутри прямоугольника. Его длина должна равняться длине маршрута, а ширина – в два раза превышать максимально допустимое значение отклонения x соответствующего метода навигации RNAVx/RNPx (например, RNP10, ширина составляет 20 морских миль), т. е.:

$F^m\subseteq S_{rec}, S_{rec}=\left|N_0^m{N}_{last}^m\right|\times 2x$. (9)

Ограничения каждого маршрута – m

• действительные маршруты ОВД должны идти от начальной точки до конечной точки. Маршрут m не имеет дуг, входящих в начальную точку, и дуг, выходящих из конечной точки, т. е.:

$d_{N_v,N_0^m}^m=d_{N_{last}^m,N_t}^m=0$, (10)

где: $N_t\in N^{m^{+}}\left(N_{last}^m\right), N_v\in N^{m^{-}}\left(N_0^m\right)$

$\sum _{j\in N^{m^{+}}\left(N_0^m\right)}{O}_{N_0^m,j}^m-\sum _{j\in N^{m^{-}}\left(N_0^m\right)}{O}_{j,N_0^m}^m=\mathrm{1,} \forall m\in M$. (11)

$\sum _{j\in N^{m^{-}}\left(N_{last}^m\right)}{O}_{j,N_{last}^m}^m-\sum _{j\in N^{m^{+}}\left(N_{last}^m\right)}{O}_{N_{last}^m,j}^m=\mathrm{1,} \forall m\in M$. (12)

• для любого узла N (кроме начальной и конечной точек) количество входящих в него дуг равно количеству выходящих из него дуг, т. е.:

$\sum _{N\in N^{m^{-}}\left(j\right)}{O}_{N,j}^m=\sum _{N\in N^{m^{+}}\left(j\right)}{O}_{j,N}^m, m\in M, \forall j\in N^m-\left\{N_0^m,N_{last}^m\right\}$. (13)

• маршруты ОВД не могут проходить через бесполётные зоны, т.е.:

$\sum _{F(N,j)\in F_S}{S}_k\times O_{N,j}^m=0; \forall F(N, j)\cap S_k=\varnothing$, (14)

где: F_S – множество всех дуг, которые могут проходить через бесполётные зоны.

Ограничения пары маршрутов ОВД «m» и «n»

– согласно DOC 4444, для обеспечения бокового эшелонирования ВС, находящихся на одном эшелоне полёта при прохождении навигационных точек, две линии пути ВС должны встретиться друг с другом под минимальным углом. Таким образом, при проектировании маршрута ОВД удобно использовать уравнение, где $\Delta {\theta }_{{}^q}^{m,n}$ – это угол между маршрутами ОВД в точке их пересечения q:

$\Delta {\theta }_{{}^q}^{m,n}=\left|{\theta }_{q,p}^m-{\theta }_{q,p\text{'}}^n\right|\ge {\theta }_{\min }$. (15)

Значение θ_min зависит от навигационной станции в узле θ:

• если узел q является географическим пунктом: θ_min = 30°;
• если узел q является станцией NDB: θ_min = 30°;
• если узел q является станцией VOR: θ_min = 15°.
• если два маршрута ОВД проектируются параллельно, необходимо соблюдать следующее ограничение:

$r^{m,n}\ge R^m$, (16)

где: r^m,n – расстояние между двумя параллельными маршрутами ОВД – «m» и «n».

 

Рисунок 2. Описание ограничений пар маршрутов ОВД «m» и «n»

 

Программа оптимизации сети маршрутов ОВД с использованием алгоритма А-star

Алгоритм A-star находит оптимальный маршрут

Современные методы оптимизации путей основаны на обширных научных исследованиях в таких областях, как теория оптимального управления, статистика, теория игр и теория графов и т.д. Было проведено множество исследований и доказано, что методы теории оптимального управления [Гаракоев и др., 2023; Самохина и др., 2024; Храмов, 2024; Ekrami Kivaj et al., 2023; Optimal control…, 2022; Zwick et al., 2023] и теории графов [Костин и др., 2023; Нгуен и др., 2024; Неретин и др., 2022; Clothoid-Based Path…, 2023; Ntakolia et al., 2022; Optimization…, 2019; UAV…, 2023] дают хорошие результаты для оптимизации траектории или пути транспортного средства в пространственно-временных координатах. Вышеприведенные исследования показывают, что для задач с непрерывным процессом методы теории оптимального управления вполне эффективны, в то время как метод теории графов даёт лучшие результаты для дискретных задач оптимизации. Однако в этих исследованиях основное внимание уделялось оптимизации траектории полёта ВС или отдельных маршрутов ОВД, но ни одно из них не касалось оптимизации всей сети маршрутов ОВД. На основе представленной выше математической модели авторы намерены разработать программу, способную оптимизировать всю сеть маршрутов ОВД с учетом заданных ограничений. Новизна модели, достигнутая после успешного завершения исследования, позволит внедрить её в практику для повышения ПС ВП, снижения задержек и повышения эффективности ИВП. Это, в свою очередь, позволит ВС выполнять полеты по более коротким маршрутам, что приведет к экономии топлива и сокращению времени полёта.

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

Основываясь на анализе жизнеспособных методов оптимизации сети маршрутов ОВД с гибкой маршрутизацией и в соответствии с предложенной математической моделью, в программе был выбран алгоритм A-Star. Использование алгоритма A-star обеспечит построение кратчайшего маршрута ОВД с учётом таких ограничений, как зона действия радионавигационных средств системы ОрВД, боковое эшелонирование и т.п.

Алгоритм A-star позволяет найти маршрут с наименьшей стоимостью от начального узла до конечного узла и рассчитывает его на основе взвешенного графа. Взвешенный граф – это граф, в котором каждой дуге присвоено определенное значение (вес дуги). Алгоритм A-star стал одним из самых важных и популярных алгоритмов в области искусственного интеллекта и поиска маршрута. Основная причина в том, что алгоритм A-star позволяет рассчитать стоимость маршрута в сочетании с математическим и эвристическим подходом, что является его отличительной особенностью. Это помогает алгоритму A-star избегать ненужных маршрутов и находить кратчайший путь за приемлемое время.

В алгоритме A-star, если f (N) является наименее затратным маршрутом к целевому узлу через узел N, то функция будет иметь вид:

$f\left(N\right)=g\left(N\right)+h\left(N\right)$, (17)

где: N – это текущий узел; g (N) – функция стоимости достижения от начального узла до текущего узла; h (N) – эвристическая функция оценивает стоимость расстояния от текущего узла N до конечного узла.

В алгоритме A-star появление эвристической функции h (N) помогает найти маршрут к целевому узлу в определенном направлении вместо скалярного поиска, как в других алгоритмах, таких как алгоритм Дейкстры. Эвристика служит функцией оценки, оценивая стоимость достижения цели из каждого оцениваемого узла. Алгоритм A-star не определяет тип эвристики, используемой в алгоритме. Вместо этого эвристику можно сформулировать и адаптировать к потребностям пользователя. Важной особенностью эвристики является допустимость. Эвристика считается «допустимой», если предполагаемая стоимость достижения целевого узла всегда меньше фактической стоимости для всех узлов.

Модель применения A-star в оптимизации сети маршрутов ОВД

Оптимизация сети маршрутов ОВД с использованием алгоритма A-star начинается со сбора начальных и конечных узлов в соответствии с фактическими эксплуатационными потребностями полёта (см. рис. 3). На этом этапе open_set² и close_set³ являются пустыми множествами. После определения начальных и конечных узлов анализируются промежуточные узлы для инициализации матрицы расстояний. Затем алгоритм использует обработанную матрицу расстояний для идентификации всех возможных последующих узлов-преемников, добавления их в open_set и вычисления g (N), h (N) и f (N) для каждого узла.

Из множества open_set выбирается узел N_k с минимальным значением функции f (N_k). Если существует несколько узлов с одинаковым значением f (N_k), алгоритм выбирает любой из них, но всегда отдает предпочтение узлу из множества K (K – множество, содержащее конечные узлы). Если , узел N_k добавляется в множество close_set, и алгоритм завершается, что означает, что найден оптимальный путь для маршрута ОВД.

В случае, если N_k ∈ K, узел N_k добавляется в множество close_set, и процесс поиска продолжается для узла N_k+1, который является следующим соседним узлом для N_k, с целью продолжить поиск оптимального пути. На этом этапе узел N_k называется родительским узлом (parent) для N_k+1.

Далее вычисляется значение f (N_k+1) для всех соседних узлов N_k+1 узла N_k, и узлы, которые не входят в множество close_set, добавляются в множество open_set. Узел с минимальным значением f (N_k+1) выбирается для дальнейшего анализа, который продолжается аналогичным образом, как это было описано выше для узла f (N_k).

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

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

С целью минимизации расстояния маршрутов ОВД функция f (N) представляется целевой функции математической модели (уравнение 4). Кроме того, при проектировании маршрута ОВД (уравнения 9–15) необходимо учитывать уравнения ограничений на протяжении всего процесса оптимизации.

В соответствии с уравнением 16, эвристическая функция h (N) играет ключевую роль в достижении оптимальных результатов. В данном исследовании для анализа влияния эвристической функции на оптимизацию маршрутов ОВД авторы создают модель с использованием различных типов эвристик, включая манхэттенскую функцию, евклидову функцию, диагональную функцию с параметром D = 1, D₂ = $\sqrt{2}$, гауссову функцию с параметром σ = 1, а также функцию потенциального поля.

 

Рисунок 3. Блок-схема алгоритма A-star в оптимизации сети маршрутов ОВД

 

Далее координаты бесполётной зоны обрабатываются в ВП, чтобы убедиться, что маршрут ОВД их избегает (уравнение 13). В сети промежуточных точек зоны представлены наборами точек, что ускоряет алгоритм A-star, исключая их из поиска. Блок-схема обработки бесполётных зон показана на рис. 4.

 

Рисунок 4. Блок-схема алгоритма обработки данных бесполётной зоны в предлагаемой модели

 

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

$d\left(км\right)=111.12{\cos }^{-1}\left[\sin x_1\times \sin x_2+\cos x_1\times \cos x_2\times \cos (y_2-y_1)\right]$, (18)

где: d (км) – расстояние по большому кругу между 2 координатами в км; x₁ и x₂ – широты узлов N и N + 1 соответственно; y₁ и y₂ – долготы узлов N и N + 1 соответственно.

Практический пример: результаты и анализ

Для применения алгоритма A-star необходимо определить граф G, представляющий структуру ВП. В настоящее время в ВП РДЦ Хошимина в общей сложности имеется 114 узлов, используемых для построения маршрутов ОВД. Применение уравнения 5 будет иметь 6441 дугу. Это относительно большое число, что может привести к увеличению времени вычислений. Поэтому для сокращения времени работы программы координаты узлов будут обработаны и разделены на 3 зоны: северную, южную и восточную. При построении маршрута ОВД в зоне используются только соответствующие узлы и дуги в этой зоне.

В этом практическом примере представлены результаты оптимизации трех важных маршрутов ОВД в ВП РДЦ Хошимина, а именно:

• международный аэропорт Тан Сон Нхат (VVTS) – международный аэропорт Дананга (VVDN). Причина выбора: это чрезвычайно важный маршрут ОВД, осуществляющий внутренний рейс, соединяющий 2 крупнейших аэропорта ВП РДЦ Хошимина. Этот рейс имеет достаточно высокую плотность выполнения операций (в среднем 25 полетов в день). Кроме того, этот маршрут ОВД соединяет два района полетной информации во Вьетнаме, помогая соединить полёты с юга на север Вьетнама, включая международный аэропорт Нойбай (VVNB). В 2023 году маршрут VVNB – VVTS занял четвертое место в мире по загруженности маршрута ОВД с объемом перевозки 10,9 млн пассажиров⁵;
• международный аэропорт Тан Сон Нхат (VVTS) – точка передачи управления ARESI. Причина выбора: это маршрут ОВД, соединяющий аэропорт Тан Сон Нхат с Восточным морем (восток Вьетнама), который помогает соединить аэропорт Тан Сон Нхат (аэропорт Камрань) со странами Восточной Азии, такими как Япония и Корея;
• международный аэропорт Камрань (VVCR) – международный аэропорт Фукуок (VVPQ): Причина выбора: это второй по загруженности внутренний маршрут ОВД в ВП РДЦ Хошимина. Кроме того, при выборе маршрута ОВД на этом маршруте могут выполняться и другие внутренние рейсы, такие как VVTS – VVPQ, VVTS – VVCR и т.д.

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

Из результатов таблицы 1 видно, что эвристическая функция Манхэттена даёт наихудшие оптимальные результаты. Это можно объяснить тем, что данный метод вычисляет расстояние между двумя точками вдоль перпендикулярных осей, не принимая во внимание диагональ. Между тем, при проектировании маршрутов ОВД диагональные линии (т.е. прямые линии, непосредственно соединяющие две точки) не ограничены, и они обычно приводят к наименьшему расстоянию. Диагональная эвристическая функция и функция потенциального поля дают аналогичные результаты, лучше, чем эвристическая функция Манхэттена на маршрутах ОВД VVTS – ARESI и VVCR – VVPQ. Наилучшие результаты, полученные с помощью двух эвристических функций: Евклида и Гаусса, оказываются одинаковыми. Причиной этого является то, что обе функции вычисляют расстояние на основе формулы Евклида, при этом в функции Гаусса результат корректируется с учётом стандартного отклонения. Однако, поскольку расчёты ведутся в двумерном пространстве, эта корректировка не вносит значительных изменений. Аналогично, метод потенциального поля оказался бы более эффективным, если бы в модели присутствовали дополнительные ограничения по высоте, но при проектировании двухмерной сети маршрутов ОВД ограничения по высоте препятствий не учитываются. Поэтому в дальнейших исследованиях при проектировании всей сети маршрутов ОВД авторы будут отдавать приоритет выбору евклидовой функции, поскольку её использование проще и при этом она даёт хорошие оптимальные результаты, аналогичные более сложным функциям.

 

Таблица 1. Результаты с применением различных эвристических функций

	Эвристическая функция Манхэттена	Эвристическая функция Эвклида	Эвристическая функция диагонали	Эвристическая функция Гаусса	Функция потенциального поля
VVTS – VVDN	636.85 км TSH - KADUM - BMT - ENGIM - MUMGA - BANSU - SADIN - DAD	626.83 км TSH - KADUM - PATMA - SADAS - DADEN - TATIM - DAD	636.85 км TSH - KADUM - BMT - ENGIM - MUMGA - BANSU - SADIN - DAD	626.83 км TSH - KADUM - PATMA - SADAS - DADEN - TATIM - DAD	636.85 км TSH - KADUM - BMT - ENGIM - MUMGA - BANSU - SADIN – DAD
VVTS – ARESI	959.41 км TSH - ESDOB - AC - IBUNU - CRA - DAMEL - MESOX - ARESI	931.36 км TSH - ESDOB - AC - IBUNU - CRA - NITOM - MESOX - ARESI	931.36 км TSH - ESDOB - AC - IBUNU - CRA - NITOM - MESOX - ARESI	931.36 км TSH - ESDOB - AC - IBUNU - CRA - NITOM - MESOX - ARESI	931.36 км TSH - ESDOB - AC - IBUNU - CRA - NITOM - MESOX - ARESI
VVCR – VVPQ	616.75 км CRA - VETOM - AC - TSH - POTIX - TUNPO - PQU	612.32 км CRA - IBUNU - AC - ESDOB - TSH - ATGAS - TUNPO - PQU	612.91 км CRA - VETOM - AC - TSH - ATGAS - TUNPO - PQU	612.32 км CRA - IBUNU - AC - ESDOB - TSH - ATGAS - TUNPO - PQU	612.91 км CRA - VETOM - AC - TSH - ATGAS - TUNPO - PQU

 

Оптимальные результаты трёх маршрутов ОВД с использованием евклидовой эвристической функции представлены на рис. 5. На нём черная линия обозначает маршрут ОВД, соединяющий VVTS и VVDN, красная линия – маршрут VVCR и VVPQ, а синяя линия – маршрут между VVTS и ARESI.

 

Рисунок 5. Оптимальный маршрут ОВД с использованием алгоритма A-star

 

Серые круги указывают зоны действия навигационных станций VOR/DME, а жёлтые круги обозначают зоны действия навигационных станций NDB в ВП РДЦ Хошимина. Результаты показывают, что все маршруты ОВД на континентальной части находятся в пределах зон действия навигационных станций (т.е. удовлетворяют уравнению 7). Для маршрута ОВД, соединяющего точки VVTS и ARESI, начиная с точки NITOM и далее, маршрут проходит через район, расположенный в Восточном море, где установка навигационной станции затруднительна, поэтому для расчётов применяется уравнение 8. Оранжевый прямоугольник обозначает границы региона. Кроме того, на рисунке также показаны названия узлов и длины дуг (расстояния между двумя узлами на маршруте ОВД). Длина дуги указывается в конечной точке. Например, дуга TSH – KADUM на маршруте ОВД VVTS – VVDN имеет длину 74,65 км.

 

Рисунок 6. Результаты испытаний маршрута ОВД не прошли через бесполётную зону

 

В ВП РДЦ Хошимина существуют запретные зоны, опасные зоны и зоны ограниченных полётов, влияющие на деятельность ВС на маршруте ОВД (опасная зона MAY TAO – VVD32 и запретная зона Хошимина – VVP4). При проектировании и оптимизации маршрутов ОВД прохождение этих зон не допускается (уравнение 13). На рис. 6 показано, что оптимизированные маршруты ОВД вообще не нарушают бесполётные зоны. В частности, зона VVP4 находится на очень близком расстоянии от узла TSH, но все же гарантирует это ограничение.

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

 

Таблица 2. Сравнение оптимальных и фактических маршрутов ОВД

	Используемый в настоящее время маршрут ОВД		Маршрут ОВД оптимальной программы
VVTS – VVDN	TSH - KADUM - PATMA - SADAS - MUMGA - BANSU - SADIN - DAD	631,42 км	TSH - KADUM - PATMA - SADAS - DADEN - TATIM - DAD	626,83 км
VVTS – ARESI	TSH - ESDOB - AC - VETOM - LKH - SOSRA - CRA - ATVIT - NITOM - MESOX - ARESI	935 км	TSH - ESDOB - AC - IBUNU - CRA - NITOM - MESOX - ARESI	931,36 км
VVCR – VVPQ	CRA - SOSRA - LKH - VETOM - AC - ESDOB - TSH -  ATGAS - TUNPO - PQU	615,74 км	CRA - IBUNU - AC - ESDOB - TSH - ATGAS - TUNPO - PQU	612,32 км

 

Заключение

С точки зрения теории графов и алгоритма A-star была разработана модель для анализа характеристик маршрутов ОВД, тем самым построена математическая модель и программа оптимизации маршрутной сети ОВД. Хотя практический пример, представленный в этой статье, оптимизировал только три маршрута ОВД, результаты, тем не менее, демонстрируют эффективность и точность программы, которая является основой для будущей общей оптимизации сети маршрутов ОВД в ВП РДЦ Вьетнама. Так как данные результаты оптимизируют только три маршрута ОВД, оптимизация для пары маршрутов ОВД «m» и «n» (уравнения 14 и 15) еще не рассматривалась. Это будет рассмотрено в последующих исследованиях.

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

В соответствии со стандартами и рекомендациями, разработанными Международной организацией гражданской авиации (ИКАО) для обеспечения безопасности полетов, требуется разработка как основного, так и альтернативного маршрутов ОВД, в случае невозможности применения основного. Исходя из этого, государствам-членам рекомендуется разработать playbook route⁶ для внедрения и эффективного управления такими чрезвычайными ситуациями. Это также является целью будущих исследований авторов помимо использования алгоритмов оптимизации всей основной сети маршрутов ОВД в ВП РДЦ Хошимина.

В дальнейшем данное направление исследований будет развиваться с целью применения при ОрВД во Вьетнаме. Использование программы оптимизации сети маршрутов ОВД и проектирования ВП путем перераспределения секторов [Хоанг Куан и др., 2024] будет способствовать повышению пропускной способности, эксплуатационной эффективности и обеспечению безопасности ВД в ВП РДЦ Хошимина.

¹ Искусственный интеллект (ИИ, англ. Artificial intelligence, AI) – это область компьютерных наук, занимающаяся созданием систем, способных выполнять задачи, которые обычно требуют человеческого интеллекта.

² Множество open_set содержит потенциальные узлы, которые помогают алгоритму расширять пространство поиска. Это означает, что все точки в этом множестве могут быть использованы для нахождения оптимального пути для маршрута – m.

³ Множество close_set включает узлы, которые уже обработаны или принадлежат сети, но не могут быть использованы для поиска маршрута – m (например, точки, находящиеся в зонах, запрещённых для полётов). Это помогает алгоритму избегать повторного рассмотрения этих узлов в процессе поиска.

⁴ Great Circle Distance Formula // [Электронный ресурс]. – 2023. URL: https://www.geeksforgeeks.org/great-circle-distance-formula (дата обращения: 11.11.2024).

⁵ OAG Aviation Worldwide Limited. The busiest flight routes of 2023 // [Электронный ресурс]. – 2023. URL: https://www.oag.com/busiest-routes-world-2023 (дата обращения: 09.10.2024).

⁶ Playbook route – это набор стандартных маршрутов ОВД, которые ОВД может использовать в определенных обстоятельствах, когда основной маршрут недоступен. Эти маршруты созданы для обеспечения возможности быстрого внедрения по мере необходимости.

About the authors

Ngoc Hoang Quan Nguyen

Moscow State Technical University of Civil Aviation; Vietnam Aviation Academy

Author for correspondence.
Email: quannnh@mail.ru
ORCID iD: 0009-0003-8873-9263

Postgraduate Student

Russian Federation, 20, Kronstadtsky Blvd., Moscow, 125493; Ward 8, 104 Nguyen Van Troi, Phu Nhuan District, Ho Chi Minh City, Vietnam

Vladimir N. Nechaev

Moscow State Technical University of Civil Aviation

Email: v.nechaev@mstuca.ru
ORCID iD: 0009-0005-9610-9397

Candidate of Historical Sciences, Associate Professor

Russian Federation, 20, Kronstadtsky Blvd., Moscow, 125493

Vyacheslav B. Malygin

Moscow State Technical University of Civil Aviation

Email: mbv898@yandex.ru
ORCID iD: 0009-0001-1375-4421

Applicant

Russian Federation, 20, Kronstadtsky Blvd., Moscow, 125493

References

Supplementary files