A selection hyper-heuristic approach to the single airport slot allocation problem
针对机场时刻分配问题，提出一种基于自适应大邻域搜索的超启发式方法，能在两小时内给出接近最优的解，优于商业求解器。
There is a significant imbalance between air traffic demand and airport capacity at many congested airports. As a result, airlines are required to request time slots for aircraft take-off or landing. The effective allocation of slots forms the basis of the single airport slot allocation problem. A significant amount of existing research on this problem focuses on mathematical modelling and exact solution methods for relatively small-scale problem instances. As the computational effort required for such approaches can be prohibitive as the size of a problem increases, heuristic search methods are often deployed as a more practical alternative. In this paper, we propose a new hyper-heuristic solution approach based on adaptive large neighbourhood search. The proposed approach consists of two stages, a constructive stage, which quickly generates initial feasible solutions, and an improvement stage, which attempts to improve an incumbent solution through an iterative process of destroy and repair. In the improvement stage, five destroy operators are used to modify a solution, including a novel operator which identifies a set of related slot requests to be rescheduled. The destroy operators are selected by an adaptive selection hyper-heuristic according to their past performance. The results using data from a real-world airport show that the proposed approach can provide near-optimal solutions within two hours, whereas a commercial solver can only find feasible solutions of much lower quality within the same time frame.