On the Optimality Gap of Full Airport Slot Assignments: Capacity-Limited Packing with Pareto Optimality Constraints

We study a combinatorial packing problem with Pareto optimality constraints which arises naturally in the aviation industry. In fact, it has been observed that the current practice of assigning takeoff and landing rights at major airports may result in a significant gap between full and maximal flight schedules in practice. We analyze the specific packing problem theoretically and, particularly, study the occurring optimality gap under the prevailing regulatory regimes at the major airports in Germany. Finally, we report on the findings of a computational study based on real-world flight requests for one highly congested German airport.