Approximate Dynamic Programming Approach for Airport Gate Assignment Problem

Abstract

In real-world airport gate assignment problem (AGAP), the planning of flight-to-gate assignments involves more than a thousand of flights and is subject to frequent real-time adjustments. Thus, an efficient solution approach for AGAP is required for airport operation in practice. Here, we propose an approximate dynamic programming (ADP) approach for AGAP. In our ADP approach, value function is approximated by the interpolation of upper bound and lower bound of true value function with consideration of lookahead horizon. Heuristic algorithms and the linear programming relaxation values of integer programming (IP) models for AGAP are used for the upper bound and the lower bound, respectively. We first compare the bounds for several IP models and show that the pattern-based model provides the strongest bound, whose size is exponential to the input size. Next, we propose an efficient column generation method and ADP acceleration techniques to over the computational complexity arising when using the pattern-based model. The effectiveness and practicality of our ADP approach were demonstrated by computational experiments.

본 연구에서는 공항 운영상의 제약을 고려하여 항공기를 게이트에 적절히 배분하는 공항 게이트 할당 문제를 다룬다. 현실에서는 많은 수의 항공기와 게이트를 고려해야 하고, 동시에 상황 변화에 따른 계획의 재수립이 빈번하여, 이에 유연하고 신속하게 대처할 수 있는 효율적인 방법이 필요하다. 이를 위해 본 연구에서는 전방 탐색 길이를 고려한 근사동적계획 해법을 제안한다. 근사동적계획법에서 가치함수를 추정하기 위해 패턴기반모형의 선형계획완화문제의 하한을 활용한다. 패턴기반모형은 강한 하한을 제공하나 지수적으로 많은 개수의 변수를 가지고 있어 이 모형을 활용할 시 매우 큰 계산적 부담이 발생한다. 이 문제점을 극복하기 위해 효율적인 열생성 방법 및 근사동적계획 가속화 기법을 제안한다. 다양한 실험을 통해 열생성 방법 및 근사동적계획 가속화 기법의 효과성을 확인하였다. 그리고 실제 데이터에 기반한 실험을 통하여 제안한 해법이 기존 방법 대비 합리적인 시간 내에 좋은 성능의 해를 제공하는 것을 확인하였다.