ASPaeroFlow: Decomposition Heuristics for Joint Air Traffic Flow & Capacity Management

우리 머리 위의 하늘을 끝없는 푸른 빈 공간이 아니라, 보이지 않는 방들로 이루어진 북적이는, 보이지 않는 도시라고 상상해 보십시오. 이 방들은 "섹터(sectors)"라고 불리며, 도시에서 가장 스트레스가 많은 경호원처럼 행동하는 항공 교통 관제사 팀에 의해 관리됩니다. 그들의 임무는 한 방에 들어가려는 비행기의 수가 그 방이 안전하게 수용할 수 있는 인원을 초과하지 않도록 하는 것입니다. 너무 많은 비행기가 끼어들려고 하면 관제사들은 압도당하고 안전이 위험에 처하게 됩니다.

수십 년 동안 이 하늘 도시를 관리하는 시스템은 두 개의 별개 차선으로 작동해 왔습니다. 한 차선은 비행기에게 지상에서 대기하도록 지시하거나(지연) 다른 경로로 가도록 지시하여(경로 재설정) 교통 체증을 해결하려고 노력합니다. 다른 한 차선은 벽을 재배치하여 방을 더 크게 만들거나 작게 만드는 방식으로(공역 구성 변경) 방 자체를 수정하려고 노력합니다. 문제는 이 두 차선이 서로 대화하지 않는다는 점입니다. 이는 마치 고속도로에 새로운 차선을 열 수 있다는 사실은 무시한 채, 자동차들에게 기다리라고만 말하며 교통 체증을 해결하려는 것과 같습니다. 이러한 분리는 혼란스러운 순환을 만듭니다. 즉, 방의 크기가 얼마나 커질지 알기 전에는 얼마나 많은 비행기를 지연시켜야 할지 알 수 없고, 얼마나 많은 비행기가 올지 알기 전에는 방을 어떻게 더 크게 만들지 알 수 없는 것입니다.

여기서 ASPaeroFlow라고 불리는 새로운 접근 방식이 등장합니다. 이것을 하늘 전체를 한눈에 내려다보는 초스마트하고 모든 것을 알고 있는 교통 관리자로 생각하십시오. 이 방식은 비행기와 방 문제를 각각 따로 해결하는 대신, 두 문제를 동시에 해결하려고 시령합니다. 하지만 하늘은 너무나 거대하고 가능한 조합의 수가 너무 많아서, 세계에서 가장 빠른 슈퍼컴퓨터조차 완벽한 답을 찾으려다 막히곤 합니다. 이는 마치 수십억 개의 조각이 있는 퍼즐을 풀 때, 모든 조각을 다른 모든 조각과 일일이 대조하며 확인하려는 것과 같으며, 시간이 너무 오래 걸립니다.

이 논문의 저자들인 오스트리아, 독일, 프랑스의 연구팀은 영리한 지름길이 필요하다는 것을 깨달았습니다. 그들은 전체 퍼즐을 한꺼번에 풀려고 하지 않았습니다. 대신 "분해(decomposition)"라는 방법이 발명했습니다. 거대하고 어지러운 물건들로 가득 찬 방을 상상해 보십시오. 방 전체를 한 번에 치우려고 하는 대신, 딱 한 구석에만 집중하여 그곳을 완벽하게 치운 다음 다음 구석으로 이동하는 것입니다. 이 논문은 거대한 하늘 문제를 작고 관리 가능한 지역 문제들로 나누고 그 문제들을 완벽하게 해결함으로써, 압도당하지 않고 전체적인 혼란을 정리할 수 있다고 제안합니다.

핵심 아이디어: 하늘을 한 입 크기의 조각들로 나누기

이 논문의 핵심은 ASPaeroFlow라는 새로운 도구입니다. 저자들은 이 도구를 "결합 항공 교통 흐름 및 용량 관리(Joint Air Traffic Flow and Capacity Management)" 문제를 처리하기 위해 구축했습니다. 쉬운 말로 설명하자면, 그들은 비행기(흐름)와 공역의 방(용량)을 정확히 동시에 관리하는 최선의 방법을 찾아내고자 했습니다.

저자들은 기존의 방식, 즉 비행기를 먼저 해결하거나 방을 먼저 해결하는 방식이 최선이 아니라고 주장합니다. 그들은 모든 것을 한꺼번에 해결하려고 할 때 훨씬 더 좋은 결과를 얻지만, 그것이 계산하기 매우 어렵다는 것을 발견했습니다. 이를 극복하기 위해 그들은 **답 집합 프로그래밍(Answer Set Programming, ASP)**이라는 기술을 사용했습니다. ASP를 복잡한 퍼즐을 푸는 데 탁-월한, 매우 논리적이고 규칙을 따르는 로봇이라고 생각하면 됩니다. 다만 퍼즐이 너무 커지면 속도가 느려질 수 있습니다.

따라서 팀은 로봇의 두뇌와 "분할 정복(divide and conquer)" 전략을 결합했습니다. 그들의 알고리즘이 작동하는 단계는 다음과 같습니다:

1. 문제 포착: 시스템은 하늘을 살피며 첫 번째 "과부하된" 섹터(너무 많은 비행기가 들어있는 방)를 찾아냅니다.
2. 확대: 전체 세상을 보는 대신, 바로 그 문제 지점과 관련된 몇몇 비행기에만 초점을 맞춥니다. 이를 통해 아주 작은 국소적 버전의 문제를 만듭니다.
3. 국소적으로 모든 경우의 수 시도: 이 작은 문제에 대해, 시스템은 논리적 로봇(ASP)을 사용하여 가능한 모든 조합의 해결책을 시도합니다. "이 비행기를 지연시키면 어떻게 될까? 저 비행기의 경로를 바꾸면 어떨까? 이 방을 두 개의 작은 방으로 나누면 어떨까?"라고 묻는 것입니다.
4. 최선의 선택: 과부하를 제거하는 가장 좋은 국소적 해결책을 선택합니다.
5. 반복: 지도를 업데이트하고 다음 문제 지점을 찾아, 하늘이 깨끗해질 때까지 이 과정을 반복합니다.

