Distributionally Robust Airport Ground Holding Problem under Wasserstein Ambiguity Sets

본 논문은 공항 수용량 예측의 불확실성과 분포 이동을 고려하여 물러스틴 불확실성 집합을 기반으로 한 분포 강건 지상 대기 문제를 해결하고, 새로운 이중 분할 및 원상 복구 알고리즘을 통해 계산 효율성을 극대화함과 동시에 외표본 성능을 크게 향상시키는 방안을 제시합니다.

핵심

🌩️ 비유: "날씨 예보가 틀릴 때를 대비한 공항의 지혜"

상상해 보세요. 여러분이 공항에서 비행기를 기다리고 있는데, 갑자기 폭풍우가 몰아쳐 공항이 문을 닫을지 모릅니다.

1. 기존 방식 (예측에 의존하기):
   공항 관리자는 "내일 비가 오겠지만, 10% 정도만 지연될 거야"라고 한 가지 예측만 믿습니다. 그리고 그 예측대로 비행기들을 하늘에 띄워두거나 지상에 대기시킵니다.

   • 문제점: 만약 예보가 틀려서 폭풍우가 훨씬 더 심해지면? 비행기들이 하늘에 떠서 기름을 다 태우고, 승객들은 지친 채로 대기해야 합니다. 이는 엄청난 비용과 스트레스를 줍니다.

2. 이 논문이 제안하는 새로운 방식 (불확실성에 대비하기):
   "예보가 틀릴 수도 있잖아. 비가 조금 올 수도 있고, 태풍이 올 수도 있고, 아예 안 올 수도 있지."라고 생각합니다.
   이 논문은 **"예보가 틀릴 수 있는 모든 가능성 (확률 분포) 을 고려해서, 최악의 상황에서도 손해가 가장 적게 나는 계획"**을 세우는 방법을 개발했습니다. 이를 **'분포 강건 최적화 (Distributionally Robust Optimization)'**라고 합니다.

---

🔍 핵심 내용 3 가지

1. 왜 이 연구가 필요한가요? (기후 변화의 영향)

과거에는 "내일 날씨가 어떨지"를 과거 데이터로 쉽게 예측할 수 있었습니다. 하지만 기후 변화 때문에 이제는 과거의 패턴이 통하지 않습니다.

• 비유: 과거에는 "봄에는 꽃이 필 확률이 90%"라고 믿었는데, 기후 변화로 인해 갑자기 "봄에 폭설이 내릴 수도 있고, 가뭄이 들 수도 있다"는 식으로 날씨 패턴 자체가 뒤바뀌고 예측 불가능해졌습니다.
• 이 논문은 이런 **예측 불가능한 상황 (기후 변화로 인한 공항 수용 능력 변동)**에서도 공항 운영이 무너지지 않도록 돕는 '방탄 조끼' 같은 시스템을 만듭니다.

2. 어떻게 해결책을 찾나요? (수학의 마법)

연구진은 두 가지 강력한 수학적 도구를 섞어서 새로운 알고리즘을 만들었습니다.

