Robust Aircraft Scheduling in Point Merge System Under Uncertainties

Abstract

This dissertation reports on the scheduling algorithms in the Point Merge System (PMS). Specifically, two problems are addressed: a scheduling problem without uncertainties, including a holding pattern, and a robust scheduling problem considering uncertainties. In the PMS, the scheduling algorithm including a holding pattern is described based on the previous result, a PMS scheduling algorithm. The PMS configuration is transformed to a node--link structure, and the optimization problem is formulated using binary and integer variables. The conventional Mixed Integer Linear Programming (MILP) formulation cannot be directly applied to the transformed node-link structure because of the characteristics of holding patterns. Thus, to apply the MILP formulation to the proposed PMS holding algorithm, the route structure is changed, and virtual fixes are introduced. Several suitable constraints such as first-in-first-out and discrete holding delay constraints are introduced to incorporate the characteristics of the holding procedure in the MILP formulation. Moreover, the robust scheduling algorithm of the PMS is provided considering the uncertainties of the Estimated Time of Arrival (ETA) and Continuous Descent Approach (CDA). The methodology of robust optimization is described. Because the uncertain constraint can be converted to a deterministic constraint through the chance constraint, the ETA and CDA uncertainty models are assumed to follow a normal distribution. In particular, the dependence of the ETA uncertainty on the remaining flight time, and the correlation between the previous and subsequent uncertainties are reflected through a multivariate normal distribution. The sliding window technique is used to reduce the computation load in the numerical simulation. The numerical simulations demonstrate the performance of the proposed scheduling algorithms. The Monte Carlo simulation results show that the PMS algorithm considering a holding pattern exhibits a high aircraft capability and an additional degree of freedom. Moreover, the performance of the robust scheduling algorithm is evaluated in terms of the number of constraint violations, average delay, and amount of schedule change. The Monte Carlo simulation indicates that the robust scheduling algorithm corresponds to fewer constraint violations and reduces the amount of schedule change.

본 논문에서는 포인트 머지 시스템에서의 스케줄링 알고리즘을 제시하였다. 불확실성이 없는 상황에서 홀딩패턴(Holding Pattern)을 포함한 포인트 머지 시스템(Point Merge System)의 스케줄링 문제와 불확실성이 존재하는 상황에서 포인트 머지 시스템의 스케줄링 문제를 각각 고려하였다. 불확실성이 없을 때 홀딩패턴을 포함한 포인트 머지 시스템에서의 스케줄링 알고리즘은 노드 링크 구조로 모델링하였으며, 이산 변수와 정수 변수를 이용하여 최적화 문제를 공식화하였다. 홀딩패턴의 특성 때문에 기존의 노드 링크 구조 기반의 혼합정수 선형계획법을 적용할 수 없으므로, 가상의 픽스를 도입하고 노드 링크 구조를 변경하여 혼합정수 선형계획법 기반의 최적화 문제를 제시하였다. 이 과정에서 선입선출 조건과 홀딩패턴의 이산 시간지연 조건을 추가하여 홀딩패턴의 특성을 스케줄링 알고리즘에 반영하였다. 한편, 예상도착시간과 연속강하접근의 불확실성을 고려한 포인트 머지 시스템에서의 강건 스케줄링 알고리즘을 제시하였다. 강건 최적화 방법론에 따르면 정규분포를 따르는 불확실한 매개변수가 포함된 구속조건은 확률제한 구속조건을 이용하여 불확실성이 포함되지 않은 구속조건으로 변환될 수 있다. 따라서 예상도착시간과 연속강하접근의 불확실성이 정규분포를 따른다고 가정하고 모델링을 수행하였다. 예상도착시간의 불확실성은 연속강하접근의 불확실성과는 달리 확률분포가 잔여비행시간에 의존하고 이전 시간의 불확실성과 다음 시간의 불확실성 사이의 관계가 존재하므로 다변수 정규분포를 이용하여 모델링하였다. 알고리즘의 계산량을 감소시키기 위해 슬라이딩 윈도우 기법을 사용하였다. 본 논문에서 제시된 스케줄링 알고리즘의 성능을 평가하기 위해 수치 시뮬레이션을 수행하였다. 먼저, 몬테 카를로 시뮬레이션을 통해 홀딩패턴이 포함된 포인트 머지 시스템의 스케줄링 알고리즘의 효과를 검증하였다. 시뮬레이션 결과, 홀딩패턴이 포함될 경우 관제사의 개입률이 감소하였으며, 스케줄링의 자유도가 증가함에 따라 시간 지연량에도 이득이 있음을 확인하였다. 다음으로 불확실성을 고려하는 강건 스케줄링 알고리즘의 성능을 검증하기 위해 구속조건 위반 횟수와 평균 시간지연량, 스케줄 변동량을 기준으로 분석하였다. 몬테 카를로 시뮬레이션을 수행한 결과, 불확실성을 고려하지 않은 일반 스케줄링 알고리즘에 비해 강건 스케줄링 알고리즘은 불확실성에 의해 스케줄이 변동되는 스케줄 변동량과 구속조건 위반 횟수에서 유의미한 성능 향상이 있음을 보였다.