A GRASP Algorithm for Multi-objective Airport Gate Assignment Problem

Abstract

The assignment of flights to appropriate gates is a complex combinatorial optimization problem that airport managers have to deal with every day. It is an important decision-making problem involving multiple and conflicting objectives. Considering the different stakeholders of the problem, a multi-objective airport gate assignment problem is proposed and formulated as a Binary Integer Programming Model. This paper studies two main objectives, namely maximizing total flight-to-gate assignment utility and minimizing total flight conflict probability. Unlike most of the mathematical models presented in the literature, Airport Gate Assignment Problem is considered an over-constraint problem where flight-to-gate eligibility, apron safety and night-stand flight constraints are involved. As a solution methodology, a Greedy Randomized Adaptive Search Procedure (GRASP) algorithm on over-constrained AGAP is proposed since the algorithm produces a series of good features such as intuitive greedy appeals and is trivial to be efficiently implemented on parallel processors like gates. The paper aims to demonstrate the efficiency of the proposed solution methodology concerning determined objective functions.