• 켈리의 절단 평면법 (Kelly's Cutting Plane): 마치 미로를 풀 때, "여기는 길이 아니다"라고 벽을 하나씩 세워가며 길을 좁혀가는 방법입니다.
• 정수 L-형 방법 (Integer L-shaped Method): 큰 문제를 작은 조각으로 잘게 나누어 해결하는 방식입니다.
• 결과: 기존에 컴퓨터로 이 문제를 풀면 몇 시간 걸리던 것을, 이 새로운 방법은 10 배에서 100 배 이상 빠르게 풀어냅니다. (예: 24 시간 걸리던 것을 15 분 만에 해결!)

3. 실제로 효과가 있나요? (실험 결과)

연구진은 뉴어크 공항 (미국) 의 실제 데이터를 가지고 실험을 했습니다.

• 실험 설정: "날씨 예보가 틀려서 공항 수용 능력이 20% 나 떨어진다"거나 "날씨 변동성이 2 배가 된다"는 가상의 시나리오를 만들었습니다.
• 결과:
  • 기존 방식 (단순 예측) 은 예상치 못한 폭풍우가 오면 비용이 20~27% 나 폭증했습니다.
  • 이 논문의 새로운 방식은 최악의 상황에서도 비용을 20% 이상 절감했습니다.
  • 특히, **가장 극단적인 재해 상황 (CVaR)**에서 위험을 줄이는 데 탁월한 효과를 보였습니다.

---

💡 요약: 이 논문이 우리에게 주는 교훈

이 논문은 **"완벽한 예측을 기다리지 말고, 예측이 틀릴 때를 대비하라"**는 메시지를 전달합니다.

• 과거: "내일 날씨가 이럴 거야"라고 믿고 계획했다가, 날씨가 바뀌면 큰 손해를 보았다.
• 현재 (이 논문의 제안): "날씨가 이렇게 변할 수도, 저렇게 변할 수도 있어. 그중에서 가장 나쁜 경우를 상정하고 계획을 세우자."
• 효과: 조금 더 보수적으로 (안전하게) 계획을 세우는 대신, 갑작스러운 재해 (기후 변화 등) 가 왔을 때 시스템이 무너지지 않고, 오히려 비용을 크게 아낄 수 있다.

마치 우산을 들고 나가는 것과 같습니다.
비가 올 확률이 10% 라면, "안 올 거야"라고 믿고 우산을 안 들고 나가는 게 편할 수 있습니다. 하지만 기후 변화로 인해 비가 올 확률이 불규칙해지고, 한 번 오면 폭우가 될 수 있다면, 비가 오지 않아도 우산 (이 논문의 알고리즘) 을 챙기는 것이 훨씬 현명하고 경제적이라는 것입니다.

이 기술이 실제 공항에 적용된다면, 기후 변화로 인한 폭풍우 속에서도 비행기 지연이 줄어들고, 승객들은 더 편안하게 여행을 즐길 수 있게 될 것입니다.

기술 요약

1. 문제 정의 (Problem Definition)

배경 및 동기:
항공 교통 시스템에서 수요와 수용 능력 (Capacity) 의 불균형은 항공사, 승객, 환경에 심각한 부정적 영향을 미칩니다. 이를 해결하기 위해 항공 관제 당국은 공항의 도착 수용 능력이 감소할 때 항공기를 지상에서 대기시키는 **지상 지연 프로그램 (Ground Delay Programs, GDPs)**을 운영합니다. 지상 대기 비용은 비행 중 대기 비용보다 훨씬 낮기 때문에, 항공기를 지상에 머물게 하는 것이 비용 효율적입니다.

핵심 도전 과제:
기존의 확률적 최적화 (Stochastic Programming) 모델은 미래의 공항 수용 능력을 예측하는 확률 분포에 의존합니다. 그러나 기후 변화, 운영적 교란, 예측 오차 등으로 인해 실제 수용 능력의 분포가 예측된 분포와 달라지는 분포 이동 (Distribution Shift) 현상이 빈번하게 발생합니다. 이러한 분포 이동이 발생할 때, 단일 예측 분포에 최적화된 정책은 실제 환경 (Out-of-sample) 에서 성능이 급격히 저하될 수 있습니다.

연구 목표:
본 논문은 공항 수용 능력의 불확실성뿐만 아니라, 그 확률 분포 자체의 불확실성 (Uncertainty of Uncertainties) 을 고려하여, **Wasserstein 모호성 집합 (Wasserstein Ambiguity Set)**을 기반으로 한 분포 강건 최적화 (Distributionally Robust Optimization, DRO) 프레임워크를 단일 공항 지상 대기 문제 (dr-SAGHP) 에 적용하는 것을 목표로 합니다.

---

2. 방법론 (Methodology)

2.1 수학적 모델링 (dr-SAGHP)

• 2 단계 확률적 프로그래밍: 1 단계에서는 항공기의 지상 대기 시간을 결정하고, 2 단계에서는 실제 수용 능력 시나리오가 실현된 후 비행 중 대기 (Airborne Holding) 를 결정합니다.
• Wasserstein 모호성 집합: 추정된 경험적 분포 $\hat{P}$를 중심으로 Wasserstein 거리 (거리 측정치) $\epsilon$ 이내의 모든 가능한 분포 $q$를 포함하는 집합을 정의합니다.
• 최악의 경우 기대값 최소화: 추정된 분포에 대한 기대 비용이 아닌, 모호성 집합 내의 모든 분포에 대해 발생하는 **최악의 경우 기대 비용 (Worst-case Expected Cost)**을 최소화하는 정책을 찾습니다.
  $$\min_{x} \left( \text{Ground Cost} + \max_{p \in \mathcal{P}_\epsilon(\hat{P})} \mathbb{E}_{p}[Q(x, \xi)] \right)$$

2.2 결정적 동등 형식 (Deterministic Equivalent)

• Esfahani 와 Peyman (2018) 의 방법을 차용하여 내부 최대화 문제를 쌍대 (Dual) 문제로 변환하고, 이를 1 단계 문제에 통합하여 결정적 동등 형식을 유도했습니다.
• 그러나 이 형식은 시나리오 수에 따라 제약 조건이 이차적으로 증가하여 대규모 문제에서 계산 비용이 매우 큽니다.

2.3 효율적인 분해 알고리즘 (Decomposition Algorithm)
대규모 문제를 해결하기 위해 저자들은 **Kelly 절단 평면법 (Cutting Plane Method)**과 **정수 L-형 방법 (Integer L-shaped Method)**을 결합한 새로운 알고리즘을 개발했습니다.

• 핵심 아이디어: Kelly 의 절단 평면법에서 필요한 **서브그래디언트 (Subgradient)**를 효율적으로 계산하기 위해 분포 강건 문제의 구조를 활용합니다.
• 이중 이분법 (Dual Bisection): Wasserstein 모호성 집합 내의 최악의 분포를 찾기 위한 쌍대 변수 ($\lambda$) 를 구하기 위해 이분법을 사용합니다.
• 원형 복구 (Primal Recovery): 최적의 쌍대 해를 통해 최적의 운송 계획 (Transportation Plan) 과 최악의 분포를 복원하는 알고리즘을 설계했습니다.
• 알고리즘 흐름:
  1. 1 단계 결정 변수 $x$를 고정.
  2. 이중 이분법으로 최악의 분포 $p^*$ 및 관련 쌍대 변수 계산.
  3. Danskin 정리를 활용하여 목적 함수의 서브그래디언트 계산.
  4. 계산된 서브그래디언트로 절단 평면 (Cut) 을 생성하여 1 단계 문제를 업데이트.
  5. 정수 L-형 방법의 분기 - 절단 (Branch-and-Cut) 프레임워크 내에서 반복 수행.

---

3. 주요 기여 (Key Contributions)

1. 분포 강건 SAGHP 모델 제안: 기후 변화 및 예측 오차로 인한 분포 이동에 대비하여, 공항 수용 능력 분포의 부정확성을 명시적으로 헤지 (Hedge) 하는 단일 공항 지상 대기 문제를 최초로 공식화했습니다.
2. 고효율 분해 알고리즘 개발: 두 단계 분포 강건 정수 계획법 (Two-stage DRO Integer Programs) 에 적용 가능한 새로운 알고리즘을 제시했습니다. 이는 Kelly 절단 평면법과 정수 L-형 방법을 결합하고, 서브그래디언트 계산을 위한 이중 이분법 및 원형 복구 기법을 포함하여 계산 효율성을 극대화했습니다.
3. 실증적 평가 및 기후 변화 시나리오 분석:
   • Gaussian Process Regression (GPR) 을 사용하여 공항 수용 능력 시나리오를 생성했습니다.
   • GPR 모델의 평균과 분산을 인위적으로 조작하여 기후 변화로 인한 수용 능력 저하 (평균 감소) 및 예측 불확실성 증가 (분산 증가) 시나리오를 시뮬레이션했습니다.
   • 기존 확률적 모델 (s-SAGHP) 과의 비교를 통해 분포 이동 하에서의 성능을 평가했습니다.

---

4. 실험 결과 (Results)

4.1 계산 성능 (Computational Performance)

• 제안된 알고리즘 (K-IL) 은 직접적인 결정적 형식 (DE) 을 푸는 것보다 12.87 배에서 102.25 배까지 빠른 속도를 보였습니다.
• 최적성 간극 (Optimality Gap) 은 0% ~ 0.063% 로 거의 무시할 수 있을 정도로 작아, 계산 효율성과 정확성을 동시에 달성했습니다.

4.2 분포 이동 하의 성능 (Out-of-Sample Performance)

• 평균 감소 시나리오 (Mean Reduction): 기후 변화로 인해 공항 수용 능력이 평균적으로 감소하는 상황 (5%~20% 감소) 에서, dr-SAGHP 는 s-SAGHP 대비 최대 27.20% 까지 기대 비용을 절감했습니다. 감소 폭이 클수록 dr-SAGHP 의 우위가 두드러졌습니다.
• 분산 증가 시나리오 (Variance Increase): 예측 불확실성이 커지는 상황에서도 dr-SAGHP 는 극단적 리스크 (Tail Risk) 를 효과적으로 관리했습니다.
  • CVaR (Conditional Value-at-Risk) 개선: 극단적인 상황 (Tail) 에서의 비용이 s-SAGHP 대비 최대 26% 감소했습니다.
  • 트레이드오프: 분산 증가가 mild 한 경우 s-SAGHP 가 약간 더 낮은 기대 비용을 보일 수 있으나, dr-SAGHP 는 극단적 리스크에 대한 강력한 보호막을 제공합니다.

4.3 모호성 반경 ($\epsilon$) 의 영향

• $\epsilon$이 증가함에 따라 정책은 더 보수적이 되어 인-sample 비용은 증가하지만, 분포 이동이 발생하는 out-of-sample 상황에서는 성능이 크게 향상됩니다.
• 기후 변화로 인한 심각한 분포 이동이 예상될 때는 큰 $\epsilon$을 선택하는 것이, 안정적인 상황에서는 작은 $\epsilon$ (또는 s-SAGHP) 을 사용하는 것이 바람직함을 시사합니다.

---

5. 의의 및 결론 (Significance & Conclusion)

• 기후 변화 대응: 기후 변화로 인해 과거 데이터 기반의 확률 분포가 더 이상 유효하지 않은 시대에, 분포 강건 최적화 (DRO) 는 항공 교통 관리 시스템의 회복탄력성 (Resilience) 을 높이는 핵심 도구임을 입증했습니다.
• 실용적 가이드라인: 운영 환경이 안정적일 때는 기존 확률적 모델을 사용하되, 기후 변화 등으로 인한 불확실성이 커지거나 분포 이동이 예상될 때는 분포 강건 모델을 적용하여 극단적 리스크를 관리해야 함을 제안합니다.
• 확장성: 제안된 알고리즘은 단일 공항뿐만 아니라 다중 공항 문제 (MAGHP) 나 다단계 동적 결정 문제로 확장 가능하여, 향후 항공 교통 시스템 전반의 최적화 기법으로 활용될 잠재력이 큽니다.

요약하자면, 이 논문은 기후 변화와 예측 불확실성이라는 현실적인 도전에 대응하기 위해, 이론적으로 엄밀하고 계산적으로 효율적인 분포 강건 지상 대기 정책 프레임워크를 제시하며, 이를 통해 항공 시스템의 비용 절감과 운영 안정성을 동시에 달성할 수 있음을 증명했습니다.