This thesis considers Airport Gate Assignment Problem (AGAP) which is finding an effective gate schedule while satisfying passengers walking distance, space restriction and ground time conditions. The objective of this problem is finding a robust solution which is quite insensitive to variation in flight schedule. Even though the idle time between two consecutive flights is assumed to be uncertain, a solution can be accomplished by the robust combinatorial optimization. We formulate this problem as an integer linear program (ILP) using variables corresponding to flight series which can be assigned to a certain gate. To solve the problem, we develop a branch and price algorithm where an efficient branching rule is adopted. Furthermore, we stabilize the column generation to accelerate a convergence. The pricing problem is solved easily by composing networks for each gate separately. To test the performance of the algorithm, we have tested the algorithm with real flights and gates data provided by Incheon International Airport. Computational results are reported.
이 논문은 주기장 배정 문제 ( Gate Assignment Problem ) 에 대해 다루고 있다. 주기장 배정 문제는 승객의 이동거리, 주기장 공간 제약, 주기 시간 제약 조건을 만족하면서도 효과적인 주기장 스케줄을 찾는 문제이다. 이 문제의 목적은 정해진 스케줄 변동에도 민감하지 않은 강건한 해 ( robust solution ) 를 찾는 것이다. 심지어 두 연속된 항공기 사이의 idle time이 불확실하다고 가정된 상황에서도, robust optimization을 이용하여 해를 얻어낼 수 있다. 이 문제를 하나의 flight series에 대응하는 변수를 도입하여, 정수 계획 문제로 formulate하였다. 이 문제를 풀기 위하여, 분지 평가법 ( branch and price algorithm) 을 이용하였으며, 빠른 convergence를 위해 열생성 기법 ( column generation ) 을 stabilize 했다. 부문제 ( pricing problem ) 는 주기장 별로 네트워크를 형성하여 쉽게 해를 구했다. 이 알고리즘의 성능을 시험하기 위해, 실제 인천 공항의 데이터를 이용하였다.
