Airport Gate Assignment as a Nash Equilibrium Problem

Abstract

The airport gate assignment problem addresses the optimal assignment of a set of aircraft to a set of stands. The underlying combinatorial optimization problem is usually modeled as a binary quadratic assignment problem, whereby the stand assignment of a certain aircraft depends on the stand assignment of all other aircraft. The solving time of the optimization problem may increase exponentially with the number of aircraft and stands considered. For this reason, real-case scenarios can be solved only by heuristics in due time. In this paper, we propose a novel approach on modeling and solving the airport gate assignment problem by making use of the game theory. The aim is to identify a Nash equilibrium as a solution of the airport gate assignment problem in the following sense: no aircraft can improve its stand assignment by a sole deviation from its assigned stand. The algorithm is capable of delivering an assignment for a real-case scenario in minutes instead of hours. The performance of the algorithm is demonstrated by modeling and solving a real-case scenario for terminal 2 of the Munich Airport.