A novel scaling-based landing first constructive heuristic algorithm for aircraft scheduling and parking problem in multi-runway airports

The aircraft scheduling and parking problem focuses on strategically optimizing landing, parking and take-off schedules to increase airport throughput, which is essential for efficient operations. This challenge is particularly urgent during emergencies at multi-runway airports, where rapid, high-quality scheduling is required to manage large-scale scenarios. This paper first develops a mixed-integer linear programming (MILP) model to formalize the problem. A novel scaling-based idea is then proposed to quickly generate an optimal or near-optimal solution sequence by deriving an exact parking plan from reduced-size, less complex instances. Additionally, a Landing-First (LF) strategy is proposed to convert the solution sequence into a complete scheduling plan. Moreover, extensive experiments compare the proposed algorithm with the exact CPLEX solution for small instances, and with the state-of-the-art approach for medium and large instances, including up to 604 aircraft and 5 runways. The results show that the proposed algorithm achieves an average gap between the upper and lower bounds approximately 2% smaller than that of the state-of-the-art approach, while requiring about one thousandth of its computing time. Finally, we validate the practical applicability of our approach through a case study on Xi’an Xianyang International Airport.