The Multiple Connections Multi-Airport Ground Holding Problem: Models and Algorithms

In recent years air traffic has dramatically increased without a corresponding development of airports. Therefore, airports' limited capacity causes air traffic congestion and consequent expensive delays. The only strategy that can be applied in the short term with low investments aims at the optimal management of present resources; its principal device is Ground Holding, which consists of delaying an aircraft take off whenever it is foreseen it will not land in time because of congestion. We consider a traffic situation with “multiple connections” or “banking,” i.e., the situation where some flights are assigned a set of “preceding” flights; no “successive” flight can start until all its preceding flights have landed. The problem consists of distributing delays to flights, so as to minimize the total delay cost, by respecting airport capacity, connections, and time constraints imposed by airlines. We construct an integer linear programming model and we solve it to optimality with CPLEX. Because the computation time is too high (hours) for real-world instances, we propose an alternative heuristic algorithm, which shows a very low computation time (seconds) and acceptable errors when tested on 30 realistic instances with strongly diversified data.