그들이 발견한 것: 벽을 움직이는 힘

연구진은 작은 가상의 시나리오부터 수천 개의 항공편과 유럽 및 미국의 복잡한 지도를 포함한 거대한 실제 규모의 시뮬레이션에 이르기까지 다양한 테스트를 수행했습니다. 그들은 이들의 새로운 도구를 오늘날 항공사들이 사용하는 기존의 "선착순(First-Come, First-Served)" 규칙뿐만 아니라 다른 고급 수학 모델들과 비교했습니다.

주요 발견 사항은 다음과 같습니다:

1. 동시 해결이 순차적 해결보다 낫다
이 논문은 문제를 한꺼번에 해결하는 것(비행기와 방을 함께 수정)이 단계적으로 하는 것보다 우월하다고 제안합니다. 방을 먼저 수정하고 그다음 비행기를 수정하는 방식(순차적 접근)을 시도했을 때, 방이 유일한 문제였던 경우에는 잘 작동했습니다. 하지만 방을 충분히 수정해도 교통량을 감당할 수 없는 상황이라면 순차적 접근 방식은 막혀버렸습니다. 반면, 동시 접근 방식은 지연, 경로 재설정, 방 변경을 혼합하여 다른 방식들이 실패한 곳에서도 해결책을 찾아낼 수 있었습니다.

2. "방"이 "비행기"보다 중요하다
교통 체증을 실제로 해결하는 것이 무엇인지에 대한 가장 놀라운 발견 중 하나였습니다. 저자들은 어떤 기능이 가장 큰 역할을 하는지 알아보기 위해 특정 기능을 꺼보는 "절제 연구(ablation study)"를 실시했습니다. 그 결과, **공역 구조 조정(방 변경)**이 단순히 비행기를 움직이는 것보다 지연과 과부하를 줄이는 데 훨씬 더 큰 영향을 미친다는 것을 발견했습니다.
이렇게 생각해 보십시오. 작은 거실에 파티가 열렸는데 50명이 나타났다면, 몇 명에게 밖에서 기다리라고 하거나(지연) 주방으로 가라고 할 수 있습니다(경로 재설정). 하지만 가장 효과적인 해결책은 벽을 허물고 거실과 식당을 합치는 것입니다(구조 조정). 이 논문은 하늘에서도 "벽을 허무는 것"(섹터 나누기)이 우리가 가진 가장 강력한 도구라고 제nd합니다.

3. 실제 규모에서도 작동한다
저자들은 자신들의 방법이 "산업 규모"의 사례들을 처리할 수 있음을 보여주었습니다. 시뮬레이션에서 그들은 최대 31,622개의 항공편과 19,000개 이상의 항행 지점을 가진 그래프를 테스트했습니다. 정확한 수학적 모델들(전체 퍼즐을 한 번에 완벽하게 풀려는 모델들)은 이러한 대규모 문제에서 작동이 멈추거나 메모리 부족 현상을 겪었지만, ASPaeroFlow는 합리적인 시간 내에 해결책을 찾아내며 계속해서 작업을 수행했습니다.

4. 기존 규칙보다 뛰어나다
기존의 "선착순" 방식(CASA라고 불림)과 비교했을 때, 이 새로운 도구는 지상에서 대기해야 하는 비행기의 수를 현저히 줄였습니다. 테스트 결과, 새로운 방식은 거의 모든 교통 체증을 해결한 반면, 기존 방식은 많은 문제를 해결하지 못한 채 남겨두었습니다.

한계와 미래

이 논문은 이것이 모든 것을 즉각 해결하는 마법 지팡이가 아님을 주의 깊게 명시하고 있습니다. 이 방법은 "휴리스틱(heuristic)"인데, 이는 매우 잘 작동하는 똑똑한 추측이지만, 전체 하늘에 대해 수학적으로 절대적인 "완벽한" 답을 보장하지는 않는다는 의미입니다. 이 방식은 작은 조각들을 완벽하게 해결함으로써 매우 좋은 답을 찾아내는 것입니다.

저자들은 또한 현재 모델이 날씨와 비행기가 계획대로 정확하게 움직인다고 가정한다는 점을 지적했습니다. 현실 세계에서는 폭풍이나 기계적 결함이 발생합니다. 그들은 향후 연구가 이러한 "확률적 교란(stochastic disruptions, 무작위적인 돌발 상황)"을 다루어야 하며, 인간 관제사가 컴퓨터의 결정을 신뢰할 수 있도록 컴퓨터가 왜 특정 결정을 내렸는지 설명해 주는 "설명 가능한 AI(Explainable AI)"를 사용해야 한다고 제안합니다.

결론적으로, 이 논문은 항공 교통 관리의 미래가 비행기를 움직일 것인가 아니면 벽을 움직일 것인가를 선택하는 문제가 아니라고 시사합니다. 그것은 두 가지를 동시에 수행하며, 거대하고 불가능해 보이는 문제를 작고 해결 가능한 덩어리로 나누는 스마트한 전략을 사용하는 것입니다. 컴퓨터가 "벽을 허물고" "비행기를 움직이는" 일을 동시에 할 수 있게 함으로써, 우리는 하늘을 조금 더 원활하게 흐르게 만들 수 있을 것입니다.