Heuristic search for allocation of slots at network level
Heuristic search for allocation of slots at network level
复制标题
DOI：
10.1016/j.trc.2017.03.015
复制
发表时间：
2018
影响因子：
8.3
通讯作者：
Una Benlic
中科院分区：
文献类型：
--
作者：
Una Benlic
本文考虑了协调（拥挤）机场网络的起降时刻分配，其中术语“起降时刻”是指特定日期的某个时间，该时刻允许承运人使用全套机场基础设施，以便在起降时刻控制的机场着陆和起飞。我们考虑了现有的 IATA 规则和指南：航班时刻请求的优先级、每个机场的容量限制、同一架飞机到达和随后起飞之间的最短周转时间，以及分配到一系列航班时刻而不是单个航班时刻。考虑到问题的复杂性，我们提出了一种方法，其中包括（i）建设性的启发式程序，从网络中为每个机场生成可行且一致的航班时刻分配，以及（ii）迭代启发式，以提高初始可行解决方案在航班延误（分配的航班时刻与航空公司请求之间的时间差）方面的质量。为了评估该方法在实际操作中是否实用，我们对一组生成的跨越整个调度季节的基准实例进行测试。这些实例因网络中机场的数量以及给定网络中机场之间的请求分布而异 - 形成网络的最大机场数量为 100 个，而每半年考虑的最大飞机起降总数超过 4.6·10 6。我们提供了与独立考虑网络中每个机场（忽略航路约束）时获得的解决方案的计算比较。这些结果表明，考虑航路约束可以确保始发地和目的地机场的航班时刻分配一致，但只会轻微降低航班时刻表延误和未满足请求的数量。此外，我们研究了容量减少场景的启发式性能。
This paper considers the allocation of slots for a network of coordinated (congested) airports, where the term “slot” refers to a time on a specific day when a carrier is given permission to use the full range of airport infrastructure for the purpose of landing and take-off at a slot-controlled airport. We take into account the existing IATA rules and guidelines: priorities of requests for slots, the capacity limitations at each airport, the minimal turnaround time between arrival and subsequent departure of the same aircraft, and allocation to series of slots rather than to individual slots. Given the complexity of the problem, we propose an approach that consists of (i) a constructive heuristic procedure to generate a feasible and coherent allocation of slots for each airport from the network, and (ii) an iterative heuristic to improve the quality of an initial feasible solution in terms of the schedule delay (time difference between allocated time slots and airline requests). To evaluate whether the approach would be practical in real operation, we perform tests on a set of generated benchmark instances that span an entire scheduling season. The instances differ by the number of airports in the network and by the distribution of requests among airports from a given network-the largest number of airports forming a network is 100, while the maximum total number of aircraft movements considered on a half-yearly basis exceeds 4.6· 10 6. We provide computational comparisons with solutions obtained when each airport from a network is considered independently (the en-route constraint is ignored). These results reveal that the consideration of the en-route constraint, which ensures a coherent allocation of slots at origin and destination airports, introduces only a minor degradation in the schedule delay and in the number of unaccommodated requests. Furthermore, we investigate the heuristic performance for reduced-capacity scenarios.