This article presents an exact algorithm that is combined with a heuristic method to find the optimal solution for an airplane landing problem. For a given set of airplanes and runways, the objective is to minimize the accumulated deviations from the target landing time of the airplanes. A cost associated with landing either earlier or later than the target landing time is incurred for each airplane within its predetermined time window. In order to manage this type of large-scale optimization problem, a set partitioning formulation that results in a mixed integer linear program is proposed. One key contribution of this article is the development of a branch-and-price methodology, in which the column generation method is integrated with the branch-and-bound method in order to find the optimal integer solution. In addition to the exact algorithm, a simple heuristic method is also presented to tighten the solution space. Numerical experiments are undertaken for the proposed algorithm in order to confirm its effectiveness using public data from the OR-Library. As an application in the real-world situation of airplane landing, air traffic data from Incheon International Airport is employed to assure the efficiency of the proposed algorithm.
본 논문에서는 항공기 도착 문제에 대한 최적해를 구하기 위하여 휴리스틱 알고리즘을 결합한 최적 알고리즘을 제안하였다. 주어진 항공기와 활주로 집합에 대하여, 목적함수는 착륙하는 항공기들의 목표 도착시각에 대한 실제 도착시각의 누적 편차를 최소화하는 것이다. 착륙하는 모든 항공기에 대하여, 이미 정의된 시간 창 형태의 목표 도착시각보다 일찍 도착하거나 늦게 도착하였을 때 비용이 발생한다. 이러한 형태의 대형 최적화 문제를 해결하기 위하여, 집합 분할 개념을 활용한 혼합정수선형계획법에 기반하여 항공기 도착 문제를 새로이 설정하였다. 본 논문의 핵심적인 의의는 열 생성 기법과 분기한정법을 통합한 분지평가 해법을 구현한 것이라 할 수 있다. 제안된 최적 알고리즘 외에도 해 공간을 축소시키기 위하여 간단한 휴리스틱 기법도 제시하였다. 제안된 알고리즘의 유효성을 검증하기 위하여 '오알-라이브러리(OR-Library)'에서 제공되는 공용 데이터를 사용한 수치 실험을 수행하였다. 또한, 항공기 도착에 대한 실제 상황을 적용하기 위하여 인천국제공항에 착륙하는 항공교통 데이터를 적용하여 제안된 알고리즘의 효율성을 확인하였다.
