THE MULTIPLE CONNECTIONS MULTI-AIRPORT GROUND HOLDING PROBLEM - MODELS AND ALGORITHMS

In recent years air traffic has dramatically increased without a corre sponding development of airports. Therefore, airports' limited capacit y causes air traffic congestion and consequent expensive delays. The o nly strategy that can be applied in. the short term with low investmen ts 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 conges tion. We consider a traffic situation with ''multiple connections'' or ''banking,'' i.e., the situation where some flights are assigned a se t of ''preceding'' flights; no ''successive'' flight can start until a ll its preceding flights have landed. The problem consists of distribu ting delays to flights, so as to minimize the total delay cost, by res pecting airport capacity, connections, and time constraints imposed by airlines. We construct an integer linear programming model and we sol ve it to optimality with CPLEX. Because the computation time is too hi gh (hours) for real-world instances, we propose an alternative heurist ic algorithm, which shows a very low computation time (seconds) and ac ceptable errors when tested on 30 realistic instances with strongly di versified data.